文法分析中最重要算法是LL自顶向下和LR自底向上算法.前面几篇文章主要讲解的是LL算法的理论和一个LL算法的文法分析器javacc.本文以LL(1)算法中最简单的一种形式递归下降算法来分析常规算法问题中的数学表达式问题.同时,本文也介绍手工构造EBNF文法的分析器代码普遍方法.希望本文的实践能对大家实现自己的语法分析器带来帮助.
数学表达式问题
在学习算法的时候,四则混合运算的表达式处理是个很经典的算法问题.
比如这里有个数学表达式”122+2*(11-1)/(3-(2-0))”.我们需要根据这个字符串的描述,然后计算出其结果.
Input:
122+2*(11-1)/(3-(2-0))
Output:
142
四则混合运算中还需要考虑到括号,乘除号与加减号的优先运算问题,通常的解决办法就是使用堆栈.那种常规的算法和LL算法有异曲同工之处,更或者说,那么的算法其实是一样的.
传统数学表达式处理算法简介
这个传统算法其实不知不觉地使用LL(1)算法的精髓.它就是主要依靠栈式的数据结构分别保存数和符号,然后根据运算符号的优先级别进行数学计算,并将结果保存在栈里面.
传统算法中使用了两个栈.一个是保存数值,暂时就叫值栈. 另一个是保存符号的,叫符号栈.我们规定一个记号#,来表示栈底.下面我们就来看看如何计算一个简单的表达式11+2-8*(5-3).
为了显示整个计算过程,我们以下面这个栈的变化图来表示.
符号栈和值栈的变化是根据输入串来进行的.基本上栈的操作可以简单用下面几句话来说.
Start:
1. 如果当前输入串中得到的是数字,则直接压入值栈.然后转到Start.
2. 如果当前输入串中得到的是符号,那么对符号进行判断.
1)如果符号是’+’或者’-‘,则依次弹出符号栈的符号,计算栈中数值,直到弹出的符号不是*,/,+,-.
2)如果符号是’*’或者’/’,则压入符号栈
3)如果符号是’(‘,则直接压’(‘入符号栈
4)如果符号是’)’,则依照符号栈的顺序弹出符号,计算栈中数值,把结果压入值栈,直到符号栈顶是’(‘,最后再弹出’(‘ .
最后转到Start.
3. 如果当前输入串得到的是EOF(字符串结束符号),则计算栈中数值,知道符号栈没有符号.
语法分析数学表达式
或者可能你以前运用过自己的办法来解决过这个程序问题,不过下面我们将通过编译原理建立的一套文法分析理论,来十分精彩地解决这个算法问题.
首先是建立数学表达式的文法EBNF.EBNF文法可以更灵活地表示BNF,是BNF范式文法的一种扩展.下面是上一篇javacc的介绍中使用到的计算表达式的文法.
Expression -> Term { Addop Term }
Addop -> "+" | "-"
Term -> Factor { Mulop Factor }
Mulop -> "*" | "/"
Factor -> ID | NUM | "(" Expression ")"
我们来看看如何根据这个EBNF文法实现一个递归下降的分析程序.大致上来说要分那么几步来实现.(注意,下面的几个步骤不光是针对本节的数学表达式问题,而是包含所有通常的递归下降文法分析器的实现)
语法分析实现
1. Step 建立词法分析
本系列文章开篇第一节就是讲的词法分析相关问题.因为词法分析是语法分析的前提,那么我们在实现递归下降算法的时候,同样应该把词法分析的实现考虑进去.
本文要处理只是个数学表达式的问题,那么通过上面的文法,可以看到需要识别的词法无非就是2个ID,NUM和4个运算符号’+’’-‘‘*’’/’以及2个括号’(‘‘(‘.本文没有对词法分析的自动机原理进行讲解,这部分内容应该在编译原理中讲得比较透彻.所谓自动机,就是按一定步骤识别每个字符的算法.可以用下面的几个图来表示ID和NUM的识别自动机(识别步骤或算法)
NUM:
基本算法就是,如果输入的字符是digit(‘0’-‘9’),那么进入check循环,如果输入还是digit,那么再跳回循环查看,如果输入是other(不是’0’-‘9’),那么就直接accept,接收这个串为NUM类型的TOKEN.
ID:
同NUM一样,当输入的是letter,那么进入ID的有限自动机.只是在进入check循环后,有两种可能都继续留在循环,那就是digit和letter(‘a’-‘Z’).当输入既不是digit,也不是letter的时候,就跳出check循环,进入accept,把接收到的字符归结成ID类型的TOKEN.
通过这个有限自动机的图示,我们就很容易写出词法分析程序.
不过在此之前,我们得写出识别letter和digit的代码.我们建立两个函数IsLetter和IsDigit来完成这个功能.
int IsLetter(char ch)
{
if(ch >= 'A' && ch <= 'Z')
return 1;
if(ch >='a' && ch <='z')
return 1;
return 0;
}
int IsDigit(char ch)
{
if(ch >= '0' && ch <='9')
return 1;
return 0;
}
有个这两个辅助函数,那么接下来,我们就直接写gettoken词法分析函数,它的功能就是从输入中分析,得到一个一个的token.我们首先定义token的类型.
#define ID 1
#define NUM 2
#define PLUS 3 // ‘+’
#define MINUS 4 // ‘-‘
#define TIMERS 5 // ‘*’
#define OVER 6 // ‘/’
#define LPAREN 7 // ‘(‘
#define RPAREN 8 // ‘)’
#define ERROR 255
上面注释已经说符号token代表的意思,我也不再多说.不过需要注意的是,这里我们定义了个ERROR的常量,但是我们这里并没有ERROR的token,它只是为我们后面处理结果时候的一个错误处理信息的定义.
char token[10];
char *nextchar;
const char g_strCalculate[]="122+2*(11-1)/(3-(2-0))";
我们需要定义token记号和一个指到输入串的指针.token记录的就是当前gettoken()得到的token的text(字符串).nextchar是当前指到输入串的指针.最后,我们随便定义一个要分析的数学表达式的输入串g_strCalculate.
int gettoken()
{
char *ptoken =token;
while(*nextchar == ' ' || *nextchar=='/n' || *nextchar=='/t')
nextchar++;
switch(*nextchar)
{
case '+': nextchar++; return PLUS;
case '-': nextchar++; return MINUS;
case '*': nextchar++; return TIMERS;
case '/': nextchar++; return OVER;
case '(': nextchar++; return LPAREN;
case ')': nextchar++; return RPAREN;
default: break;
}
// ID的词法识别分析
if(IsLetter(*nextchar))
{
while(IsLetter(*nextchar) || IsDigit(*nextchar))
{
*ptoken = *nextchar;
nextchar++;
ptoken++;
}
*ptoken ='/0';
printf("gettoken: token = %s/n",token);
return ID;
}
// NUM的词法识别分析
if(IsDigit(*nextchar))
{
while(IsDigit(*nextchar))
{
*ptoken = *nextchar;
nextchar++;
ptoken++;
}
*ptoken ='/0';
printf("gettoken: token = %s/n",token);
return NUM;
}
return ERROR;
}
代码很简单,我没有写多少任何注释.函数中,首先使用了char *ptoken记录token的首地址,它为后面的字符串复制(构造token)所用.同时,在处理代码的第一部分是过滤掉空格,制表符和换行符.然后是计算符号的词法分析.计算符号就是一个固定的字符号,所以它的识别很简单,直接用switch来判断*nextchar.而后面的ID,NUM的识别就是完全按照前面的有限自动机表示图表来进行编写的.以ID的图表来说,ID的自动机首先是要识别出第一个字符是letter,那么我就写了第一行if(IsLetter(*nextchar)),如果满足,则进入check循环,也就是while(IsLetter(*nextchar) || IsDigit(*nextchar))循环.循环中我们记录了*nextchar到token符号中.最后跳出check循环,进入accept,在代码中return ID.对于NUM的词法识别也是如此的,我就不多说了.
2. /span>根据EBNF文法建立文法识别函数
首先看到第一条非终结产生式
Expression -> Term { Addop Term }
Expression也是我们总的输入结果函数.我们先定义函数int Expression(),其返回值就是我们要处理的表达式的值.右边的产生式中,第一个是Term,我们就直接调用Term函数完成.然后是0到无限次的Addop Term,那么用一个循环即可.文法中使用非终结符号Addop.程序代码中我没有特别为此非终结符号创建函数.我们直接在代码以’+’ || ‘-‘代替Addop. 代码如下.
int expression()
{
int temp = term(); // 对应文法中的第一个Term
int tokentype;
while(*nextchar == '+' || *nextchar == '-') // 对应文法中的{ Addop Term }
{
tokentype = gettoken();
switch(tokentype)
{
case PLUS:
temp +=term();
break;
case MINUS:
temp -=term();
break;
default:
break;
}
}
return temp;
}
然后是第二条文法.同样,我也没有特别为Mulop特别写一个文法函数,而是直接以’*’|| ‘/’代替.
Term -> Factor { Mulop Factor }
同理,建立如下函数
int term()
{
int temp;
int tokentype;
temp = factor(); // 对应文法中的Factor
while(*nextchar == '*' || *nextchar == '//') // 对应文法中的 {Mulop Factor}
{
tokentype =gettoken();
switch(tokentype)
{
case TIMERS:
temp *= factor();
break;
case OVER:
temp /= factor();
break;
default:
break;
}
}
return temp;
}
最后是Factor文法 Factor -> ID | NUM | "(" Expression ")"
这个文法涉及到文法中的产生式的选择.由LL(1)文法的理论我们可以知道,这完全可以是通过ID,NUM, “(“Expression”)”三个产生式的第一个终结符的不同来判断的.ID的第一个字符号肯定是letter.而NUM第一个字符号肯定是digit. "(" Expression ")"第一个字符号肯定是”(“.而ID,NUM的判断我们已经在词法分析的时候做好了(int gettoken()函数中).下面列出Factor文法函数的代码.
int factor()
{
int number;
switch(gettoken())
{
case ID: break;
case NUM:
number = atoi(token);
break;
case LPAREN:
number = expression();
if(gettoken() != RPAREN)
&bsp; printf("lost ')' in the expression /n");
break;
default:
break;
}
return number;
}
好了,把上面出现的函数都写到程序文件中,加上个main函数,就可以编译运行了.
int main(int argc, char *argv[])
{
nextchar = g_strCalculate;
printf("result = %d/n",expression());
system("PAUSE");
return 0;
}
整个数学表达式的源程序大家可以在这里下载.
http://member.netease.com/~qinj/tangl_99/my doc/calculate/main.c
3. 总结
从上面三个EBNF文法实现我们可以容易得出一些机械性规律出来.
1. 对于EBNF文法中的非终结符都可以写成了一个单独的文法函数出来,比如前面Expression(),Term(),Factor().
2. 文法中的产生式的选择可以根据第一个字符号来进行识别,这就是LL(1)算法中提到的First集合.比如上面的Factor是直接通过gettoken得到下一个token的类型,然后根据类型的不同的token来switch处理不同产生式的代码.
3. 文法中的{}(0到无限次循环),比如{Addop Term},{ Mulop Factor}可以直接通过循环语句完成.不过循环的条件还是需要判断下一token是不是Addop或者Mulop的First集合的元素.比如上面的代码中,Addop就是’+’和’-‘,Mulop’*’和’/’,所以判断很容易,直接通过*nextchar也可以判断.如果下一个token不是Addop或者Mulop的First集合元素,那么就应该跳出循环.返回文法函数.
虽然EBNF文法构造递归下降文法分析器代码是如此的简单,但是正如<<编译原理及实践>>书上提到的,它有它的特殊性.很多时候,仅仅是把BNF文法转换成EBNF文法本身就是一件十分困难的事情.这就需要我们前面提到的LL(1)文法的消除左递归和提取左因式的问题.
与传统算法的比较
当我们明白了EBNF文法和递归下降的分析后,构造的数学表达式处理代码比传统算法要简单,要容易.原因前面也提到过,首先种东西的EBNF文法十分容易写,其次,从EBNF文法到代码的创建也十分机械化,也十分容易,最后,递归下降算法没有接触到栈的操作,利用了程序语言本身的递归本身特性,让程序语言去处理栈的操作(并不是说递归下降的算法一点都没有接触到栈,可以说数据结构中递归处理就等于栈处理).
递归下降的算法也和容易扩展表达式的计算操作.比如说,我们想把函数(如sin,cos)加进去,而且是加到所有运算的最高级别.那么我们修改Factor文法即可
Factor -> ID | NUM | "(" Expression ")"
| “sin””(“ Expression “)”
| “cos””)” Expression “)”
至于代码的实现,我们也只需要在int Factor函数中的switch中增加几个case语句就可以了.