《ANTLR 4权威指南》笔记5 - 设计语法

4种语言模式：

• sequence 序列
• choice 选择
• token dependency 依赖
• nested phrase 嵌套短语

要实现这几种模式，只需要3种语法规则 （BNF ）：

• alternatives
• token references
• rule references

为了方便起见，将这些元素组合成?、*、+子规则（EBNF)

5.1 从示例语言推导出语法⌗

grammar MyG;

rule1 : <start rule> ;
rule2 : <more stuff> ;
...

top-down语法规则，从粗粒度到细粒度。

例子，CSV：

file: row+ ;
row: field+ ;
field: number | string ;

例子，Java：

compilationUnit : «optional packageSpec then classDefinitions» ;

packageSpec : 'package' identifier ';' ;

classDefinition :
    'class' «optional superclassSpec optional implementsClause classBody» ;

superclassSpec : 'super' identifier ;

implementsClause :
    'implements' «one or more identifiers separated by comma» ;

classBody : '{' «zero-or-more members» '}' ;

member : «nested classDefinition or field or method» ;
...

5.2 使用已有语法⌗

5.3 用ANTLR语法识别常用语言模式⌗

Sequence模式⌗

最简单常用的模式，一系列连续的元素

比如，POP协议语法：

USER parrt
PASS secret
RETR 1

语法描述：

retr : 'RETR' INT '\n' ;

可以包括任意简单的字符序列，比如'RETR'、'\n'。语法中的其他地方可以用retr来引用。

子规则：

(INT)+  // 出现1次或更多
(INT)*    // 出现0次或更多
('=' expr)?    // 出现0次或1次
('=' expr |) // 与?等价

比如，CSV语法：

file : (row '\n')* ; // sequence with a '\n' terminator
row : field (',' field)* ; // sequence with a ',' separator
field: INT ; // assume fields are just integers

其他例子：

stats : (stat ';')* ; // match zero or more ';'-terminated statements
exprList : expr (',' expr)* ;
rule : ID ':' alternative ('|' alternative )* ';' ;

Choice（alternatives）模式⌗

“或”规则用 | 符号表示。

field: INT | STRING ;
type: 'float' | 'int' | 'void' ;
stmt: node_stmt
    | edge_stmt
    | attr_stmt
    | id '=' id
    | subgraph
    ;

Token dependency模式⌗

成对的symbol，比如()、[]和{}

a[(i)]
{while(b){i=1}}

例子：

vector: '[' INT+ ']' ;

例子，表达式：

expr: expr '()' exprList? ')'  // function call f(), f(x), f(1,2)
    | expr '[' expr ']'        // array index a[i]
    ...
    ;

例子，函数定义：

functionDecl
    : type ID '(' formalParameters? ')' block // "void f(int x) {...}"
    ;
formalParameters
    : formalParameter (',' formalParameter)*
    ;
formalParameter
    : type ID
    ;

例子，JSON：

object
    : '{' pair (',' pair)* '}'
    | '{' '}'
    ;
pair: STRING ':' value ;

有些符号不是依赖的，比如a?b:c三目运算符。

Nested phrase模式⌗

嵌套短语有自相似的语言结构，递归规则。

比如while语句，直接递归：

stat : 'while' '(' expr ')' stat
    | '{' stat* '}'
    ...
    ;

间接递归：

stat: 'while' '(' expr ')' stat
    | block
    ...
    ;
block: '{' stat* '}' ;

ANTLR核心语法符号⌗

文法	描述
x	匹配token，规则引用或子规则x
x y … z	匹配一系列的规则
(…|…|…)	多种可能，或
x?	出现0次或1次
x*	出现0次或更多
x+	出现1次或更多
r: …;	定义规则r
r: …|…|…;	定义规则r，有多种可能

语法总结⌗

Sequence

x y z
'[' INT+ ']'

Sequence with terminator

(statement ';')*
(row '\n')*

Sequence with separator

expr (',' expr)*
(expr (',' expr)* )?
'./'? name ('/' name)*
stat ('.' stat)*

Choice

type: 'int' | 'float' ;
stat: ifstat | whilestat | 'return' expr ';' ;
expr: '(' expr ')' | INT | ID ;
tag: '<' Name attribute* '>' | '<' '/' Name '>' ;

Token dependency

'(' expr ')' // nested expression
ID '[' expr ']' // array index
'{' stat* '}' // statements grouped in curlies
'<' ID (',' ID)* '>' // generic type specifier

Nested phrase

expr : '(' expr ')' | ID ;
classDef : 'class' ID '{' (classDef|method|field) '}' ;

5.4 处理优先级、左递归、结合方式⌗

优先级⌗

expr : expr '^'<assoc=right> expr // ^ operator is right associative
    | expr '*' expr // match subexpressions joined with '*' operator
    | expr '+' expr // match subexpressions joined with '+' operator
    | INT // matches simple integer atom
    ;

左递归⌗

自顶向下语法和解析器在普通情况下无法处理左递归。ANTLR3无法处理左递归，ANTLR4可以处理直接左递归，但依然无法处理间接左递归。

例子，ANTLR4可以处理的情况：

expr: expr '+' expr ;

decl : decl '[' ']' // match [] suffixes using direct left-recursion
    | '*' decl // *x, *x[], **x
    | '(' decl ')' // (x), (x[]), (*x)[]
    | ID
    ;

使用ANTLR3要手工解决左递归：

expr : addExpr ;
addExpr : multExpr ('+' multExpr)* ;
multExpr: atom ('*' atom)* ;
atom : INT ;

例子，ANTLR4无法处理的情况：

expr: expo 
    | ...
    ;
expo: expr '^'<assoc=right> expr ;

结合方式⌗

expr: expr '^'<assoc=right> expr
    | INT
    ;

5.5 识别常见词法结构⌗

词法规则名称用大写开头，一般全大写。比如ID是词法规则，expr是语法规则。

许多词法规则是通用的，标识符、数字、字符串、注释、空格等。

关键字、运算符、标点符号不需要词法分析规则，可以直接写在语法规则里，比如'while'、'*'、'++'。

例子：C语言的词法分析器可以识别JSON

{"title":"Cat wrestling","chapters":[ {"Intro":"..."}, ... ]}

例子：Java的块注释/*...*/和XML的注释<!--...-->只相差开始和结束符号

匹配标识符⌗

ID : [a-zA-Z]+ ; // Unicode需要用\uXXXX

问题：如果词法分析和语法分析有冲突，比如enum可以是关键字也可以是词法单元：

grammar KeywordTest;
enumDef : 'enum' '{' ... '}' ;
...
FOR : 'for' ;
...
ID : [a-zA-Z]+ ; // does NOT match 'enum' or 'for

ANTLR会将语法规则中的字符串常量分离出来作为词法规则，直接跟在语法规则后面，并且在用户定义的词法规则之前，所以会优先匹配！

grammar KeywordTestReordered;
FOR : 'for' ;
ID : [a-zA-Z]+ ; // does NOT match 'enum' or 'for'
...
enumDef : 'enum' '{' ... '}' ;
...

ANTLR会重新排列规则，词法规则总是在语法规则之后！

匹配数字⌗

INT : [0-9]+ ; // match 1 or more digits
FLOAT: DIGIT+ '.' DIGIT* // match 1. 39. 3.14159 etc...
    | '.' DIGIT+ // match .1 .14159
    ;
fragment
DIGIT : [0-9] ; // match single digit

其中DIGIT是辅助规则，fragment表示这条规则只会被其他此法规则使用，而不是token，所以不能在语法规则中引用。

匹配字符串常量⌗

例如"hello"

STRING : '"' .*? '"' ;

正则表达式.*匹配任意多个字符，使用贪心策略，后面加上?表示非贪心策略。

字符串中双引号需要转义，

STRING: '"' (ESC|.)*? '"' ;
fragment ESC : '\\' [btnr"\\] ;

匹配注释空格⌗

LINE_COMMENT : '//' .*? '\r'? '\n' -> skip ;
COMMENT : '/*' .*? '*/' -> skip ;
WS : [ \t\r\n]+ -> skip ;

词法规则总结⌗

标点符号：

call: ID '(' exprList ')' ;
// or
call : ID LP exprList RP ;
LP : '(' ;
RP : ')' ;

5.6 词法分析和语法分析的界线⌗

日志文件：

192.168.209.85 "GET /download/foo.html HTTP/1.0" 200

语法用来记录行数：

file : NL+ ;
STUFF : ~'\n'+ -> skip ;
NL: '\n' ;

完整语法：

file: row+ ;
row: IP STRING INT NL ;

IP: INT '.' INT '.' INT '.' INT ; // 192.168.209.85
INT : [0-9]+ ;
STRING: '"' .*? '"' ;
NL:'\n' ;
WS:' ' -> skip ;