Stanford公開課《編譯原理》學習筆記（2）遞歸下降法

示例代碼托管在：http://www.github.com/dashnowords/blogs

部落格園位址：《大史住在大前端》原創博文目錄

華為雲社群位址：【你要的前端打怪更新指南】

一. Parse階段
- CFG
- Recursive Descent（遞歸下降周遊）
二. 遞歸下降周遊
- 2.1 預備知識
- 2.2 多行語句的處理思路
- 2.3 簡易的文法定義
- 2.4 文法産生式的代碼轉換
- 2.5 逐行解析
- 2.6 檢視計算過程
三.小結

B站位址：【編譯原理】

Stanford公開課：【Stanford大學公開課官網】

課程裡涉及到的内容講的還是很清楚的，但個别地方有點脫節，建議課下自己配合經典著作《Compilers-priciples, Techniques and Tools》(也就是大名鼎鼎的龍書）作為補充閱讀。

詞法分析階段的任務是将字元串轉為

Token

組，而

Parse

階段的目标是将

Token

變為

Parse Tree

，本篇隻是這部分内容最基礎的一部分。

CFG

即

context free grammer

，定義一種

CFG

文法規則需要聲明如下特征：

一組終止符号集，也稱為“詞法單元”
一組非終止符号集，也稱為“文法變量”
一個開始符号集
若幹産生式規則（産生式則就是指在目前 CFG 的文法下，産生符号 -> 左右兩側可以互相替代）

CFG

的基本轉換流程如下：

從隸屬于開始集

開始，嘗試将字元串中的非終止符

替換為終止集的形式(

X->Y1Y2...Yn

)，重複這個步驟直到字元串序列中不再有非終止符。這個過程被稱為

Derivation

(派生)，它是一系列變換過程的序列，可以轉換為樹的形式，樹的根節點即為起始集合

中的成員，轉換後的每個終止集以子節點的形式挂載在根節點下，這棵生成的樹就被稱為Parse Tree,可以看出最後的結果實際上就是

Parse Tree

的葉節點周遊結果。

當需要轉換的非終結字元有多個時，需要按照一定的順序來逐個推導，派生過程可以按照

left-most

或

right-most

進行，但有時會得到不同的合法的轉換樹，通常會通過修改轉換集文法或設定優先級來解決。

Recursive Descent

是一種周遊

parse tree

的政策，是一種典型的遞歸回溯算法，從樹的根節點開始，逐個嘗試目前父節點上記錄的非終止字元能夠支援的産生規則，并判斷其子節點是否符合這樣的形式，直到子節點符合某個特定的産生式規則，然後再繼續遞歸進行深度周遊，如果在某個非終止節點上嘗試完所有的産生式規則都無法繼續向下進行使得子樹的葉節點都符合終止符号集，則需要通過回溯到上一節點并嘗試父節點的下一個産生式規則，使得循環程式可以繼續向後進行。課程裡用了很多的數學符号定義和僞代碼來描述遞歸周遊的過程，如果覺得太抽象不好了解可以暫時略過。需要注意左遞歸文法會使得遞歸下降周遊進入死循環，在文法設計時應該避免，龍書中也提供了一種通用的拆分方法來解決這個問題。

【聲明】由于課程中并沒有看到從 tokens 到 parse tree 的全貌，隻能先逐漸消化基礎知識。下文的過程隻是筆者自己的了解（尤其是逐行分析的形式，因為尚未涉及任何結構性文法，是以通用性還有待考量），僅供參考，也歡迎交流指正。但對于直覺了解遞歸下降法而言是足夠的。

本節中使用

JavaScript

來實作遞歸下降周遊，目标代碼仍是上一篇博文中的示例代碼：

var b3 = 2;
a = 1 + ( b3 + 4);
return a;

經過上一節的分詞器後可以得到下面的詞素序列：

[ 'keywords', 'var' ],
[ 'id', 'b3' ],
[ 'assign', '=' ],
[ 'num', '2' ],
[ 'semicolon', ';' ],
[ 'id', 'a' ],
[ 'assign', '=' ],
[ 'num', '1' ],
[ 'plus', '+' ],
[ 'lparen', '(' ],
[ 'id', 'b3' ],
[ 'plus', '+' ],
[ 'num', '4' ],
[ 'rparen', ')' ],
[ 'semicolon', ';' ],
[ 'keywords', 'return' ],
[ 'id', 'a' ],
[ 'semicolon', ';' ]

文法分析是基于文法規則的，所謂文法規則，通常是指一系列CFG表示的産生式，大多數開發者并不具備設計一套文法規則的能力，此處直接借鑒

Mozilla

中的

Javascript

引擎

SpiderMonkey

中的文法定義來進行基本産生式，由于

Javascript

語言中涉及的文法非常多，本節隻篩選出與目标解析式相關的一部分簡化的文法規則（圖中标記為藍色的部分）：

完整的文法規則可以檢視【SpiderMonkey_ParserAPI】進行了解。

我們把上面的目标解析代碼當做是一段

Javascript

代碼，自頂向下分析時，根節點的類型是

Program

，它可以由多個

Statement

節點（語句節點）構成，是以本例中進行簡化後以

semicolon

（分号）作為詞素批量處理的分界點，每次将兩個分号之間的部分讀入緩沖區進行分析，由于上例中均為單行語句，是以了解起來比較簡單。

在更為複雜的情況中，代碼中包含

條件語句

循環語句

等一些結構化的關鍵詞時可能會存在跨行的語句，此時可以在遞歸下降之前先對緩沖區的詞素隊列進行基本的結構分析，如果發現比對的結構化模式，就從

tokens

序列中将下一行（或多行）也讀入緩沖區，直到緩沖區中的所有

tokens

放在一起符合了某些特定的結構，再開始進行遞歸下降。

為友善了解，本例中均使用關鍵詞縮寫來表示可能的文法規則集，如果你對

Javascript

語言有一定了解，它們是非常容易了解的

/**
 * 文法定義-生産規則
 * Program -> Statement
 * P -> S
 * 
 * 語句 -> 塊狀語句 | if語句 | return語句 | 聲明 | 表達式 |......
 * Statement -> BlockStatement | IfStatement | ReturnStatement | Declaration | Expression |......
 * S -> B | I | R | D | E
 * 
 * B -> { Statement }
 * 
 * I -> if ( ExpressionStatement ) { Statement }
 * 
 * R -> return Expression | null
 * 
 * 聲明 -> 函數聲明 | 變量聲明
 * Declaration -> FunctionDeclaration | VariableDeclaration
 * D -> F | V
 * 
 * F -> function ID ( SequenceExpression ) { ... }
 * 
 * V -> 'var | let | const' ID [= Expression | Null] ?
 * 
 * 表達式 -> 指派表達式 | 序清單達式 | 一進制運算表達式 | 二進制運算表達式 |......
 * Expression -> AssignmentExpression | SequenceExpression | UnaryExpression | BinaryExpression | BracketExpression......
 * E -> A | Seq | U | BI | BRA |...
 * 
 * A -> E = E //指派表達式
 * 
 * Seq -> ID,ID,ID//類似形式
 * 
 * //一進制表達式
 * U -> "-" | "+" | "!" | "~" | "typeof" | "void" | "delete" E
 * 
 * //二進制表達式
 * BI -> E "==" | "!=" | "===" | "!=="
         | "<" | "<=" | ">" | ">="
         | "<<" | ">>" | ">>>"
         | "+" | "-" | "*" | "/" | "%"
         | "|" | "^" | "&" | "in"
         | "instanceof" | ".."  E
 * 
 * //括号表達式
 * BRA -> ( E )
 * 
 * N -> null  
 */

需要額外注意的是表達式

Expression

到指派表達式

AssignmentExpression

的産生式，

的判斷規則裡需要判斷

，而

的邏輯裡又再次調用了

，這裡就是一種左遞歸，如果不進行任何處理，在代碼運作時就會陷入死循環然後爆棧，這也就是前文強調的需要在文法産生式設計時消除左遞歸的場景。這裡并不是說

spiderMonkey

的

parserAPI

是錯的，因為消除左遞歸的文法改造隻是一種等價形式的轉換，是為了防止産生式産生無限遞推（或者說程式實作時進入無限遞歸的死循環）而做的一種形式處理，改造的過程可能隻是引入了某個中間集合來消除這種場景的影響，對于最終的文法表意并不會産生影響。

下文示例代碼中并沒有進行嚴謹的"左遞歸消除"，而是簡單地使用了一個

E_

集合，與原本的

進行一些微小的差異區分，進而避免了死循環。

下面将上一小節的文法規則進行代碼翻譯（隻包含部分産生式的推導，本例中的完整代碼可以從demo或代碼倉中擷取）：

//判斷是否為Statement
function S(tokens) {
    //把結尾的分号全部去除
    while(tokens[tokens.length - 1][0] === TT.semicolon){
        tokens.pop();
    }
    return B(tokens) || I(tokens) || R(tokens) || D(tokens) || E(tokens);
}

//判斷是否為BlockStatement  B -> { Statement } (本例中并不涉及本方法，故暫不考慮末尾分号和文法遞歸的情況)
function B(tokens) {
     //本例中不涉及，直接傳回false
    return false;
}

//判斷是否為IfStatement I -> if ( ExpressionStatement ) { Statement }
function I(tokens) {
    //本例中不涉及，直接傳回false
    return false;
}
//判斷是否為ReturnStatement  R -> return Expression | null
function R(tokens) {
    return isReturn(tokens[0]) && (E(tokens.slice(1)) || N(tokens.slice(1)[0]));
}

//判斷是否為聲明語句 Declaration -> FunctionDeclaration | VariableDeclaration
function D(tokens) {
    return F(tokens) || V(tokens);
}

//判斷是否為函數聲明  F -> function ID ( SequenceExpression ) { ... }
function F(tokens) {
    //本例中不涉及，直接傳回false
    return false;
}

//判斷是否為變量聲明  V -> 'var | let | const' ID [= Expression | Null] ?
function V(tokens) {
    //判斷為1.單純的聲明 還是 2.帶有初始值的聲明
    if (tokens.length === 2) {
        return isVariableDeclarationKeywords(tokens[0]) && tokens[1][0] === TT.id;
    }
    return isVariableDeclarationKeywords(tokens[0]) && (A(tokens.slice(1))) || N(tokens.slice(1));
}

//....其他代碼形式雷同，不再贅述

解析時預設每次遇到一個分号時表示一個

statement

的結束，前文已經提及過對于多行語句的處理思路。實作時隻需要将

tokens

序列一點點讀進buffer數組并從頂層的

方法啟動分析，即可完成自頂向下的推理過程。

/**parser */
function parse(tokens) {
    let buffer = nextStatement(tokens);
    let flag = true;

    while (buffer && flag){

       if (!S(buffer)) {
           console.log('檢測到不符合文法的tokens序列');
           flag = false;
       } 
       buffer = nextStatement(tokens);
    }   
    
    //如果沒有出錯則提示正确
    flag && console.log('檢測結束，被檢測tokens序列是合法的代碼段');
}

//将下一個Statement全部讀入緩沖區
function nextStatement(tokens) {
    let result = [];
    let token;

    while(tokens.length) {
        token = tokens.shift();
        result.push(token);
        //如果不是換行符則
        if (token[0] === CRLF) {
            break;
        }
    }

    return result.length ? result : null;
}

單步執行檢視計算過程可以幫助我們更好地了解遞歸下降法的執行過程：

在demo所在目錄下打開指令行，輸入：

node --inspect-brk recursive-descent.js

，然後單步執行就很容易看出代碼在執行過程中如何實作遞歸和回溯：

單純地遞歸下降法最終的結果隻找出了不滿足任何文法規則的語句，或是最終所有語句都符合文法規則時給出提示，但并沒有得到一個樹結構的對象，也沒有向下一個環節提供輸出，如何在編譯過程中與後續環節進行連接配接還有待探索。

Stanford公開課《編譯原理》學習筆記（2）遞歸下降法

繼續閱讀

編譯器"自舉與移植"原理

什麼是字母表和串---編譯原理

語言的定義——編譯原理

LEX自動生成詞法分析器

lex && yacc

PERL原碼分析2

vs2008中的lex&yacc

分析Perl的Lex和Yacc部分

Perl原碼分析3

Cygwin環境的熟悉和lex的使用1一. 目的：二. 内容：三．要求：四．參考：五．源代碼：六．結果及分析：七.附錄

Android源代碼編譯原理與前期準備

Antlr實作任意四則運算表達式求值

【編譯原理】作業十三編譯原理第13次作業

編譯原理上機實戰---詞法分析

在Windows 10上将C語言程式轉成16位8086彙編代碼

_stdcall與_cdecl的差別 _stdcall與_cdecl的差別