原文地址：https://lisperator.net/pltut/

解析器的作用

解析器在分詞器之上，直接操作 token 流，不用處理單個字符，把代碼解析成一個個對象

lambda 解析器

解析標記流的過程中，當遇到 lambda 關鍵字則會調用parse_lambda函數

fib = lambda (n) if n < 2 then n else fib(n - 1) + fib(n - 2); function parse_lambda() {return {type: 'lambda',vars: delimited('(', ')', ',', parse_varname),body: parse_expression(),}; }

delimited 函數：獲取形參列表

// parser 是一個 function，負責解析 start 和 stop 之間的 token function delimited(start, stop, separator, parser) {var a = [],first = true;// skip_punc(token)：當前 token 是否是給定的符號，若是，將其從輸入流中丟棄并繼續，否則拋出異常skip_punc(start);while (!input.eof()) {// is_punc(token)：若當前 token 是給定的符號，返回 true（不消耗掉當前 token）if (is_punc(stop)) break;// first 標識當前 token 是否是第一個// 因為參數的格式是這樣的(arg1, arg2, arg3...)// 除去第一個參數之外，每次讀一個新參數之前都要先把","給讀走if (first) first = false;else skip_punc(separator);// 沒有和之前的重復// 加上這個的原因是防止(arg1, arg2, arg3,)的情況，多了一個逗號// while 開頭的 is_punc(stop) 就攔截不下來了，而是繼續掠過","讀下一個參數，當然這個時候是讀到是")"，出問題了if (is_punc(stop)) break;// 解析出參數名a.push(parser());}skip_punc(stop);return a; }

parse_expression 函數：解析表達式

盡可能地向右擴展一個表達式

function parse_expression() {return maybe_call(function () {return maybe_binary(parse_atom(), 0);}); }

有兩種可能性：

表達式為 f(a); 類型，調用函數

表達式為 c = a + b; 類型，就是普通的表達式

maybe_call 函數：如果是后面是調用函數，就拿一個 call 類型的對象把它包裹起來；如果不是就直接返回表達式本身

function maybe_call(expr) {// expr 是 maybe_binary() 的返回值expr = expr();// 如果在那個疑似二元表達式之后，有一個 "(" 那就是說明調用函數型表達式，交給 parse_call(expr) 處理// 如果不是，說明是普通表達式，直接返回就好了// 例：f(a);// expr 傳進去的是 function() { f }// f 后面跟著一個 (，所以是調用函數型表達式return is_punc("(") ? parse_call(expr) : expr; } ? // 處理調用函數型表達式：用一個 call 類型的對象包起來 function parse_call(func) {return {type: "call",func: func,args: delimited("(", ")", ",", parse_expression)}; }

maybe_binary：如果后面跟的是一個二元表達式，那就用一個結點（可能是 binary 類型，也可能是 assign 類型）包裹住它；如果不是就直接返回

談到二元表達式就避不開操作符優先級的話題，這個用一個 PRECEDENCE 對象解決

// 定義操作符優先級，越大優先級越高 var PRECEDENCE = {'=': 1,'||': 2,'&&': 3,'<': 7,'>': 7,'<=': 7,'>=': 7,'==': 7,'!=': 7,'+': 10,'-': 10,'*': 20,'/': 20,'%': 20, };

實現思路：

1 + 2 * 3;

初始化：

讀一個原子表達式(1)

取當前運行時的優先級({INIT,0})：my_prec 初始化為 0

調用 maybe_binary(left, my_prec)，左邊的是表達式，右邊的是運行時當前的優先級

maybe_binary 將會解析緊跟著原子表達式的內容：

緊跟的不是運算符，直接原樣返回左參數(1)

是運算符，但優先級低于 my_prec，返回左參數(1)

是運算符且優先級更高({+,10} > {INIT,0})，

將左參數(1)包裹到一個新的二元表達式 “binary” 節點中

遞歸調用 maybe_binary，找出右參數(2…)的具體值：

讀一個原子表達式(2)

取當前運行時的優先級({+,10})

調用 maybe_binary(left, my_prec)，左邊的是表達式，右邊的是運行時當前的優先級

遞歸進去：maybe_binary(2, 10) 將會解析緊跟著原子表達式(2)的內容(*)

緊跟的不是運算符，直接原樣返回左參數(2)

是運算符，但優先級低于 my_prec，返回左參數(2)

是運算符且優先級更高({*,20} > {+,10})，

將左參數包裹到一個新的二元表達式 “binary” 節點中

遞歸調用 maybe_binary，找出右參數(3…)的具體值：

讀一個原子表達式(3)

取當前運行時的優先級({*,20})

調用 maybe_binary(left, my_prec)，左邊的是表達式，右邊的是運行時當前的優先級

遞歸進去：maybe_binary(3, 20) 將會解析緊跟著原子表達式(2)的內容(*)

后面跟的是";"，不是運算符，直接原樣返回左參數(3)

// my_prec 初始化為 0 function maybe_binary(left, my_prec) {var tok = is_op();if (tok) {var his_prec = PRECEDENCE[tok.value];if (his_prec > my_prec) {input.next();var right = maybe_binary(parse_atom(), his_prec);var binary = {type: tok.value == '=' ? 'assign' : 'binary',operator: tok.value,left: left,right: right,};// 為什么上面遞歸過了還要再遞歸一次？直接 return binary 不行嗎？// 原因：以 a * b + c * d 為例：// 第一層調用：a，返回// {// left: a,// right: maybe_binary(b,*)// }// 第二層調用：b，返回 b// 然后就斷了// 返回 maybe_binary(binary, my_prec) 是為了讓這個過程繼續進行下去，以現有被分析好的// {// left: a,// right: b// }// 為左參數，接著向右拓展return maybe_binary(binary, my_prec);}}return left; }

parse_atom：解析原子表達式

parse_atom() 依據當前的 token 進行調度

function parse_atom() {return maybe_call(function(){// 如果解析到了一個"("，則其必定是一個括號表達式 — 因此首先會跳過開括號，然后調用 parse_expression()，然后跳過")"if (is_punc("(")) {input.next();var exp = parse_expression();skip_punc(")");return exp;}?// 如果解析到了某個關鍵字，則會調用對應關鍵字的解析函數if (is_punc("{")) return parse_prog();// is_kw 和 is_punc 是一樣的，只是一個是針對字符串一個是針對字符，若當前 token 是給定的符號，返回 true（不消耗掉當前 token）if (is_kw("if")) return parse_if();if (is_kw("true") || is_kw("false")) return parse_bool();if (is_kw("lambda") || is_kw("λ")) {input.next();return parse_lambda();}// 如果解析到了一個常量或者標識符，則會原樣返回 tokenvar tok = input.next();if (tok.type == "var" || tok.type == "num" || tok.type == "str")return tok;// 如果所有情況都未滿足，則會調用 unexpected() 拋出一個錯誤。unexpected();}); }

parse_prog：解析語句序列

當期望是一個原子表達式但解析到 { 的情況，調用 parse_prog 來解析整個序列的表達式，這里有一個優化，如果只有一個表達式就直接返回那個表達式，不再套一層了

var FALSE = { type: 'bool', value: false };function parse_prog() {var prog = delimited('{', '}', ';', parse_expression);// 如果 prog 節點為空，則直接返回 FALSEif (prog.length == 0) return FALSE;// 如果程序只包含一個表達式，則返回表達式的解析結果if (prog.length == 1) return prog[0];// 否則返回一個包含表達式的 "prog" 節點return { type: 'prog', prog: prog }; }

parse_if：解析 if 語句

if a <= b then { # 這里的 then 是可選的print(a);if a + 1 <= b {print(", ");print-range(a + 1, b);} else println(""); # newline }; function parse_if() {// 類似 skip_puncskip_kw('if');// cond 是條件var cond = parse_expression();// 如果條件之后不是直接跟著 "{"，那肯定是跟著 "then" 了if (!is_punc('{')) skip_kw('then');// then 是當條件為 true 是要處理的表達式var then = parse_expression();// 用一個 if 類型的對象把 cond 和 then 包起來var ret = { type: 'if', cond: cond, then: then };// 如果有 else 的話把 else 也包起來if (is_kw('else')) {input.next();ret.else = parse_expression();}return ret; }

---

以上這些函數似乎在互相調用：

parse_atom() 函數基于當前的 token 來調用其它函數，如 parse_if()

parse_if()調用 parse_expression()

parse_expression()會再次調用 parse_atom()

之所以沒有發生死循環，是因為每步處理中，每個函數都會至少消費掉一個 token。

上述類型的解析器叫做 “遞歸下降解析器”（recursive descent parser），也可能算是可以手寫實現的最簡單類型。

整體程序（prog 節點）解析器

通過不停地調用 parse_expression() 函數來讀取輸入流中的表達式（expression）

function parse_toplevel() {var prog = [];while (!input.eof()) {prog.push(parse_expression());// 表達式以分號分隔，跳過分號再進行下一個expression的解析if (!input.eof()) skip_punc(';');}return { type: 'prog', prog: prog }; }

總結

以上是生活随笔為你收集整理的【编译器实现笔记】2. 解析器（parser）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。