前言
文法分析中最重要算法是
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.
根据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