在语句结束时解析可选分号

Question

我正在编写一个解析器来解析类似C语法的语法.

首先,它现在可以解析代码:

a = 1;
b = 2;

现在我想在行尾添加分号可选.

最初的YACC规则是:

stmt: expr ';' { ... }

新行由我自己编写的词法分析器处理(代码简化):

rule(/\r\n|\r|\n/)          { increase_lineno(); return :PASS }

指令:此处的PASS相当于在LEX中不返回任何内容,它会删除当前匹配的文本并跳到下一个规则,就像通常使用空格一样.

因此,我不能简单地将我的YACC规则更改为:

stmt: expr end_of_stmt { ... }
;
end_of_stmt: ';'
    | '\n'
;

所以我选择相应地通过解析器动态地改变词法分析器的状态.

像这样:

stmt: expr { state = :STATEMENT_END } ';' { ... }

并添加一个lexer规则,可以将新行与新状态匹配:

rule(/\r\n|\r|\n/, :STATEMENT_END) { increase_lineno(); state = nil; return ';' }

这意味着当词法分析器处于以下状态时:STATEMENT_END状态.它将像往常一样首先增加行号,然后将状态设置为初始状态,然后假装自己是分号.

奇怪的是,它实际上不适用于以下代码:

a = 1
b = 2

我调试它并得到它实际上并没有得到';' 正如所期望的那样,在数字1之后扫描换行符,并且状态指定的规则并未真正执行.

并且设置新状态的代码在已经扫描新行并且没有返回任何内容之后执行,这意味着,这些工作按以下顺序完成:

1. 扫描a,=和1
2. 扫描换行符并跳过,因此获取下一个值 b
3. 插入的代码({ state = :STATEMENT_END })被执行
4. 提出错误 - b这里意外

这就是我的期望:

1. 扫描a,=和1
2. 发现它符合规则expr,所以减少到stmt
3. 执行插入的代码以设置新的词法分析器状态
4. 扫描换行符并;根据新的状态匹配规则返回
5. 继续扫描并解析以下行

在内省之后我发现可能由于YACC使用LALR(1)而引起,此解析器将首先读取一个令牌.当它扫描到那里时,状态尚未设置,因此无法获得正确的令牌.

我的问题是:如何使其按预期工作？我不知道这个.

谢谢.

Answer 1

要认识到的第一件事是,使用这样的可选行终止符会在您的语言中引入歧义,因此您首先需要确定要解决歧义的方式.在这种情况下,主要歧义来自可能是中缀或前缀的运算符.例如:

a = b
-c;

您是否希望将上述内容视为单个expr语句,或者将第一个分号排除在两个单独的语句之后？使用类似C语言的函数调用语法会出现类似的潜在歧义:

a = b
(c);

如果您希望将这些语句解析为两个语句,则可以使用您尝试过的方法; 你只需要提前设置一个令牌.这很棘手,因为如果你有未闭括号,你不想设置状态,所以你最终需要一个额外的状态var来记录paren嵌套深度,并且只设置insert-semi-before-newline状态,当它是0.

如果你想将上述情况作为一个陈述来解决,事情会变得棘手,因为你实际上需要更多的前瞻来决定换行何时应该结束一个陈述 - 至少你需要在换行符之后查看令牌(以及任何评论或其他被忽略的东西).在这种情况下,你可以让词法分析器做额外的前瞻.如果您使用flex(您显然不是？),我建议使用/运算符(直接查找),或者推迟返回分号,直到匹配下一个标记的词法分析器.

一般来说,在进行这种令牌状态记录时,我发现尽可能在词法分析器中完成它是最容易的,所以你不需要担心解析器有时(但不总是)完成前瞻性的额外令牌.在这种特定情况下,一个简单的方法是让词法分析器记录括号(+1表示(,-1表示)),并返回最后一个标记.然后,在换行规则中,如果paren级别为0且最后一个标记是可以结束表达式的内容(ID或常量或)仅后缀运算符),则返回额外的;

另一种方法是将词法分析器NEWLINE作为自己的标记返回.然后,您将更改解析器以接受stmt: expr NEWLINE语法中大多数其他令牌之间的可选换行符.这会将歧义直接暴露给解析器(它现在不是LALR(1)),所以你需要通过使用yacc的运算符优先级规则(棘手且容易出错)或使用bison的%glr-parser选项或btyacc的回溯能力来解决它.直接含糊不清.