最近在尝试实现一个c语言编译器。其中涉及到语法树的构建。在解析表达式时，就需要考虑左递归和优先级问题。左递归，可以通过 百度百科 中的方式来消除左递归。但是由于表达式又存在优先级问题。所以消除过程十分繁琐。如下简单的计算器实现例子：
消除左递归，并添加优先级后，如下：
Num: [0-9]+
factor: Num | '(' expr3 ')'
term_tail: | ('*' expr1 | '/' expr1) term_tail
term: factor term
expr_tail: | ('+' expr2 | '-' expr2) expr_tail
expr: term expr_tail
可以看出，表达式比较复杂。如果再添加其他运算，如位移运算，逻辑运算，以及其他自定义运算。则实现起来及其复杂。
Antlr4
如果使用 antlr4则语法就会变得很简单。如下，有左递归的表达式在或中越靠前，优先级越高，factor 类则无影响。
Num: [0-9]+
expr:
Number
| '(' expr ')'
| expr ('*'|'/') expr
| expr ('+'|'-') expr
;
可以在vscode 中使用 ANTLR4 grammar syntax support 插件 测试该语法。
-
编写g4 文件
-
ctrl+s 保存以下，生成 .antlr文件夹
-
添加 .vscode/launch.json 写入如下内容
{ "version": "0.2.0", "configurations": [ { "name": "Debug ANTLR4 grammar - Test - Expr", "type": "antlr-debug", "request": "launch", "input": "test.txt", // 测试内容文件 "grammar": "Test.g4", // 语法文件 "startRule": "expr", // 入口表达式 "printParseTree": true, // 是否打印语法树 "visualParseTree": true, // 是否显示语法树 } ] } -
在 Test.g4 目录下 F5 调试即可
image-20200626180223745
可以看到，正确生成语法树。且优先级正确。没有错误匹配。
自己动手实现
antlr 虽然好用，但是如果我们想要实现一个新的语言，并实现自举，则antlr并不是一个很好的选择。需要自己实现语法树的构建。其中的难点也是表达式的解析。以下使用一种特殊的方式消除左递归：左递归表达式中，左边的值的 tryx 必须大于自己，右边的 tryx 必须 大于等于自己。即 expr: A op B 中的 A必须优先级高于自己， B优先级至少是自己。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Calculator {
public static int Num = 1024;
public static int[] tokens;
public static String[] values;
public static int tkAt = 0;
public static void main(String[] args) {
tokens = new int[1024];
values = new String[1024];
lexer("3 - 4 * 5 + 6 * (7 - 1)");
Node root = new Node();
root.value = "root";
if (valueExpr(0, root)) {
Tree.print(root);
} else {
System.err.println("error");
}
}
// 词法器
public static void lexer(String content) {
int at = 0;
for (int i = 0; i < content.length(); i++) {
char tk = content.charAt(i);
if (tk == ' ') {
continue;
}
if (tk > '0' && tk <= '9') {
int start = i;
int end = i + 1;
for (; end < content.length(); end++) {
tk = content.charAt(end);
if (!(tk >= '0' && tk <= '9')) {
break;
}
}
i = end - 1;
String str = content.substring(start, end);
values[at] = str;
tokens[at++] = Num;
continue;
}
if (tk == '+' || tk == '*' || tk == '/' || tk == '-' || tk == '(' || tk == ')') {
tokens[at++] = tk;
continue;
}
System.err.println("unkown token :" + tk);
System.exit(0);
}
}
public static void next() {
tkAt++;
}
public static boolean match(int tk) {
if (tk == tokens[tkAt]) {
return true;
}
return false;
}
public static class Node {
public String value;
public List<Node> children = new ArrayList<>();
@Override
public String toString() {
return String.format("[value: %s, children: %s]", value, Arrays.toString(children.toArray()));
}
}
// valueExpr:
// 3 Num
// 2 | '(' valueExpr ')'
// 1 | valueExpr ('*' | '/') valueExpr
// 0 | valueExpr ('+' | '-') valueExpr
public static boolean valueExpr(int tryx, Node parent) {
try {
Thread.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
int tkAtBck = tkAt;
int step = 0;
// 由于java不支持 goto, 这里用循环实现 goto
while (true) {
tkAt = tkAtBck;
switch (step + "") {
case "0":
if (tryx <= step++) {
Node node = new Node();
if (!valueExpr(step, node)) {
continue;
}
next();
if (!match('+') && !match('-')) {
continue;
}
node.value = "" + (char) tokens[tkAt];
next();
if (!valueExpr(step - 1, node)) {
return false;
}
parent.children.add(node);
return true;
}
break;
case "1":
if (tryx <= step++) {
Node node = new Node();
if (!valueExpr(step, node)) {
continue;
}
next();
if (!match('*') && !match('/')) {
continue;
}
node.value = "" + (char) tokens[tkAt];
next();
if (!valueExpr(step - 1, node)) {
return false;
}
parent.children.add(node);
return true;
}
break;
case "2":
if (tryx <= step++) {
Node node = new Node();
if (!match('(')) {
continue;
}
next();
if (!valueExpr(0, node)) {
return false;
}
next();
if (!match(')')) {
return false;
}
node.value = "()";
parent.children.add(node);
return true;
}
break;
case "3":
if (tryx <= step++) {
Node node = new Node();
if (match(Num)) {
node.value = values[tkAt];
parent.children.add(node);
return true;
}
}
break;
default:
return false;
}
}
}
}
其中 Tree.print(root); 就是打印生成节点树。运行结果如下。
image-20200626174621941
如果需要实现计算，则只需对节点树进行后序遍历，入栈。遇到符号弹出两个值进行计算，然后放回栈继续即可。
网友评论