>[success] # 語法分析 ( parsing) ~~~ 1.語法分析器(parser)從詞法分析器輸出的token序列中識別出各類短語，并構造語法 分析樹(parse tree) 2.如圖我們將我們的 tokens 經過語法分析器變成一棵ast 語法樹 ~~~  >[danger] ##### 圖形理解 ~~~ 1.將各個token標記成對應 ast 樹節點 [ { type: 'paren', value: '(' }, { type: 'name', value: 'add' }, { type: 'number', value: '2' }, { type: 'paren', value: '(' }, { type: 'name', value: 'subtract' }, { type: 'number', value: '4' }, { type: 'number', value: '2' }, { type: 'paren', value: ')' }, <<< Closing parenthesis { type: 'paren', value: ')' }, <<< Closing parenthesis ] 2.然后根據類型轉變生成對應ast 樹節點，舉個例子type:number 轉換對應ast 樹節點，類型應為 'NumberLiteral' { type: 'NumberLiteral', value: token.value, } 想變成這樣形式需要循環每一個token 詞，代碼對照情況 if (token.type === "number") { current++; return { type: "NumberLiteral", value: token.value, }; } 當遇到括號時候其實就會形成遞歸 括號作為'CallExpression' 節點這個節點下又包括新的'NumericLiteral' ~~~ * 代碼如下 ~~~ // 語法分析器 參數：詞法單元數組tokens function parser(tokens) { let current = 0; // 設置當前解析的詞法單元的索引，作為游標 // 遞歸遍歷（因為函數調用允許嵌套），將詞法單元轉成 LISP 的 AST 節點 function walk() { // 獲取當前索引下的詞法單元 token let token = tokens[current]; // 數值類型詞法單元 if (token.type === 'number') { current++; // 自增當前 current 值 // 生成一個 AST節點 'NumberLiteral'，表示數值字面量 return { type: 'NumberLiteral', value: token.value, }; } // 字符串類型詞法單元 if (token.type === 'string') { current++; // 生成一個 AST節點 'StringLiteral'，表示字符串字面量 return { type: 'StringLiteral', value: token.value, }; } // 函數類型詞法單元 if (token.type === 'paren' && token.value === '(') { // 跳過左括號，獲取下一個詞法單元作為函數名 token = tokens[++current]; let node = { type: 'CallExpression', name: token.value, params: [] }; // 再次自增 current 變量，獲取參數詞法單元 token = tokens[++current]; // 遍歷每個詞法單元，獲取函數參數，直到出現右括號"）" while ((token.type !== 'paren') || (token.type === 'paren' && token.value !== ')')) { node.params.push(walk()); token = tokens[current]; } current++; // 跳過右括號 return node; } // 無法識別的字符，拋出錯誤提示 throw new TypeError(token.type); } // 初始化 AST 根節點 let ast = { type: 'Program', body: [], }; // 循環填充 ast.body while (current < tokens.length) { ast.body.push(walk()); } // 最后返回ast return ast; } ~~~  [圖片來自](https://juejin.cn/post/6844904105937207304#heading-12) >[danger] ##### 以babel 生成ast語法樹 簡化了展示 ~~~ // const a = 1 const a = { program: { type: "Program", body: [ { type: "VariableDeclaration", declarations: [ { type: "VariableDeclarator", id: { type: "Identifier", name: "a", }, init: { type: "NumericLiteral", value: 1, }, }, ], kind: "const", }, ], }, }; // a=1 const b = { program: { type: "Program", body: [ { type: "ExpressionStatement", expression: { type: "AssignmentExpression", operator: "=", left: { type: "Identifier", name: "a", }, right: { type: "NumericLiteral", value: 1, }, }, }, ], }, }; /** * function a(str){ const z = str console.log(z) } * */ const c = { program: { type: "Program", body: [ { type: "FunctionDeclaration", id: { type: "Identifier", name: "a", }, generator: false, async: false, params: [ { type: "Identifier", name: "str", }, ], body: { type: "BlockStatement", body: [ { type: "VariableDeclaration", declarations: [ { type: "VariableDeclarator", id: { type: "Identifier", name: "z", }, init: { type: "Identifier", name: "str", }, }, ], kind: "const", }, { type: "ExpressionStatement", expression: { type: "CallExpression", callee: { type: "MemberExpression", object: { type: "Identifier", name: "console", }, computed: false, property: { type: "Identifier", name: "log", }, }, arguments: [ { type: "Identifier", name: "z", }, ], }, }, ], }, }, ], }, }; ~~~ >[danger] ##### 代碼 [直接用了 Babel是如何讀懂JS代碼的中的代碼](https://zhuanlan.zhihu.com/p/27289600) ~~~js function parse (tokens) { let i = -1; // 用于標識當前遍歷位置 let curToken; // 用于記錄當前符號 // 讀取下一個語句 function nextStatement () { // 暫存當前的i，如果無法找到符合條件的情況會需要回到這里 stash(); // 讀取下一個符號 nextToken(); if (curToken.type === 'identifier' && curToken.value === 'if') { // 解析 if 語句 const statement = { type: 'IfStatement', }; // if 后面必須緊跟著 ( nextToken(); if (curToken.type !== 'parens' || curToken.value !== '(') { throw new Error('Expected ( after if'); } // 后續的一個表達式是 if 的判斷條件 statement.test = nextExpression(); // 判斷條件之后必須是 ) nextToken(); if (curToken.type !== 'parens' || curToken.value !== ')') { throw new Error('Expected ) after if test expression'); } // 下一個語句是 if 成立時執行的語句 statement.consequent = nextStatement(); // 如果下一個符號是 else 就說明還存在 if 不成立時的邏輯 if (curToken === 'identifier' && curToken.value === 'else') { statement.alternative = nextStatement(); } else { statement.alternative = null; } commit(); return statement; } if (curToken.type === 'brace' && curToken.value === '{') { // 以 { 開頭表示是個代碼塊，我們暫不考慮JSON語法的存在 const statement = { type: 'BlockStatement', body: [], }; while (i < tokens.length) { // 檢查下一個符號是不是 } stash(); nextToken(); if (curToken.type === 'brace' && curToken.value === '}') { // } 表示代碼塊的結尾 commit(); break; } // 還原到原來的位置，并將解析的下一個語句加到body rewind(); statement.body.push(nextStatement()); } // 代碼塊語句解析完畢，返回結果 commit(); return statement; } // 沒有找到特別的語句標志，回到語句開頭 rewind(); // 嘗試解析單表達式語句 const statement = { type: 'ExpressionStatement', expression: nextExpression(), }; if (statement.expression) { nextToken(); if (curToken.type !== 'EOF' && curToken.type !== 'sep') { throw new Error('Missing ; at end of expression'); } return statement; } } // 讀取下一個表達式 function nextExpression () { nextToken(); if (curToken.type === 'identifier') { const identifier = { type: 'Identifier', name: curToken.value, }; stash(); nextToken(); if (curToken.type === 'parens' && curToken.value === '(') { // 如果一個標識符后面緊跟著 ( ，說明是個函數調用表達式 const expr = { type: 'CallExpression', caller: identifier, arguments: [], }; stash(); nextToken(); if (curToken.type === 'parens' && curToken.value === ')') { // 如果下一個符合直接就是 ) ，說明沒有參數 commit(); } else { // 讀取函數調用參數 rewind(); while (i < tokens.length) { // 將下一個表達式加到arguments當中 expr.arguments.push(nextExpression()); nextToken(); // 遇到 ) 結束 if (curToken.type === 'parens' && curToken.value === ')') { break; } // 參數間必須以 , 相間隔 if (curToken.type !== 'comma' && curToken.value !== ',') { throw new Error('Expected , between arguments'); } } } commit(); return expr; } rewind(); return identifier; } if (curToken.type === 'number' || curToken.type === 'string') { // 數字或字符串，說明此處是個常量表達式 const literal = { type: 'Literal', value: eval(curToken.value), }; // 但如果下一個符號是運算符，那么這就是個雙元運算表達式 // 此處暫不考慮多個運算銜接，或者有變量存在 stash(); nextToken(); if (curToken.type === 'operator') { commit(); return { type: 'BinaryExpression', left: literal, right: nextExpression(), }; } rewind(); return literal; } if (curToken.type !== 'EOF') { throw new Error('Unexpected token ' + curToken.value); } } // 往后移動讀取指針，自動跳過空白 function nextToken () { do { i++; curToken = tokens[i] || { type: 'EOF' }; } while (curToken.type === 'whitespace'); } // 位置暫存棧，用于支持很多時候需要返回到某個之前的位置 const stashStack = []; function stash (cb) { // 暫存當前位置 stashStack.push(i); } function rewind () { // 解析失敗，回到上一個暫存的位置 i = stashStack.pop(); curToken = tokens[i]; } function commit () { // 解析成功，不需要再返回 stashStack.pop(); } const ast = { type: 'Program', body: [], }; // 逐條解析頂層語句 while (i < tokens.length) { const statement = nextStatement(); if (!statement) { break; } ast.body.push(statement); } return ast; } const ast = parse([ { type: "whitespace", value: "\n" }, { type: "identifier", value: "if" }, { type: "whitespace", value: " " }, { type: "parens", value: "(" }, { type: "number", value: "1" }, { type: "whitespace", value: " " }, { type: "operator", value: ">" }, { type: "whitespace", value: " " }, { type: "number", value: "0" }, { type: "parens", value: ")" }, { type: "whitespace", value: " " }, { type: "brace", value: "{" }, { type: "whitespace", value: "\n " }, { type: "identifier", value: "alert" }, { type: "parens", value: "(" }, { type: "string", value: "\"if 1 > 0\"" }, { type: "parens", value: ")" }, { type: "sep", value: ";" }, { type: "whitespace", value: "\n" }, { type: "brace", value: "}" }, { type: "whitespace", value: "\n" }, ]); ~~~ 最終得到結果： ~~~js { "type": "Program", "body": [ { "type": "IfStatement", "test": { "type": "BinaryExpression", "left": { "type": "Literal", "value": 1 }, "right": { "type": "Literal", "value": 0 } }, "consequent": { "type": "BlockStatement", "body": [ { "type": "ExpressionStatement", "expression": { "type": "CallExpression", "caller": { "type": "Identifier", "value": "alert" }, "arguments": [ { "type": "Literal", "value": "if 1 > 0" } ] } } ] }, "alternative": null } ] } ~~~ >[info] ## 參考文章 [Building a Debugger: Code Analysis](https://www.nan.fyi/debugger) https://github1s.com/narendrasss/compiler/blob/main/src/parser.ts#L61 [Babel是如何讀懂JS代碼的](https://zhuanlan.zhihu.com/p/27289600) [語法上用解析樹生根](https://medium.com/basecs/grammatically-rooting-oneself-with-parse-trees-ec9daeda7dad) [# 【圖文詳解】200行JS代碼，帶你實現代碼編譯器（人人都能學會）](https://juejin.cn/post/6844904105937207304#heading-12) https://github.com/YongzeYao/the-super-tiny-compiler-CN/blob/master/the-super-tiny-compiler.js