從零寫一個(gè)編譯器（六）：語(yǔ)法分析之表驅(qū)動(dòng)語(yǔ)法分析

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

前言

上一篇已經(jīng)正式的完成了有限狀態(tài)自動(dòng)機(jī)的構(gòu)建和足夠判斷reduce的信息，接下來(lái)的任務(wù)就是根據(jù)這個(gè)有限狀態(tài)自動(dòng)機(jī)來(lái)完成語(yǔ)法分析表和根據(jù)這個(gè)表來(lái)實(shí)現(xiàn)語(yǔ)法分析

reduce信息

在完成語(yǔ)法分析表之前，還差最后一個(gè)任務(wù)，那就是描述reduce信息，來(lái)指導(dǎo)自動(dòng)機(jī)是否該進(jìn)行reduce操作


reduce信息在ProductionsStateNode各自的節(jié)點(diǎn)里完成，只要遍歷節(jié)點(diǎn)里的產(chǎn)生式，如果符號(hào)“.”位于表達(dá)式的末尾，那么該節(jié)點(diǎn)即可根據(jù)該表達(dá)式以及表達(dá)式對(duì)應(yīng)的lookAhead
set得到reduce信息

reduce信息用一個(gè)map來(lái)表示，key是可以進(jìn)行reduce的符號(hào)，也就是lookahead sets中的符合，value則是進(jìn)行reduce操作的產(chǎn)生式
public HashMap<Integer, Integer> makeReduce() { HashMap<Integer, Integer> map
= new HashMap<>(); reduce(map, this.productions); reduce(map,
this.mergedProduction); return map; } 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())); } } } }
語(yǔ)法分析表的構(gòu)建


語(yǔ)法分析表的構(gòu)建主要在StateNodeManager類里，可以先忽略loadTable和storageTableToFile的邏輯，這一部分主要是為了儲(chǔ)存這張表，能夠多次使用


主要邏輯從while開(kāi)始，遍歷所有節(jié)點(diǎn)，先從跳轉(zhuǎn)信息的Map里拿出跳轉(zhuǎn)關(guān)系和跳轉(zhuǎn)的目的節(jié)點(diǎn)，然后把這個(gè)跳轉(zhuǎn)關(guān)系（這個(gè)本質(zhì)上對(duì)應(yīng)的是一開(kāi)始Token枚舉的標(biāo)號(hào)）和目的節(jié)點(diǎn)的標(biāo)號(hào)拷貝到另一個(gè)map里。接著拿到reduce信息，找到之前對(duì)應(yīng)在lookahead
set里的符號(hào)，把它們的value改寫成- （進(jìn)行reduce操作的產(chǎn)生式編號(hào)），之所以寫成負(fù)數(shù)，就是為了區(qū)分shift操作。

所以HashMap<Integer, HashMap<Integer, Integer>>這個(gè)數(shù)據(jù)結(jié)構(gòu)作為解析表表示：

* 第一個(gè)Integer表示當(dāng)前節(jié)點(diǎn)的編號(hào)
* 第二個(gè)Integer表示輸入字符
* 第三個(gè)Integer表示，如果大于0則是做shift操作，小于0則根據(jù)推導(dǎo)式做reduce操作 public HashMap<Integer,
HashMap<Integer, Integer>> getLrStateTable() { File table = new
File("lrStateTable.sb"); if (table.exists()) { return loadTable(); } Iterator
it; if (isTransitionTableCompressed) { it = compressedStateList.iterator(); }
else { it = stateList.iterator(); } while (it.hasNext()) { ProductionsStateNode
state = (ProductionsStateNode) it.next(); HashMap<Integer,
ProductionsStateNode> map = transitionMap.get(state); HashMap<Integer, Integer>
jump = new HashMap<>(); if (map != null) { for (Map.Entry<Integer,
ProductionsStateNode> item : map.entrySet()) { jump.put(item.getKey(),
item.getValue().stateNum); } } HashMap<Integer, Integer> reduceMap =
state.makeReduce(); if (reduceMap.size() > 0) { for (Map.Entry<Integer,
Integer> item : reduceMap.entrySet()) { jump.put(item.getKey(),
-(item.getValue())); } } lrStateTable.put(state.stateNum, jump); }
storageTableToFile(lrStateTable); return lrStateTable; }
表驅(qū)動(dòng)的語(yǔ)法分析

語(yǔ)法分析的主要過(guò)程在LRStateTableParser類里，由parse方法啟動(dòng).


和第二篇講的一樣需要一個(gè)輸入堆棧，節(jié)點(diǎn)堆棧，其它的東西現(xiàn)在暫時(shí)不需要用到。在初始化的時(shí)候先把開(kāi)始節(jié)點(diǎn)壓入堆棧，當(dāng)前輸入字符設(shè)為EXT_DEF_LIST，然后拿到語(yǔ)法解析表
public LRStateTableParser(Lexer lexer) { this.lexer = lexer;
statusStack.push(0); valueStack.push(null); lexer.advance(); lexerInput =
Token.EXT_DEF_LIST.ordinal(); lrStateTable =
StateNodeManager.getInstance().getLrStateTable(); }
語(yǔ)法解析的步驟：

* 拿到當(dāng)前節(jié)點(diǎn)和當(dāng)前字符所對(duì)應(yīng)的下一個(gè)操作，也就是action > 0是shift操作，action < 0是reduce操作
* 如果進(jìn)入action > 0，也就是shift操作
* 把當(dāng)前狀態(tài)節(jié)點(diǎn)和輸入字符分別壓入堆棧
* 這里要區(qū)分如果當(dāng)前的字符是終結(jié)符，這時(shí)候就可以直接讀入下一個(gè)字符
*
但是這里如果是非終結(jié)符，就應(yīng)該直接用當(dāng)前字符跳轉(zhuǎn)到下一個(gè)狀態(tài)。這里是一個(gè)需要注意的一個(gè)點(diǎn)，這里需要把當(dāng)前的這個(gè)非終結(jié)符，放入到下一個(gè)節(jié)點(diǎn)的對(duì)應(yīng)輸入堆棧中，這樣它進(jìn)行reduce操作時(shí)彈出退棧的符號(hào)才是正確的
* 如果action > 0，也就是reduce操作
* 拿到對(duì)應(yīng)的產(chǎn)生式
* 把產(chǎn)生式右邊對(duì)應(yīng)的狀態(tài)節(jié)點(diǎn)彈出堆棧
* 把完成reduce的這個(gè)符號(hào)放入輸入堆棧 public void parse() { while (true) { Integer action =
getAction(statusStack.peek(), lexerInput); if (action == null) {
ConsoleDebugColor.outlnPurple("Shift for input: " +
Token.values()[lexerInput].toString()); System.err.println("The input is
denied"); return; } if (action > 0) { statusStack.push(action); text =
lexer.text; // if (lexerInput == Token.RELOP.ordinal()) { // relOperatorText =
text; // } parseStack.push(lexerInput); if (Token.isTerminal(lexerInput)) {
ConsoleDebugColor.outlnPurple("Shift for input: " +
Token.values()[lexerInput].toString() + " text: " + text); // Object obj =
takeActionForShift(lexerInput); lexer.advance(); lexerInput = lexer.lookAhead;
// valueStack.push(obj); } else { lexerInput = lexer.lookAhead; } } else { if
(action == 0) { ConsoleDebugColor.outlnPurple("The input can be accepted");
return; } int reduceProduction = -action; Production product =
ProductionManager.getInstance().getProductionByIndex(reduceProduction);
ConsoleDebugColor.outlnPurple("reduce by product: "); product.debugPrint(); //
takeActionForReduce(reduceProduction); int rightSize =
product.getRight().size(); while (rightSize > 0) { parseStack.pop(); //
valueStack.pop(); statusStack.pop(); rightSize--; } lexerInput =
product.getLeft(); parseStack.push(lexerInput); //
valueStack.push(attributeForParentNode); } } } private Integer
getAction(Integer currentState, Integer currentInput) { HashMap<Integer,
Integer> jump = lrStateTable.get(currentState); return jump.get(currentInput); }
歧義性語(yǔ)法


到現(xiàn)在已經(jīng)完成了語(yǔ)法分析的所有內(nèi)容，接下來(lái)就是語(yǔ)義分析了，但是在這之前還有一個(gè)需要說(shuō)的是，我們當(dāng)前構(gòu)造的有限狀態(tài)自動(dòng)機(jī)屬于LALR(1)語(yǔ)法，即使LALR(1)語(yǔ)法已經(jīng)足夠強(qiáng)大，但是依舊有LALR(1)語(yǔ)法處理不了的語(yǔ)法，如果給出的推導(dǎo)式不符合，那么這個(gè)有限狀態(tài)自動(dòng)機(jī)依舊不能正確解析，但是之前給出的語(yǔ)法都是符合LALR(1)語(yǔ)法的

小結(jié)

這一篇主要就是

* 利用有限狀態(tài)自動(dòng)機(jī)和reduce信息完成語(yǔ)法解析表
* 利用語(yǔ)法解析表實(shí)現(xiàn)表驅(qū)動(dòng)的語(yǔ)法解析

• ? 上一篇：從零寫一個(gè)編譯器（十二）：代碼生成之生成邏輯
• ? 下一篇：深圳流水線工廠，我差點(diǎn)和主管打了起來(lái) | 十年系列