點(diǎn)擊查看 基于Swift的PrattParser項(xiàng)目

PrattParser項(xiàng)目概述

---

前段時(shí)間一直想著手惡補(bǔ) 編譯原理 的相關(guān)知識(shí), 一開始打算直接讀大學(xué)的 編譯原理, 雖然內(nèi)容豐富, 但是著實(shí)抽象難懂. 無意間看到B站的熊爺關(guān)于普拉特解析器相關(guān)內(nèi)容, 感覺是一個(gè)非常好的切入點(diǎn).所以就寫了基于Swift版本的 PrattParser.

下面是我整理的項(xiàng)目中各個(gè)類以及其中函數(shù)的作用.

更加具體的請查看 PrattParser解釋器項(xiàng)目類與函數(shù)

接下來, 我把整個(gè)項(xiàng)目UML圖發(fā)出來, 大家可以借鑒查看.

更加具體的請查看 PrattParser的Swift項(xiàng)目UML圖

接下來, 我就以 詞法分析 、語法分析 、 中間代碼生成 三部分逐步來說明一下這個(gè) 基于Swift的PrattParser項(xiàng)目

詞法分析

---

詞法分析的核心類是 Lexer, 輸入的原始代碼字符串 code, 輸出的是一組詞法單元 Token.

在詞法分析器 Lexer 中, 核心函數(shù)就是 nextToken, nextToken函數(shù)職責(zé)一共有兩個(gè)職責(zé).

• 去除代碼格式化的邏輯, 例如, 去除 空格 換行 等等. 這一步主要是通過調(diào)用 skipWhitespace() 函數(shù)實(shí)現(xiàn)的.

  public func skipWhitespace() {while (hasNext()) {if (word == " " || word == "\t" || word == "\n" || word == "\r")  {readCodeAction();} else {break}}
  }
  

• 讀取數(shù)學(xué)符號(hào)與數(shù)字并且生成 詞法單元Token

  switch(word) {
  case "+" :token = PrattParser.Token(TokenType.PLUS, "+")break
  case "-" :token = PrattParser.Token(TokenType.MINUS, "-")break
  case "*" :token = PrattParser.Token(TokenType.ASTERISK, "*")break
  case "/" :token = PrattParser.Token(TokenType.SLASH, "/")break
  case "(" :token = PrattParser.Token(TokenType.LPAREN, "(")break
  case ")" :token = PrattParser.Token(TokenType.RPAREN, ")")break
  case "^" :token = PrattParser.Token(TokenType.HAT, "^")break
  case nil :token = PrattParser.Token(TokenType.EOF, "")break
  default:if (isDigit(word)) {let num: String = readNum();token = PrattParser.Token(TokenType.NUM, num);return token;} else {throw LexerError.lexerError(message: "Lexer error")}
  }
  

生成詞法單元函數(shù) nextToken 的整體邏輯流程圖如下所示. 基本涉及了詞法分析器 Lexer 的所有函數(shù).

這里要補(bǔ)充的一點(diǎn)的就是由于數(shù)學(xué)符號(hào)大部分是單個(gè)字符, 例如 + - * / ( ), 這個(gè)讀取直接生成即可. 但是數(shù)字可能是有多位的, 所以生成的過程需要通過循環(huán)一直查找. 在該項(xiàng)目中的代碼實(shí)現(xiàn)中讀取數(shù)字字符的邏輯代碼主要存在于 readNum 函數(shù)中.

public func readNum() -> String {var num: String = ""while (isDigit(word)) {num += word ?? ""readCodeAction()}return num;
}

生成數(shù)字函數(shù) readNum 的整體邏輯流程圖如下所示.

在該項(xiàng)目中, 詞法分析器Lexer 的外部驅(qū)動(dòng)力是 語法分析器Parser, 也就是說語法分析器Parser一直在調(diào)用 Lexer 的 nextToken 函數(shù)從而不斷地生成詞法單元 Token.

語法分析

---

在 詞法分析 模塊, 我們了解到了 詞法分析器Lexer 會(huì)為 語法分析器Parser 提供源源不斷生成的詞法單元 Token.

語法分析器Parser 則會(huì)這些詞法單元 Token根據(jù) 符號(hào)的優(yōu)先級(jí) 生成一顆 AST語法樹.

在 語法分析器Parser 生成 AST語法樹 的過程中, 其入口函數(shù)是 parseMain(), 核心函數(shù)是 parseExpression(), 具體代碼如下所示.

func parseExpression(_ precedence: Precedence) -> Expression? {let funcName: String?  = prefixParseFnHashMap[cur?.type ?? TokenType.None];if (funcName == nil) {print("未找到AST節(jié)點(diǎn)構(gòu)建函數(shù)名稱")return nil}// 生成前置節(jié)點(diǎn), 獲取左節(jié)點(diǎn)var leftExpression: Expression? = getPrefixExpression(funcName);// 能遞歸的原因 判斷下一個(gè)詞法單元是否是EOF, 判斷下一個(gè)詞法單元的優(yōu)先級(jí)是否大于當(dāng)前的優(yōu)先級(jí)while (!peekTokenIs(TokenType.EOF) && precedence.rawValue < peekPrecedence()?.rawValue ?? 0) {let infixParseFnName: String?  = infixParseFnHashMap[peek?.type ?? TokenType.None];if (infixParseFnName == nil) {print("未找到AST節(jié)點(diǎn)構(gòu)建函數(shù)名稱")return leftExpression;}//讀取下一個(gè)詞法單元nextToken();// 生成中置節(jié)點(diǎn), 更新AST語法樹leftExpression = parseInfixExpression(leftExpression);}return leftExpression
}

由于遞歸過程比較復(fù)雜, 我整理了一下整體的邏輯流程圖.

當(dāng)我們看到上一個(gè)圖的時(shí)候, 我們會(huì)詫異, 說好的遞歸過程在哪呢? 其實(shí)遞歸過程主要隱藏在生成中置節(jié)點(diǎn)函數(shù) parseInfixExpression() 中, 由于 parseExpression() → parseInfixExpression() → parseExpression() → .... 的調(diào)用關(guān)系會(huì)最終產(chǎn)生遞歸效果.

在中置節(jié)點(diǎn)生成函數(shù)parseInfixExpression中, 右節(jié)點(diǎn)的生成依然會(huì)依賴 parseExpression(), 這也就遞歸產(chǎn)生的驅(qū)動(dòng)力.

// 中置節(jié)點(diǎn)生成函數(shù)
func parseInfixExpression(_ left: Expression?) -> Expression? {let infixExpression = InfixExpression();infixExpression.left = left;infixExpression.operatorValue = cur?.value;let precedence: Precedence = Precedence.getPrecedence(cur?.type);nextToken();// 右節(jié)點(diǎn)的生成是遞歸產(chǎn)生的驅(qū)動(dòng)力infixExpression.right = parseExpression(precedence);return infixExpression
}

中置節(jié)點(diǎn)生成函數(shù)parseInfixExpression的邏輯流程圖如下所示.

粗略的說了大致的流程, 接下來, 我們就詳情的說一下具體的執(zhí)行流程.

具體的以 1 + 4 - 3 和 1 + 2 * 3 兩個(gè)數(shù)學(xué)運(yùn)算為示例.

1 + 4 - 3 的AST語法樹構(gòu)建過程

---

強(qiáng)烈建議大家一邊項(xiàng)目斷點(diǎn), 一邊對(duì)照該模塊的流程!!!

• 整體還是以 parseMain() 為入口, 初始過程中會(huì)傳入一個(gè)最低的優(yōu)先級(jí)(Precedence.LOWEST)用于驅(qū)動(dòng)整個(gè)AST語法樹的構(gòu)建. 當(dāng)然了, 這時(shí)候詞法單元讀取模塊也已經(jīng)準(zhǔn)備就緒了.

  // 構(gòu)建AST樹主入口
  public func parseMain() -> Expression? {return parseExpression(Precedence.LOWEST);
  }
  

  

• 通過 parseMain 函數(shù)進(jìn)入的 parseExpression() 函數(shù)中, 首先找的就是前置節(jié)點(diǎn), 通過 詞法單元讀取模塊 獲取到第一個(gè)詞法單元 1. 并且生成根據(jù) 前置節(jié)點(diǎn)的類型 生成 數(shù)字類型的AST前置節(jié)點(diǎn). getPrefixExpression 就不過多敘述了, 比較簡單.

  let funcName: String?  = prefixParseFnHashMap[cur?.type ?? TokenType.None];
  if (funcName == nil) {print("未找到AST節(jié)點(diǎn)構(gòu)建函數(shù)名稱")return nil
  }
  // 獲取左節(jié)點(diǎn)
  var leftExpression: Expression? = getPrefixExpression(funcName);
  

  func getPrefixExpression(_ funcName: String?) -> Expression? {switch(funcName) {case "parseInteger" :return parseInteger()case "parsePrefixExpression":return parsePrefixExpression()case "parseGroupExpression":return parseGroupExpression()default:return nil}
  }
  

  func parseInteger() -> Expression? {let number = Double(cur?.value ?? "0")let integerExpression = IntegerExpression(value: number)return integerExpression
  }
  

  

• 緊接著就是去找到中置節(jié)點(diǎn), 這時(shí)候通過peekPrecedence() 知道下一個(gè)詞法單元為 +, 優(yōu)先級(jí)較高, 滿足優(yōu)先級(jí)條件. 進(jìn)入遞歸循環(huán). 然后nextToken()讀取下一個(gè)詞法單元 +, 然后通過調(diào)用 parseInfixExpression() 嘗試生成AST中的中置節(jié)點(diǎn).

  while (!peekTokenIs(TokenType.EOF) && precedence.rawValue < peekPrecedence()?.rawValue ?? 0) {let infixParseFnName: String?  = infixParseFnHashMap[peek?.type ?? TokenType.None];if (infixParseFnName == nil) {print("未找到AST節(jié)點(diǎn)構(gòu)建函數(shù)名稱")return leftExpression;}nextToken();leftExpression = parseInfixExpression(leftExpression);
  }
  

  

• 在中置節(jié)點(diǎn)生成函數(shù) parseInfixExpression() 中, 由于當(dāng)前的詞法單元為 + , 左節(jié)點(diǎn)為前置節(jié)點(diǎn) 1, 我們可以直接構(gòu)建出這一部分的AST語法樹.

  let infixExpression = InfixExpression();
  infixExpression.left = left;
  infixExpression.operatorValue = cur?.value;
  

  

• 構(gòu)建了中置節(jié)點(diǎn)的值和左節(jié)點(diǎn), 我們嘗試用 parseExpression() 遞歸的形式找到 +的中置節(jié)點(diǎn) 的右節(jié)點(diǎn), 我們需要先讀取當(dāng)前 + 的優(yōu)先級(jí)(Precedence.SUM), 然后讀取下一個(gè)節(jié)點(diǎn).

  let precedence: Precedence = Precedence.getPrecedence(cur?.type);
  nextToken();
  infixExpression.right = parseExpression(precedence);
  

  

• 在 parseExpression() 尋找 +的中置節(jié)點(diǎn) 的右節(jié)點(diǎn), 首先, 就是獲取 數(shù)字詞法單元4 生成前置節(jié)點(diǎn), 然后往后讀取, 發(fā)現(xiàn)是 符號(hào)詞法單元- 優(yōu)先級(jí)與 當(dāng)前 符號(hào)詞法單元+ 的優(yōu)先級(jí)相同, 所以就不進(jìn)入while循環(huán), 故+的中置節(jié)點(diǎn) 的右節(jié)點(diǎn)是 前置節(jié)點(diǎn)4.

  // 參數(shù)優(yōu)先級(jí)為 Precedence.SUM
  func parseExpression(_ precedence: Precedence) -> Expression? {let funcName: String?  = prefixParseFnHashMap[cur?.type ?? TokenType.None];if (funcName == nil) {print("未找到AST節(jié)點(diǎn)構(gòu)建函數(shù)名稱")return nil}// 獲取左節(jié)點(diǎn), 生成 數(shù)字前置節(jié)點(diǎn) 4var leftExpression: Expression? = getPrefixExpression(funcName);//  - 與 + 的優(yōu)先級(jí)相同不進(jìn)入while循環(huán)while (!peekTokenIs(TokenType.EOF) && precedence.rawValue < peekPrecedence()?.rawValue ?? 0) {let infixParseFnName: String?  = infixParseFnHashMap[peek?.type ?? TokenType.None];if (infixParseFnName == nil) {print("未找到AST節(jié)點(diǎn)構(gòu)建函數(shù)名稱")return leftExpression;}nextToken();leftExpression = parseInfixExpression(leftExpression);}// 返回 數(shù)字前置節(jié)點(diǎn) 4return leftExpression
  }
  

  

• 這時(shí)候, 對(duì)于 中置節(jié)點(diǎn)+號(hào) 的AST語法樹就構(gòu)建完成了, 如圖所示.

  

• 然后外部又一次進(jìn)行while循環(huán), 這次找到的是 ? 號(hào), 然后把 中置節(jié)點(diǎn)+號(hào) 的AST語法樹 整體作為?中置節(jié)點(diǎn)的左節(jié)點(diǎn)傳入.

  // 這時(shí)候再次進(jìn)入 減號(hào)? 的循環(huán)中
  while (!peekTokenIs(TokenType.EOF) && precedence.rawValue < peekPrecedence()?.rawValue ?? 0) {let infixParseFnName: String?  = infixParseFnHashMap[peek?.type ?? TokenType.None];if (infixParseFnName == nil) {print("未找到AST節(jié)點(diǎn)構(gòu)建函數(shù)名稱")return leftExpression;}// 讀取詞法單元減號(hào)?nextToken();// 這里的leftExpression是 加號(hào)? 的AST語法樹//   +//  ╱ ╲// 1   4leftExpression = parseInfixExpression(leftExpression);
  }
  

  

• 在 ? 號(hào)的中置節(jié)點(diǎn) 構(gòu)建過程中, 中置節(jié)點(diǎn)+號(hào) 的AST語法樹 作為其左節(jié)點(diǎn), - 作為其值, 右節(jié)點(diǎn)繼續(xù)通過parseExpression()尋找.

  let infixExpression = InfixExpression();
  // 這里的left是 加號(hào)? 的AST語法樹
  //   +
  //  ╱ ╲
  // 1   4
  infixExpression.left = left;
  infixExpression.operatorValue = cur?.value;

  

• 和 中置節(jié)點(diǎn)+號(hào) 尋找右節(jié)點(diǎn)的邏輯是一樣. 我們繼續(xù)嘗試用 parseExpression() 遞歸的形式找到 -的中置節(jié)點(diǎn) 的右節(jié)點(diǎn), 我們需要先讀取當(dāng)前 - 的優(yōu)先級(jí)(Precedence.SUM), 然后讀取下一個(gè)節(jié)點(diǎn).

  let precedence: Precedence = Precedence.getPrecedence(cur?.type);
  nextToken();
  infixExpression.right = parseExpression(precedence);
  

  

• 這次在 parseExpression() 就很簡單了, 我們先構(gòu)建了前置節(jié)點(diǎn)3 然后往后查找過程發(fā)現(xiàn)是結(jié)束詞法單元EOF, 我們直接返回 前置節(jié)點(diǎn)3 即可.

  func parseExpression(_ precedence: Precedence) -> Expression? {let funcName: String?  = prefixParseFnHashMap[cur?.type ?? TokenType.None];if (funcName == nil) {print("未找到AST節(jié)點(diǎn)構(gòu)建函數(shù)名稱")return nil}// 構(gòu)建 前置節(jié)點(diǎn)3var leftExpression: Expression? = getPrefixExpression(funcName);// peekToken == EOF 不滿足while循環(huán)條件while (!peekTokenIs(TokenType.EOF) && precedence.rawValue < peekPrecedence()?.rawValue ?? 0) {let infixParseFnName: String?  = infixParseFnHashMap[peek?.type ?? TokenType.None];if (infixParseFnName == nil) {print("未找到AST節(jié)點(diǎn)構(gòu)建函數(shù)名稱")return leftExpression;}nextToken();leftExpression = parseInfixExpression(leftExpression);}// 返回 前置節(jié)點(diǎn)3return leftExpression
  }
  

  

• 返回了右節(jié)點(diǎn)之后, 我們就直接構(gòu)建 ?減號(hào)的AST語法樹, 這里看一下整體的構(gòu)建過程.

  

• ?減號(hào)的AST語法樹 然后再次返回整體的循環(huán), 發(fā)現(xiàn)當(dāng)前的詞法節(jié)點(diǎn)以及全部循環(huán)完成了, 所以就跳出了while循環(huán), 返回最終的AST語法樹. 這里就把整理的流程貼圖如下所示.

  

• 所以1 + 4 - 3 形成的AST語法樹是這樣的. 如下圖所示.

  

1 + 2 * 3 的AST語法樹構(gòu)建過程

---

相比于 1 + 4 - 3 的最終結(jié)果來說, 1 + 2 * 3 其中 乘法* 一定要比 加法+ 優(yōu)先級(jí)高. 最終應(yīng)該是這樣的 1 + (2 * 3) . 也就是我們預(yù)想的AST語法樹應(yīng)該如下所示.

接下來, 我們就一起看一下 1 + 2 * 3 的AST語法樹構(gòu)建邏輯.

• 對(duì)于 1 + 2 * 3 一直到加法的中置節(jié)點(diǎn)尋找右節(jié)點(diǎn)之前的邏輯都是與先前一樣的. 這里直接貼圖了, 就不過多敘述代碼了.

  

• 接下來, 對(duì)于 中置節(jié)點(diǎn)加號(hào)+ 需要通過 parseExpression() 去尋找它自身的右節(jié)點(diǎn). 這時(shí)候準(zhǔn)備工作也要做好, 讀取下一個(gè)詞法單元2, 獲取當(dāng)前加號(hào)的優(yōu)先級(jí)(Precedence.SUM).

  // 當(dāng)前加號(hào)的優(yōu)先級(jí)為 Precedence.SUM
  let precedence: Precedence = Precedence.getPrecedence(cur?.type);
  // 下一個(gè)詞法單元為 詞法單元2
  nextToken();
  // 尋找 中置節(jié)點(diǎn)加號(hào)+ 的 右節(jié)點(diǎn)
  infixExpression.right = parseExpression(precedence);
  

  

• 然后, 在 parseExpression() 就是先構(gòu)建 前置節(jié)點(diǎn)2, 然后查看后一個(gè)詞法單元, 發(fā)現(xiàn)是 乘法符號(hào)*, 乘法符號(hào)的優(yōu)先級(jí)(Precedence.PRODUCT) 要比 加法符號(hào)的優(yōu)先級(jí)(Precedence.SUM) 要高, 所以進(jìn)入while循環(huán)中. 繼續(xù)構(gòu)建關(guān)于 中置節(jié)點(diǎn)乘法* 的相關(guān)AST語法樹.

  // 當(dāng)前優(yōu)先級(jí)是 Precedence.SUM, 當(dāng)前Token是 2
  func parseExpression(_ precedence: Precedence) -> Expression? {let funcName: String?  = prefixParseFnHashMap[cur?.type ?? TokenType.None];if (funcName == nil) {print("未找到AST節(jié)點(diǎn)構(gòu)建函數(shù)名稱")return nil}// 構(gòu)建左節(jié)點(diǎn) 前置節(jié)點(diǎn)2var leftExpression: Expression? = getPrefixExpression(funcName);// 乘法符號(hào)的優(yōu)先級(jí)比當(dāng)前加號(hào)優(yōu)先級(jí)高, 正常進(jìn)入while循環(huán)while (!peekTokenIs(TokenType.EOF) && precedence.rawValue < peekPrecedence()?.rawValue ?? 0) {let infixParseFnName: String?  = infixParseFnHashMap[peek?.type ?? TokenType.None];if (infixParseFnName == nil) {print("未找到AST節(jié)點(diǎn)構(gòu)建函數(shù)名稱")return leftExpression;}// 讀取下一個(gè)詞法單元 乘法符號(hào)*nextToken();// 生成乘法符號(hào)的中置節(jié)點(diǎn)并且更新leftExpressionleftExpression = parseInfixExpression(leftExpression);}return leftExpression
  }
  

  let infixExpression = InfixExpression();
  infixExpression.left = left;
  infixExpression.operatorValue = cur?.value;
  // 當(dāng)前的乘法符號(hào) 的AST語法樹
  //   *
  //  ╱ ╲
  // 2   ?
  

  

• 緊接著, 就是尋找乘法AST語法樹的右節(jié)點(diǎn), 仍然是通過 parseExpression() 函數(shù), 傳入的Token則是 詞法單元3, 乘法符號(hào)的優(yōu)先級(jí)為 Precedence.PRODUCT,

  // 乘法符號(hào)的優(yōu)先級(jí)為 Precedence.PRODUCT
  let precedence: Precedence = Precedence.getPrecedence(cur?.type);
  // 讀取詞法單元3
  nextToken();
  infixExpression.right = parseExpression(precedence);
  

  

• 在這次乘法符號(hào)尋找右節(jié)點(diǎn)的 parseExpression() 中, 首先構(gòu)建了 前置節(jié)點(diǎn)3, 由于看到下一個(gè)節(jié)點(diǎn)是 結(jié)束詞法單元EOF, 所以不進(jìn)入循環(huán), 直接返回 前置節(jié)點(diǎn)3.

  func parseExpression(_ precedence: Precedence) -> Expression? {let funcName: String?  = prefixParseFnHashMap[cur?.type ?? TokenType.None];if (funcName == nil) {print("未找到AST節(jié)點(diǎn)構(gòu)建函數(shù)名稱")return nil}// 構(gòu)建 前置節(jié)點(diǎn)3var leftExpression: Expression? = getPrefixExpression(funcName);// peekToken == EOF 不滿足while循環(huán)條件while (!peekTokenIs(TokenType.EOF) && precedence.rawValue < peekPrecedence()?.rawValue ?? 0) {let infixParseFnName: String?  = infixParseFnHashMap[peek?.type ?? TokenType.None];if (infixParseFnName == nil) {print("未找到AST節(jié)點(diǎn)構(gòu)建函數(shù)名稱")return leftExpression;}nextToken();leftExpression = parseInfixExpression(leftExpression);}// 返回 前置節(jié)點(diǎn)3return leftExpression
  }
  

  

• 這時(shí)候也就構(gòu)建完成了乘法的AST語法樹部分了. 我們一起看一下整體的乘法符號(hào)的AST語法樹構(gòu)建過程.

  

• 由于已經(jīng)遍歷到了最后(遇到了EOF), 緊接著就跳出了 加法符號(hào)尋找右節(jié)點(diǎn)的parseExpression()過程中的while循環(huán). 并把 乘法符號(hào)的AST語法樹作為 加法符號(hào)的右節(jié)點(diǎn)進(jìn)行了添加.

  // 這里是加法符號(hào)尋找右節(jié)點(diǎn)的遞歸方法
  // 當(dāng)前優(yōu)先級(jí)是 Precedence.SUM, 當(dāng)前Token是 2
  func parseExpression(_ precedence: Precedence) -> Expression? {let funcName: String?  = prefixParseFnHashMap[cur?.type ?? TokenType.None];if (funcName == nil) {print("未找到AST節(jié)點(diǎn)構(gòu)建函數(shù)名稱")return nil}// 構(gòu)建左節(jié)點(diǎn) 前置節(jié)點(diǎn)2var leftExpression: Expression? = getPrefixExpression(funcName);// 乘法符號(hào)的優(yōu)先級(jí)比當(dāng)前加號(hào)優(yōu)先級(jí)高, 正常進(jìn)入while循環(huán)while (!peekTokenIs(TokenType.EOF) && precedence.rawValue < peekPrecedence()?.rawValue ?? 0) {let infixParseFnName: String?  = infixParseFnHashMap[peek?.type ?? TokenType.None];if (infixParseFnName == nil) {print("未找到AST節(jié)點(diǎn)構(gòu)建函數(shù)名稱")return leftExpression;}// 讀取下一個(gè)詞法單元 乘法符號(hào)*nextToken();// 生成乘法符號(hào)的中置節(jié)點(diǎn)并且更新leftExpressionleftExpression = parseInfixExpression(leftExpression);}// 最終 leftExpression 是乘法符號(hào)的AST語法樹//   *//  ╱ ╲// 2   3return leftExpression
  }
  

  上述代碼就是下圖中 紅色的parseExpression()的內(nèi)部過程.

  

• 最后返回初始那一層 由 parseMain() 進(jìn)入的 parseExpression() 過程, 也是已經(jīng)遍歷到了最后(遇到了EOF), 跳出循環(huán), 返回最終的AST語法樹.

  // 這里是由 `parseMain()` 進(jìn)入的 `parseExpression()`
  func parseExpression(_ precedence: Precedence) -> Expression? {let funcName: String?  = prefixParseFnHashMap[cur?.type ?? TokenType.None];if (funcName == nil) {print("未找到AST節(jié)點(diǎn)構(gòu)建函數(shù)名稱")return nil}// 構(gòu)建左節(jié)點(diǎn) 前置節(jié)點(diǎn)1var leftExpression: Expression? = getPrefixExpression(funcName);// 構(gòu)建了加法的AST語法樹之后, 就退出了循環(huán)while (!peekTokenIs(TokenType.EOF) && precedence.rawValue < peekPrecedence()?.rawValue ?? 0) {let infixParseFnName: String?  = infixParseFnHashMap[peek?.type ?? TokenType.None];if (infixParseFnName == nil) {print("未找到AST節(jié)點(diǎn)構(gòu)建函數(shù)名稱")return leftExpression;}nextToken();leftExpression = parseInfixExpression(leftExpression);}// 最終 leftExpression 是加法符號(hào)的AST語法樹//   +//  ╱ ╲// 1   *//    ╱ ╲//   2   3return leftExpression
  }
  

  

• 這樣我們對(duì)于數(shù)學(xué)表達(dá)式的 1 + 2 * 3 的 AST語法樹構(gòu)建過程就有整體的了解,最終輸出的AST語法樹如下所示.

  

中間代碼生成與驗(yàn)證

---

對(duì)于上面的 1 + 4 - 3 和 1 + 2 * 3 的兩個(gè)示例, 我們對(duì)PrattParser構(gòu)建AST語法樹的過程有了大體的了解.

接下來就是中間代碼生成過程(其實(shí)不太準(zhǔn)確, 大體模擬吧~), 我們會(huì)直接輸入一個(gè)結(jié)果對(duì)象(MInt), 模擬中間代碼的生成.

中間代碼生成是由 Evaluator 來實(shí)現(xiàn)的, 其主要作用就是解析AST語法樹, 生成中間代碼結(jié)果對(duì)象(MInt). 這部分也是很簡單, 主要是通過 eval() 函數(shù)來遞歸解析AST語法樹, 然后通過 op() 函數(shù)進(jìn)行各種數(shù)學(xué)計(jì)算. 整體的計(jì)算也是由遞歸完成的.

• eval() 函數(shù)中 主要有三個(gè)邏輯分支, 一個(gè)是數(shù)字的前置節(jié)點(diǎn) 一個(gè)是符號(hào)的前置節(jié)點(diǎn), 最后一個(gè)是中置節(jié)點(diǎn). 數(shù)字的前置節(jié)點(diǎn) 和 中置節(jié)點(diǎn) 沒有什么好說的, 符號(hào)的前置節(jié)點(diǎn) 主要應(yīng)對(duì)于第一個(gè)前置節(jié)點(diǎn)帶符號(hào)的情況例如 -1 和 +349 等等.

  public static func eval(_ node: Node?) -> MObj? {if let nodeValue = node as? IntegerExpression {// 純數(shù)字節(jié)點(diǎn)邏輯return MInt(nodeValue.value)} else if let nodeValue = node as? PrefixExpression {// 帶符號(hào)的數(shù)字節(jié)點(diǎn)邏輯if (nodeValue.operatorValue == "-") {return minus(node);} else if (nodeValue.operatorValue == "+") {return eval(nodeValue.right);}} else if let nodeValue = node as? InfixExpression {// 中置節(jié)點(diǎn)邏輯let left = eval(nodeValue.left);let right = eval(nodeValue.right);return op(left, right, nodeValue.operatorValue);}return nil;
  }
  

• op() 就是根據(jù)符號(hào)進(jìn)行不同的數(shù)學(xué)運(yùn)算, 整體邏輯比較簡單, 這里就不過多敘述了.

  public static func op(_ left: MObj?, _ right: MObj?, _ operatorValue: String?) -> MObj? {if let leftValue = left as? MInt,let rightValue = right as? MInt {switch(operatorValue) {case "+" :return MInt(leftValue.number + rightValue.number)case "-" :return MInt(leftValue.number - rightValue.number)case "*" :return MInt(leftValue.number * rightValue.number)case "/" :return MInt(leftValue.number / rightValue.number)case "^" :return MInt(pow(leftValue.number, rightValue.number))default:return nil;}}return nil;
  }
  

• minus() 函數(shù)主要是用來處理帶符號(hào)的前置節(jié)點(diǎn)情況. 整體邏輯也比較簡單, 這里就不過多敘述了.

  public static func minus(_ node: Node?) -> MObj? {if let nodeValue = node as? PrefixExpression {let m : MObj? = eval(nodeValue.right);if let mValue = m as? MInt {if (nodeValue.operatorValue == "-") {mValue.number = -mValue.number}return mValue;}}return nil;
  }
  

最后, 我們就能看到最終的輸出結(jié)果.

var code = "1+2*3"var lexer: Lexer! = Lexer(code: code)var parser: Parser! = Parser(lexer)var expression: Expression? = parser.parseMain()if let intObj = Evaluator.eval(expression) as? MInt {print(intObj.toString())
}

總結(jié)

---

通過這篇博客詳細(xì)大家對(duì) PrattParser解析器的前端工作有個(gè)大體的了解了. 希望看這篇博客是可以一邊斷點(diǎn)項(xiàng)目, 一邊查看, 主要是遞歸過程比較繞, 希望有耐心看完.

點(diǎn)擊查看 基于Swift的PrattParser項(xiàng)目