Yan`s Notepad

--- My Notepad......Articles, tools and etc.
给递归下降语法分析器添加特设语法制导转换
分析LL(1)文法所使用的递归下降语法分析器是最适合人编写的。因此,我们将尝试为递归下降语法分析器添加特设语法制导转换。以经典的表达式文法为例子,对表达式文法进行左递归消除后,以Goal为目标符号、nil代表ε,number表示任何数字,我们将得到以下文法:
 1    Goal  ->   Expr
 2    Expr  ->   Term Expr'
 3    Expr' -> + Term Expr'
 4           | - Term Expr'
 5           | nil
 6    Term  ->   Fact Term'
 7    Term' -> * Fact Term'
 8           | / Fact Term'
 9           | nil
 10   Fact  -> number
 11          | ( Expr )
对于递归下降语法分析器。举个简单的例子,我们考虑拓展表达式文法中的一部分,对应的还有它的FIRST+集(就是SELECT集)。
Expr' -> + Term Expr'      { + }
       | - Term Expr'      { - }
       | nil               { nil, eof, )}
为了识别Expr',我们会在之后使用一个过程parser_EPrime,该函数内部实现很简单——按照三个的FIRST+集,选择合适的规则,进行匹配。如果在这其中找到了错误,那么就报告语法错误。对于每一个产生式右侧的句型,函数会直接去测试输入流的情况。为了检查某个非终结符(假如是A)的存在,它会调用A过程。而检验终结符,它则会直接去匹配。当这个检查成功的时候,调用nextWord(),移动到下一个单词。但是注意,如果匹配到的是ε产生式,那么不应该移动输入流。按照这个思路,我们可以给出parser_EPrime的大致样子,其中的nextWord(0负责返回下一个单词,而cur_word则记录了当前的单词。
bool parser_EPrime()
{
    if(cur_word == "+")                      // Expr' -> + Term Expr'
    {
        word = nextword();   
        if(parser_Term())
        {
            return parser_EPrime();
        }
        else {
            // 报告错误
            return false;
        }
    }
    else if(cur_word == "-")                 // Expr' -> - Term Expr'
    {
        word = nextword();   
        if(parser_Term())
        {
            return parser_EPrime();
        }
        else {
            // 报告错误
            return false;
        }
    }
    else if(cur_word == eof || cur_word == "(")
    {                                        // Expr' -> nil
        return true;
    }
    else {
        // 报告错误
        return false;
    }
    
}
构建其余的部分也是一样的,完整的程序将会与特设语法制导转换混合,出现在文章末尾。
特设语法制导转换类似于属性文法的这种规则求值思路,它直接把操作关联到产生式,每一次当语法分析器位于某个产生式的时候,都会调用这些操作,完成对应的任务。为了将特设语法制导转换与它结合起来,我们先考虑上面的文法对表达式1-2*3-4的分析过程,则会得到以下结果(图片画的时候发现小了...最后几张有点丑),注意各个节点的构建顺序以及表达式原本的运算顺序:
···图片正在加载···
images/adhSDT/parser_1.png
解析过程1
···图片正在加载···
images/adhSDT/parser_2.png
解析过程2
···图片正在加载···
images/adhSDT/parser_3.png
解析过程3
···图片正在加载···
images/adhSDT/parser_4.png
解析过程4
···图片正在加载···
images/adhSDT/parser_5.png
解析过程5
···图片正在加载···
images/adhSDT/parser_6.png
解析过程6
···图片正在加载···
images/adhSDT/parser_7.png
解析过程7
当然,上图中省略了目标符号最开始的推导。我们可以看到整个递归下降语法分析器在自顶向下构建语法树的过程,最终的结果来看,它像极了一颗表达式树。想到LR(1)移进-归约语法分析器,它提供了一个显式的符号栈,或许我们可以类比,想到LL(1)递归下降语法分析器也应该提供一个显式的栈。重新回去看整个构建的过程,可以发现希望计算的值(Expr'等产生式)流动情况:
···图片正在加载···
images/adhSDT/way_1.png
值流动过程
这表明,我们需要在每个产生式规则的前两个单词(或非终结符)推导完成后,就进行计算,这个结果作为新的值流动到其它的位置。类似于LR(1)语法分析器提供的栈那样,我们可以该值可以存放在栈中,待另外的产生式需要时,再弹出来。对于终结符number的计算是无需的,只需要将它压入栈中等待使用即可。特设语法制导转换的思想是强大的,但是具体实现却的确值得人思考。我们在文法中以{}插入特设语法制导转换操作,即可得到以下文法:
 1   Goal  ->   { init() } Expr
 2   Expr  ->   Term Expr'
 3   Expr' -> + Term { b = pop, a = pop, push(a + b) } Expr'
 4          | - Term { b = pop, a = pop, push(a - b) } Expr'       
 5          | nil
 6   Term  ->   Fact Term'
 7   Term' -> * Fact { b = pop, a = pop, push(a * b) } Term'       
 8          | / Fact { b = pop, a = pop, push(a / b) } Term'       
 9          | nil
10   Fact  -> { push(number) } number
11          | ( Expr )
在递归下降语法分析器的对应位置,插入栈操作,即可得到完整的程序:
#include <stdio.h>
#include <tchar.h>
#include <iostream>
#define IS_NUMBER(c)                ((c) >= '0' && (c) <= '9')
#define STACK_DEEP                  8
#define STACK_INIT(stk)             stk.top = 0 
#define STACK_PUSH(stk, d)          stk.dat[stk.top++] = d
#define STACK_POP(stk)              stk.dat[--stk.top]
#define STACK_TOP(stk)              stk.dat[stk.top - 1]
typedef double  calcdat;
enum tokenType
{
    token_eof, token_num,
    token_add, token_sub, token_neg,
    token_mul, token_div, token_larc,
    token_rarc,
};
typedef struct _token
{
    tokenType  type;
    calcdat    dat;
}calctoken;
typedef struct _datList
{
    calcdat     dat[STACK_DEEP];
    int	        top;                    	// 栈顶指针
}datList;
char       *pstr;
calctoken   curWord;
datList     datstk;
bool        parser_Goal     ();
bool        parser_Expr     ();
bool        parser_EPrime   ();
bool        parser_Term     ();
bool        parser_TPrime   ();
bool        parser_Fact     ();
void        nextWord        (calctoken *);
void        stack_calc2     (char);
// Goal -> Expr
bool parser_Goal()
{
    STACK_INIT(datstk);                 // 初始化栈
    nextWord(&curWord);
    if (parser_Expr())
    {
        if (*pstr == 0)
            return true;
    }
    return false;
}
// Expr -> Term Expr'
bool parser_Expr()
{
    if (parser_Term())
        return parser_EPrime();
    return false;
}
// Expr' -> + Term Expr'
//        | - Term Expr'
//        | nil
bool parser_EPrime()
{
    if (curWord.type == token_add)
    {
        nextWord(&curWord);
        if (parser_Term())
        {
            bool ret;
            stack_calc2('+');           // 在Expr'推导开始前, 执行语义动作, 下同
            ret = parser_EPrime();
            return ret;
        }
        else {
            return false;
        }
    }
    else if (curWord.type == token_sub)
    {
        nextWord(&curWord);
        if (parser_Term())
        {
            bool ret;
            stack_calc2('-');
            ret = parser_EPrime();
            return ret;
        }
        else {
            return false;
        }
    }
    else if (curWord.type == token_rarc || curWord.type == token_eof)
    {
        return true;                    // 空产生式规则不移动word的位置
    }
    return false;
}
// Term -> Fact Term'
bool parser_Term()
{
    if (parser_Fact())
        return parser_TPrime();
    return false;
}
// Term' -> * Fact Term'
//        | / Fact Term'
//        | nil
bool parser_TPrime()
{
    if (curWord.type == token_mul)
    {
        nextWord(&curWord);
        if (parser_Fact())
        {
            bool ret;
            stack_calc2('*');
            ret = parser_TPrime();
            return ret;
        }
        else {
            return false;
        }
    }
    else if (curWord.type == token_div)
    {
        nextWord(&curWord);
        if (parser_Fact())
        {
            bool ret;
            stack_calc2('/');
            ret = parser_TPrime();
            return ret;
        }
        else {
            return false;
        }
    }
    else if (curWord.type == token_add || curWord.type == token_sub || curWord.type == token_rarc || curWord.type == token_eof)
    {
        return true;
    }
    return false;
}
// Fact  -> number
//        | ( Expr )
bool parser_Fact()
{
    if (curWord.type == token_num)
    {
        STACK_PUSH(datstk, curWord.dat);
        nextWord(&curWord);
    }
    else if (curWord.type == token_larc)
    {
        nextWord(&curWord);
        if (!parser_Expr())
        {
            return false;
        }
        if (curWord.type != token_rarc)
        {
            return false;
        }
        nextWord(&curWord);
    }
    else {
        return false;
    }
    return true;
}
// 一个简单的词法分析实现
// 取得一个token
void nextWord(calctoken *o)
{
    int     n = 0;                          // 整数部分
    calcdat r = (calcdat)0.1, v = 0;
    switch (*pstr)
    {
    case '+':  o->type = token_add;  pstr++;  break;
    case '-':  o->type = token_sub;  pstr++;  break;
    case '*':  o->type = token_mul;  pstr++;  break;
    case '/':  o->type = token_div;  pstr++;  break;
    case '(':  o->type = token_larc; pstr++;  break;
    case ')':  o->type = token_rarc; pstr++;  break;
    case '\0': o->type = token_eof;           break;
    default:
        o->dat = 0;
        o->type = token_num;
        while (IS_NUMBER(*pstr))
        {
            n = n * 10 + *pstr - '0';
            pstr++;
        }
        o->dat += n;
        if (*pstr && *pstr == '.')
        {
            pstr++;
            while (IS_NUMBER(*pstr))
            {
                v = v + (*pstr - '0') * r;
                r = r * (calcdat)0.1;
                pstr++;
            }
            o->dat += v;
        }
    }
}
// 特设语法制导转换的语义动作
// 栈操作: +, -, *, /
void stack_calc2(char op)
{
    calcdat a, b, r;
    b = STACK_POP(datstk);
    a = STACK_POP(datstk);
    switch (op)
    {
    case '+': r = a + b; break;
    case '-': r = a - b; break;
    case '*': r = a * b; break;
    case '/': r = a / b; break;
    }
    STACK_PUSH(datstk, r);
}

int main()
{
    char   str[100];
    std::cin >> str;
    pstr = str;                         // 指向字符串开始的位置, 准备分析
    printf("%s\n", parser_Goal() ? "符合语法" : "分析失败");
    printf("%g\n", STACK_TOP(datstk));  // 如果正常的话, 栈顶会留下结果
    return 0;
}