乐者为王

Do one thing, and do it well.

ANTLR 4权威参考读书笔记(10)

一个模棱两可的短语或句子通常是指它有不止一种解释。换句话说,短语或句子能匹配不止一种语法结构。要解释或转换一个短语,程序必须要能唯一地确认它的含义,这意味着我们必须提供无歧义的语法,以便生成的语法分析器能用明确的一个方法匹配每个输入短语。

在这里,让我们展示一些有歧义的语法以便让二义性的概念更具体。如果你以后在构建语法时陷入二义性,你可以参考本节的内容。

一些明显有歧义的语法:

1
2
3
4
5
6
7
assign
    : ID '=' expr    // 匹配一个赋值语句,例如f()
    | ID '=' expr    // 前面选项的精确复制
    ;

expr
    : INT ;

大多数时候二义性是不明显的,就像下面的语法,它能通过规则stat的两个选项匹配函数调用:

1
2
3
4
5
6
7
8
9
stat
    : expr          // 表达式语句
    | ID '(' ')'    // 函数调用语句
    ;

expr
    : ID '(' ')'
    | INT
    ;

这里是输入f()的两个解释,从规则stat开始:

左边的语法分析树显示f()匹配规则expr。右边的语法分析树显示f()匹配规则stat的第二个选项。

因为大部分语言它们的语法都被设计成无歧义的,有歧义的语法类似于编程缺陷,所以我们需要识别语法并为每个输入短语提交单一选择给语法分析器。如果语法分析器发现一个有歧义的短语,它必须选一个可行的选项。ANTLR通过选择涉及决定的第一个选项解决二义性。在本例中,语法分析器将选择与左边的语法分析树有关的f()的解释。

二义性可以发生在词法分析器中也能发生在语法分析器中,但ANTLR可以自动地解决它们。ANTLR通过使输入字符串和语法中第一个指定的词法规则匹配来解决词法二义性。为了明白这是如何工作的,让我们看看对大部分编程语言都很普遍的二义性:在关键字和标志符规则中的二义性。关键字begin(后面有个非字母)也是标志符,至少词法上,因此词法分析器可以匹配b-e-g-i-n到两者中的任何一个规则。

1
2
BEGIN : 'begin' ;    // 匹配b-e-g-i-n序列,即把二义性解析为BEGIN
ID    : [a-z]+ ;     // 匹配一个或多个任意小写字母

注意,词法分析器会试着为每个记号尽可能匹配最长的字符串,这意味着输入beginner将仅仅匹配规则ID。词法分析器不会把beginner匹配成BEGIN然后ID匹配输入ner。

有时候语言的语法就明显有歧义,没有任何的语法重组能改变这个事实。例如,算术表达式的自然语法可以用两种方式解释像1+2*3这样的输入,要么从左到右执行运算符,要么像大部分语言那样按优先级顺序。

C语言展示了另一种二义性,但我们可以使用上下文信息比如标志符如何被定义来解决它。考虑代码片段i*j;。在语法上,它看起来像是一个表达式,但它的含义或者语义依赖i是类型名还是变量。如果i是类型名,那么这个片段不是表达式,而是一个声明为指向类型i的指针变量j。

Comments