乐者为王

Do one thing, and do it well.

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

编程语言在词法上看起来惊人地相似,无论是函数式、过程式、声明式还是面向对象语言,看起来几乎都是一样的。这很棒,因为我们只需要学习一次如何描述标志符和整数,没有太大的变化,就可以把它们应用到大多数编程语言上。正如语法分析器以及词法分析器使用规则去描述各种语言构造体一样,我们要使用基本相同的表示法。唯一的区别是语法分析器识别在记号流中的语法结构,而词法分析器识别在字符流中的语法结构。

因为词法分析和语法分析有相似的结构,ANTLR允许我们把两者合并在单个语法文件中。但是因为词法分析和语法分析是语言识别的两个不同阶段,我们必须告诉ANTLR每个规则是和哪个阶段相关联的。我们可以通过以大写字母开始的词法规则名字和以小写字母开始的语法规则名字做到这点。例如,ID是一个词法规则名字,expr则是一个语法规则名字。

当开始构建一个新的语法时,对于那些常用的词法构造体:标志符、数字、字符串、注释以及空格等,我们可以从已经存在的语法中拷贝粘贴规则。然后,通过一些细微的调整,就可以让它运行起来。几乎所有的语言,甚至像JSON和XML这样的非编程语言,都有这些记号的变体。例如,C语言的词法分析器完全可以标记化以下的JSON代码:

1
2
3
4
{
  "title":"Cat wrestling",
  "chapters":[ {"Intro":"..."}, ... ]
}

另一个例子就是块注释。在C语言中,它们是被/* ... */括起来的。而在XML里,注释是被<!-- ... -->括起来的。但它们除了开始和结束符号之外,或多或少都有相同的词法构造。

对于关键字、运算符和标点符号,我们不需要词法规则,因为我们可以在语法分析规则中直接引用它们,用单引号括起来,就像'while''*''++'这样。有些开发者更喜欢使用像MUL而不是字面量'*'这样的词法规则引用,这些都没问题,因为它们都有相同的记号类型。

为了阐明词法规则看起来像什么,让我们从标志符开始构建一个常用记号的简单版本。

匹配标志符

在语法伪代码中,一个基本的标志符是由大写或小写字母组成的一个非空序列。根据已经学习到的知识,我们知道需要用(...)+表示法来表示这样的序列模式。因为序列元素可以是大写或小写字母,所以在子规则中我们需要使用选择运算符:

1
ID : ('a'..'z'|'A'..'Z')+ ;    // 匹配一个或多个大小写字母

唯一的新ANTLR表示法是范围运算符:'a'..'z'代表从a到z的任意字符。或者你也可以使用Unicode码位字面量'\uXXXX',这里的XXXX是Unicode字符码位值的十六进制值。

作为字符集的一个简写,ANTLR支持我们使用更熟悉的正则表达式集合表示法:

1
ID : [a-zA-Z]+ ;    // 匹配一个或多个大小写字母

有时候我们会发现像下面这样的语法貌似存在冲突的现象:

1
2
3
enumDef : 'enum' '{' ... '}' ;
FOR : 'for' ;
ID : [a-zA-Z]+ ;    // 不匹配'enum'或者'for'

规则ID也可以同时匹配enum和for这样的关键字,这意味着同样的字符串能被多个规则匹配。但事实上,ANTLR处理这种混合语法时会把字符串字面量以及词法规则与语法规则分隔开,像enum这样的字面量就变成了词法规则并紧随在语法规则之后和在显式的词法规则之前。

ANTLR词法分析器通过偏爱首先指定的规则来解决词法规则间的二义性,这意味着ID规则应该定义在所有的关键字规则之后。ANTLR把隐式的为字面量生成的词法规则放在显式的词法规则之前,因此它们总是有更高的优先级。在这里,'enum'被自动赋予比ID高的优先级。

因为ANTLR总是会重新排序词法规则并让它们在语法规则之后发生。所以上面的语法与下面的变体是相同的:

1
2
3
FOR : 'for' ;
ID : [a-zA-Z]+ ;    // 不匹配'enum'或者'for'
enumDef : 'enum' '{' ... '}' ;

匹配数字

描述像10这样的整型数字非常容易,因为它只是一个数字序列。

1
INT : '0'..'9'+ ;    // 匹配一个或多个数字

或者

1
INT : [0..9]+ ;    // 匹配一个或多个数字

浮点数要复杂的多,但如果我们忽略指数的话,可以很容易地制作一个简化版本。浮点数是数字序列后面跟着一个句点和一个可选的小数部分;或者以一个句点开始,然后是数字序列。单独一个句点是不合法的。因此我们的浮点规则使用一个选择和一些序列模式:

1
2
3
4
5
6
FLOAT: DIGIT+ '.' DIGIT*    // 匹配1. 39. 3.14159等等
     | '.' DIGIT+           // 匹配.1 .14159
     ;

fragment
DIGIT: [0-9] ;              // 匹配单个数字

这里我们使用了一个帮助规则DIGIT,因此我们不必到处去写[0-9]。通过在规则前面加上fragment前缀,我们让ANTLR知道该规则仅被其它词法规则使用。它本身不是一个记号,这意味着我们不能在语法规则中引用它。

匹配字符串字面量

计算机语言中共同具有的下一个常用记号是字符串字面量,例如"hello"。大部分使用双引号作分隔符,有些使用单引号或者两者都使用。以双引号为分隔符而言,在语法伪代码中,一个字符串就是在双引号中的任意字符序列:

1
STRING : '"' .*? '"' ;    // 匹配在双引号中的任意字符

语法中的点是通配符运算符,它可以匹配任意单个字符。因此,“.*”是一个能够匹配任意零个或多个字符的序列的循环。当然,它也将消费字符直到文件结尾,所以不是很有用。幸运的是,ANTLR通过正则表达式表示法(?后缀)提供对非贪婪模式规则的支持。非贪婪模式意味着“直到看见在词法规则中跟在子规则后的字符时才停止吃掉字符”。更确切地说,非贪婪模式规则匹配最小数量的字符,同时仍然允许整个周围的规则被匹配。相反,“.*”被认为是贪婪模式,因为它贪婪地消费能够匹配循环内部的所有字符。

以上的STRING规则做得还不够好,因为它不允许字符串中有双引号。为了做到这点,大部分语言定义了以反斜杠开始的转义字符。在字符串中的双引号我们可以使用“\"”。为支持常用的转义字符,我们需要使用以下规则:

1
2
3
4
STRING: '"' (ESC|.)*? '"' ;

fragment
ESC : '\\"' | '\\\\' ;    // 匹配字符\"和\\

ANTLR自身也需要避开转义字符,所以这里我们需要用“\”去指定反斜杠字符。

现在,在STRING规则中的循环既可以通过调用fragment规则ESC去匹配转义字符序列,也可以通过点通配符去匹配任意字符。当看到一个非转义双引号字符时,“*?”子规则运算符终止“(ESC|.)*?”循环。

匹配注释和空格

词法分析器会把匹配到的记号通过记号流传递给语法分析器,然后语法分析器检查流的语法结构。但我们希望当词法分析器匹配到注释和空格时能把它们扔掉。那样,语法分析器就不必为匹配无处不在的可选的注释和空格担心。例如,当WS是一个空格的词法规则时以下的语法规则就非常尴尬和容易出错:

1
assign : ID (WS|COMMENT)? '=' (WS|COMMENT)? expr (WS|COMMENT)? ;

定义这些被丢弃的记号和定义非丢弃的记号一样,我们只需要使用skip指令去表明词法分析器应该扔掉它们。以下是匹配那些衍生自C的语言的单行和多行注释的语法规则:

1
2
LINE_COMMENT : '//' .*? '\r'? '\n' -> skip ;    // 匹配"//" stuff '\n'
COMMENT      : '/*' .*? '*/'       -> skip ;    // 匹配"/*" stuff "*/"

在COMMENT中,“.*?”消费在“/*”和“*/”之间的任意字符。在LINE_COMMENT中,“.*?”消费“//”之后的任意字符,直到它看到一个换行符。

词法分析器接受若干跟随在->运算符后的指令,skip只是它们中的一个。例如,我们可以通过使用channel指令把传递给语法分析器的记号放进隐藏通道。

最后,让我们处理空格(换行符等也被当作空格)这个常用记号。大部分编程语言都把空格当作记号分隔符,但是另一方面又忽略它们。(Python是个例外,因为它把空格用作特殊语法目的:终止命令和缩进级别的换行符。)以下是告诉ANTLR如何扔掉空格的语法:

1
WS : (' '|'\t'|'\r'|'\n')+ -> skip ;    // 匹配一个或多个空格但丢弃

或者

1
WS : [ \t\r\n]+ -> skip ;    // 匹配一个或多个空格但丢弃

当换行符既是要被忽略的空格又是命令终结符时,就会有个问题。换行符是上下文有关的,在语法上下文中,我们要扔掉换行符,但在其它地方,我们需要把它传递给语法分析器以便让它知道某个命令已经结束。例如,在Python中,后面有换行符的f()会执行代码,调用f()方法,但是如果我们在括号中也插入一个额外的换行符,Python就会在执行调用前等待直到右括号后面的换行符为止。

Comments