項(xiàng)目的完整代碼在 C2j-Compiler <https://github.com/dejavudwh/C2j-Compiler>

通過(guò)上一篇對(duì)幾個(gè)構(gòu)造自動(dòng)機(jī)的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的描述，現(xiàn)在就可以正式來(lái)構(gòu)造有限狀態(tài)自動(dòng)機(jī)

我們先用一個(gè)小一點(diǎn)的語(yǔ)法推導(dǎo)式來(lái)描述這個(gè)過(guò)程
s -> e e -> e + t e -> t t -> t * f t -> f f -> ( e ) f -> NUM
初始化

狀態(tài)0是狀態(tài)機(jī)的初始狀態(tài)，它包含著語(yǔ)法表達(dá)式中的起始表達(dá)式，也就是編號(hào)為0的表達(dá)式：

0: s -> . e

這里的點(diǎn)也就是之前Production類中的dosPos

負(fù)責(zé)這個(gè)操作的方法在StateNodeManager類中，前面先判斷當(dāng)前目錄下是不是已經(jīng)構(gòu)建好語(yǔ)法分析表了，如果有的話就不需要再次構(gòu)建了。

productionManager.buildFirstSets();可以先略過(guò)，后面會(huì)講到。

ProductionsStateNode就是用來(lái)描述狀態(tài)節(jié)點(diǎn)的
public static int stateNumCount = 0; /** Automaton state node number */ public
int stateNum; /** production of state node */ public ArrayList<Production>
productions;
接著就是放入開始符號(hào)作為第一個(gè)狀態(tài)節(jié)點(diǎn)，也就是這一步的初始化
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(); }
對(duì)起始推導(dǎo)式做閉包操作

注意之前的 . ,也就是Production里的dosPos，這一步就有用了，利用這個(gè)點(diǎn)來(lái)做閉包操作

對(duì).右邊的符號(hào)做閉包操作，也就是說(shuō)如果 . 右邊的符號(hào)是一個(gè)非終結(jié)符，那么肯定有某個(gè)表達(dá)式，->左邊是該非終結(jié)符，把這些表達(dá)式添加進(jìn)來(lái)
s -> . e e -> . e + t e -> . t

對(duì)新添加進(jìn)來(lái)的推導(dǎo)式反復(fù)重復(fù)這個(gè)操作，直到所有推導(dǎo)式->右邊是非終結(jié)符的那個(gè)所在推導(dǎo)式都引入，這也就是ProductionsStateNode里的makeClosure方法

主要邏輯就是先將這個(gè)節(jié)點(diǎn)中的所有產(chǎn)生式壓入堆棧中，再反復(fù)的做閉包操作。closureSet是每個(gè)節(jié)點(diǎn)中保存閉包后的產(chǎn)生式
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)); } } } }
對(duì)引入的產(chǎn)生式進(jìn)行分區(qū)

把 . 右邊擁有相同非終結(jié)符的表達(dá)式劃入一個(gè)分區(qū)，比如
s -> . e e -> . e + t
就作為同一個(gè)分區(qū)。最后把每個(gè)分區(qū)中的表達(dá)式中的 . 右移動(dòng)一位，形成新的狀態(tài)節(jié)點(diǎn)
s -> e . e -> e . + t
分區(qū)操作就在ProductionsStateNode類中的partition方法中


主要邏輯也很簡(jiǎn)單，遍歷當(dāng)前的closureSet，如果分區(qū)不存在，就以產(chǎn)生式點(diǎn)的右邊作為key，產(chǎn)生式列表作為value，并且如果當(dāng)前產(chǎn)生式列表里不包含這個(gè)產(chǎn)生式，就把這個(gè)產(chǎn)生式加入當(dāng)前的產(chǎn)生式列表
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
===="); }
對(duì)所有分區(qū)節(jié)點(diǎn)構(gòu)建跳轉(zhuǎn)關(guān)系

根據(jù)每個(gè)節(jié)點(diǎn) . 左邊的符號(hào)來(lái)判斷輸入什么字符來(lái)跳入該節(jié)點(diǎn)

比如， . 左邊的符號(hào)是 t, 所以當(dāng)狀態(tài)機(jī)處于狀態(tài)0時(shí)，輸入時(shí) t 時(shí)， 跳轉(zhuǎn)到狀態(tài)1。

. 左邊的符號(hào)是e, 所以當(dāng)狀態(tài)機(jī)處于狀態(tài) 0 ，且輸入時(shí)符號(hào)e時(shí)，跳轉(zhuǎn)到狀態(tài)2：
0 – e -> 2

這個(gè)操作的實(shí)現(xiàn)再ProductionsStateNode的makeTransition方法中


主要邏輯是遍歷所有分區(qū)，每個(gè)分區(qū)都是一個(gè)新的節(jié)點(diǎn)，所以拿到這個(gè)分區(qū)的跳轉(zhuǎn)關(guān)系，也就是partition的key，即之前產(chǎn)生式的點(diǎn)的右邊。然后構(gòu)造一個(gè)新的節(jié)點(diǎn)和兩個(gè)節(jié)點(diǎn)之間的關(guān)系
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的邏輯也很簡(jiǎn)單，就是拿到這個(gè)分區(qū)的產(chǎn)生式列表，然后返回一個(gè)新節(jié)點(diǎn)
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已經(jīng)出現(xiàn)很多次了，它是類StateNodeManager，它的作用是管理節(jié)點(diǎn)，分配節(jié)點(diǎn)，統(tǒng)一節(jié)點(diǎn)。之后對(duì)節(jié)點(diǎn)的壓縮和語(yǔ)法分析表的最終構(gòu)建都在這里完成，這是后話了。

上面用到的兩個(gè)方法：


transitionMap相當(dāng)于一個(gè)跳轉(zhuǎn)表：key是起始節(jié)點(diǎn)，value是一個(gè)map，這個(gè)map的key是跳轉(zhuǎn)關(guān)系，也就是輸入一個(gè)終結(jié)符或者非終結(jié)符，value則是目標(biāo)節(jié)點(diǎn)
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先從判斷如果這個(gè)節(jié)點(diǎn)沒有創(chuàng)建過(guò)，創(chuàng)建過(guò)的節(jié)點(diǎn)都會(huì)加入stateList中，就創(chuàng)建一個(gè)新節(jié)點(diǎn)。如果存在就會(huì)返回這個(gè)原節(jié)點(diǎn)
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; }
對(duì)所有新生成的節(jié)點(diǎn)重復(fù)構(gòu)建


這時(shí)候的第一輪新節(jié)點(diǎn)才剛剛完成，到等到所有節(jié)點(diǎn)都完成節(jié)點(diǎn)的構(gòu)建才算是真正的完成，在makeTransition中調(diào)用的extendFollowingTransition正是這個(gè)作用
private void extendFollowingTransition() { for (Map.Entry<Integer,
ProductionsStateNode> entry : transition.entrySet()) { ProductionsStateNode
state = entry.getValue(); if (!state.isTransitionDone()) {
state.buildTransition(); } } }
小結(jié)

創(chuàng)建有限狀態(tài)自動(dòng)機(jī)的四個(gè)步驟

* makeClosure
* partition
* makeTransition
* 最后重復(fù)這些步驟直到所有的節(jié)點(diǎn)都構(gòu)建完畢
至此我們對(duì)
public void buildTransition() { if (transitionDone) { return; } transitionDone
= true; makeClosure(); partition(); makeTransition(); }
的四個(gè)過(guò)程都已經(jīng)完成，自動(dòng)機(jī)的構(gòu)建也算完成，應(yīng)該進(jìn)行語(yǔ)法分析表的創(chuàng)建了，但是這個(gè)自動(dòng)機(jī)還有些問(wèn)題，下一篇會(huì)來(lái)改善它。

另外我的github博客：https://dejavudwh.cn/ <https://dejavudwh.cn/>

• ? 上一篇：abp(net core)+easyui+efcore實(shí)現(xiàn)倉(cāng)儲(chǔ)管理系統(tǒng)目錄
• ? 下一篇：@程序員，你該如何磨快你的鋸子