从零写一个编译器(四):语法分析之构造有限状态自动机

项目的完整代码在 C2j-Compiler

通过上一篇对几个构造自动机的基础数据结构的描述,现在就可以正式来构造有限状态自动机

我们先用一个小一点的语法推导式来描述这个过程

1
2
3
4
5
6
7
s -> e
e -> e + t
e -> t
t -> t * f
t -> f
f -> ( e )
f -> NUM

初始化

状态0是状态机的初始状态,它包含着语法表达式中的起始表达式,也就是编号为0的表达式:

0: s -> . e

这里的点也就是之前Production类中的dosPos

负责这个操作的方法在StateNodeManager类中,前面先判断当前目录下是不是已经构建好语法分析表了,如果有的话就不需要再次构建了。

productionManager.buildFirstSets();可以先略过,后面会讲到。

ProductionsStateNode就是用来描述状态节点的

1
2
3
4
5
public static int stateNumCount = 0;
/** Automaton state node number */
public int stateNum;
/** production of state node */
public ArrayList<Production> productions;

接着就是放入开始符号作为第一个状态节点,也就是这一步的初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
public void buildTransitionStateMachine() {
File table = new File("lrStateTable.sb");
if (table.exists()) {
return;
}
ProductionManager productionManager = ProductionManager.getInstance();
productionManager.buildFirstSets();
ProductionsStateNode state = getStateNode(productionManager.getProduction(Token.PROGRAM.ordinal()));

state.buildTransition();

debugPrintStateMap();
}

对起始推导式做闭包操作

注意之前的 . ,也就是Production里的dosPos,这一步就有用了,利用这个点来做闭包操作

对.右边的符号做闭包操作,也就是说如果 . 右边的符号是一个非终结符,那么肯定有某个表达式,->左边是该非终结符,把这些表达式添加进来

1
2
3
s -> . e
e -> . e + t
e -> . t

对新添加进来的推导式反复重复这个操作,直到所有推导式->右边是非终结符的那个所在推导式都引入,这也就是ProductionsStateNode里的makeClosure方法

主要逻辑就是先将这个节点中的所有产生式压入堆栈中,再反复的做闭包操作。closureSet是每个节点中保存闭包后的产生式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private void makeClosure() {
Stack<Production> productionStack = new Stack<Production>();
for (Production production : productions) {
productionStack.push(production);
}

if (Token.isTerminal(production.getDotSymbol())) {
ConsoleDebugColor.outlnPurple("Symbol after dot is not non-terminal, ignore and process next item");
continue;
}

while (!productionStack.empty()) {
Production production = productionStack.pop();
int symbol = production.getDotSymbol();
ArrayList<Production> closures = productionManager.getProduction(symbol);
for (int i = 0; closures != null && i < closures.size(); i++) {
if (!closureSet.contains(closures.get(i))) {
closureSet.add(closures.get(i));
productionStack.push(closures.get(i));
}
}
}
}

对引入的产生式进行分区

把 . 右边拥有相同非终结符的表达式划入一个分区,比如

1
2
s -> . e
e -> . e + t

就作为同一个分区。最后把每个分区中的表达式中的 . 右移动一位,形成新的状态节点

1
2
s -> e .
e -> e . + t

分区操作就在ProductionsStateNode类中的partition方法中

主要逻辑也很简单,遍历当前的closureSet,如果分区不存在,就以产生式点的右边作为key,产生式列表作为value,并且如果当前产生式列表里不包含这个产生式,就把这个产生式加入当前的产生式列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private void partition() {
ConsoleDebugColor.outlnPurple("==== state begin make partition ====");

for (Production production : closureSet) {
int symbol = production.getDotSymbol();
if (symbol == Token.UNKNOWN_TOKEN.ordinal()) {
continue;
}

ArrayList<Production> productionList = partition.get(symbol);
if (productionList == null) {
productionList = new ArrayList<>();
partition.put(production.getDotSymbol(), productionList);
}

if (!productionList.contains(production)) {
productionList.add(production);
}
}

debugPrintPartition();
ConsoleDebugColor.outlnPurple("==== make partition end ====");
}

对所有分区节点构建跳转关系

根据每个节点 . 左边的符号来判断输入什么字符来跳入该节点

比如, . 左边的符号是 t, 所以当状态机处于状态0时,输入时 t 时, 跳转到状态1。

. 左边的符号是e, 所以当状态机处于状态 0 ,且输入时符号e时,跳转到状态2:
0 – e -> 2

这个操作的实现再ProductionsStateNode的makeTransition方法中

主要逻辑是遍历所有分区,每个分区都是一个新的节点,所以拿到这个分区的跳转关系,也就是partition的key,即之前产生式的点的右边。然后构造一个新的节点和两个节点之间的关系

1
2
3
4
5
6
7
8
9
10
11
12
13
private void makeTransition() {
for (Map.Entry<Integer, ArrayList<Production>> entry : partition.entrySet()) {
ProductionsStateNode nextState = makeNextStateNode(entry.getKey());

transition.put(entry.getKey(), nextState);

stateNodeManager.addTransition(this, nextState, entry.getKey());
}

debugPrintTransition();

extendFollowingTransition();
}

makeNextStateNode的逻辑也很简单,就是拿到这个分区的产生式列表,然后返回一个新节点

1
2
3
4
5
6
7
8
9
10
11
private ProductionsStateNode makeNextStateNode(int left) {
ArrayList<Production> productions = partition.get(left);
ArrayList<Production> newProductions = new ArrayList<>();

for (int i = 0; i < productions.size(); i++) {
Production production = productions.get(i);
newProductions.add(production.dotForward());
}

return stateNodeManager.getStateNode(newProductions);
}

stateNodeManager已经出现很多次了,它是类StateNodeManager,它的作用是管理节点,分配节点,统一节点。之后对节点的压缩和语法分析表的最终构建都在这里完成,这是后话了。

上面用到的两个方法:

transitionMap相当于一个跳转表:key是起始节点,value是一个map,这个map的key是跳转关系,也就是输入一个终结符或者非终结符,value则是目标节点

1
2
3
4
5
6
7
8
9
public void addTransition(ProductionsStateNode from, ProductionsStateNode to, int on) {
HashMap<Integer, ProductionsStateNode> map = transitionMap.get(from);
if (map == null) {
map = new HashMap<>();
}

map.put(on, to);
transitionMap.put(from, map);
}

getStateNode先从判断如果这个节点没有创建过,创建过的节点都会加入stateList中,就创建一个新节点。如果存在就会返回这个原节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ProductionsStateNode getStateNode(ArrayList<Production> productions) {
ProductionsStateNode node = new ProductionsStateNode(productions);

if (!stateList.contains(node)) {
stateList.add(node);
ProductionsStateNode.increaseStateNum();
return node;
}

for (ProductionsStateNode sn : stateList) {
if (sn.equals(node)) {
node = sn;
}
}

return node;
}

对所有新生成的节点重复构建

这时候的第一轮新节点才刚刚完成,到等到所有节点都完成节点的构建才算是真正的完成,在makeTransition中调用的extendFollowingTransition正是这个作用

1
2
3
4
5
6
7
8
private void extendFollowingTransition() {
for (Map.Entry<Integer, ProductionsStateNode> entry : transition.entrySet()) {
ProductionsStateNode state = entry.getValue();
if (!state.isTransitionDone()) {
state.buildTransition();
}
}
}

小结

创建有限状态自动机的四个步骤

  • makeClosure
  • partition
  • makeTransition
  • 最后重复这些步骤直到所有的节点都构建完毕

至此我们对

1
2
3
4
5
6
7
8
9
10
public void buildTransition() {
if (transitionDone) {
return;
}
transitionDone = true;

makeClosure();
partition();
makeTransition();
}

的四个过程都已经完成,自动机的构建也算完成,应该进行语法分析表的创建了,但是这个自动机还有些问题,下一篇会来改善它。