概述词法和语法可以使用正则表达式和BNF范式表达而最终描述文法含义的事状态转换图Lex与YACC词法分析器Lex词法分析词Lex是一种生成词法分析的工具描述器是识别文本中词汇模式的程序这些词汇模式是在特殊的句子结构中定义的Lex 接收到文件或文本形式的输入时会将文本与常规表达式进行匹配一次读入一个输入字符直到找到一个匹配的模式如果能够找到一个匹配的模式Lex就执行相关的动作(比如返回一个标记Token)。另外如果没有可以匹配的常规表达式将会停止停止进一步的处理Lex将显示一个错误信息Lex 和 C语言是强耦合的一个.lex文件通过Lex解析并生成C的输出文件这些文件被编译为词法分析器的可执行版本lex 或 .l 文件在格式上分为以下3段全局变量声明部分词法规则部分函数定义部分Lex 变量表变量名详细解释yyinFILE* 类型。它指向lexer 正在解析的当前文件yyoutFILE* 类型。它指向记录lexer输出的位置。默认情况下yyin 和 yyout 都指向标准输入和输出yytext匹配模式的文本存储在这一变量中(char*)yyleng给出匹配模式的长度yylineno提供当前的行数信息(lexer不一定支持)Lex 函数表函数名详细解释yylex()这一函数开始分析。它由Lex自动生成yywrap()这一函数在文件(或输入)的末尾调用。如果函数的返回值是1就停止解析。它可以用来解析多个文件yyless(int)这一函数可以用来输出除来前n个字符外的所有读出标记yymore()这一函数告诉Lexer将下一个标记附加到当前标记后代码文件 a.l%{ #include stdio.h extern char *yytext; extern FILE *yyin; int count 0; %} %%// 两个百分号标记指出了 Lex 程序中这一段的结束和第二段的开始 \$[a-zA-Z][a-zA-Z0-9]* {count; printf( 变量%s, yytext);} [0-9\/.-] printf(数字%s, yytext); printf(被赋值为); \n printf(\n); [ \t] /* 忽略空格 */; %% // 函数定义部分 int main(int avgs, char *avgr[]) { yyin fopen(avgr[1], r); if (!yyin) { return 0; } yylex(); printf(变量总数为:%d\n, count); fclose(yyin); return 1; }对于以上代码解释如下全局变量声明部分: 声明了一个int型全局变量count用来记录变量的个数规则部分: 第1个规则是找符号开头、第 2 个符号为字母且后面为字符或数字的变量类似于 符号开头、第2个符号为字母且后面为字符或数字的变量类似于符号开头、第2个符号为字母且后面为字符或数字的变量类似于a,并计数加1. 同时将满足条件的yytext输出第2个规则是找数字第3个规则是找 号第4个规则是输出\n; 第5个规则是忽略空格函数定义部分: 打开一个文件然后调用yylex 函数进行词法解析输出变量的技术最后调用fclose关闭文件lex 代码编译lex a.l gcc lex.yy.c -o test -ll测试文件 file$a 1 $b 2执行如下命令./test file 变量$a被赋值为数字1 变量$b被赋值为数字2 变量总数为:2语法分析词YACCYACC(Yet Another Compiler-Compiler) 是 UNIX/Linux 上一个用来生成编译器的编译器(编译器代码生成器). YACC使用BNF范式定义语法能处理上下文无关文法YACC 语法规则YACC 语法包括3部分即定义段、规则段和用户代码段… 定义段 …%%… 规则段 …%%… 用户代码段 …代码词法分析文件: cal.l%{ #include y.tab.h #include math.h %} %% ([0-9]|([0-9]*\.[0-9])([eE][-]?[0-9])?) { yylval.dval atof(yytext); return NUMBER; } [ \t] ; \n | . return yytext[0]; %%语法分析文件: calc.y%{ #include stdio.h #include string.h #include math.h int yylex(void); void yyerror(char *); %} %union { double dval; } %token dval NUMBER %left - %left * / %nonassoc UMINUS %type dval expression %% statement_list: statement \n | statement_list statement \n ; statement: expression { printf( %g\n, $1); } ; expression: expression expression {$$ $1 $3;} | expression - expression { $$ $1 - $3; } | expression * expression { $$ $1 * $3; } | expression / expression { if ($3 0.0) yyerror(divide by zero); else $$ $1 / $3; } | - expression %prec UMINUS { $$ -$2; } | ( expression ) { $$ $2; } | NUMBER { $$ $1; } %% void yyerror(char *str) { fprintf(stderr, error:%s\n, str); } int yywrap() { return 1; } int main() { yyparse(); }从代码中可以看出规则部分使用BNF范式expression 最终是NUMBER以及使用、-、* 、/ 和 ()的组合对加、减、乘、除、括号、负号进行表达statement 是由expression 组合而成的可以输出计算结果statement 是由expression 组合而成的可以输出计算结果statement_list 是statement的组合lex 编译lex cal.l通过这个命令会生成lex.yy.c,里面维护了NUMBER这个Token的有穷自动机使用 YACC对 calc.yyacc -d calc.y会生成y.tab.c、y.tab.h最终执行结果gcc -o calc y.tab.c lex.yy.c ./calc 12 3 36 9Re2C 与 Bison词法分析器 Re2cRe2c 是一个词法编译器可以将符合Re2c规范的生成高效的C/C代码Re2c会将正则表达式生成对应的有穷状态机代码num.l#include stdio.h enum num_t {ERR, DEC}; static num_t lex(const char *YYCURSOR) { const char *YYMARKER; /*!re2c re2c:define:YYCTYPE char; re2c:yyfill:enable 0; end \x00; dec [1-9][0-9]*; * {return ERR;} dec end {return DEC;} */ } int main(int argc, char **argv) { for (int i 1; i argc; i) { switch (lex(argv[i])) { case ERR: printf(error\n); break; case DEC: printf(十进制表示\n); break; } } return 0; }执行以下命令转换成c代码re2c num.l -o num.cnum.c/* Generated by re2c 3.0 on Sun May 26 21:58:19 2024 */ #line 1 num.l #include stdio.h enum num_t {ERR, DEC}; static num_t lex(const char *YYCURSOR) { const char *YYMARKER; #line 11 num.c { char yych; yych *YYCURSOR; switch (yych) { case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: goto yy3; default: goto yy1; } yy1: YYCURSOR; yy2: #line 14 num.l {return ERR;} #line 32 num.c yy3: yych *(YYMARKER YYCURSOR); switch (yych) { case 0x00: goto yy4; case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: goto yy5; default: goto yy2; } yy4: YYCURSOR; #line 15 num.l {return DEC;} #line 53 num.c yy5: yych *YYCURSOR; switch (yych) { case 0x00: goto yy4; case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: goto yy5; default: goto yy6; } yy6: YYCURSOR YYMARKER; goto yy2; } #line 16 num.l } int main(int argc, char **argv) { for (int i 1; i argc; i) { switch (lex(argv[i])) { case ERR: printf(error\n); break; case DEC: printf(十进制表示\n); break; } } return 0; }从上面代码中可以看出这个状态机一共有8种状态分别是开始状态、yy3至yy9状态其中yy3状态是错误输出返回ERRyy5 状态是对应的正则匹配状态返回DECYYCURSOR 是指向输入的指针根据状态的流转指针加1语法编译器Bison对于一条BNF文法规则其左边是一个非终结符(symbol 或者 non-terminal)其右边则定义该非终结符是如何构成的也称为产生式(production)产生式可能包含非终结符也可能包含终结符(terminal)还可能二者都有利用BNF文来分析目标文本比较流行的算法有LL分析(自顶向下的分析,top-down parsing),LR分析(自底向上的分析bottom-up parsing或者叫移进-归约分析, shift-down parsing)其中LR算法有很多不同的变种按照复杂度和能力递增的顺序依次是LR(0)、SLR、SLR、LALR和LR(1)Bison是基于LALR分析法实现的适合上下文无关文法当Bison读入一个终结符TOKEN时会将该终结符及其语意值一起压榨其中这个栈叫做分析器栈(parse stack)把一个TOKEN压入栈叫作移进。举个例子对于计算12 * 3, 假设现已经读入来1 2 * 那么下一个准备读入的是3这个栈当前就有4个元素即1、、2和*当已经移进的后n个终结符和组(grouping)与一个文法规则相匹配时它们会根据该规则结合起来这叫归约(reduction)栈中哪些终结符和组会被单个的组(grouping)替换。同样以1 2 * 3为例最后一个输入的字符为分号表示结束那么按照下面的规则进行归约expression * expression { $$ $1 * $3 }代码bcalc.y 文件%{ #define YYSTYPE double #include math.h #include ctype.h #include stdio.h %} /* 定义部分 */ %token NUM %left - %left * / %left NEG %right ^ /* 语法部分 */ %% input: /* empty string*/ | input line ; line: \n | exp \n {printf(\t%.10g\n, $1);} exp: NUM { $$ $1; } | exp exp { $$ $1 $3; } | exp - exp { $$ $1 $3; } | exp * exp { $$ $1 $3; } | exp / exp { $$ $1 $3; } | - exp %prec NEG { $$ -$2; } | exp ^ exp { $$ pow($1, $3); } | ( exp ) { $$ $2; } ; /* 代码部分 */ %% yylen() { int c; /* 跳过空格 */ while ((c getchar()) || c \t) ; if (c . || isdigit(c)) { ungetc(c, stdin); scanf(%lf, yylval); return NUM; } if (c EOF) return 0; return c; } yyerror (char *s) /* 错误是被 yyparse 调用 */ { printf(%s\n, s); } main() { yyparse(); }通过Bison 对 bcalc.y进行编译bison -d bcalc.y执行下面的命令可以生成对应的可以执行文件gcc -o bcalc bcalc.tab.c bcalc.tab.h -lm参考资料手把手教程-lex与yacc/flex与bison入门一使用windows环境
