用java开发编译器:构建LR跳转表

本文主要是介绍用java开发编译器:构建LR跳转表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

阅读博客的朋友可以到我的网易云课堂中，通过视频的方式查看代码的调试和执行过程：

http://study.163.com/course/courseMain.htm?courseId=1002830012

如果大家运行上一节的代码，可以得到压缩后的LR有限状态机，以及节点间的跳转关系：

***begin to print a map row***

from state:
State Number: 0
STMT -> .EXPR look ahead set: { EOI }
on symbol: TERM
to state:
State Number: 1
EXPR -> TERM .look ahead set: { EOI }
TERM -> TERM .TIMES FACTOR look ahead set: { EOI }
TERM -> TERM .TIMES FACTOR look ahead set: { TIMES }
EXPR -> TERM .look ahead set: { PLUS }
TERM -> TERM .TIMES FACTOR look ahead set: { PLUS }
EXPR -> TERM .look ahead set: { RIGHT_PARENT }
TERM -> TERM .TIMES FACTOR look ahead set: { RIGHT_PARENT }
on symbol: EXPR
to state:
State Number: 2
STMT -> EXPR .look ahead set: { EOI }
EXPR -> EXPR .PLUS TERM look ahead set: { EOI }
EXPR -> EXPR .PLUS TERM look ahead set: { PLUS }
on symbol: NUM_OR_ID
to state:
State Number: 3
FACTOR -> NUM_OR_ID .look ahead set: { EOI }
FACTOR -> NUM_OR_ID .look ahead set: { TIMES }
FACTOR -> NUM_OR_ID .look ahead set: { PLUS }
FACTOR -> NUM_OR_ID .look ahead set: { RIGHT_PARENT }
on symbol: LEFT_PARENT
to state:
State Number: 4
FACTOR -> LEFT_PARENT .EXPR RIGHT_PARENT look ahead set: { EOI }
FACTOR -> LEFT_PARENT .EXPR RIGHT_PARENT look ahead set: { TIMES }
FACTOR -> LEFT_PARENT .EXPR RIGHT_PARENT look ahead set: { PLUS }
FACTOR -> LEFT_PARENT .EXPR RIGHT_PARENT look ahead set: { RIGHT_PARENT }
on symbol: FACTOR
to state:
State Number: 5
TERM -> FACTOR .look ahead set: { EOI }
TERM -> FACTOR .look ahead set: { TIMES }
TERM -> FACTOR .look ahead set: { PLUS }
TERM -> FACTOR .look ahead set: { RIGHT_PARENT }
***end a map row***

上面是程序输出的一部分结果，它表明了从节点0如何跳转到其他节点，例如，从上面的节点可以看出，当处于节点0的时候，在输入为t(term) 时，跳转到节点1，以此类推。

在上面的信息输出中，只表明了节点间的跳转关系，有另一层信息并没有显示出来，那就是当处于某个节点时，是否要采取reduce操作。

我们看节点3，点符号处于节点表达式的末尾，当状态机处于该节点，并且当输入属于EOI，TIMES，PLUS，RIGHT_PARENT，
其中之一时，我们应该采取reduce操作，在我们程序的输出信息中，reduce操作的相关信息并没有显示，因此，要构造一个完整的跳转表，我们还需要构建每个节点的reduce信息。

reduce信息的构建不难，只要遍历每个节点，查看节点包含的表达式，如果符号”.”位于表达式的末尾，那么该节点即可根据该表达式以及表达式对应的look ahead 集合，打印相关的reduce信息。在GrammarState中，我添加了一个reduce函数，它的作用是构建对应节点的reduce信息：


private void  reduce(HashMap<Integer, Integer> map, ArrayList<Production> productions) {for (int i = 0; i < productions.size(); i++) {if (productions.get(i).canBeReduce()) {ArrayList<Integer> lookAhead = productions.get(i).getLookAheadSet();for (int j = 0; j < lookAhead.size(); j++) {map.put(lookAhead.get(j), (productions.get(i).getProductionNum()));}}}
}

代码的逻辑，大家可观看稍后的代码解读。

有了节点的跳转信息，和reduce信息，我们就可以构建完整的状态跳转表了。

跳转表的构建在GrammarStateManager中，在该类中有一个成员变量：

HashMap<Integer, Map<Integer, Integer>> lrStateTable.

这个变量是一个间套的HashMap, 红色的Integer表示当前节点的编号，蓝色的Integer表示对应的输入符号所对应的数值，第三个紫色的Integer代表两个含义，如果它是大于0的正数，那表明，从红色Integer表示的节点跳转到紫色的Integer所表示的节点，如果它是0或负数，表明当处于红色Integer的节点时，要做一次reduce操作，举个例子：
Integer: 3
Integer: 0 (EOI)
Integer: -6

上面的数据表明，当处于节点3，输入是EOI时，根据表达式6(f->NUM)做一个reduce操作.于是当解析器在解析时，将当前所在的状态节点号，当前输入符号的数值在上面的跳转表中查找，如果得到的第三更Integer是正数，那么解析器就跳转到指定节点，如果得到的是负数，那么解析器就根据相应数值做一次reduce操作。
结合跳转关系和reduce信息后，我们构造的状态机跳转表如下：

这里写图片描述