ANTLR4 与 CYaRon!

ANTLR4 是一款语法生成器，所谓的语法生成器就是通过编写的某种特定的语法，来生成解析这种语法的解析器。而这种解析器，则称为 Parser。

解析语法

解析语法有两个重要的概念：词法解析器（Lexer）和语法解析器（Parser）

词法解析器一般是将源代码（例如字符串）转化为 Token 序列，这是为了方便 Parser 解析：例如字符串 foo(1, "2") 转换成 Token 序列 [Symbol(foo), LB, Number(1), COMMA, String("2"), RB]，将难以解析的字符按照某种特定的语法去处理成单独的 Token。

而语法解析器就是将 Token 转化为抽象语法树（Abstract Syntax Tree），或许某些人有见过表达式树：

1 + 2

与

PLAIN

+
|-1
|-2

表达式树也是抽象语法树，比如上面的 foo(1, "2") 可以表达为：

PLAIN

FunCall(foo)
|-<arguments>
  |-Number(1)
  |-String("2")

复杂一点的，比如 C 语言的 if (i == 1) { printf("%d", i); }：

PLAIN

if
|-<condition>
  |-Eq
    |-Symbol(i)
    |-Number(1)
|-<statement>
  |-FunCall(printf)
    |-<arguments>
      |-String("%d")
      |-Symbol(i)

最终，通过编写这些 AST 的求值代码，就得到一个解释器了。

ANTLR4 语法

ANTLR4 用大写开头的名称表示 Token，例如：

ANTLR

Number: [0-9]+;
Add: '+';
Mul: '*';

Number 是 Token 的名称，而冒号到分号的内容，是 Number 所解析的字符串内容。比如 [0-9] 代表 '0' 到 '9' 之间的所有字符，而 + 代表一个或多个。这和正则表达式的语法很像，* 代表零个或多个，而 ? 代表零个或一个。

用小写开头的名称表示规则，例如：

ANTLR

exp: add | mul | number;
add: exp Add exp;
mul: exp Mul exp;
number: Number;

exp 是规则的名称，而 | 则代表 或，比如 exp 规则解析 add 规则或 mul 规则，或者是 number 规则。规则可以使用 Token，反之不可。

歧义

但仔细看看，1+2*3 有不同的解析方法：

PLAIN

  exp
= exp Add exp
= 1 + exp
= 1 + exp Mul exp
= 1 + 2 * 3

或者是

PLAIN

  exp
= exp Mul exp
= exp * 3
= exp Add exp * 3
= 1 + 2 * 3

这种语法规则是有歧义的，而且从这歧义中可以看出，这份语法规则并没有体现出加法和乘法的优先级关系。

对于二元运算 + 和 *，如果 * 比 + 优先级高，则应该写成：

ANTLR

exp: add;
add: add + mul | mul;
mul: mul * number | number;
number: Number;

题外话：如果 + 是左结合的，那么应该写成 A: A + B | B;，如果是右结合的，则应该写成 A: B + A | B;，如果无结合性，则应该写成 A: B + B | B;

左递归

再仔细看看：

ANTLR

exp: add;
add: add + mul | mul;

add 会直接解析 add 规则，再去解析后续的规则。这种递归是无止境的，让解析器进入无穷递归，最终耗尽物理资源。这种递归被称为左递归，某些词法生成器会提供针对左递归的语法，ANTLR4 也有，但还是需要学习一下如何消除左递归的知识。

以二元运算加法为例，消除左递归一般是把 1+2 的 +2 部分看做一个整体：

ANTLR

exp: add;
add: mul add_;
add_: (Add add add_)?;
mul: number mul_;
mul_: (Mul number mul_)?;
number: Number;

在维基百科有更详细的说明。

最终的语法代码应该是这样的：

ANTLR

Number: [0-9]+;
Add: '+';
Mul: '*';

exp: add;
add: mul add_;
add_: (Add mul add_)?;
mul: number mul_;
mul_: (Mul number mul_)?;
number: Number;

CYaRon! 语言

CYaRon! ~~（以下简称瞎龙）~~ 语言是一门语法比较简单，功能不完善的语言，接下来我就试着用 ANTLR4 来编写瞎龙语言的语法解析器。

首先是 Token 部分，先把所有字面量都表示出来：

ANTLR

Vars: 'vars';
For: 'hor';
If: 'ihu';
While: 'while';
BlockStart: '{';
BlockEnd: '}';
Int: 'int';
Array: 'array';
ArrStart: '[';
ArrEnd: ']';
To: '..';
Comma: ',';
Colon: ':';
Plus: '+';
Minus: '-';
LT: 'lt';
GT: 'gt';
LE: 'le';
GE: 'ge';
EQ: 'eq';
NEQ: 'neq';

Digit: [0-9]+;
Symbol: [a-zA-Z]+;
Comment: '#' ~[\r\n]* '\r'? '\n' -> skip;
WS: [\n\t\r ]+ -> skip;

比较特别的是最后两个，-> skip 代表这两个 Token 会被 Parser 忽略。

接下来是规则部分，按照题目的代码示例，先实现定义变量部分：

ANTLR

definitionBlock:
    BlockStart Vars
    definitionLine*
    BlockEnd

接下来是变量定义的行部分：

ANTLR

definitionLine:
    WS* Symbol Colon type

好像因为 * 是连续的规则，中间不能夹杂其他东西，所以要手动加上 WS*。不过行尾没加也不会报错，可能是某些奇妙的魔法……

类型：

ANTLR

typeInt: Int;
typeArray: Array ArrStart type Comma Digit To Digit ArrEnd;
type: typeInt | typeArray;

函数调用：

ANTLR

opt: Plus | Minus;                                              // 二元运算符
indexing: ArrStart rightValue ArrEnd;                           // 数组索引规则 [1]

funCall: Colon Symbol parameter?;                               // 函数调用规则 :yosoro 1, a
parameter: rightValue | rightValue (Comma rightValue)*;         // 参数规则 1, a
leftValue: Symbol | leftValue indexing;                         // 左值规则 a, arr[1][2]
formulaValue : leftValue | Digit | funCall;                     // 算术值规则，仅用于二元运算解析用
rightValue: formulaValue | formula;                             // 右值规则，包含函数调用
formula: formulaValue formula_;                                 // 二元运算规则
formula_: (opt formula formula_)?;

表达式块：

ANTLR

statementLine: WS* (funCall | definitionBlock | ifBlock | whileBlock | forBlock);       // 单行代码
statement: statementLine*;                                                              // 多行代码

if、for、while 块：

ANTLR

condOpt: LT | GT | LE | GE | EQ | NEQ;                      // 条件运算符
cond: condOpt Comma rightValue Comma rightValue;            // 条件规则
forCond: rightValue Comma rightValue Comma rightValue;      // for 块条件规则

// if 块
ifBlock:
    BlockStart If cond
    statement
    BlockEnd;

// while 块
whileBlock:
    BlockStart While cond
    statement
    BlockEnd;

// for 块
forBlock:
    BlockStart For forCond
    statement
    BlockEnd;

这些就是瞎龙语言的全部语法代码了，statement 规则也可以作为整个文件的根规则进行解析。

文章操作

解析语法

ANTLR4 语法

歧义

左递归

CYaRon! 语言

相关推荐

评论

ANTLR4 与 CYaRon!