词法与语法分析器介绍-尧图网络科技

概述

词法和语法可以使用正则表达式和BNF范式表达，而最终描述文法含义的事状态转换图

Lex与YACC

词法分析器Lex

词法分析词Lex，是一种生成词法分析的工具，描述器是识别文本中词汇模式的程序，这些词汇模式是在特殊的句子结构中定义的

Lex 接收到文件或文本形式的输入时，会将文本与常规表达式进行匹配：一次读入一个输入字符，直到找到一个匹配的模式

如果能够找到一个匹配的模式，Lex就执行相关的动作(比如返回一个标记Token)。另外，如果没有可以匹配的常规表达式，将会停止停止进一步的处理，Lex将显示一个错误信息

Lex 和 C语言是强耦合的，一个.lex文件通过Lex解析并生成C的输出文件，这些文件被编译为词法分析器的可执行版本

lex 或 .l 文件在格式上分为以下3段

1. 全局变量声明部分
1. 词法规则部分
1. 函数定义部分

Lex 变量表

变量名	详细解释
yyin	FILE* 类型。它指向lexer 正在解析的当前文件
yyout	FILE* 类型。它指向记录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

语法分析词YACC

YACC(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.y

yacc -d calc.y

会生成y.tab.c、y.tab.h

最终执行结果

gcc -o calc y.tab.c lex.yy.c ./calc 1+2 = 3 3+6 = 9

Re2C 与 Bison

词法分析器 Re2c

Re2c 是一个词法编译器，可以将符合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.c

num.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状态是错误输出，返回ERR

yy5 状态是对应的正则匹配状态，返回DEC

YYCURSOR 是指向输入的指针，根据状态的流转，指针加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压入栈叫作移进。举个例子，对于计算1+2 * 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环境）

资讯详情

概述