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

Lexer - flex

flex 文件格式:

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

%{
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:刚刚匹配到的字符串的长度。

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

%{
#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

%{
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 代码,可在产生式被应用时执行。

    • 例:

      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 动作设置 $$ 的值,最后将 $$ 入栈。

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

%{
#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();
}

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。