Lexer & Parser Toolchain

推荐一个非常好的编译器工具链入门教程： https://pandolia.net/tinyc/index.html

Lexer - flex

flex 文件格式：

https://pandolia.net/tinyc/ch8_flex.html

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

%{
Declarations
%}

Definitions

%%
Rules
%%

User subroutines

• Declarations：声明，会被原样复制入 lex.yy.c 。一般用于声明全局变量和函数。

• Definitions：定义，可以定义正则表达式的名字，用于 Rules 中使用，通过名字直接使用预定义的正则表达式。

• Rules：规则，每一行都是一条规则，由匹配模式 pattern （正则表达式）和事件 action （C 代码）组成。

• User subroutines：用户定义过程，会被原样复制到 lex.yy.c 的最末尾。

• yywrap() 用于把多个输入文件打包成一个输入，当 yylex 将一个文件读入到结尾 EOF 时，会向 yywrap 询问是否继续。若需连续解析多个文件，需要在 yywrap 中打开文件，并返回 0。返回 1 则表示后面没有文件可以读取了，使得 yylex 函数结束。

• yytext：刚刚匹配到的字符串的值。

• yyleng：刚刚匹配到的字符串的长度。

如一个简单的计算器实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

%{
#include "y.tab.h"
%}

%%
[0-9]+          { yylval = atoi(yytext); return T_NUM; }
[-/+*()\n]      { return yytext[0]; }
.               { return 0; /* end when meet everything else */ }
%%

int yywrap(void) { 
    return 1;
}

Parser - Yacc/Bison

bison 可以认为是 yacc 的开源实现。

Bison 文件的格式：

https://pandolia.net/tinyc/ch13_bison.html

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

%{
Declarations
%}

Definitions

%%
Productions
%%

User subroutines

• Declarations：声明，会被原样复制入 y.tab.c 。一般用于声明全局变量和函数。

• Definitions：定义，可以定义 bison 专有的变量。

  • %token：单字符 token （token type 值与字符的 ASCII 码相同）不需要使用 %token 进行预定义，其他类型的 token 都需要使用 %token 进行预定义。bison 会自动为 token 分配一个编号，并写入 y.tab.h 中，因此在 flex 文件中是可以直接调用的。
  • %left 、%right：表示符号是左（左向右）、右（右向左）结合的。
  • %nonassoc ：表示符号是不可结合的，如 x op y op z 是非法的。
  • %prec：上下文依赖的优先级，如「负号」就是一个很典型的例子，见 Context-Dependent Precedence。
  • 更多定义可见 bison Declarations。

• Productions：

  • : 代表 ->，或 EBNF 式中的 =。

  • | 用于分隔同一个非终结符的不同产生式。

  • /* empty */ ，若产生式右边为 $\epsilon$ 时，不需要写任何符号，可写为注释 /* empty */。

  • ; 表示结束一个非终结符的产生式。

  • 每个产生式后面花括号内，都是一段 C 代码，可在产生式被应用时执行。

  • 例：

    1 2 3

    s : S E '\n' { printf("ans = %d\n", $2); } | /* empty */ { /* empty */} ;

• User subroutines：用户定义过程，会被原样复制到 y.tab.c 的最末尾。

bison 会将语法产生式以及符号优先级转换成一个 C 语言的 LALR(1) 动作表，输出到 y.tab.c 中。并会将这个动作表转换为可读形式输出至 y.output 中。

bison 会根据自定义语法文件在 y.tab.c 中生成一个函数 int yyparse(void) 。这个函数按照 LR(1) 解析流程，对词法分析中得到的 token 流进行解析。每当读取下一个符号时，就会执行一次 x = yylex() 。每当要执行一个折叠动作（reduce）时，相应的产生式后的 C 代码将被执行，执行完后将相应的状态出栈。

若 token 流不合法，yyparse 会在第一次出错的地方终止，并调用 yyerror 函数，最后返回 1。

在 reduce 动作时，可用 $1, $2 … $n 来引用属性栈的属性（可以认为是产生式中的第 n 个属性内容，并在最后将这个状态下的属性出栈。其中，$$ 代表产生式左侧的终结符，可在 reduce 动作设置 $$ 的值，最后将 $$ 入栈。

如一个简单的计算器实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

%{
#include <stdio.h>
void yyerror(const char* msg) {}
int yylex();
%}

%token T_NUM

%left '+' '-'
%left '*' '/'

%%

S   :   S E '\n'        { printf("ans = %d\n", $2); }
    |   /* empty */     { /* empty */ }
    ;

E   :   E '+' E         { $$ = $1 + $3; }
    |   E '-' E         { $$ = $1 - $3; }
    |   E '*' E         { $$ = $1 * $3; }
    |   E '/' E         { $$ = $1 / $3; }
    |   T_NUM           { $$ = $1; }
    |   '(' E ')'       { $$ = $2; }
    ;

%%

int main() {
    return yyparse();
}