iris
归档 标签 分类 系列 关于 友人帐
iris

词法分析软件 Flex 及语法分析软件 Bison 的用法

GinShio  收录于  类别 CompilerPrinciple
     约 7308 字   预计阅读 35 分钟 

正正规规地开始写实现一个编译器感觉压力还是蛮大的。初步选型是

  • 基础工具
    • Git
    • CMake
    • gcc
  • 编译器生成工具
    • Flex
    • GNU Bison
  • 其他工具
    • Clang Format
    • CppLint
    • EditConfig

C++ 支持 17 简直太棒了！！！还不知道毕昇杯能不能用 CMake 去构建。

由于是多人合作项目，代码风格暂时定的是 Google，估计啥都不知道。想想到时候 review 代码就头大。

这篇主要是记录下从 info (Emacs 看 info 真方便) 中学习的 Flex 和 GNU Bison 相关用法。

TL;DR. main 函数示例 或 北大编译实践

Flex 可以理解为词法分析器生成工具 Lex 的开源版本，意为 fast lexical analyzer generator。根据描述的正则表达式与 C 代码 (这些被称为 规则)，来生成对应的分析器代码 (文件名默认为 lex.yy.c)，其中定义了接口 yylex() 用来启动分析器，函数原型如下

1

int yylex(void);

Flex 默认会生成标准的 C99 代码，而非 K&R 风格代码。在调用 yylex 时，它会持续从全局输入文件 yyin 中扫描 token，直到遇到 EOF 或 action 执行返回语句。如果 yylex 因 return 停止扫描，可以再次调用扫描器，从中断处继续扫描。当扫描到 EOF 时，只有 yywrap() 返回 0 才继续读取其他文件，返回非零时扫描器会终止并返回 0。如果你不实现 yywrap(),需要使用 %option noyywrap 或链接 -lfl 使用总返回 1 的默认版本。

话说回来，学习词法分析最大的收获应该是知道了正则是怎么运作的，自己哪天心血来潮了说不定就手撕一个。

输入文件被分为三个部分，两个部分之间使用 %% 分隔。

1
2
3
4
5

definitions
%%
rules
%%
user code

定义部分会声明一些 name 方便后续使用，或者声明开始条件。

name 是以字母或下划线 (_) 开头，并在后面跟随零或多个字母、数字、下划线、短线 (-)。声明通常是一个正则表达式，可以看作是 name 的值。语法如下

1

name definition

有点难懂？那就看一个示例

1
2

DIGIT   [0-9]
ID      [a-z][a-z0-9]*

这里定义了两个 name，当然我们可以在其他 name 中使用已声明的 name，比如声明 FLOAT

1
2

FLOAT   {DIGIT}+"."{DIGIT}*
FLOAT2  ([0-9])+"."([0-9])*

这个例子中 FLOAT 与 FLOAT2 的声明是完全等价的。

注释与 C 的多行注释相同。lex 中可以直接写 C 代码，当然要用 %{ 和 %} 包裹起来，这个块将在生成代码时被完全复制。另外 top 块是很重要的一个语法，它会被生成在文件的顶端，在所有的代码之前，因此你可以在 top 块中定义一些感兴趣的宏或文件。top 块示例如下：

1
2
3
4
5

%top{
    /* This code goes at the "top" of the generated file. */
    #include <stdint.h>
    #include <inttypes.h>
}

规则部分每个规则一行，同样地你可以在 %{ 和 %} 之间的块中写 C 语言代码，Flex 会帮你完全一致的复制到生成文件中。语法如下

1

pattern   action

pattern 相当于给定的正则表达式，当输入与 pattern 匹配时将执行 action 所对应的动作。详细说明一下支持的 pattern 用法

x
字符 x
.
除换行外的任意字符
[xyz]
一个字符集，可以匹配其中一个字符，示例可以匹配 x 或 y 或 z
[abj-oZ]
一个带范围的字符集，匹配其中一个字符。示例可以匹配 a 或 b 或 j 到 o 之间的字符或 Z
[^A-Z]
一个否定字符集，匹配其中没有出现的字符。示例可以匹配除了大写字母外的任意字符
[a-z]{-}[aeiou]
一个带除外集的字符集，匹配除了后面集合外的所有出现在集合中的字符。示例可以匹配小写辅音字母
r*
匹配零或多个 r
r+
匹配一或多个 r
r?
匹配零或一个 r
r{2,5}
匹配二到五个 r
r{2,}
匹配二或更多 r
r{4}
正好四个 r
{name}
匹配第一节中定义的 name
[xyz]\[foo
转义字符
\123
字符的八进制表示。示例为大写字母 S
\x53
字符的十六进制表示。示例为大写字母 S
(r)
利用 () 优先级修改匹配优先级
(?r-s:pattern)
对 pattern 应用 r 模式但不应用 s 模式。其中可选模式如下
  • i: 不区分大小写
  • s: 修改 . 语义，匹配任意字符 (包括换行)
  • x: 忽略 pattern 中的注释与空白符。空白符依旧可以出现在 "" 中、转义字符、或字符集中。
  • 示例
    示例 等价表示
    \((?:foo)\) \((foo)\)
    \((?i:ab7)\) \(([aA][bB]7)\)
    \((?-i:ab)\) \((ab)\)
    \((?s:.)\) \(([\backslash{}x00-\backslash{}xFF])\)
    \((?ix-s:\ a\ .\ b)\) \(([Aa][\^\backslash{}n][bB])\)
    \((?x:a\ b)\) \((“ab”)\)
    \((?x:a\backslash\ b)\) \((“a\ b”)\)
    \((?x:a"\ “b)\) \((“a\ b”)\)
    \((?x:a[\ ]b)\) \((“a\ b”)\)
    \(\begin{aligned}(?x: & a\\ & /* comment */\\ & b\\ & c)\end{aligned}\) \((abc)\)
(?# comment)
忽略 () 中的所有内容，且可以跨多行，但是注释不能有 ) 字符
rs
cat
r|s
or
r/s
尾随上下文 (trailing context)，只有在 s 之前的情况下匹配 r，但只进行 r 的行为
^r
仅在行首匹配 r
r$
仅在行尾匹配 r
<s>r
仅以 s 开始的 r
<s1,s2,s3>r
仅以 s1 或 s2 或 s3 开始的 r
<*>r
以任意条件开始的 r
<<EOF>>
文件末尾
<s1,s2><<EOF>>
以条件 s1 或 s2 开始的文件末尾

在字符串中，除了转义符 (\)、字符集运算符 (- 和 ]]) 以及行首标记 (^)，其他特殊字符均失去了其特殊意义。

另外上面的 pattern 是根据优先级排列的，最上面的优先级最高。比如表达式 \(foo|bar*\) 与表达式 \((foo)|(ba(r*))\) 相同。如果想要改为重复 foo 或 bar 数次，可以写为表达式 \((foo|bar)*\)。

Flex 支持 POSIX Bracket Expressions，但是没找到相应的 Shorthand 支持。不过从 info 上看，支持了，但没全支持。

POSIX Description ASCII Shorthand
[:alnum:] 字母和数字 \([a-zA-Z0-9]\)
[:alpha:] 字母 \([a-zA-Z]\)
[:ascii:] ASCII 字符 \([\backslash{}x00-\backslash{}xFF]\)
[:blank:] 空格及 Tab \([ \backslash{}t]\) \h
[:cntrl:] 控制字符 \([\backslash{}x00-\backslash{}x1F\backslash{}x7F]\)
[:digit:] 数字 \([0-9]\) \d
[:graph:] 可见字符 \([\backslash{}x21-\backslash{}x7E]\)
[:lower:] 小写字符 \([a-z]\) \l
[:print:] 可见字符及空格 \([\backslash{}x20-\backslash{}x7E]\)
[:punct:] 标点字符 \([!"\backslash\#\$\%\&’()*+,\backslash-./:;<=>?@\backslash[\backslash\backslash\backslash]\verb!^!\_\verb!`!\{\mid\}\verb!~!]\)
[:space:] 空白字符 \([\ \backslash{}t\backslash{}r\backslash{}n\backslash{}v\backslash{}f]\) \s
[:upper:] 大写字符 \([A-Z]\) \u
[:word:] 单词字符 \([a-zA-Z0-9\_]\) \w
[:xdigit:] 十六进制字符 \([a-fA-F0-9]\)

其中 Flex 不支持 [:ascii:] 和 [:word:] 两个字符集。

在 Flex 配置文件中，字符集将被立即展开，这意味着 flex 环境对字符集感兴趣。

  • 如果添加了大小写不敏感标记，那么 [:upper:] 和 [:lower:] 与 [:alpha:] 等价

  • 有范围的字符类在跨越大小写字符时 (比如 [a-Z])，在不区分大小写的扫描器上应该慎用。此时 Flex 并不知道你是想将所有的大小写字符折叠在一起，还是要指定 ASCII 数值范围。在出现此类问题时，Flex 优先指定数值范围，并发出一个警告。

    范围 结果 数值范围 二义性范围
    [a-t] ok \([a-tA-T]\)
    [A-T] ok \([a-tA-T]\)
    [A-t] 二义性 \([A-Z\backslash[\backslash\backslash\backslash]\verb!_!\verb!`!a-t]\) \([a-tA-T]\)
    [_-{] 二义性 \(\verb!_!\verb!`!a-z\{\) \(\verb!_!\verb!`!a-zA-Z\{\)
    [@-C] 二义性 \(@ABC\) \(@A-Z\backslash[\backslash\backslash\backslash]\verb!_!\verb!`!abc\)

  • Flex 允许否定 POSIX 字符集，只需要在字符类名称前加上 ^，但是大小写不敏感的扫描器上 [:^upper:] 和 [:^lower:] 会被跳过，它们的含义不清。

  • 操作符 {-} 可以为两个字符集做差，但小心生成一个永远不会被匹配的空集。不过做差的两个集合不必是包含关系，比如 [a-c]{-}[b-z] 的结果为 [a]。

  • 操作符 {+} 求两个字符集的并集。比如 [[:alpha:]]{-}[[:lower:]]{+}[q] 的结果为 [A-Zq]。

  • 一个 pattern 最多有一个尾随上下文 (/ 或 $)，开始条件、^ 和 <<EOF>> 只能出现在 pattern 的开头。这些内容均不能出现在 () 的优先级分组中。另外 ^ 与 $ 没有出现在相应位置的情况下，将被视为普通字符。

最后一部分即代码段，用来写 C 语言代码，并完全复制到生成文件的末尾部分。主要是用来定义一些辅助函数，或单独使用 Flex 时的入口函数。

Flex 的匹配原则是最长匹配，且按优先级匹配。即多个同时匹配的规则，采用匹配到文本最长的规则；多个同时匹配且长度相同的规则，采用第一个列出的规则 (最上面的优先级最高)。长度包含尾随上下文的尾随部分。

当匹配成功时，匹配的文本将可以使用全局指针 yytext 获取，长度可以通过全局整型 yyleng 获取。之后开始执行匹配模式相应的 action，然后再扫描剩余的输入。但是没有匹配时，将执行默认规则：输入的下一个字符将被当作匹配并复制到标准输出。

需要注意，yytext 可以用两种不同的方式定义：字符指针或字符数组。在定义部分，你可以用 %pointer 或 %array 来指定用何种方式，当然默认使用指针的方式，如果有 lex 兼容选项默认使用数组。使用指针带来的劣势是：修改 yytext 将会受限，且调用 unput() 会破坏其中的内容，也可能出现 lex 的移植性问题。

遗憾的是，生成 C++ 扫描器类是不能使用 %pointer 方式的。

每一个匹配都有一个想对应的动作，在匹配成功时将执行这个动作。pattern 在第一个非转义空白处结尾，这行剩下的则是 action 部分，action 由任意的 C 代码片段组成。

比如下面这个程序，压缩空白符到一个空格，并丢弃所有行末空白符。

1
2

[ \t]+     putchar(' ');
[ \t]+$    /* ignore this token */

action 可以用 { 和 } 包括起来，在里面写多行 C 语言代码，类似于 C 的代码块。Flex 会甄别字符串和注释中括号，更好的方式是用 %{ 和 %} 来定义代码块。

如果 action 是一个 \(\mid\)，意思是同下一个规则的 action 相同。

之前说了可以包含 return 语句，它将返回值给名为 yylex 的函数，这个函数每次在上次停止的地方继续向下处理，直到到达文件末尾或执行返回。

action 可以自由修改 yytext，除了延长它 (末尾添加字符将覆盖之后的字符，在使用 array 方式时不能修改)。action 还可以自由修改 yyleng，除非 action 还包括使用 yymore()。

还为 action 定义了一些预设指令

ECHO
复制 yytext 到扫描器输出
BEGIN
将扫描器重定位在开始条件末尾
REJECT
拒绝当前的最优匹配，采用次优匹配。如果你的 action 由其他动作，需要放在 REJECT 之前，否则不会执行。以下代码，在匹配 ‘abcd’ 时会输出 ‘abcdabcaba’ 
1
2
3
4
5

a      |
ab     |
abc    |
abcd   ECHO; REJECT;
.|\n   /* */
yymore()
告诉扫描器下次匹配到规则时，将当前的 token 放在 yytext 的首部。比如以下代码，在匹配 ‘mega-kludge’ 时会输出 ‘mega-mega-kludge’ 
1
2

mega-    ECHO; yymore();
kludge   ECHO;

使用 yymore 的时候需要注意两点

  • yymore 依赖于 yyleng，因此不要在使用时修改 yyleng
  • yymore 会导致扫描器的匹配速度略微下降
yyless(n)
当前 token 将使用开始的 n 个字符，扫描会从匹配的 n 个字符之后继续扫描。在使用 yyless 之后，yytext 与 yyleng 将会被调整 (yyleng 将等于 n)。比如以下代码，匹配 ‘foobar’ 时会输出 ‘foobarbar’ 
1
2

foobar   ECHO; yyless(3);
[a-z]+   ECHO;

要十分注意 yyless() 的使用，如果参数为 0 时，扫描器将陷入无限循环中。

unput(c)
将字符 c 重新放入输入中，它会是下一个带扫描的字符。如果使用 %pointer 情况下会导致 yytext 被破坏，从最右端开始每次吞一个字符。如果需要调用 unput()，需要使用 %array 构建或者先将 yytext 复制到其他地方 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

{
/* Copy yytext because unput() trashes yytext */
char* yycopy = strdup(yytext);
unput(')');
for (int i = yyleng - 1; i >= 0; --i) {
    unput(yycopy[i]);
}
unput('(');
free(yycopy);
}
input()
从输入流中读取下一个字符。比如 C 风格注释，将全部注释丢弃。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

"/*"        {
            int c;
            while (1) {
                while ((c = input()) != '*' && c != EOF) {
                    continue;
                }  /* eat up text of comment */
                if (c == '*') {
                    while ((c = input()) == '*') {
                        continue;
                    }
                    if (c == '/') {
                        break;
                    }  /* found the end */
                }
                if (c == EOF) {
                    error( "EOF in comment" );
                    break;
                }
            }  /* end of while */
            }

需要注意一点，如果用 C++ 编译，则需要使用 yyinput() 防止 input 和 C++ 的 stream 冲突。

YY_FLUSH_BUFFER
清空内部缓冲区，在下次匹配是先使用 YY_INPUT() 重填缓冲区。这个方法会在之后解释。
yyterminate()
替代 action 中的返回语句并返回 0 表示全部完成。通常在遇到 EOF 时使用该函数。

<<EOF>> 是个特殊规则，表示遇到文件末尾且 yywrap 返回非零值时 (表示没有其他文件要处理) 要执行的操作，好像并不是每个文件的 EOF 规则。该 action 通常执行以下操作之一：

  • 将 yyin 分配给新的输入文件；
  • 执行返回语句；
  • 或，使用 yy_switch_to_buffer 切换到新的缓冲区 (见 多输入缓冲区)

EOF 只能与开始条件一起使用，不合格的 EOF 将适用于所有没有 EOF 的开始动作。

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

%x quote
%%

...other rules for dealing with quotes...

<quote><<EOF>>   {
         error( "unterminated quote" );
         yyterminate();
         }
<<EOF>>  {
         if ( *++filelist )
             yyin = fopen( *filelist, "r" );
         else
            yyterminate();
         }

开始条件 (sc) 相当于一种激活机制，用 BEGIN 触发 sc，在下次 BEGIN 前，给定 sc 都是激活状态，而其他 sc 都是屏蔽状态。

在定义部分声明，有 %s (兼容性) 或 %x (排他性) 两种 sc，后跟随名称列表。兼容性 sc 激活时不会屏蔽非 sc 规则，但排他性 sc 激活时不但屏蔽其他 sc 规则，还屏蔽非 sc 规则。

1
2
3
4

%s example
%%
<example>foo  do_something();
bar           something_else();

等价于

1
2
3
4

%x example
%%
<example>foo            do_something();
<INITIAL,example> bar   something_else();

对于下面这个代码，如果没有 <INITIAL,example> 那么 bar 会被屏蔽；而如果只使用 <example> sc，只有在 example sc 被激活时才能匹配 bar。

另外有一个特殊的sc <*> 可以在任何 sc 激活时被匹配。使用 BEGIN(0) 或 BEGIN(INITIAL) 可以回到初始状态，即非 sc 状态。如果你希望

BEGIN 动作也可以在 rules 开头作为 action 给出，直接进入指定的 sc 激活状态。

1
2
3
4
5
6
7
8

         int enter_special;
%x SPECIAL
%%
         if ( enter_special )
             BEGIN(SPECIAL);

<SPECIAL>blahblahblah
......

给出一个示例，这个示例将检测整数和浮点数，但是浮点数可能以整数开头被认为是一个整数，因此，这个例子采用 sc 来扫描整数或浮点数。一行一个数字，如果是浮点数将以 expect-floats 开头。

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

%{
#include <math.h>
%}
%s expect

%%
expect-floats        BEGIN(expect);
<expect>[0-9]+.[0-9]+      {
            printf( "found a float, = %f\n",
                    atof( yytext ) );
            }
<expect>\n           {
            /* that's the end of the line, so
             * we need another "expect-number"
             * before we'll recognize any more
             * numbers
             */
            BEGIN(INITIAL);
            }
[0-9]+      {
            printf( "found an integer, = %d\n",
                    atoi( yytext ) );
            }
"."         printf( "found a dot\n" );

当然用 sc 来扫描注释是更加简便的一种方式，相比之前介绍的 input() 方式，这很简单。

1
2
3
4
5
6
7
8

%x comment
%%
        int line_num = 1;
"/*"         BEGIN(comment);
<comment>[^*\n]*        /* eat anything that's not a '*' */
<comment>"*"+[^*/\n]*   /* eat up '*'s not followed by '/'s */
<comment>\n             ++line_num;
<comment>"*"+"/"        BEGIN(INITIAL);

如果你希望得到一个高性能的扫描器，那就需要每个规则尽可能多的匹配文本。

另外，sc 的存储方式实际是 int，因此你可以采用如此方式记录上一个状态。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

%x comment foo
%%
        int line_num = 1;
        int comment_caller;

"/*"         {
             comment_caller = INITIAL;
             BEGIN(comment);
             }
...
<foo>"/*"    {
             comment_caller = foo;
             BEGIN(comment);
             }

<comment>[^*\n]*        /* eat anything that's not a '*' */
<comment>"*"+[^*/\n]*   /* eat up '*'s not followed by '/'s */
<comment>\n             ++line_num;
<comment>"*"+"/"        BEGIN(comment_caller);

一个更好的方式是，YY_START 可以记录当前的 sc 状态，因此写成 comment_caller = YY_START; 是更好的方式。如果你想兼容 lex 则可以用它的别名 YYSTATE。

最后，看一份 C 风格的字符串示例

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

%x str
%%
        char string_buf[MAX_STR_CONST];
        char *string_buf_ptr;

\"      string_buf_ptr = string_buf; BEGIN(str);

<str>\"        { /* saw closing quote - all done */
        BEGIN(INITIAL);
        *string_buf_ptr = '\0';
        /* return string constant token type and
         * value to parser
         */
        }
<str>\n        {
        /* error - unterminated string constant */
        /* generate error message */
        }
<str>\\[0-7]{1,3} {
        /* octal escape sequence */
        int result;

        (void) sscanf( yytext + 1, "%o", &result );

        if ( result > 0xff )
                /* error, constant is out-of-bounds */

        *string_buf_ptr++ = result;
        }
<str>\\[0-9]+ {
        /* generate error - bad escape sequence; something
         * like '\48' or '\0777777'
         */
        }
<str>\\n  *string_buf_ptr++ = '\n';
<str>\\t  *string_buf_ptr++ = '\t';
<str>\\r  *string_buf_ptr++ = '\r';
<str>\\b  *string_buf_ptr++ = '\b';
<str>\\f  *string_buf_ptr++ = '\f';
<str>\\(.|\n)  *string_buf_ptr++ = yytext[1];
<str>[^\\\n\"]+        {
        char *yptr = yytext;

        while ( *yptr )
                *string_buf_ptr++ = *yptr++;
        }

像上面的代码，在一个 sc 下可能有很多规则，你可以使用 Flex 提供的 scope 语法来将太们写在一起

1
2
3
4
5
6
7

<str>{
    "\\n"  *string_buf_ptr++ = '\n';
    "\\t"  *string_buf_ptr++ = '\t';
    "\\r"  *string_buf_ptr++ = '\r';
    "\\b"  *string_buf_ptr++ = '\b';
    "\\f"  *string_buf_ptr++ = '\f';
}

当启用 %option stack 之后，你也可以使用内建的 sc 栈，可能你需要用到以下函数

  • 将状态压入栈 (即切换到状态) 
    1

    void yy_push_state(int new_state);
  • 将状态弹出栈 (即回到上一个状态) 
    1

    void yy_pop_state();
  • 获取栈顶元素 (即获取当前状态的值) 
    1

    int yy_top_state();

sc 栈是动态增长的，也没有内建大小限制，但是内存用尽时程序将退出。

一些扫描器 (如 C/C++ 支持的 include) 需要从多个输入流中读取，因此无用简单地通过到达文件末尾才读取下一个输入的 YY_INPUT 来控制，因为可能从使用 include 到文件末尾需要很长时间。

针对这一问题，Flex 给出了多个缓冲区之间的创建和切换机制。连带的是更多的 flex 函数。

  • 创建缓冲区

    1
2

    YY_BUFFER_STATE yy_create_buffer(FILE *file, int size);  // c style
YY_BUFFER_STATE yy_new_buffer(FILE* file, int size);     // c++ style (use new and delete)

    YY_BUFFER_STATE 是不透明结构 struct yy_buffer_state 的指针。如果重定义了没有使用 yyin 的 YY_INPUT，需要可以安全地将 NULL 传给 file。

  • 切换缓冲区

    1

    void yy_switch_to_buffer(YY_BUFFER_STATE new_buffer);

    将扫描器输入切换到新的缓冲区上，但并不会改变 sc。

  • 删除缓冲区

    1

    void yy_delete_buffer(YY_BUFFER_STATE buffer);

  • 压入状态

    1

    void yypush_buffer_state(YY_BUFFER_STATE buffer);

    将新的状态推送到 flex 维护的内部堆栈，推送的状态成为新的当前状态。

  • 弹出状态

    1

    void yypop_buffer_state(YY_BUFFER_STATE buffer);

    将当前状态弹出栈，并删除缓冲区，并将堆栈的下一个状态 (如果有) 设置为新的当前状态。

  • 丢弃缓冲区

    1

    void yy_flush_buffer(YY_BUFFER_STATE buffer);

    丢弃当前缓冲区的所有内容，扫描器的下次匹配将先调用 YY_INPUT() 重新填充缓冲区。

最后还有一些宏，比如 YY_CURRENT_BUFFER 将返回当前缓冲区的 YY_BUFFER_STATE 句柄，但是请不要将它作为左值。

看下示例吧！Talk is cheap. Show me the code.

首先示例是一个关于 include 功能的实现，使用 yypush_buffer_state 和 yypop_buffer_state 实现 (利用 Flex 自身维护堆栈)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

/* the "incl" state is used for picking up the name
 * of an include file
 */
%x incl
%%
include             BEGIN(incl);

[a-z]+              ECHO;
[^a-z\n]*\n?        ECHO;

<incl>[ \t]*      /* eat the whitespace */
<incl>[^ \t\n]+   { /* got the include file name */
        yyin = fopen(yytext, "r");
        if (!yyin) error(...);
        yypush_buffer_state(yy_create_buffer(yyin, YY_BUF_SIZE));
        BEGIN(INITIAL);
    }

<<EOF>> {
        yypop_buffer_state();
        if (!YY_CURRENT_BUFFER) yyterminate();
    }

当然也可以自己管理输入文件的堆栈，就比如下面这个等价的例子

 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
31
32
33
34
35
36
37
38

/* the "incl" state is used for picking up the name
 * of an include file
 */
%x incl

%{
#define MAX_INCLUDE_DEPTH 10
YY_BUFFER_STATE include_stack[MAX_INCLUDE_DEPTH];
int include_stack_ptr = 0;
%}

%%
include             BEGIN(incl);

[a-z]+              ECHO;
[^a-z\n]*\n?        ECHO;

<incl>[ \t]*      /* eat the whitespace */
<incl>[^ \t\n]+   { /* got the include file name */
        if (include_stack_ptr >= MAX_INCLUDE_DEPTH) {
            fprintf(stderr, "Includes nested too deeply");
            exit(1);
        }
        include_stack[include_stack_ptr++] = YY_CURRENT_BUFFER;
        yyin = fopen( yytext, "r" );
        if (!yyin) error(...);
        yy_switch_to_buffer(yy_create_buffer(yyin, YY_BUF_SIZE));
        BEGIN(INITIAL);
    }

<<EOF>> {
        if (--include_stack_ptr == 0) {
            yyterminate();
        } else {
            yy_delete_buffer(YY_CURRENT_BUFFER);
            yy_switch_to_buffer(include_stack[include_stack_ptr]);
        }
    }

也可以在一个内存缓冲区上而非文件上进行缓冲区操作。当然只是在创建阶段有区别，其他阶段没有任何区别。

1
2
3

YY_BUFFER_STATE yy_scan_string(const char *str);  // c style string
YY_BUFFER_STATE yy_scan_bytes(const char *bytes, int len);  // string with end of non-NULL
YY_BUFFER_STATE yy_scan_buffer(char *base, yy_size_t size);  // no copy buffer

前两者会复制一份数据，这在希望修改缓冲区内容时是安全的，但你想避免复制时需要使用第三个函数。需要注意，它并不是末尾 non-NULL 字符串，它的最后两个字节必须是 YY_END_OF_BUFFER_CHAR。因此真正扫描的数据在 0 到 size-2。

YY_USER_ACTION
提供了一种始终在匹配 action 之前执行的操作。当使用该宏时，变量 yy_act 用于指示当前动作的编号 (下标从 1 开始)，而 YY_NUM_RULES 指出了规则的总数。因此你可以这样统计每个规则被执行了多少次 
1
2

int ctr[YY_NUM_RULES];
#define YY_USER_ACTION ++ctr[yy_act]
YY_USER_INIT
提供了在第一次扫描之前或者内部初始化之前，执行的操作。比如说打开日志文件。
yy_set_interactive(is_interactive)
控制当前缓冲区是否是交互的。交互式的缓冲区性能差，但输入源是交互式的可以避免由于等待填充缓冲区导致的问题。也可以使用操作 %option always-interactive 或 %option never-interactive 指定是否为交互式缓冲区，但该宏会覆盖这两个操作。其值零表示为非交互的。
yy_set_bol(at_bol)
控制当前缓冲区是否开启行头的扫描上下文。零值表示为 ^ 规则无效。宏 YY_AT_BOL 可以给出当前的情况。
char *yytext
当前 token 的文本。你可以修改它但不能增长它。另外 %array 模式不能在生成 C++ 版本扫描器时使用
int yyleng
当前 token 的文本长度。
FILE *yyin
当前读取文件的指针。如果想修改需要在扫描开始之前或遇到 EOF 之后，否则 UB，这种情况请使用 yyrestart()。
void yyrestart(FILE *new_file);
要求 yyin 指向新的输入文件。
FILE *yyout
当前输出的文件。
YY_CURRENT_BUFFER
当前缓冲区的 YY_BUFFER_STATE 句柄。
YY_START
当前 sc 的值，通常用于 BEGIN action。

有很多 scanner option，但通常只需要指定一些就够了

1
2
3
4

%option   8bit reentrant bison-bridge
%option   warn nodefault
%option   yylineno
%option   outfile="scanner.c" header-file="scanner.h"

flex 你可以在第一部分中写入 %option，大部分选项都以名称的形式给出，你可以在前面加上 no 来表示否形式。这些名称与相应的命令行选项相同。

如果你有些强迫症，需要将没用的过程全部关闭，不让 flex 生成相关过程。下列函数是默认生成的：

input, unput
yy_push_state, yy_pop_state, yy_top_state
yy_scan_buffer, yy_scan_bytes, yy_scan_string

yyget_extra, yyset_extra, yyget_leng, yyget_text,
yyget_lineno, yyset_lineno, yyget_in, yyset_in,
yyget_out, yyset_out, yyget_lval, yyset_lval,
yyget_lloc, yyset_lloc, yyget_debug, yyset_debug

  • 指定导出的头文件名称
    • long name: header-file
    • option name: header-file
    • param: FILE
    • comment: 与 --c++ 选项不兼容
  • 指定导出的源文件名称
    • short name: o
    • long name: outfile
    • option name: outfile
    • param: FILE
  • 将生成的扫描器写入 stdout 而不是 lex.yy.c
    • short name: t
    • long name: stdout
    • option name: stdout
  • 修改构造扫描器模板
    • short name: S
    • long name: skel
    • param: FILE
    • comment: 除非你是 flex 的开发人员，否则不要使用此选项
  • 将序列化的扫描器 DFA 表写入文件
    • long name: tables-file
    • param: FILE
    • comment: 生成的扫描器将不会包含该表，并在运行时加载
  • 检查序列化表的一致性
    • long name: tables-verify
    • comment: 开发选项。序列化 DFA 表，并在运行时与代码内表进行匹配验证，而不是加载序列化表
  • 不区分大小写
    • short name: i
    • long name: case-insensitive
    • option name: case-insensitive
    • comment: 虽然匹配将忽略大小写，但 yytext 获得的数据还是保留了大小写
  • AT&T lex 兼容
    • short name: l
    • long name: lex-compat
    • option name: lex-compat
    • comment: 最大成度兼容 AT&T lex，但不保证完全兼容。会拖慢扫描器性能，还会导致大量选项不可用。
  • 交互式扫描器
    • short name: I
    • long name: interactive
    • option name: interactive
    • comment: 以性能换取足够的交互性，默认采用这种模式，除非你使用了 -Cf 或 -CF 提高性能的选项。
  • 7 bit 扫描器
    • short name: 7
    • long name: 7bit
    • option name: 7bit
    • comment: 只能识别输入中的 7 bit 字符的扫描器。优点是器生成的表格的大小仅有 8bit 的一半，需要同时指定 -Cf 或 -CF 的表压缩选项才会有显著提升。但输入包含 8bit 字符将挂起或崩溃。
  • 8 bit 扫描器
    • short name: 8
    • long name: 8bit
    • option name: 8bit
  • 生成默认规则
    • long name: default
    • option name: default
  • 始终交互式扫描器
    • long name: always-interactive
    • option name: always-interactive
    • comment: 通常新的输入文件上，扫描器都会调用 isatty() 来确定扫描器的源是否是交互式的，因此一次读入一个字符。该选项会认为始终是交互式源，不会有相关调用。
  • 绝不交互式扫描器
    • long name: never-interactive
    • option name: never-interactive
  • POSIX lex 兼容
    • short name: x
    • long name: posix
    • option name: posix
    • comment: 最大成度兼容 POSIX 1003.2-1992 定义的 lex，由于最初实现是为 POSIX 定义所设计的，因此只有很少的行为不一致。已知的是 cat 与重复 {} 之间的优先级问题，大多数 POSIX 程序使用的扩展正则表达式 (ERE) 优先级与 flex 默认优先级一致，都是 cat 低于重复 (即 ab{3} 将产生 abbb)，而 POSIX 定义下是高于的 (即 ab{3} 将产生 ababab)。
  • 启用 sc 栈
    • long name: stack
    • option name: stack
  • 初始化输入输出为标准 IO
    • long name: stdinit
    • option name: stdinit
  • 读取行号
    • long name: yylineno
    • option name: yylineno
  • 文件结束判断
    • long name: yywrap
    • option name: yywrap
  • GNU Bison 支持
    • long name: bison-bridge
    • option name: bison-bridge
    • comment: 指示扫描器将被 GNU Bison 调用，增加了对 Bison 兼容性，以及对一些 API 的修改
  • GNU Bison locations 支持
    • long name: bison-locations
    • option name: bison-locations
    • comment: 指示扫描器正在使用 GNU Bison %locations，yylex 将而额外增加一个 yylloc 参数。这个选项意味着启用了上一个选项。
  • 不生成 #line 指令
    • short name: L
    • long name: noline
    • option name: noline
    • comment: 不加这个选项时，Flex 生成的 action 错误消息将相对原始，有助于错误定位
  • 生成可重入的 C 扫描器
    • short name: R
    • long name: reentrant
    • option name: reentrant
    • comment: 生成可重入的扫描器，该扫描器可能是线程安全的。但是 API 可能与非可重入扫描器有所区别。因此可能需要修改代码，另外 --c++ 选项与该选项不兼容。
  • 生成 C++ 扫描器
    • short name: +
    • long name: c++
    • option name: c++
  • yytext 使用数组实现
    • long name: array
    • option name: array
  • yytext 使用指针实现
    • long name: pointer
    • option name: pointer
  • 修改默认的前缀名称

    • short name: P

    • long name: prefix

    • option name: prefix

    • param: PREFIX

    • comment: 将全局可见变量和函数名称默认的 yy 前缀修改为指定前缀，比如 prefix=foo 将 yytext 变为了 footext，另外默认生成的源文件也会从 lex.yy.c 改为 lex.foo.c。以下是所有受影响的名称

      • yy_create_buffer
      • yy_delete_buffer
      • yy_flex_debug
      • yy_init_buffer
      • yy_flush_buffer
      • yy_load_buffer_state
      • yy_switch_to_buffer
      • yyin
      • yyleng
      • yylex
      • yylineno
      • yyout
      • yyrestart
      • yytext
      • yywrap
      • yyalloc
      • yyrealloc
      • yyfree

      但是，如果是 C++ 扫描器只会影响到 yywrap 和 yyFlexLexer。另外你需要自己实现对应名称的 yywrap。

  • 生成一个默认的 main
    • long name: main
    • optino name: main
    • comment: 为扫描器生成一个默认的、简单调用 yylex 的 main 函数，此选项会开启 noyywrap 选项。
  • 禁止使用 unistd.h
    • long name: nounistd
    • optino name: nounistd
    • comment: 针对不存在 POSIX 的环境，flex 将不包含头文件 unistd.h。但某些选项可能依赖于该头文件。
  • C++ 类名称
    • long name: nounistd
    • optino name: nounistd
    • param: NAME
    • comment: 告诉 Flex 你将使用 NAME 作为 yyFlexLexer 派生的子类名称。代码将生成在子类中的 yylex() 中，如果你调用 yyFlexLexer::yylex() 将会发生运行时错误。

压缩表的程度在以下选项中，通常被认为是在小型表和高性能扫描器之间的选择

  • 不适用等价类或元等价类的压缩表
    • short name: C
  • 以表的大小空间换取性能
    • short name: Ca
    • long name: align
    • option name: align
    • comment: 利用表的元素更好地内存对齐与计算，但可能将表格大小增加四倍。某些 RISC 架构上获取和操作长字比使用较小尺寸的短字更有效。
  • 为扫描表构造等价类
    • short name: Ce
    • long name: ecs
    • option name: ecs
    • comment: 等价类会显著减小最终表 / 目标文件的大小 (通常是 2 ~ 5 倍)，并且不会付出太多额外性能。
  • 构造完整的扫描表
    • short name: Cf
    • comment: 不通过利用不同状态的类似转换函数来压缩表
  • 构造快速扫描表
    • short name: CF
    • comment: 不应与 --c++ 一起使用
  • 构造元等价表
    • short name: Cm
    • long name: meta-ecs
    • option name: meta-ecs
    • comment: 通常元等价表更为小巧，且对性能影响适中。但没有压缩的表无法启用该选项，因此不能与 -Cf 或 -CF 一起使用。
  • 绕开标准 IO 库的输入
    • short name: Cr
    • long name: read
    • option name: read
    • comment: Flex 直接使用 syscall read() 进行输入，而非标准 IO 库的 fread() 或 getc()。除非你还使用 -Cf 或 -CF，否则其性能提升可以忽略不计。

表格的压缩选项可以组合起来，比如默认的表格选项是 -Cem，Flex 默认开启了等价类和元等价类选项，这是最慢的一种情况，但是表格最小的情况。可以理解的是，Flex 支持以生成表格的大小来换取扫描器的性能，从表格最小到扫描器性能最高的选项依次是 -Cem、-Cm、-Ce、-C、-C{f,F}e、-C{f,F}e、-C{f,F}a。往往越小的表格生成和编译也就越快，而 -Cfe 选项通常是在压缩大小与性能之间比较好的权衡。

  • 构造完整扫描表
    • short name: f
    • long name: full
    • option name: full
    • comment: 等价于 -Cfr
  • 构造快速扫描器
    • short name: F
    • long name: fast
    • option name: fast
    • comment: 等价于 -CFr
  • 备份信息到 lex.backup
    • short name: b
    • long name: backup
    • option name: backup
    • comment: 备份扫描器的状态列表和需要备份输入字符。如果消除所有的备份状态并使用 -Cf 或 -CF，生成的扫描器将运行得更快。
  • debug 模式
    • short name: d
    • long name: debug
    • option name: debug
    • comment: 当匹配到规则并全局变量 yy_flex_debug 不为零时，将给 stderr 中写入如下形式 
      1

      -accepting rule at line 53 ("the matched text")
  • 性能报告
    • short name: p
    • long name: perf-report
    • option name: perf-report
    • comment: 获得导致扫描器性能严重下降的功能注释，如果包含两次该选项，还会报告轻微性能损失。使用 REJECT、可变尾随上下文会导致严重的性能损失，而 yymore()、^ 运算符和 --interactive 会导致轻微性能下降。
  • 抑制默认规则
    • short name: s
    • long name: nodefault
    • option name: nodefault
    • comment: 将不匹配的输入回显到 stdout。
  • 追踪模式
    • short name: T
    • long name: trace
    • option name: trace
    • comment: 在 stderr 中生成更多关于 NFA 与 DFA 的消息，通常用于维护 Flex。
  • 不生成警告消息
    • short name: w
    • long name: nowarn
    • option name: nowarn
  • 详细消息
    • short name: v
    • long name: verbose
    • option name: verbose
    • comment: 在 stderr 中生成更多有关生成扫描器的统计信息。但是大多数信息对于临时使用 Flex 的用户没什么用。
  • 警告信息
    • long name: warn
    • option name: warn
    • comment: 如果可以匹配默认规则但没有给出默认规则，则 flex 会发出警告。建议始终使用此选项。

Flex 的首要目标是构造高性能扫描器，因此已经针对大量规则进行了优化。但是除了表格与性能的取舍外，还有很多操作会降低性能，这里列出从严重影响性能到轻微影响性能的操作：

  • REJECT
  • 可变的尾随上下文
  • 需要备份的模式集
  • %option yylineno
  • %array
  • %option interactive
  • %option always-interactive
  • ^ 运算符
  • yymore()

另外需要注意，unput 的实现可能会有大量的调用，而 yyless 很轻量，因此只是放回扫描的多余文本，请使用后者。

flex 具有生成可移植的可重入 C 扫描器的能力。简单地说，即可以不需要与其他线程同步的情况下，创建多线程并行的扫描器。另外根据 info 的描述，所有的 C++ 扫描器都是可重入的。

你可以同时扫描两个或多个文件来对比 token 级别的差异，而非字符串级别的差异，比如

1
2
3
4
5
6
7
8

/* Example of maintaining more than one active scanner. */
do {
    int tok1 = yylex(scanner_1);
    int tok2 = yylex(scanner_2);
    if (tok1 != tok2) {
        printf("Files are different.\n");
    }
} while (tok1 && tok2);

另一个用途是创建递归扫描器，虽然也可以通过不可重入扫描器和缓冲区状态实现。下面是一个 eval 的实现

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

/* Example of recursive invocation. */
%option reentrant
%%
"eval(".+")"  {
                  yyscan_t scanner;
                  YY_BUFFER_STATE buf;
                  yylex_init( &scanner );
                  yytext[yyleng-1] = ' ';
                  buf = yy_scan_string( yytext + 5, scanner );
                  yylex( scanner );
                  yy_delete_buffer(buf,scanner);
                  yylex_destroy( scanner );
             }
...
%%

可重入扫描器与不可重入扫描器有一定区别。

  • 所有的函数需要加上参数 yyscanner
  • 所有的全局变量被它们的相应的等价宏替代，比如 yytext 被替换为 
    1

    #define yytext (((struct yyguts_t*)yyscanner)->yytext_r)
  • yylex_init 和 yylex_destroy 必须分别在 yylex 之前和之后调用 
    1
2
3
4

    int yylex_init(yyscan_t *ptr_yy_globals);
int yylex_init_extra(YY_EXTRA_TYPE user_defined, yyscan_t *ptr_yy_globals);
int yylex(yyscan_t yyscanner);
int yylex_destroy(yyscan_t yyscanner);
  • 使用访问器方法 (get/set) 对常见的 flex 变量进行访问，格式为 yyget_NAME 或 yyset_NAME，另外还有额外的参数 yyscanner 
    1
2
3
4
5

    /* Set the last character of yytext to NULL. */
void chop(yyscan_t scanner) {
    int len = yyget_leng(scanner);
    yyget_text(scanner)[len - 1] = '\0';
}
  • 用户特定的数据可以存储在 yyextra 中。可重入场景下，不能直接访问全局变量，因此用户的全局状态可以存储于 yyextra 中。 
    1
2
3

    #define YY_EXTRA_TYPE  void*
YY_EXTRA_TYPE  yyget_extra(yyscan_t scanner);
void           yyset_extra(YY_EXTRA_TYPE arbitrary_data, yyscan_t scanner);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

/* This scanner prints "//" comments. */
%option reentrant stack noyywrap
%x COMMENT

%%

"//"                 yy_push_state(COMMENT, yyscanner);
.|\n
<COMMENT>\n          yy_pop_state(yyscanner);
<COMMENT>[^\n]+      fprintf(yyout, "%s\n", yytext);

%%

int main(int argc, char *argv[]) {
    yyscan_t scanner;
    yylex_init(&scanner);
    yylex(scanner);
    yylex_destroy(scanner);
    return 0;
}

GNU Bison 与 Flex 一样，都是遵循 GPL 协议发布的软件，不同的是，它是 GNU 项目！

GNU Bison 是一个通用的语法分析生成器，它可以将上下文无关文法生成使用 LALR(1) 分析表的确定性 LR 或通用 LR (GLR) 解析器。另外还可以生成实验性的 IELR(1) 或规范 LR(1) 分析表。

Bison 兼容 Yacc 项目，因此无需任何修改 Yacc 语法就能在 Bison 上运行。你可以使用 C 或 C++ 进行编写程序，但 Bison 现在实现性的增添了 Java 支持。

形式语言是数学表达，因此 Bison 需要定义自己的语法来生成相关的分析器。

非终结符，即表达式左边的标识符，在 Bison 中用小写表示，比如 epxr, stmt 等。终结符或 token 在 BISON 中用大写表示，如 INTEGRE, RETURN 等。需要额外注意的是 error 作为保留标识用于错误处理。还有一种标记终结符的方法是使用 C 字符串常量的形式。示例 C 语言 return 语句的 Bison 语法

1

stmt: RETURN expr ';' ;

如果一条规则表示的终结符是整数常量，那么任意整数常量都是有效的。也就是说，解析输入与具体的值是无关的：可以解析 x+4 的语法，也可以解析 x+1 或 x+5452。

但是对于被解析之后，精确值是十分重要的。无法区分精确值的编译器不是好的编译器！因此对每个 token，Bison 都会有一个 token 类型和一个语义值。

一般来说 token 类型是一个语法的终结符，比如说 INTEGER、IDENTIFIER 或 ',' 等。它可以提供决定 token 是否出现得正确和怎样组织其他 token 的所需的一切，比如整数字面量的值，或标识符的名称。而语法规则除了 token 类型外什么都不必知道。

每个分组还可以具有语义值以及非终结符。比如计算器程序，表达式通常是数字语义值，而编译器中语义值描述的是树结构。

同样地不止需要解析输入，还要对输入有一些对应的行为，Bison 对文法规则的行为 (action) 也是 C 代码段，每次解析器发现匹配的规则时都会执行相应的行为。

更多时候 action 的目的是根据部分语义值计算真个构造的语义值。比如说有一个规则是加法规则

1

expr: expr '+' expr   { $$ = $1 + $3; };

这个 action 说明了如何用两个子表达式的值生成 sum 表达式的语义值。

Bison 的确定性 LR(1) 解析算法无法在某些语法上决定如何在这个操作点上给出确定的操作，即产生了 归约/归约 冲突或 移入/归约 冲突。

有时需要更通用的解析文法，你的文件中声明 %glr-parser 就能生成 GLR (Generalized LR) 解析器。GLR 解析器与确定性解析器处理普通 Bison 文法相同，只有在发生冲突时，GLR 采用两者兼顾的权宜之计，有效复刻出解析器以遵循这两种方式。每个复刻的解析器可以继续复刻，因此可以尝试任意可能的结果。解析器也同步进行，它们都消耗给定的符号才进入下一阶段。每个复刻出的解析器在发生错误时就将消亡，而没有错误的解析器则会和其他解析器合并，因为已经将输入减少到了同一组相同的符号。

期间的所有解析器只会记录 action 而不会操作，如果解析器消亡那么 action 也随之消亡。只有合并时根据记录的 action，根据语法的优先级，或执行所有 action 后在结果值上调用用户定义的函数产生合并结果。

更多有关 GLR 的内容，可以查看 Scott 在 2000 年发表的 Tomita-Style Generalised LR Parsers。

  • 无二义性 GLR 解析器示例

    这个简单的示例是用 GLR 解析无二义性但无法成为 LR(1) 的文法，这种文法是典型需要向前看不止一个符号的文法。考虑在 Pascal 语言中出现的枚举声明与 subrange 类型。

    1
2

    type subrange = lo .. hi;
type enum = (a, b, c);

    原始的语言标准只允许数字字面量或常量标识符出现在 subrange 中，但扩展 Pascal (ISO/IEC 10206) 和更多的 Pascal 实现都允许任意表达式。这就可以比如这样的表达式

    1

    type subrange = (a) .. b;

    但是枚举类型的声明与这很类似

    1

    type enum = (a);

    在 .. 之前这都是相同的，当 LR(1) 文法解析到这里时不可能在两种形式上做出决定，但解析器必须做出这一点。如果是 subrange 的话 a 可以是一个常量或函数调用，而枚举的话则必须是一个标识符。如果将 (a) 解析成未指定的标识符从而稍后解决，但这通常需要在语义动作和大部分语法中进行大量扭曲。

    你可能希望通过 lex 为当前定义和未定义的标识符返回不同的标记来区分两种状态。但声明出现在 local 但 a 为 extern 定义，那么需要重新定义 a 或使用 extern 的 a。所以这是行不通的。

    简单的方法就是使用 GLR 算法，分裂成两个分支，同时解析两个语法规则，迟早会有一个分支因错误而消亡。在下一个 ; 之前有一个 .. 会导致枚举规则的分支解析失败，否则导致 subrange 的分支解析失败。因此只有一个分支会保存下来。如果两个分支都失败， GLR 则会像往常一样发出一个语法错误。所有的一切影响是解析器似乎猜到正确的分支，或者说这似乎比底层使用的 LR(1) 支持了更多的向前看符号。虽然示例是个 LR(2) 的文法，但 GLR 也可以针对 LR(k) 的情况做正确的处理。

    一般来说 GLR 解析器可以采用二到三次最坏的情况时间，但 GLR 的某些语法解析可能需要指数的时间与空间，实际上这种情况对于许多语法来说不会发生。示例中仅在两个规则之间发生了冲突，且这两个冲突的类型声明上下文不能嵌套。因此任意时间存在的分支被限制在两个，解析时间依然是线性的。

    虽然用户可以不加修改语法文件的情况下，将 LR 解析器替换为 GLR 解析器，用户甚至不会注意解析器在何时分叉。但需要注意的是， LR 解析器在冲突中会静态选择错误的替代方案，GLR 则会进行分叉继续向下分析，从而导致问题不那么明显。另外需要小心地与词法分析器进行交互，分叉后解析器不进行任何执行动作，因此无法通过解析器获取操作信息。好在 Bison 可以将复杂性从与词法分析器的交互转移到 GLR 解析器，但仍要检查其余情况的正确性。

  • 二义性文法 GLR 解析器示例

    从一个简化的 C++ 语法示例看起

     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
31
32
33
34
35
36
37
38
39
40
41
42

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

%token TYPENAME ID

%right '='
%left '+'

%glr-parser

%%

prog:
  %empty
| prog stmt                          { printf ("\n"); }
;

stmt:
  expr ';'  %dprec 1
| decl      %dprec 2
;

expr:
  ID                                 { printf ("%s ", $$); }
| TYPENAME '(' expr ')'              { printf ("%s <cast> ", $1); }
| expr '+' expr                      { printf ("+ "); }
| expr '=' expr                      { printf ("= "); }
;

decl:
  TYPENAME declarator ';'            { printf ("%s <declare> ", $1); }
| TYPENAME declarator '=' expr ';'   { printf ("%s <init-declare> ", $1); }
;

declarator:
  ID                                 { printf ("\"%s\" ", $1); }
| '(' declarator ')'
;

    如果解析一个二义性程序

    1

    T (x) = y + z;

    这个语法将在 x 被解释为 ID 后 (假设 T 被解释成 TYPENAME) 分叉，因为规则 expr: ID 和 declarator: ID 都可以归约，这里产生归约/归约冲突。之后随着进行 expr 分支被归约为 stmt: expr ';' 而 decl 分支被归约为 stmt: decl，之后两个解析器都看到了 prog stmt 以及剩余相同的未处理输入，这里需要进行合并。但 bison 语法定义的 %dprec 声明将优先将示例解析为 decl。

    当然 %dprec 仅在多个解析器存在的时候有效，比如以下这个例子，这里没有歧义，在看到 + 时 decl 分支将消亡，因此 bison 不会看 %dprec 定义

    1

    T (x) + y;

    如果你不想解决歧义，而是像查看所有可能性，那就必须合并分支，而不是选择一个分支。因此需要更改 stmt 声明为

    1
2
3
4

    stmt:
  expr ';'   %merge <stmtMerge>
| decl       %merge <stmtMerge>
;

    并定义以下函数

    1
2
3
4

    static YYSTYPE stmtMerge(YYSTYPE x0, YYSTYPE x1) {
    printf("<OR> ");
    return "";
}

    当然还要进行 C 声明 (类似 flex)

    1
2
3
4

    %{
#define YYSTYPE char const *
static YYSTYPE stmtMerge(YYSTYPE x0, YYSTYPE x1);
%}

    Bison 要求参与合并的产生体都要有相同的 merge 句柄，否则将无法处理歧义，解析器也会因存在不合法合并而报错。

  • GLR 语义行为

    GLR 解析的性质与解析器的结构为语义值与行为产生了一些限制。

    • 延迟语义行为

      延迟行为不会与关联的归约一同执行，这可能会对在 GLR 解析器的语义行为中使用某行功能产生影响。

      • yychar 可以确定相关归约出现时的向前看 token 的类型。
      • yylval 与 yylloc 可以在 yychar 不为 YYEMPTY 或 YYEOF 时，确定向前看 token 的语义值与位置。

      非延迟行为你可以修改这些变量来影响语法分析结果，但延迟语义即使修改变量也意味着语法分析已经结束。另外延迟行为中，它们被设置为相关归约时具有的值的浅拷贝，因此修改它们是十分危险的。修改的结果是一个 UB。

    • YYERROR

      可以在语义行为中调用 YYERROR 来进行错误恢复，但延迟行为导致错误的精确点不再确定，因此会重新恢复到确定性解析，选择一个未指定的栈继续处理语法错误，YYERROR 会静默调用测试。

    • 限制语义值和位置

      GLR 解析器会要求在使用 C++ 代码时，为语义值与位置使用 POD 类型。

  • 位置

    解释器或编译器需要对错误信息进行详尽、有用的反馈，这就需要可以追踪源代码的文本位置。好在 Bison 在每个 token 都关联了位置，但位置类型是所有 token 或分组完全相同的。

    比如示例

    1

    expr: expr '+' expr   { $$ = $1 + $3; } ;

    当前分组的位置为 $$，而子表达式的位置为 $1 和 $3。通常不用为每个规则描述其 $$ 如何形成的，默认行为是采用第一个符号的开头和最后一个符号的结尾。

Bison 输入上下文无关的语法，并生成识别语法的 C 语言代码。

语法文件类似于以下结构

1
2
3
4
5
6
7
8
9

%{
PROLOGUE
%}

BISON DECLARATIONS
%%
GRAMMAR RULES
%%
EPILOGUE

并且可以使用 C 和 C++ 样式的注释。

序言 (Prologue) 部分可以包含宏定义以及函数与变量的声明，这将拷贝到生成文件的开头。这部分内容存放在 %{ 与 %} 块中。这与 Flex 类似。序言可以与 Bison 的声明混在一起，可以与 C 与 Bison 相互引用。但是通常将序言放在所有 Bison 声明之前更安全。比如任何的功能测试宏的定义 _GNU_SOURCE 和 _POSIX_C_SOURCE 都应如此。

声明 (Declaration) 部分包含定义终结符、非终结符、指定优先级等。一些简单的语法可能不需要声明。声明主要定义用于指定语法的符号和语义值的数据类型。

规则 (Rule) 部分至少有一个规则，用来编写语法分析处理行为。

结尾 (Epilogue) 会将所有代码复制到生成的解析器的末尾，和之前 Flex 的结尾一样。

Bison 语法 (Grammar)

  • Bison 语法规则

    语法规则很简单

    1

    RESULT: COMPONENTS ...;

    其中 RESULT (结果) 是该规则的非终结符，COMPONENTS (组件) 是有改规则组合在一起的各种终结符和非终结符。散布在组件之间的可以是确定规则的语义行为，通常是 C 语言行为，但 Bison 不会检查其正确性，只会完完整整地复制代码。

    1

    { C STATEMENTS }

    也可以用 | 连接多个规则。

    1
2
3
4
5

    RESULT:
  RULE1-COMPONENTS ...
| RULE2-COMPONENTS ...
...
;

    如果一个规则的 COMPONENTS 为空，则称为 empty。那么 RESULT 可以匹配空字符串。

    1

    RUSULT: | ";" ;

    上一个写法可能不那么好看，有个更好的写法是

    1
2
3
4

    RUSULT:
  %empty
| ";"
;

    如果添加 -Wempty-rule 将警告没有 %empty 的空规则，如果想关掉则使用 -Wno-empty-rule。另外这是 Bison 的扩展，如果想兼容 POSIX Yacc，则写法是

    1
2
3
4

    RUSULT:
  /* empty */
| ";"
;

  • Bison 递归规则

    当一个规则的非终结符也出现在右部时，这就是递归。递归几乎是 Bison 语法必须的部分，因为这是定义任意数量的特定事物序列的唯一方法。下面示例中，expseq1 是左递归的，而 expseq2 是右递归的，但这两个非终结符是等价的。

    1
2
3
4
5
6
7
8
9

    expseq1:
  exp
| expseq1 ',' exp
;

expseq2:
  exp
| exp ',' expseq2
;

    但是在编写时，应该更多地使用左递归，即迭代，它可以在有限堆栈空间上解析任意数量的元素，但右递归 (递归) 所用堆栈空间与元素数量成正比。

    另外还有间接或相互执行的递归。

    1
2
3
4
5
6
7
8
9

    expr:
  primary
| primary '+' primary
;

primary:
  constant
| '(' expr ')'
;

语言的语法规则仅约定语法，语义是由各种标记和分组相关的语义值，以及在识别各个分组时所采取的动作确定的。

  • 语义值的数据类型

    一个简单的程序中，语义值采用相同的类型就够了，比如计算器。Bison 通常将其设置为 int，如果要指定其他类型，则需要

    1

    %define api.value.type {double}

    或者使用 C/C++ 的预处理器来定义 YYSEYPE

    1

    #define YYSTYPE double

    这个宏必须写在 Prologue 中，如果需要对 POSIX Yacc 的兼容性，则需要使用它。

    但是你可能需要不止一种语义值的数据类型，但是想用多数据类型就要做两件事

    1. 指定数据类型的整个集合，有以下几种选择
      • 让 Bison 根据分配的标签计算
      • 使用 Bison 的 %union 声明
      • 使用 %define 将变量 api.value.type 定义为联合类型
      • 使用 typedef 或 #define 将 YYSTYPE 定义为联合类型，其成员名称是类型标签
    2. 使用语义值的每个符号选择其中一种类型

  • 生成语义值类型

    用 %define 定义变量 api.value.type 为 union，用 Bison 提供的 %type 与 %token 定义真正的类型。如下

    1
2
3
4
5

    %define api.value.type union
%token <int> INT "integer"
%token <int> 'n'
%type <int> expr
%token <char const *> ID "identifier"

    生成适当的 YYSTYPE 值来支持每种符号类型。由 token 声明的标识符 (如上面的 INT 和 ID)，在 YYSTYPE 中以字段名称的形式出现。而 ’n’ 并不是指定名称的字段，因此编写代码时不应依赖它们

    1
2
3
4
5
6
7
8
9

    // For an "integer"
yylval.INT = 42;
return INT;
// For an 'n', also declared as int
*((int*)&yylval) = 42;
return 'n';
// For an "identifier"
yylval.ID = "42";
return ID;

    为了避免名称冲突，来可以用 %define 来指定 api.token.prefix 来定义前缀。当然这又是个 Bison 扩展，

    1
2
3
4

    // %define api.token.prefix {TOK_}
// For an "integer"
yylval.TOK_INT = 42;
return TOK_INT;

  • Union 声明

    %union 声明语义值指定了可能包含的数据类型的集合，其中包含与 C 的 union 中的内容相同。

    1
2
3
4

    %union {
    double val;
    symrec *tptr;
}

    还可以为 union 加上 vaule 标签，在定义了 api.vaule.union.name 时可以生成类型的名称，在不定义时默认使用 YYSTYPE。由于 POSIX 可以多次声明 union，最终将这些 union 串联起来，因此只有第一个 union 定义可以加 value 标签。

    如果语法至少包含一个 <type> 标签，则可以使用自己定义的 YYSTYPE，

    1
2
3
4
5

    // parser.h
union YYSTYPE {
    double val;
    symrec *tptr;
};

    并修改为

    1
2
3
4
5
6

    %{
#include "parser.h"
%}
%define api.value.type {union YYSTYPE}
%type <val> expr
%token <tptr> ID

  • Bison 行为

    每个行为都可以在识别时带有一个 C 代码行为，这些行为的任务多是根据与标记或较小分组关联的语义值计算由规则构建的分组的语义值。

    之前也见到了，

    1

    expr : | expr '+' expr { $$ = $1 + $3; }

    当然还可以给每个位置命名

    1

    expr[result]: | expr[left] '+' expr[right] { $result = $left + $right; }

    如果没为规则指定操作，Bison 会使用默认的 $$ = $1，空规则应该具有显式的行为，除非规则的值无关紧要。

    另外指定位置为 0 或负数是十分危险的行为，除非你确定上下文的规则了，否则不要使用它。比如下面这个示例，$0 总是指 foo 中定义在 bar 之前的 expr，如果存在还可以通过 yylval 访问前瞻语义值。

    1
2
3
4
5
6
7
8

    foo:
  expr bar '+' expr { ... }
| expr bar '0' expr { ... }
;

bar:
  %empty { previsous_expr = $0; }
;

  • 行为中值的数据类型

    如果语义值是单一数据类型，那么 $$ 与 $N 始终是相同的数据类型；但多种类型的语义值，必须为每个可以具有语义值的终结符、非终结符选择类型，每次使用 $$ 和 $N 时，它的数据类型由规则的引用符号决定。比如

    1

    expr : | expr '+' expr { $$ = $1 + $3; }

    当然也可以在引用值时指明数据类型，比如说写成 $<INT>1。

  • 规则中行为

    有时将行为放在规则中间很有用，它可以在解析器识别下一个组件前执行。

    中间规则只能引用之前的 $N，而不能引用之后的位置。规则中行为往往算作规则的组成部分，并且也具有语义值，另外行为可以通过给 $$ 设置值，规则后面的行为可以用 $N 引用这个值，由于没有符号来命名行为，因此无法提前为该值声明数据类型，每次引用都需要指定数据类型 $<TYPE>N。并无法通过规则中行为设置整体的值，唯一的方法就是规则末尾的行为。示例处理一个 let (VARIABLE) STATEMENT 的 let 语句，需要在 STATEMENT 期间临时创建一个名为 VARIABLE 的变量，在解析 STATEMENT 时必须将 VARIABLE 放入符号表，并在之后将其删除。

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

    stmt:
  "let" '(' var ')'
    {
      $<context>$ = push=context();
      declare_variable($3);
    }/* [let] */
  stmt
    {
      $$ = $6;
      pop_context($<context>5/* let */);
    }

    如果解析器启动错误恢复程序时，可能丢弃之前的上下文而不恢复它，那么 $<context>5 就泄漏了，需要一个析构函数来完成中间行为的释放。解决方法是将中间行为放在非终结符的行为中，并为该非终结符定义一个析构函数。

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

    %type <context> let
%destructor { pop_context($$); } let

%%

stmt:
  let stmt
    {
      $$ = $2;
      pop_context($let);
    };

let:
  "let" '(' var ')'
    {
      $let = push_context();
      declare_variable($3);
    };

    在编译 bison 语法时，如果使用了中间行为，加上 -Wmidrule-value 是一个不错的选择，它可以帮我们检查中间行为中的一些问题。

    1
2
3
4
5
6
7

    bison -fcaret -Wmidrule-value mid.y
     mid.y:2.6-13: warning: unset value: $$
      exp: { a(); } "b" { $$ = c(); } { d(); } "e" { f = $1; };
           ^^^^^^^^
     mid.y:2.19-31: warning: unused value: $3
      exp: { a(); } "b" { $$ = c(); } { d(); } "e" { f = $1; };
                        ^^^^^^^^^^^^^

尽管语法规则和语义行为足以编写一个功能齐全的解析器，但处理一些额外的信息，尤其是符号位置可能很有用。处理位置的方式是通过提供数据类型和匹配规则时要采取的行为来定义的。

  • 位置的数据类型

    位置定义的数据类型比语义值简单很多，毕竟所有标记与分组都是相同的类型。通过 YYLTYPE 定义位置的类型，默认 Bison 指定的类型为

    1
2
3
4
5
6

    typedef struct YYLTYPE {
    int first_line;
    int first_column;
    int last_line;
    int last_column;
} YYLTYPE;

    这些字段在解析开始时被初始化为 yylloc 的 1。自定义位置类型的话，需要使用 %initial-action 操作。

  • 位置与行为

    与访问规则类似，访问位置使用表达式 @N，而左边的非终结符位置为 @$。位置也可以用命名位置 @[NAME] 或 @NAME。

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

    exp:
  ...
| exp '/' exp
    {
      @$.first_column = @1.first_column;
      @$.first_line = @1.first_line;
      @$.last_column = @3.last_column;
      @$.last_line = @3.last_line;
      if ($3)
        $$ = $1 / $3;
      else
        {
          $$ = 1;
          fprintf (stderr, "%d.%d-%d.%d: division by zero",
                   @3.first_line, @3.first_column,
                   @3.last_line, @3.last_column);
        }
    }

    每次匹配规则时，都会运行位置的默认操作，将 @$ 的开头设置为第一个符号的开头，将 @$ 的结尾指向最后一个符号的结尾。当然这是自动执行的，因此上下两个代码等价

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

    exp:
  ...
| exp '/' exp
    {
      if ($3)
        $$ = $1 / $3;
      else
        {
          $$ = 1;
          fprintf (stderr, "%d.%d-%d.%d: division by zero",
                   @3.first_line, @3.first_column,
                   @3.last_line, @3.last_column);
        }
    }

  • 位置的默认行为

    由于位置比语义值更通用，因此行为并不是计算位置的最佳位置。在每次匹配规则时运行相关操作之前都会调用 YYLLOC_DEFAULT，处理语法错误实惠调用它来计算错误位置。在报告无法解决的语法歧义之前，GLR 也会递归调用它来计算歧义的位置。大多数时候该宏就足够通用了。

    YYLLOC_DEFAULT 有三个参数，即分组的位置 (计算结果)、元素位置、右边的大小。当 GLR 报告歧义时，将多个未定义的候选传递给 YYLLOC_DEFAULT；在错误处理时，第二个参数表示在错误处理期间被丢弃的符号位置，第三个参数时丢弃的符号数量。默认定义如下：

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

    # define YYLLOC_DEFAULT(Cur, Rhs, N)                      \
do                                                        \
  if (N) {                                                \
      (Cur).first_line   = YYRHSLOC(Rhs, 1).first_line;   \
      (Cur).first_column = YYRHSLOC(Rhs, 1).first_column; \
      (Cur).last_line    = YYRHSLOC(Rhs, N).last_line;    \
      (Cur).last_column  = YYRHSLOC(Rhs, N).last_column;  \
    } else {                                              \
      (Cur).first_line   = (Cur).last_line   =            \
        YYRHSLOC(Rhs, 0).last_line;                       \
      (Cur).first_column = (Cur).last_column =            \
        YYRHSLOC(Rhs, 0).last_column;                     \
    }                                                     \
while (0)

    其中 YYRHSLOC(rhs, k) (k 为正时，表示 RHS 的第 k 个符号)，当 k 和 N 都为零时，符号在归约之前的位置。定义 YYLLOC_DEFAULT 之前应该考虑：

    • 所有的参数都没有副作用。只有第一个 (结果) 可以被宏修改
    • 为与语义行为保持一致，右侧的有效索引范围为 1 到 N。当 N 为 0 时只有 0 时有效索引，指归约前的符号。在错误处理期间 N 始终为正。

用编号指定位置或规则一点也不好用还容易出错，因此使用名称引用更有可读性。

1

invocation: op '(' args ')' { $$ = new_invocation ($op, $args, @$); }

但是有时候一个递归语法，可能出现二义性。但是又不想用编号的情况下，可以用 [NAME] 来指定名称。

1
2
3
4
5
6
7
8

exp: exp '/' exp { $exp = $exp / $exp; }  // $exp is ambiguous.

exp: exp '/' exp { $$ = $1 / $exp; }      // One usage is ambiguous.

exp: exp '/' exp { $$ = $1 / $3; }        // No error.

exp[result]: exp[left] '/' exp[right]
  { $result = $left / $right }            // No error.

在使用点、破折等字符时，需要显式括号语法。这是由于 Bison 通常将 $name.suffix 解析为 $name 与语义值字段 suffix。为识别整体必须用此语法。

1
2

if-stmt: "if" '(' expr ')' "then" then.stmt ';'
  { $[if-stmt] = new_if_stmt ($expr, $[then.stmt]); }

当然中间行为也可以使用命名。

1
2

exp[res]: exp[x] '+' {$left = $x;}[left] exp[right]
  { $res = $left + $right; }

Bison 声明部分用于指定语法的符号和语义值的数据类型。通常必须声明所有的 token (除了像 ‘+’ 这种单字符字面量 token)。如果指定语义值的数据类型，那么就必须声明非终结符。

  • Token 类型名

    通常使用语法 %token NAME 来声明，这通常会被 Bison 在生成的解析器中用宏实现。当然还能指定其 token 的数字代码。

    1
2

    %token NUM 300
%token XNUM 0x12d  // a GNU extension

    不过更好的方式是让 Bison 自己选择数字代码，Bison 会保证其不冲突。就像之前提到的，使用自定义的语义值类型时需要自行定义其类型。

    1
2
3
4
5

    %union {          /* define stack type */
    double val;
    symrec *tptr;
}
%token <val> NUM  /* define token NUM and its type */

    如果你需要将一些字符串字面量与标记类型相关联，可以用以下这种方式

    1
2
3

    %token  <operator>  OR      "||"
%token  <operator>  LE 134  "<="
%left  OR  "<="

  • 声明运算符优先级

    你可以使用 %left、%right、%precedence 或 %nonassoc 来替换 token，来指定其关联性和优先级，它们和 %token 一致，区别就在于指定了关联性和优先级：

    • 运算符 OP 的关联性取决于运算法嵌套的方式，即有些语言中说的左结合与右结合。比如表达式 X OP Y OP Z，左结合即运算符从左向右依次计算表达式，即 (X OP Y) OP Z；右结合正好相反，即X OP (Y OP Z)。而 %nonassoc 指定为无关联性，意思是 X OP Y OP Z 被认为语法错误。
    • %precedence 赋予了符号相对的优先级，但不赋予其任何关联性。比如表达式 X OP1 Y OP2 Z，如果 OP2 的优先级高于 OP1，那么将解析为 X OP1 (Y OP2 Z)。
    • 在单个优先级声明中，所有符号的优先级相同，它们根据关联性进行分组。当两个不同优先级的符号，后一个声明的 token 优先级更高。

  • 声明非终结符的类型

    当自定义语义值类型时，就必须声明每个非终结符的类型。

    1

    %type <TYPE> NONTERMINAL...

  • 解析前执行行为

    解析器可能需要在解析之前执行一些初始化。%initial-action 指令允许这样的操作，其中可以执行任意的代码。

    1
2
3
4

    %parse-param { char const *file_name };
%initial-action {
  @$.initialize (file_name);
}

  • 释放符号

    在错误恢复期间，以压入栈的符号和来自文件其余部分的 token 将被丢弃，直到解析器停止运行。如果解析器内存不足，或它通过 YYABORT 或 YYACCEPT 返回，则必须丢弃堆栈上的所有符号。即使解释器成功，也必须丢弃开始符号。如果丢弃的数据在堆上，会造成内存泄漏，这种行为对批处理解析器 (如传统编译器) 是没问题的，但无限期解析和执行的程序 (如 shell) 是不可接受的。

    %destructor 指定了自动丢弃符号时调用的代码。

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

    %union { char *string; }
%token <string> STRING1 STRING2
%type <string> string1 string2
%union { char character; }
%token <character> CHR
%type <character> chr
%token TAGLESS

%destructor {  } <character>
%destructor { free($$); } <*>
%destructor { free($$); printf("%d", @$.first_line); } STRING1 string1
%destructor { printf("Discarding tagless symbol.\n"); } <>

    在这个示例中，解析器丢弃 CHR 和 chr 时不会做任何行为，而其他符号都会调用 free 函数来释放内存。当然在释放 STRING1 和 string1 的符号时，只会调用第二个析构函数，保证只会释放依次内存。

    Bison 生成的解析器只为用户定义的符号调用 %destructor，也不会为中间行为调用析构函数。

    丢弃的符号类型如下：

    • 错误恢复的第一阶段弹出堆栈的符号
    • 错误恢复的第二阶段写入终端
    • 解析器立即返回时的当前向前看符号和整个堆栈 (除非当前是生成体符号)
    • 解析器成功时的开始符号

  • 声明抑制冲突警告

    如果语法存在冲突，Bison 会发出警告 (虽然大部分冲突都是无害的移入归约冲突)，因此可以使用声明来抑制这些冲突。声明移入规约冲突数量为 %expect N，而声明归约归约冲突的数量为 %expect-rr N。N 说明应该有 N 个预期的相应的冲突，如果数量不对 Bison 将会发出警告。

    使用 %expect 时你应该确保：

    • 编译时不用 %expect 并且使用 -v 选项可以查看冲突发生的具体信息，还会打印冲突的数量。
    • 检查每个冲突一确保 Bison 的默认解决方案是符合预期的。不符合预期的语法需要重写并重新检查信息。
    • 添加 %expect 声明。

  • 声明开始符号

    Bison 假定文法的开始符号时指定的第一个非终结符，你可以自己指定

    1

    %start SYMBOL

  • 声明可重入解析器

    信息 
    对于 **Pure** 解析器，或许可以考虑生成 **Pure** 函数式语言代码，比如 Haskell

    通常 Bison 生成的是不可重入的，因为这是与 Yacc 兼容的最重要一步。但依然不影响你可以抛弃对 Yacc 的兼容性，采用 %define api.pure 来生成可重入解析器

    1

    %define api.pure full

    但是生成可重入代码需要付出相应的代价，那就是通信变量 yylval 与 yylloc 成为 yyparse 的局部变量，并且 yylex 生成了不同的调用约定。另外错误处理变量 yynerrs 在 pull 模式下是 yyparse 的局部变量，而 push 模式下时 yypstate 的成员。

    幸运的是，是否可重入并不影响语法规则，可以从任何有效的语法规则生成可重入或不可重入的解析器。

  • Push 解析器

    信息 
    从 GNU Bison **3.1** 开始 push parsers 不再是实验性功能

    Pull 解析器每调用一次，它都会控制直到所有输入都被解析。另一方面，每次有新 token 可用时都会被推送到解析器。客户端应用是主事件循环的一部分时，Push 解析器将很有用。需要在特定时间内触发事件循环，这通常是 GUI 的要求。

    通常 Bison 会生成的是 Pull 解析器，如果希望生成 Push 解析器，可以声明

    1

    %define api.push-pull push

    在几乎所有情况下，Push 解析器应该都是纯解析器，除非直到自已在做什么

    1
2

    %define api.pure full
%define api.push-pull push

    纯的 Push 解析器和不纯的 Push 解析器之间存在主要的功能差异。纯 Push 解析器可以同时在内存中拥有许多相同类型解析器的实例，相反不纯的只能使用一个解析器。

    yypstate 是生成的解析器用来存储解析器状态的结构，yypstate_new 是创建新解析器实例的函数，yypstate_delete 将释放相应解析器实例相关联的资源，而 yypush_parse 是当令牌可用于提供解析器时应该调用的函数。简单的调用示例如下：

    1
2
3
4
5
6

    int status;
yypstate *ps = yypstate_new();
do {
    status = yypush_parse(ps, yylex(), NULL);
} while (status == YYPUSH_MORE);
yypstate_delete(ps);

    如果用户决定使用不纯的 Push 解析器，则生成的解析器会发生一些变化。比如 yychar，将是一个全局变量而非 yypush_parse 中的局部变量。

    1
2
3
4
5
6
7
8

    extern int yychar;
int status;
yypstate *ps = yypstate_new();
do {
    yychar = yylex();
    status = yypush_parse(ps);
} while (status == YYPUSH_MORE);
yypstate_delete(ps);

    Bison 在同一个生成的解析器中还支持 Push 和 Pull 解析器接口。为获取此功能你可以使用

    1

    %define api.push-pull both

    除了上述的符号，Bison 还会生成 yyparse (调用 pull 的解析器) 和 yypull_parse。可以使用 yypush_parse 来选择一个子语法，然后用 yypull_parse 解析输入流的其他部分。但如果想在 pull 和 push 之间来回切换需要自行编写 yypull_parse 函数。

    1
2
3

    yypstate *ps = yypstate_new();
yypull_parse(ps);
yypstate_delete(ps);

  • %code 声明

    %code 可以比 %{%} 代码块提供更多的灵活性。通常情况下非限定的 %code 可以替换 %{%}。

    重点主要放在限定代码块上。语法 %code QUALIFIER { CODE }。限定符有如下几种

    • requires

      通常在这里编写 YYSTYPE 与 YYLTYPE 依赖的代码，Bison 将这里的代码复制到头文件和源文件中的 YYSTYPE 与 YYLTYPE 的定义之前。

    • provides

      通常在这里编写提供给其他模块的附加定义和声明。Bison 会将这些代码复制到 YYSTYPE、YYLTYPE 和 token 定义之后的头文件和源文件中。

    • top

      需要在 Bison 生成的源代码文件中的顶部插入代码时，应该使用该限定符。

Bison 的解析器实际上是名为 yyparse 的 C 函数。我们需要对其进行约定。请记住解析器出于内部的目的使用了很多 yy 或 YY 开头的 C 标识符，请小心冲突。

你需要调用 yyparse 来进行解析。此函数读取标记、执行行为，并在遇到输入结束或不可恢复的语法错误时最终返回。你还可以编写一个行为，指示 yyparse 立即返回，而无需继续执行。

1
2
3
4

int yyparse(void);
// RETURN YYACCEPT (0) if report success,
// RETURN YYABORT (1) if report failure,
// RETURN 2 if memory exhaustion.

如果使用纯解析器，可以声明 %parse-param 为 yyparse 和 yyerror 定义额外的参数。比如

1

%parse-param {int *nastiness} {int *randomness}

声明后，这两个的函数如下

1
2

void yyerror(int *nastiness, int *randomness, const char *msg);
void yyparse(int *nastiness, int *randomness);

当然同时使用 %define api.pure full (或仅 %define api.pure) 和 %locations， yyerror 将生成不一样的签名。

1

void yyerror(YYLTYPE *llocp, int *nastiness, int *randomness, const char *msg);

在调用时就可以这样使用

1
2

int nastiness, randomness;
value = yyparse(&nastiness, &randomness);

在语法的规则行为中，也可以使用由 yyparse 传入的参数

1

exp: ... { ...; *randomness += 1; ... }

该函数从输入流中识别并返回 token，不会由 bison 创建，你可以使用 Flex 创建它。

  • yylex 调用约定

    yylex 必须返回 token 类型的整数值，零或负数表示输入结束。当然 token 只有一个字符时也可以直接返回该字符。

     1
 2
 3
 4
 5
 6
 7
 8
 9
10

    int yylex(void) {
    if (c == EOF) {
        return 0;
    }
    if (c == '+' || c == '-') {
        return c;
    }
    // ...
    return INT;
}

    如果语法使用字符串字面量 token，yylex 可以通过两种方式确定它们的标记类型代码：

    • 如果语法将符号 token 名称定义为字符串字面量别名，则 yylex 可以像所有其他符号一样使用这些符号名称。在这种情况下，在语法文件中使用字符串字面量 token 对 yylex 没有影响。
    • yylex 可以在 yytname 表中找到多字符 token，表中的索引是该 token 的编码，该 token 的名字用双引号 (”) 包围并记录在表中。 
      1
2
3
4
5
6
7
8

      for (i = 0; i < YYNTOKENS; i++) {
    if (yytname[i] != 0 && yytname[i][0] == '"' &&
        !strncmp(yytname[i] + 1, token_buffer, strlen(token_buffer)) &&
        yytname[i][strlen(token_buffer) + 1] == '"' &&
        yytname[i][strlen(token_buffer) + 2] == 0) {
        break;
    }
}

    当使用 %token-table 声明时才会生成 yytname 表。

  • Token 的语义值

    不可重入的解析器，所有语义值都存储在 yylval 中，如果使用单一语义值类型 (默认为 int)，可以用这种方式在 yylex 中使用

    1
2

    yylval = value;  // 将值压入 Bison 栈
return INT;           // 返回 token 类型

    当使用 %union 定义了多类型时，需要正确使用各个 union 字段。比如 union 如下定义

    1
2
3
4
5

    %union {
    int intval;
    doubal val;
    symrec *tptr;
}

    yylex 中需要如下使用

    1
2

    yylval.intval = value;
return INT;

  • Token 的文本位置

    如果在行为中使用 @N 功能来跟踪 token 和分组的文本位置，那么必须在 yylex 中提供此信息。但相对的，这会明显拖慢解析器的速度。

    通常情况下只需要正确处理 yylloc 的成员即可，其类型通常为 YYLTYPE，定义通常如下

    1
2
3
4
5
6

    typedef struct YYLTYPE {
    int first_line;
    int first_column;
    int last_line;
    int last_column;
} YYLTYPE;

  • 纯解析器的调用约定

    如果你用来可重入的解析器，那不能使用全局变量 yylloc 和 yylval，需要将这两个变量以参数的形式传递给 yylex。原型如下

    1

    int yylex(YYSTYPE *lvalp, YYLTYPE *llocp);

    如果没有使用位置参数的话，将不会定义 YYSTYPE，也就不需要由参数 lvalp 了。如果还需要其他参数，可以使用 %lex-param 来声明其他参数，用法和之前的 %parse-param 一样。如果想对 yyparse 和 yylex 都传入某个参数可以使用 %param。

每当 Bison 解析器读取不能满足任何语法规则的标记时，它就会检测到语法错误。语法中的行为也可以使用宏 YYERROR 显式声明错误。Bison 解析器希望通过调用名为 yyerror 的函数来报告错误，用户必须实现该函数。函数原型如下

1

void yyerror(char const *s);

在 yyerror 返回后，yyparse 还会尝试使用编写的错误恢复规则，如果无法恢复，yyparse 将返回 1。

当你使用纯解析器时 (%define api.pure full)，将会生成原型为

1

void yyerror(YYLTYPE *locp, char const *msg);

Bison 支持解析器的国际化 (i18n)，我想这是个我用不上的功能。Bison 采用的 i18n 方案是通用的 gettext。

Bison 在读取 token 时，会将 token 及其语义值一起推送到名为 parser stack 的栈上，而这个行为被称为移入。但不会总是移入，当最后 N 个元素与语法规则相匹配时，元素将会组合，这个步骤称为归约。当解析器通过移入与归约，直到将整个输入串归约成单个分组时，我们将剩下的这个符号称作开始符号。而解析器的整个操作是自下而上的。

就像之前的理论部分，解析器向前看一个符号，来确定下一个动作是什么。如果我们写下一个阶乘代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

expr:
  term '+' expr
| term
;

term:
  '(' expr ')'
| term '!'
| "number"
;

现在假设输入上的 1+2 已被读入并移入栈

  • 如果后面是 ) 那么栈顶的三个元素将被归约为 expr，这是唯一有效的操作，因为移入之后没有规则继续
  • 如果后面是 ! 那么会移入符号，以便 2! 可以归约成一项。如果在移入之前归约，那么将没有规则可以继续

可以通过 yychar 查看向前看符号。

经典的悬空 else 问题

1
2
3
4

if_stmt:
  "if" expr "then" stmt
| "if" expr "then" stmt "else" stmt
;

当 else 成为向前看符号时，移入规则有效，归约规则也有效，这就产生了一个移入规约冲突。但是 Bison 解析器更喜欢采用移入规则解决这种冲突。

悬空 else 问题往往的解决方式是，通常原则是 else 匹配最近的 if，那么下面这两行代码等价

1
2

if x then if y then win; else lose;
if x then do; if y then win; else lose; end;

如果选用归约规则，与通常原则将大相径庭。就是下面这两行例子

1
2

if x then if y then win; else lose;
if x then do; if y then win; end; else lose;

既然移入/归约冲突都是移入优先，那用之前介绍的 %expect N 可以吗？

警告
不建议使用 %expect N (除 %expect 0)，即使移入归约冲突的数量正确，不代表发生错误的原因是预期的

算数表达式中也经常出现移入归约冲突，但这里移入不总是首选。优先级则是处理这类问题的一种解决方法。

想想这段代码，

1
2
3
4
5
6
7

expr:
  expr '+' expr
| expr '*' expr
| expr '<' expr
| '(' expr ')'
| ...
;

遇到 1+2*5 和 1+1+1 时，移入归约冲突，此时应该怎么选择，这就是优先级和结合性的作用。至于定义已经在声明运算符优先级中介绍过了。

当然也可以使用优先级去解决悬空 else 问题。比如说，token ELSE 的优先级总是高于 token THEN，这样在悬空 else 问题上，每次都优先移入 else 而非归约。

1
2

%precedence THEN
%precedence ELSE

有个很奇怪的地方就是，往往优先级是上下文相关的。最直接的例子是一元 ‘-’ (负号) 与二元 ‘-’ (减号)，比如 C 语言的定义中，符号的优先级为 2 (越小越优先)，而乘号为 3，减号为 4。但是减号与负号的区别在于上下文的不同。另一个问题，Bison 中的优先级声明只能一 token 一次，这时就需要 %prec 修饰符在规则中进行修饰。

1

%prec TERMINAL-SYMBOL

首先在规则中声明这个上下文相关的符号为一个不存在的 (虚构的) token type，在声明部分声明这个 token type 的优先级。

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

...
%left '+' '-'
%left '*'
%right UMINUS

%%
expr:
  ...
| expr '-' expr
| ...
| '-' expr %prec UMINUS
| ...
;

如果有多个规则可以应用咋同一个输入上，会发生归约归约冲突，通常这是严重的语法错误。比如下面这个示例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

sequence:
  %empty         { printf ("empty sequence\n"); }
| maybeword
| sequence word  { printf ("added word %s\n", $2); }
;

maybeword:
  %empty    { printf ("empty maybeword\n"); }
| word      { printf ("single word %s\n", $1); }
;

比如现在栈顶是 word，word 可以被归约为 maybeword，也可以被归约为 sequence。Bison 会选择首先出现在语法中的规则进行归约，但这可能超出编码预期，因此尽量不要依赖这种方式，而是选择消除所有的归约归约冲突。比如将 sequence 修改为

1
2
3
4

sequence:
  %empty         { printf ("empty sequence\n"); }
| sequence word  { printf ("added word %s\n", $2); }
;

当然有可能有其他方式产生归约归约冲突，比如下面这个例子。虽然每个规则独立看是没有问题的，但三个规则放在一起将产生错误：空输入可以被无限多种方式解析。

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

sequence:
  %empty
| sequence words
| sequence redirects
;

words:
  %empty
| words word
;

redirects:
  %empty
| redirects redirect
;

稍加修改，你会得到一个看起来不错的方法，空输入再也不会产生冲突了。

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

sequence:
  %empty
| sequence words
| sequence redirects
;

words:
  word
| words word
;

redirects:
  redirect
| redirects redirect
;

但是，如果输入为 “word word”，很明显可以被归约 words words 或 words，这有一个二义性的移入归约冲突，第二个 word 是移入还是将栈中的 word 归约。

可以用优先级解决这个问题

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

%precedence "word"
%precedence "sequence"
%%
sequence:
  %empty
| sequence word      %prec "sequence"
| sequence redirect  %prec "sequence"
;

words:
  word
| words "word"
;

当然结合性也能解决这个问题

1
2
3
4
5
6
7

%right "word" "redirect"
%%
sequence:
  %empty
| sequence word      %prec "word"
| sequence redirect  %prec "redirect"
;

有些归约归约冲突看起来根本没什么依据。这在 info 中称为 神秘 (Mysterious) 冲突。比如

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def: param_spec return_spec ',';
param_spec:
  type
| name_list ':' type
;

return_spec:
  type
| name ':' type
;

type: "id";

name: "id";
name_list:
  name
| name ',' name_list
;

这个文法是一个 LR(1) 文法，从 param_spec 开始，如果 id 后面是一个 ‘:’ 或 ‘,’ 它将被归约为 name，如果后面是一个 id 则被归约为 type。但是问题在于这不是一个 LALR(1) 文法，看起来 param_spec 和 return_spec 太像了，以至于 Bison 无法处理。

对于许多语法 (特别是非 LR(1) 语法)，LALR(1) 的局限性造成了各种问题，因此最直接的解决方法是构造不那么高效的规范 LR(1) 分析表或 IELR(1) 分析表。

信息
从 GNU Bison 3.1 开始 LR(LR,LALR,IELR) 分析表不再是实验性功能

如果只用 LALR(1) 解决这个问题，你可以添加一些东西，让这两个生成体不那么相同。以此来解决这个问题。

1
2
3
4
5

return_spec:
  type
| name ':' type
| "id" "bogus"  /* This rule is never used. */
;

很明显，yylex 不能解析出一个 bogus 的 token。在这个示例中，更好的解决方法是

1
2
3
4

return_spec:
  type
| "id" ':' type
;

构造 LR 解析器是因为历史原因的选择，现代化的 Bison 给出了一些更好的选择。

  • LR 表构建

    只要修改一下下声明，就可以从历史遗留的 LALR(1) 分析表切换到 IELR 或 canonical LR 分析表。当然，主要是由于 LALR(1) 文法不够强大，不能完全解析 LR(1) 文法。有些需要复杂重构的 LALR 文法，或许在切换到 LR(1) 文法后，就可以完全消除冲突。

    先说说怎么指定不同的分析表。

    1

    %define lr.type TYPE

    可选值如下

    • lalr (default)
    • ielr
    • canonical-lr

    当然每种 LR 分析表都有其特点，在龙书中也详细讲了 Canonical LR 与 LALR，至于 IELR 以后有机会好好学习一下。在通常情况下，IELR 都可以应对，但某些情况下 LALR 或规范 LR 可能会很有用。

    LALR : 至少这两种情况下非常推荐使用 - 没有静态解决冲突的 GLR。开始静态解决冲突时，GLR 的行为更像是确定性解析器。 - 格式错误的语法 (Malformed grammars)。在一些含有重大缺陷的复杂语法上，可能会阻碍 IELR 和 Canonical LR 构造算法。因此 LALR 分析表可以快速构造并检查错误，同时忽略 IELR 和 Canonical LR 的细微差别。

    IELR : 这是一种最小 LR 算法，给定任何语法，IELR 和 Canonical LR 解析器总是接受相同的集合。通常 IELR 比 Canonical LR 的状态少一个数量级，而冲突数量往往也少一个数量级。这可以显著降低语法开发的复杂性。

    Canonical LR : 在不使用 %nonassoc 和禁用默认归约行为时，规范 LR 可以尽快检测出语法错误，且不需要执行不必要的归约。但 IELR 在开启 LAC 的情况下可以没有限制的实现此效果。

    关于更多的 IELR 和 LALR 神秘冲突的内容，可以阅读 Denny 2008 March 和 Denny 2010 November。

  • 默认归约

    在构建好分析表后，Bison 使用每个解析器中设置的最大向前看值来进行归约。为了减少状态大小，Bison 默认删除该值，并使用默认解析器进行归约操作。这种行为被称为默认归约。默认归约不仅影响分析表的大小，还影响解析器的行为：

    • 延迟调用 yylex

      一致状态是只有一个可能的解析器操作。如果操作是归约且它被编码为默认归约，那么一致状态被称作默认状态。达到默认状态后，Bison 不会在执行归约操作之前调用 yylex。即当它在输入中达到该 token 时，或它需要前前看来决定下一个操作，此时调用 yylex。但默认开启默认归约时，将会改变解析器行为。yylex 的行为可能影响或受默认归约的影响。

    • 延迟检测语法错误

      当解析器获取新 token 时，会检查当前状态下是否有关于该 token 的操作。当且仅当

      1. 没有操作
      2. 操作时错误操作

      这时才会检测到语法错误。但启用默认归约时，条件一将不成立，因为每个 token 都有归约操作。解析器将不能直接检测出语法错误，而是会在之后的状态中检测到。

      虽然默认归约不会导致解析器接受含有错误语法的输入，但延迟检测语法可能导致意料之外的行为。另外延迟检测可能是由解析器合并，和使用 %nonassoc 引起的，这可以通过 LAC 进行修复。

    对于 Canonical LR，唯一开启默认归约的状态是接受状态，但是这不会引起上述的两个延迟问题 (毕竟直接结束了，不再需要检测错误或找下一个 token 了)。

    对于 IELR 和 LALR，默认对所有状态启用默认归约。除了

    • 对错误 token 只有移入没有归约
    • GLR 解析器不会为存在冲突的向前看 token 设置默认规约

    如果想修改 Bison 的默认行为，可以声明

    1

    %define lr.default-reduction WHERE
    • most (default for LALR and IELR)
    • consistent
    • accepting (default for canonical LR)

  • LAC

    信息 
    从 GNU Bison **3.5** 开始 lookahead correction (C++) 不再是实验性功能

从 GNU Bison **3.8** 开始 lookahead correction (Java) 不再是实验性功能

    解析器在发现语法错误前可能进行额外的规约，这些规约可能执行不符合预期的语义操作，并且可能导致错误恢复发生在其他文法上下文中。这个问题的根源通常是 %nonassoc、不一致状态下的默认规约以及 GLR 解析器合并。因此主要影响的是 IELR 和 LALR 解析器。

    LAC (前瞻校正) 是一种解析的新机制，可以在不牺牲 %nonassoc 和默认规约或状态合并的功能的前提下，解决这个问题。只需要定义

    1

    %define parse.lac VALUE
    • none (default)
    • full

    使用 LAC 时需要考虑一些注意事项：

    • 无限的解析循环

      IELR + LAC 的组合相对 Canonical LR 有一个缺点，即 Bison 可能生成一个无限循环的解析器，LAC 不会修复在遇到语法错误和检测到它之间发生的无限循环。

    • 详细错误消息限制

      一些 i18n 方面的考虑，Bison 限制了在错误消息中报告 token 列表的大小。超出限制时会简单的删除。但 LAC 会增加列表的大小。

    • 性能

      LAC 需要两次执行多解析行为，因此可能造成性能降低。但也不是所有解析操作都要执行两次。对于解析来说，最耗时的往往是文件 IO、词法分析器以及用户的语义行为，但这些不是在探索性解析期间执行的。并且探索性解析的堆栈直接指向正式堆栈，从而不会造成复制。因此，从经验来看，LAC 的性能损耗可以忽略不计。

    对于 LAC 的更多内容，可以查看 Denny 2010 May。

  • 不可达状态

    如果不存在从解析器的起始状态到某个状态 S 的转换序列，则 Bison 认为 S 是不可达状态。如果 Bison 禁用从前一个状态到该状态的转换操作，则该状态可能在冲突解决期间变得无法访问。

    默认情况下，Bison 会在冲突解决后从解析器中删除无法访问的状态，因为它们在生成的解析器中是无用的。然而，当试图理解解析器和语法之间的关系时，保留不可达状态有时很有用。

    1

    %define lr.keep-unreachable-state VALUE  // false (defaule) or true

    但需要考虑一下问题：

    • 缺少或无关的警告

      不可达状态可能包含冲突，且可能使用在任何其他状态中未使用的规则。因此保留不可打状态可能引起解析器行为无关的警告，并可能消除相关警告。

    • 其他无用的状态

      虽然 Bison 能够移除无法到达的状态，但不能保证移除其他类型的无用状态。举例就是，当 Bison 在冲突解决期间禁用规约操作时，一些 goto 操作可能变得无用，因此一些附加状态可能变得无用。如果 Bison 要计算哪些 goto 操作是无用的，然后禁用这些操作，它可以将这些状态识别为不可达，然后删除这些状态。但是，Bison 不会计算哪些 goto 操作是无用的。

信息
本节学习自 北大编译实践

sysy 采用扩展 Backus 范式 (EBNF)，CompUnit 作为开始符号。当然除了函数定义还有变量声明，但是现在我们跟着北大编译实践来学习，目前只处理 main 函数

CompUnit ::= FuncDef;

FuncDef ::= FuncType Ident ‘(’ ‘)’ Block;
FuncType ::= int;

Block ::= ‘{’ Stmt ‘}’;
Stmt ::= return Number ‘;’ ;
Number ::= INT_CONST;

根据这个我们先写一个 flex 词法分析文件 sysy.l

 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
31
32
33
34
35
36
37
38
39
40
41
42
43

%option noyywrap nodefault noinput nounput noyy_top_state stack
%top{
#include "sysy.tab.hh"

#include <stdlib.h>

#include <string>
}

WhiteSpace     [[:space:]]*
LineComment    "//".*$

Identifier     [[:alpha:]_][[:alnum:]_]*

Decimal        [1-9][[:digit:]]*
Octal          0[0-7]*
Hexadecimal    0[xX][[:xdigit:]]+
Binarydecimal  0[bB][01]+

%x COMMENT

%%

{LineComment}    { /* ignore */ }
"/*"             { yy_push_state(COMMENT); }
<COMMENT>.|\n    { /* ignore */ }
<COMMENT>"*/"    { yy_pop_state(); }

{WhiteSpace}     { /* ignore */ }

"int"            { return INT; }
"return"         { return RETURN; }

{Identifier}     { yylval.ident = new ::std::string(yytext); return IDENTIFIER; }

{Decimal}        { yylval.int_val = strtol(yytext, nullptr, 10); return INT_CONST; }
{Octal}          { yylval.int_val = strtol(yytext, nullptr, 8); return INT_CONST; }
{Hexadecimal}    { yylval.int_val = strtol(yytext, nullptr, 16); return INT_CONST; }
{Binarydecimal}  { yylval.int_val = strtol(yytext + 2, nullptr, 2); return INT_CONST; }

.                { return yytext[0]; }

%%

简单解释一下，词法分析器将忽略所有的行注释、块注释以及空白符，并且会将得到的标识符名称存入 idnet 中，解析到的整型变量存入 int_val 中。

既然有了词法分析器，我们还需要在在语法分析器中描述 sysy 的语法，即 sysy.y

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

%code requires {
#include <memory>
#include <string>
}

%code {
#include <iostream>

extern int yylex(void);

void yyerror(::std::unique_ptr<::std::string const> &ast, char const *s);
}

%parse-param { ::std::unique_ptr<::std::string const> &ast }

%union {
  ::std::string const *ident;
  int int_val;
}

%token INT RETURN
%token <ident> IDENTIFIER
%token <int_val> INT_CONST

%type <ident> FuncDef FuncType Block Stmt Number CompUnit

%%

CompUnit:
  FuncDef {
      ast = ::std::unique_ptr<::std::string const>($1);
      }
;

FuncDef:
  FuncType IDENTIFIER '(' ')' Block {
    auto type = ::std::unique_ptr<::std::string const>($1);
    auto ident = ::std::unique_ptr<::std::string const>($2);
    auto block = ::std::unique_ptr<::std::string const>($5);
    $$ = new ::std::string(*type + " " + *ident + "()" + *block);
  }
;

FuncType:
  INT { $$ = new ::std::string("int"); }
;

Block:
  '{' Stmt '}' {
    auto stmt = ::std::unique_ptr<::std::string const>($2);
    $$ = new ::std::string("{ " + *stmt + " }");
  }
;

Stmt:
  RETURN Number ';' {
    auto number = ::std::unique_ptr<::std::string const>($2);
    $$ = new ::std::string("return " + *number + ";");
  }
;

Number:
  INT_CONST { $$ = new ::std::string(::std::to_string($1)); }
;

%%

void yyerror(::std::unique_ptr<::std::string const> &ast, const char *s) {
  ::std::cerr << "error: " << s << ::std::endl;
}

很明显语法分析器中，这个语法分析可以很好得解析我们在本节开始声明的 EBNF 文法，也就是 main 函数。需要注意的是，这里不能使用 ::std::make_unique，因为其只能移动或者从参数构建智能指针，但我们的非终结符语义值都是用 new 构建好的指针 (非 POD 类型不能作为 union 成员)，因此我们需要用构造函数来构造 ::std::unique_ptr，将之前构造的指针所有权移交给智能指针。

虽然词法分析与语法分析出来了，我们还要自己编写一个主文件

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <stdio.h>

#include <iostream>
#include <memory>
#include <string>

extern FILE *yyin;
extern int yylex_destroy(void);
extern int yyparse(::std::unique_ptr<::std::string> &ast);

int main(int /* argc */, char const *argv[]) {
  auto input = argv[1];
  yyin = fopen(input, "r");

  ::std::unique_ptr<::std::string> ast;
  static_cast<void>(yyparse(ast));
  ::std::cout << *ast << ::std::endl;

  fclose(yyin);
  yylex_destroy();
}

主文件需要注意，在最后关闭 yyin 是必要操作，不然会造成资源泄漏 (虽然程序立即结束，操作系统会回收资源)。还有就是 yylex_destroy 必须在 fclose 之后关闭，否则会造成 crash。如果有兴趣可以自己写一个 deferer，然后做 RAII，保证资源的正确释放。

最后，写一个 CMake 就大功告成

 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
31
32
33
34
35
36

cmake_minimum_required(VERSION 3.5)
project(sysyc LANGUAGES CXX)

set(CMAKE_CXX_STANDARD 17)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_EXTENSIONS OFF)

if(NOT CMAKE_BUILD_TYPE)
  set(CMAKE_BUILD_TYPE "Debug")
  set(CMAKE_EXPORT_COMPILE_COMMANDS ON)
endif()

find_package(FLEX REQUIRED)
find_package(BISON REQUIRED)

file(GLOB_RECURSE L_SOURCES "src/*.l")
file(GLOB_RECURSE Y_SOURCES "src/*.y")
if(NOT (L_SOURCES STREQUAL "" AND Y_SOURCES STREQUAL ""))
  string(REGEX REPLACE ".*/(.*)\\.l" "${CMAKE_CURRENT_BINARY_DIR}/\\1.lex.cc" L_OUTPUTS "${L_SOURCES}")
  string(REGEX REPLACE ".*/(.*)\\.y" "${CMAKE_CURRENT_BINARY_DIR}/\\1.tab.cc" Y_OUTPUTS "${Y_SOURCES}")
  flex_target(Lexer ${L_SOURCES} ${L_OUTPUTS})
  bison_target(Parser ${Y_SOURCES} ${Y_OUTPUTS})
  add_flex_bison_dependency(Lexer Parser)
endif()

add_executable(${PROJECT_NAME}
  ${FLEX_Lexer_OUTPUTS}
  ${BISON_Parser_OUTPUT_SOURCE}
  ${CMAKE_CURRENT_SOURCE_DIR}/main.cc
  )
target_include_directories(${PROJECT_NAME} PRIVATE
  ${CMAKE_CURRENT_SOURCE_DIR}/include
  ${CMAKE_CURRENT_BINARY_DIR}
  )
target_sources(${PROJECT_NAME} PRIVATE
  )

非常完美，我们编写了一个能解析主函数的最简单的编译器，并且没有任何资源泄漏。现在让我们从编译到运行

1
2
3

cmake -S. -Bcmake_build_debug -DCMAKE_BUILD_TYPE=Debug
cd cmake_build_debug/ && make -j
./sysyc main.sy
更新于 05-22
阅读原始文档 | 报告问题
 Applications, SyntacticAnalysis, LexicalAnalysis
返回 | 主页