yosys深入研究和演示(2) --- 正则表达式

yosys综合的开始于frontend,比如read_verilog，其读入原始verilog设计文件，并转化为yosys内部的表述格式(RTLIL)，那么它是如何做到转化的?其中涉及大家在编译原理课程中讲述的内容：词法分析、语法分析、语义分析、中间语言。

最基础的就是词法分析，词法分析也称为分词，此阶段编译器从左向右扫描源文件，将其字符流分割成一个个的词（token、记号，后文中将称为token）。所谓token，就是源文件中不可再进一步分割的一串字符，类似于英语中单词，或汉语中的词。

编译器中的 token 中一般用一个 struct 来表示，比如：

typedef enum {
T_IF, T_WHILE, T_ADD, T_INTCONSTANT,

T_STRINGCONSTANT, T_IDENTIFIER, ...
} TokenType;

typedef struct _Token {
TokenType type;
union {
char *stringval;
int *intval;
double *doubleval;
} value;
} TokenRecord;

词法分析器每扫描到一个完整的 token 后，立即在链表中插入新建一个 TokenRecord ，将此 token 的类型记录在新插入的TokenRecord结构的type域中，将其字面值记录在value域中，然后接着扫描下一个 token 。

分词扫描一般采用正则表达式匹配扫描法，正则表达式 (Regular Expression ，常简写为 regex 、 regexp 或 RE ），又称 正规表示式 、 正规表示法 、 规则运算式 ，是 计算机科学 的一个概念。

正则表达式使用单个字符串来描述、匹配一系列符合某个句法规则的 字符串 。正则表达式一般都采用一些简写的方式，规则较多，这里只列举最常见的规则：

1）特殊字符

以下个字符：*[]^$ . | ? *+ () 被保留作特殊用途，如果想使用这些字符的字面值，需要在前面加反斜杠 “\” 转义。另外，非打印的字符或者有特殊含义的不便书写的符号可以通过在前面加 “\” 转义，如 \n 和 \t 分别表示换行符和制表符。

2）字符集

例如：[abferx] ，用方括号括起来的字符，表示匹配这些字符中的其中一个，相当于 (a|b|f|e|r|x) 。方括号内的特殊字符不需要转义([ ] - ^ 除外），如 [af({] 表示 匹配 “a”, “f”, “{”, “(” 中的其中一个。方扩号内可以使用 “-“ 来定义一个范围，且可以定义多个范围，如 [0-9] 表示匹配单个数字， [a-zA-Z] 表示匹配单个字母。

3）取反字符集

例如：[^abc] ，在方括号内的第一个字符为 ^ ，表示这是一个取反字符集，表示匹配一个不在方括号内部的字符。

4）*、?和+

*表示匹配前面的字符、或者由括号括起来的表达式、或者方括号括起来的字符集，匹配0次 或多次；

?表示匹配前面的字符、或者由括号括起来的表达式、或者方括号括起来的字符集，匹配0次或1次；

+表示匹配前面的字符、或者由括号括起来的表达式、或者方括号括起来的字符集，匹配1次或多次。

5）”.” 通配符

.表示匹配除换行符外的任意字符一次。

6）{n}

n 是一个非负整数，表示精确匹配 n 次。例如，'o{2}' 不能匹配 "Bob" 中的 'o'，但是能匹配 "food" 中的两个 o

7）{n,}

n 是一个非负整数。至少匹配n 次。例如，'o{2,}' 不能匹配 "Bob" 中的 'o'，但能匹配 "foooood" 中的所有 o。'o{1,}' 等价于 'o+'。'o{0,}' 则等价于 'o*'。

8）{n,m}

m 和 n 均为非负整数，其中n <= m。最少匹配 n 次且最多匹配 m 次。例如，"o{1,3}" 将只匹配 "fooooood" 中的前三个 o。'o{0,1}' 等价于 'o?'。请注意在逗号和两个数之间不能有空格。

9）定位符

定位符能够将正则表达式固定到行首或行尾，这些正则表达式出现在一个单词内、在一个单词的开头或者一个单词的结尾。定位符用来描述字符串或单词的边界，^和$分别指字符串的开始与结束，\b描述单词的前或后边界，\B表示非单词边界。

正则表达式的限定符有：

^

匹配输入字符串开始的位置。如果设置了 RegExp 对象的 Multiline 属性

，^ 还会与 \n 或 \r 之后的位置匹配。

$

匹配输入字符串结尾的位置。如果设置了 RegExp 对象的 Multiline 属性

，$ 还会与 \n 或 \r 之前的位置匹配。

\b匹配一个字边界，即字与空格间的位置。\B非字边界匹配。

10）选择、反向引用....

举例演示：

[0-9]+

+前面是[0-9],表示是至少匹配[0-9]一次，整个意思就是当输入是整数时匹配成功，表示找到了一个整数

[0-9]+\.[0-9]*

表示找到了一个小数，其分为为三段, [0-9]+ 和\.和[0-9]*

此处.不是代表任意一个字符，就是小数点的意思，故使用了转义\

[1-9][0-9]*

可以匹配1、21、321、6089....，但不匹配0

\”[^\”]*\”

匹配一个字符串

标识符 ：[_a-zA-Z][_a-zA-Z0-9]*

runoo+b，可以匹配 runoob、runooob、runoooooob 等，+ 号代表前面的字符必须至少匹配出现一次（1次或多次）

runoo*b，可以匹配 runob、runoob、runoooooob 等，* 号代表前面的字符可以不匹配出现，也可以匹配出现一次或者多次（0次、或1次、或多次）。

colou?r可以匹配 color 或者 colour，? 问号代表前面的字符最多只可以匹配出现一次（0次、或1次）

yosys的实现原理上和编译器非常相似：普通编译器，比如c/c++，是把c/c++语言的程序翻译为机器码，而yosys是把原始输入的行为描述verilog设计，映射翻译为标准库或LUT等资源表述的结构性verilog语言，这种映射变换，首先就是词法分析、语法分析、语义分析、抽象语法树、中间语言，这些和普通编译器都是一样的，不同之处就在于yosys加入了各种逻辑优化、逻辑映射。

更多信息和内容，也可关注即将上线的www.scuzy.cn，其中会有惊喜，比如免费使用的、专门针对国产FPGA设计的c/c++/java综合器