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 ;