{{ $root.errMsg }}

【深入淺出教你寫編譯器(Compiler)】三、語法分析器(Parser)﹣語法分析(Syntactic analysis)(上)

(已刪除)

(已關閉)

(已標記為濫發)

(已保護)


      現在我們有了 Scanner 幫我們把字元合併成 Token了,那下一步要做什麼呢?就是要把 Token 組合成有意思的“句子”了,這一步我們稱為語法分析(Syntactic analysis),而負責做這項工作的程式我們稱之為語法分析器(Parser)。

 

Parse tree

Parser 要做的工作就是,讀取 Scanner 分析出來的 Token,然後建立並返回一棵 Parse tree 給後面做語意分析(下一章再談談)。什麼是 Parse tree 呢?維基上的解釋是:

  • An ordered, rooted tree that represents the syntactic structure of a string according to some formal grammar.

意思就是一棵可以形容到你寫的句子的樹了,例如你的句子是 if a then b else c,那你的樹就可能會是這樣了:

 

  • 問:為什麼不用一些現成的工具來自動生成 Parser 呢?
  • 答:其實市面上有一些很好的工具可以根據大家寫下的規則來生成 Scanner 及 Parser,例如 ANTLR,Flex(生成 Scanner) 及 Bison(生成 Parser),不用它們的原因有三:第一、用了它們的話西杰就沒工作嚕。第二、它們大部份的 documentation 做得很差,而且網上缺乏教學,要學習的話要花很多時間,然而比起自己寫 Scanner 及 Parser 又快不了多少。第三,自己寫的通常會更加 user-friendly,可以輸出更多種錯誤訊息給開發人員 debug。

 

Top-down parser

 

      我們可以根據 Parser 建立 Parse tree 的方法來分類,一種是 Top-down parsing,另一種是 Bottom-up parsing。Top-down parsing 的意思就是先由 root 開始,一步一步地把 descendant 加到 root 之下, Bottom-up parsing 就是剛好相反,由 leaf 開始建立到 root。

      我們這裏會做的是 Recursive descent parser,是其中一種 Top-down parser,它是由多個 mutually recursive functions 組成的,什麼是 mutually recursive functions?即是各個 function 都可能會互相利用來做 recursion,看看代碼你就會大概知道是什麼意思了。

<Retrieved from Wikipedia.com>

 

      除此之外,我們的 Recursive descent parser 還會使用 lookahead 的技巧,lookahead 在我們 Parser 裏的意思就是多看一個 Token 再決定走向,類似我們之前做 Scanner 時的 nextChar-retract 技巧。

      廢話說完了,正式開始寫 code,第一步我們要為我們的 Parser 建立讀取 Token 的 function 以及 lookahead 的 function。

//Parser class
 
function Parser(scanner){
    this.scanner = scanner;
    this.currentToken = new Token();
    this.lookaheadToken = new Token();
    this.lookaheadToken.consumed = true;
}
 
Parser.prototype.nextToken = function (){
    if (this.lookaheadToken.consumed){
        var token = this.scanner.nextToken();
 
        //skip comments
        while (token == Token.tokens.LINECOMMENT_TOKEN || token == Token.tokens.BLOCKCOMMENT_TOKEN){
            token = this.scanner.nextToken();
        }
 
        this.currentToken.type = token;
        this.currentToken.text = this.scanner.currentToken.text;
 
        return token;
    }else{
        this.currentToken.type = this.lookaheadToken.type;
        this.currentToken.text = this.lookaheadToken.text;
        this.lookaheadToken.consumed = true;
        return this.currentToken.type;
    }
}
 
Parser.prototype.lookahead = function (){
    if (this.lookaheadToken.consumed){
        var token = this.scanner.nextToken();
 
        //skip comments
        while (token == Token.tokens.LINECOMMENT_TOKEN || token == Token.tokens.BLOCKCOMMENT_TOKEN){
            token = this.scanner.nextToken();
        }
 
        this.lookaheadToken.type = token;
        this.lookaheadToken.text = this.scanner.currentToken.text;
        this.lookaheadToken.consumed = false;
 
        return token;
    }else{
        return this.lookaheadToken.type;
    }
}

      nextToken() 要處理的事情有兩項,第一是看看 lookahead 的 Token 被使用了沒有,使用了的話就由 Scanner 再讀取下一個 Token,否則只需使用 lookahead 的 Token。第二是忽略所有 comment,當然如果在你的語言中 comment 是有特別作用的話(如 PHP 中有些 library 會用 comment 來做 Annotation)你也可以保留。

      lookahead() 的作用就是 lookahead 嚕,不過如果已經有一個 lookahead 了的 Token 就不要再讀下一個了(直至它被使用了),一般來說能夠 lookahead 一個 Token 已經足夠,如不足夠的話,大概是因為你設計的語言很複雜……

 

     現在寫一個 Tester 程式來試試這些功能吧:

var dataToBeCompiled = $("#wescript").text();
var reader = new Reader(dataToBeCompiled);
var scanner = new Scanner(reader);
var parser = new Parser(scanner);
while (true){
    if (parser.lookahead() == Token.tokens.PLUSPLUS_TOKEN){
        log("lookahead: PLUSPLUS_TOKEN");
    }
 
    if (parser.lookahead() == Token.tokens.PLUSPLUS_TOKEN){
        log("lookahead again: PLUSPLUS_TOKEN");
    }
 
    var token = parser.nextToken();
    log("Token: " + Token.backwardMap[token]);
 
    if (token == Token.tokens.EOS_TOKEN){
        break;
    }
}

      如果 lookahead 遇到 ++ 的話就會輸出兩次 “lookahead: …” 那句,這可以用來試試是否只能 lookahead 一個 Token,亦可以試試 nextToken() 是否能先讀取 lookahead Token 然後才讀下一個 Token,再者也要試試是否真的忽略了 comment。

 

      測試成功之後可以開始讀 Wescript 的 syntax 了,首先我們要準備一個入口給人調用這個 Parser。

//to parse a list of expressions
Parser.prototype.parseExpressions = function (expressionBlockNode){
    while (this.lookahead() != Token.tokens.RIGHTBRACE_TOKEN &&
            this.lookahead() != Token.tokens.EOS_TOKEN){
 
        var expressionNode = this.parseExpression();
 
        if (expressionNode){
            expressionBlockNode.push(expressionNode);
        }
    }
}

      就是一直 lookahead,如果未遇到 “}” RIGHTBRACE_TOKEN 或者未到結尾的話就一直 parseExpression 下去。

 

  • 問:為什麼是用 lookahead 而不是用 nextChar 呢?
  • 答:因為 parseExpressions 不能夠亦不應該“吃”掉屬於 expression 的 Token(而不是屬於 expressions 的),不然當你 parseExpression 的時候那句 expression 就會少了一個 Token。

 

//to parse an expression
Parser.prototype.parseExpression = function (){
    switch (this.lookahead()){
        case Token.tokens.PRINT_TOKEN:
            var printToken = this.nextToken();
            var expressionNode = this.parseExpression();
            return new PrintNode(expressionNode);
        break;
 
        case Token.tokens.INTLITERAL_TOKEN:
            var intToken = this.nextToken();
            return new IntNode(this.currentToken.text);
        break;
 
        default:
            //unexpected, consume it
            this.nextToken();
    }
}

      parseExpression 做什麼呢?暫時只處理兩種 expression,一種是 “print”,一種是數字,當我們遇到 PRINT_TOKEN 或者 INTLITERAL_TOKEN 時就會建立並返回相應的 Node,如果是 PRINT_TOKEN 的話更會再 parseExpression 一下,因為 print 後面是要配上一個 expression 才可以的嘛(看到嗎?這就是 syntactic level 的規則了)。現在修改一下 Tester 程式再試試運行一下吧,今次會用 console.log() 來查看一下建立出來的樹是否正確:

root 就是 ExpressionBlockNode 了,下面是由 N(這裏是 2)句 expression 組成,其中一句就是 print 了,所以建立了 PrintNode。

 

錯誤匯報

     注意到 expressions[1] 那個 PrintNode 的 expressionNode 是 undefined 嗎?因為那句 Wescript 是 print;,所以分析不到下一句 expression 了,如果我想 print 後面一定要有 expression 的話,那這個情況就算是 syntax error 了,我們可以怎樣告訴開發人員這個錯誤呢?那就要修改一下 PRINT_TOKEN 那個 case 了。

case Token.tokens.PRINT_TOKEN:
    var printToken = this.nextToken();
    var expressionNode = this.parseExpression();
    if (expressionNode == undefined){
        Errors.push({
            type: Errors.SYNTAX_ERROR,
            msg: "Missing an expression after \"print\"",
            line: this.scanner.currLine
        });
    }
    return new PrintNode(expressionNode);
break;

加多一個 if 去驗証一下 expressionNode 是不是一個正常的 Node,不是的話就匯報錯誤。再看一看運行結果。

  • “Line 3: (Syntax error) Missing an expression after "print"“
  • !!!!!!!錯誤訊息出來了!!!!!!!

 

這一節就到此為止,大家先理清以上數個概念吧,下一節會再教大家寫一些更複雜的 expression。

 

<再續>...

compiler   scanner   expressionnode   parser   syntactic analysis  


{{ ctrl.votes | shortNumber: 0 }}
寫於 {{ '2017-07-28T08:33:58.826Z' | calendarTime }}

{{ $root.errMsg }}