4.1 Matching an Arithmetic Expression Language

本节的算术表达式仅考虑：

• 加减乘除 4 个操作符
• () 包裹的表达式
• 整数
• 变量

下面的例子展示了所有该算术表达式的所有特性：

193    
a = 5  
b = 6
a + b * 2
(1 + 2) * 3

我们的算术表达式语言写成的程序有一系列 statement 组成，statement 以 newline 结束，statement 可以是 expression, assignment, 或 blank line，下面是其语法：

grammar Expr;

// the start rule, begin parsing here
prog:  stat+ ;

stat:  expr NEWLINE
    |  ID '=' expr NEWLINE
    |  NEWLINE
    ;

expr:  expr ('*' | '/') expr
    |  expr ('+' | '-') expr
    |  INT
    |  ID
    |  '(' expr ')'
    ;

ID  :  [a-zA-Z]+ ;
INT :  [0-9]+ ;
NEWLINE: '\r' ? '\n' ;
WS  :  [ \t]+ -> skip ;

• grammar 是 rule 集合，rule 用来描述语言的 syntax，rule 分两类：
  • parser rule
    • 描述 syntactic structure
    • 小写字母开头，如 prog stat expr  + lexer rule
    • 描述 vocabulary symbols(token)
    • 大写字母开头，如 ID INT
• subrule: ()
• alternative rule: |

ANTLR v4 版重要特性为处理 left-recursive rule 的能力，left-recursive rule 是指在其 alternative rule 的 开头 递归调用自己的 rule，如 expr。传统的 top-down parser 处理左递归规则比较繁琐，ANTLR v4 非常容易。

注意 -> skip 指令，该指令告诉 lexer 匹配然后 丢弃 whitespace，因为每个输入字符都必须被 至少一个 lexer rule 匹配，因此只能先匹配，后丢弃。

下面运行 ANTLR tool，测试下该语法：

>antlr4 Expr.g4
>javac *.java
>grun Expr prog -gui
(1 + 2 + 3 * 2 / 2)
EOF