语法分析

语法分析

说实话,上课我能听懂,但是,看到作业题目的我是懵逼的,到底想让我们干什么?

在阅读学长代码的时候,我仿佛又明白了想让我们干什么,就是输出而已,可是这和上课讲的符号表、语法树有什么关系呢,为啥学长代码里有符号表和语法树的部分?

后来我才知道,因为是“增量开发”,我们要先写一个大型的字符串处理器来做语法分析,然后再慢慢加上符号表等。

如何入手

先看一段代码:

// <Decl>::= <ConstDecl> | <VarDecl>
// <ConstDecl>::= 'const' 'int' <ConstDef> {, <ConstDef>}
// <VarDecl>::= 'int' <VarDef> { ',' <VarDef> } ';'
// promise: already read a token
void Parser::Decl() {
    if (type_code_ == TypeCode::CONSTTK) {
        ConstDecl();
    } else if (type_code_ == TypeCode::INTTK) {
        VarDecl();
    } else {
        handle_error("expect a const or int head of <Decl>");
    }
    output("<Decl>");
}

首先保证,当进入Decl分析时,已经读取了一个token,接下来,若这个token的类别码为const时,就进入ConstDecl分析,
若为int,就进入VarDecl分析。

分析完之后,再输出<Decl>。这就是为什么样例的最后会输出非终结符。

那么我们要做的事就明确了——为每一个非终结符写一个分析函数,在函数的结尾输出这个非终结符。

根据文法,粗粗一算,大概要写20~30个函数。

接下来,我们具体讲一讲怎么写这个递归下降的字符串处理器。

明确非终结符

为了写函数,我们得明确文法中有哪些非终结符。

我的方法是,画一棵树,这棵树表明了非终结符之间的依赖关系,而树上有所有要输出的非终结符号。

为了不遗漏地将非终结符的分析函数写出来,我们要遍历自己画的这棵树。

我画的树如下:

语法分析

各种文法情况

首先,我们约定,进入一个非终结符函数时,已经帮这个非终结符读取了一个token;

而从非终结符出来时,没有再预读。

分支处理

下面是一个典型的分支处理的例子,面对如此多的分支,进行判断,然后进入相应的非终结符处理函数。

// Stmt-> 'if' '(' Cond ')' Stmt [ 'else' Stmt ] |
//        'while' '(' Cond ')' Stmt |
//        'return' [Exp] ';' |
//        'printf''('FormatString{,Exp}')'';'

void Parser::Stmt() {
    if (type_code_ == TypeCode::IFTK) {
        IfStmt();
    } else if (type_code_ == TypeCode::WHILETK) {
        WhileStmt();
    } else if (type_code_ == TypeCode::RETURNTK) {
        ReturnStmt();
    } else if (type_code_ == TypeCode::PRINTFTK) {
        WriteStmt();
    } else {
        handle_error("expect ';' end of <Stmt>");
    }
    output("<Stmt>");
}

当然,进入分支可能需要更多的预读。比如变量定义、函数定义和主函数定义,在读取到int时,还不能判断该进入哪个分支,
这时就需要再读取。

// 一个需要更多预读的文法例子:
int a ( )
int a, b;
int main ( )

多次预读取可以帮助我们确定要进入哪个分支,但是会带来一个问题,就是进入前,读了不只一个token。

这时,我们可以引入retract()函数,将读取到的token放回去。

这个操作可以通过建立token读取列表实现:retract()时,读取序列的index回退,next_sym()时,index前进。

{} 处理

给出一些例子:

  • Vn'::= { sth } xxx
  • Vn'::= { Vn } xxx
  • Vn'::= { Vt Vn } xxx
  • Vn'::= { sth } xxx

我们要将大括号内部的句型的first集合分析出来,然后写入while。

while (token == first_of(sth)) ) {
    Vn();  // analyze Vn
    next_sym(); // read a token
}

这样我们就能保证不断地读取。

还有一些特殊的情况,比如xxx的first集合和Vn的first集合有交集,那么我们在while的内部就要再预读,不满足条件时break

形如:Vt {Vn} Vt' 的文法还有一种处理方法——自后向前处理。用在Vn的first集合难以分析的时候。

当读取到Vt时,再读取一个token,若读到Vt',说明Vn没有,直接跳过,否则,进入while。

// already read Vt
next_sym();
while (token != Vt') {
    Vn();
    next_sym();
}
// now token is Vt'

左递归文法改写

改写文法简单,但是会引起一个bug,即改写后的文法和原来的文法,

在处理相同的句子时,会造成语法树长得不一样,造成输出少了一个非终结符。

比如下面的例子,两种文法,a && b的语法树是不一样的,改写后的文法少了一个非终结符。

所以,要先擦去之前输出的终结符,再输出非终结符,最后补上终结符。

// <LAndExp>::= <EqExp> | <LAndExp> '&&' <EqExp>
// <LAndExp>::= <EqExp> { '&&' <EqExp> }
// note: left recurrence
// promise: already read a token
void Parser::LAndExp() {
    EqExp();
    next_sym();
    while (type_code_ == TypeCode::AND) {

        // ----------------------
        retract(); // erase then token before
        output("<LAndExp>"); // output the Vn
        next_sym(); // output the token
        // -----------------------

        next_sym();
        EqExp();
        next_sym();
    }
    retract();
    output("<LAndExp>");
}

检查

  1. 分号的处理是否正确
  2. 面对{}的文法,在while出来后,是否需要回退
  3. 每个非终结符定义前,进入前是否预读

bug

  1. 非终结符少输出
  2. ;没有正确处理
  3. 左递归文法改写
上一篇:扩充 jQuery EasyUI Datagrid 数据行鼠标悬停/离开事件(onMouseOver/onMouseOut)


下一篇:HaaS100开发调试系列 之 如何使用J-Link仿真器调试代码