Stanford公开课《编译原理》学习笔记（2）递归下降法

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', ';' ]

/**
 * 文法定义-生产规则
 * 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  
 */

//判断是否为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));
}

//....其他代码形式雷同，不再赘述

 /**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;
}