2

Lexer & Parser Toolchain

 7 months ago
source link: https://blog.triplez.cn/posts/lexer-parser-toolchain/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

推荐一个非常好的编译器工具链入门教程: 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 国际许可协议进行许可。

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK