预测分析法实现的语法分析器 2006-12-17 10:01:29
分类： C/C++
作者:余洪周
nickhome@163.com 版权所有，转载时请注明出自: nick19842000.cublog.cn
本文将就编译原理中比较常用的一个表达式文法，通过预测分析法来编写分析器。文中将为您提供如何通过FIRST、FOLLOW和SELECT集合来判断LL(1)方法，然后如何用预测分析法分析LL(1)方法的基本递归流程，以及如何用C语言来编程实现分析器。
题目：编写识别由下列文法所定义的表达式的预测分析程序。
EàE+T | E-T | T
TàT*F | T/F |F
Fà(E) | i
输入：每行含一个表达式的文本文件。
输出：分析成功或不成功信息。
(题目来源：编译原理实验(三)--预测(LL(1))分析法的实现)
解答:
（1）分析
a) ∵E=>E+T=>E+T*F=>E+T*(E)即有E=>E+T*(E)存在左递归。用直接改写法消除左递归，得到如下：
E à TE’ E’ à +TE’ | ?TE’|ε
T à FT’ T’ à *FT’ | /FT’|ε
F à (E) | i
对于以上改进的方法。可得：
对于E’: FIRST( E’ )=FIRST(+TE’)∪FIRST(-TE’)∪{ε}={+，?，ε}
对于T’: FIRST( T’ )=FIRST(*FT’)∪FIRST(/FT’)∪{ε}={*，∕，ε}
而且： FIRST( E ) = FIRST( T ) = FIRST( F )=FIRST((E))∪FIRST(i)={(，i }
由此我们容易得出各非终结符的FOLLOW集合如下：
FOLLOW( E )= { )，#}
FOLLOW(E’)= FOLLOW(E)={ )，#}
FOLLOW( T )= FIRST(E’)\ε∪FOLLOW(E’)={+，?，)，#}
FOLLOW( T’ ) = FOLLOW( T ) ={+，?，)，#}
FOLLOW( F )=FIRST(T’)\ε∪FOLLOW(T’)={*，∕，+，?，)，#}
由以上FOLLOW集可以我们可以得出SELECT集如下：
对E SELECT（EàTE’）=FIRST(TE’)=FIRST(T)={ (，i }
对E’ SELECT（E’ à+TE’）={ + }
SELECT（E’ à ?TE’）={ ? }
SELECT（E’ àε）={ε，)，#}
对T SELECT（TàFT’）={(，i}
对T’ SELECT（T’ à*FT’）={ * }
SELECT（T’ à ∕FT’）={ ∕ }
SELECT（T’ àε）={ε，+，?，)，#}
对F SELECT（Fà(E) ）={ ( }
SELECT（Fài）={ i }
∴ SELECT(E’ à+TE’)∩SELECT（E’ à ?TE’）∩SELECT（E’ àε）=F
SELECT(T’ à*FT’)∩SELECT（T’ à ∕FT’）∩SELECT（T’ àε）=F
SELECT（Fà(E) ）∩SELECT（Fài）= F
由上可知，有相同左部产生式的SELECT集合的交集为空，所以文法是LL（1）文法。
b) 由Select集构造文法LL(1)的预测分析表 (表1)
非终
结符
终结符
i
+
-
*
/
(
)
#
ε
E
E >TE’[0]
E->TE’[5]
E’
E’-> + T E’[11]
E’-> - TE’[12]
E’->ε[16]
E’->ε[17]
E’->ε[18]
T
T->FT’[20]
T->FT’[25]
T’
T’->ε[31]
T’->ε[32]
T’->*FT’[33]
T’->/FT’[34]
T’->ε[36]
T’->ε[37]
T’->ε[38]
F
F->i[40]
F->(E)[45]
表1. LL(1)预测分析表
（2）设计
(如：图1)。
图1.流程图
（3）程序代码如下
/************************************************************************
* 文件名 ：test3.c
* 文件描述：预测分析法实现的语法分析器。分析如下文法：
* E->E+T | E-T | T
* T->T*F | T/F |F
* F->(E) | i
* 输入：每行含一个表达式的文本文件(#号结束)。
* 输出：分析成功或不成功信息。
* 创建人：余洪周 <nick19842000.cublog.cn> 2006-12-16
* 版本号：1.0
* 说明 ：为了表示的方便采用了如下的所示表示方法：
* A=E' B=T'
* 非终结符：0=E 1=E' 2=T 3=T' 4=F
* 终结符 ：0=i 1=+ 2=- 3=* 4=/ 5=( 6=) 7=#
***********************************************************************/
#include<stdio.h>
#include<malloc.h>
struct struCH{
char ch;
struct struCH *next;
}struCH,*temp,*head,*shift,*top,*base;
/*head指向线性链表的头结点，shift指向动态建成的结点
*top和base分别指向堆栈的顶和底
*/
FILE *fp;
char curchar; /*存放当前待比较的字符*/
char curtocmp; /*存放当前栈顶的字符*/
char ch;
int right, i,j;
int table[5][9]={ /*存储预测分析表，1为有产生式，0为无*/
{1,0,0,0,0,1,0,0,0},
{0,1,1,0,0,0,1,1,1},
{1,0,0,0,0,1,0,0,0},
{0,1,1,1,1,0,1,1,1},
{1,0,0,0,0,1,0,0,0}};
void main(int argc,char *argv[]){
void puch(char ch);
void pop();
void doforpush(int t);
void identify();
int errnum=0, k=0, countchar=0, rownum;
int m=0;
int charerr=0; /*有非法字符时的开关控制量*/
/*******************以只读方式打开文件*********************/
if((fp=fopen(argv[1],"r"))==NULL){
printf("\n\tCan not open file %s,or not exist it!\n",argv[1]);
exit(0); /*文件不存在or打不开时，正常退出程序*/
}
else printf("\n\tSuccess open file: %s\n",argv[1]); /*成功打开文件*/
/******************遍历整个文件检测是否有非法字符********************/
/*如果用while(!feof(fp))语言，将会多出一个字符而难以控制，
*所以这里采用先计算字符数量再遍历整个文件来检测其否有非法字符*/
/*[1]计算文件中字符数量*/
while(!feof(fp)){
ch=getc(fp); /*这里只是让指针往前移*/
countchar++; /*统计文件中的字符数(包括换行符及文件结束符)*/
}
rewind(fp); /*将fp文件指针重新指向文件头处，以备后面对文件的操作*/
if(countchar= =0){ /*空文件*/
printf("\t%s is a blank file!\n",argv[1]);
exit(0); /*正常退出本程序*/
}
/*[2]开始遍历文件*/
while(k<(countchar-1)){/*加换行符后countchar仍多一个，故减1*/
ch=getc(fp);
if(!(ch= ='('||ch= =')'||ch= ='i'||ch= ='+'||ch= ='-'||ch= ='*'||ch= ='/'||ch= ='#'||ch= ='\n')){
charerr=1;errnum++;/*charerror出错标记，errnum统计出错个数*/
}
k++;
}
rewind(fp); /*将fp文件指针重新指向文件头处，以备后面的建链表操作*/
if(charerr= =1){ /*文件中有非法字符*/
printf("\n\t%d Unindentify characters in file %s \n",errnum,argv[1]);
exit(0); /*正常退出本程序*/
}
/*******************非空且无非法字符，则进行识别操作*****************/
for(rownum=1;m<(countchar-1);rownum++){ /*识别所有行,rownum记录行号*/
/* 初始变量及堆栈和 */
right=1;
/* '#''E'进栈 */
base=malloc(sizeof(struCH)); /*初始化堆栈*/
base->next=NULL;
base->ch='#';
temp=malloc(sizeof(struCH));
temp->next=base;
temp->ch='E';
top=temp; /*栈顶指针top指向栈顶*/
/*初始存放待识别的表达式的线性链表头*/
shift=malloc(sizeof(struCH));
shift->next=NULL;
head=shift;
/*读取一行形成线性链表*/
ch=getc(fp);putchar(ch);m++;
while(ch!='\n'&&m<(countchar)){ /*行末or到文件尾。最后会读取文件结束符*/
/*读取ch,读取存入链*/
temp=malloc(sizeof(struCH));
temp->ch=ch;
temp->next=NULL;
shift->next=temp;
shift=shift->next;
ch=getc(fp);
if(m!=(countchar-1)) putchar(ch); /*不输出最后一次读取的文件结束符*/
m++;
}
head=head->next; /*消去第一个空头结点,并使head指向非空线性链表头*/
shift=head; /*shift指向头结点，以便后面识别操作*/
putchar('\n');
identify(); /*开始识别一行*/
if(!right) /*错误提示:[文件名] Line [行号]:error expression!*/
printf("%s Line %d:\t error expression!\n",argv[1],rownum);
else /*正确提示:[文件名] Line [行号]:right expression!*/
printf("%s Line %d:\t right expression!\n",argv[1],rownum);
putchar('\n');
}/*end for*/
printf("Completed!\n");
fclose(fp); /*关闭文件*/
exit(0); /*正常退出程序*/
}
/*入栈函数*/
void push(char ch){
temp=malloc(sizeof(struCH));
temp->ch=ch;
temp->next=top;
top=temp;
}
/*出栈函数*/
void pop(void){
curtocmp=top->ch;
if(top->ch!='#')
top=top->next;
}
/*根据数组下标计算的值找对应的产生式，并入栈*/
void doforpush(int t){
switch(t){
case 0:push('A');push('T');break;
case 5:push('A');push('T');break;
case 11:push('A');push('T');push('+');break;
case 12:push('A');push('T');push('-');break;
case 20:push('B');push('F');break;
case 25:push('B');push('F');break;
case 33:push('B');push('F');push('*');break;
case 34:push('B');push('F');push('/');break;
case 40:push('i');break;
case 45:push(')');push('E');push('(');
}
}
/*根据curchar,curtocmp转为数字以判断是否有产生式*/
void changchartoint()
{
switch(curtocmp) /*非终结符:栈顶*/
{
case 'A':i=1;break;
case 'B':i=3;break;
case 'E':i=0;break;
case 'T':i=2;break;
case 'F':i=4;
}
switch(curchar) /*终结符:待识别的表达式中*/
{
case 'i':j=0;break;
case '+':j=1;break;
case '-':j=2;break;
case '*':j=3;break;
case '/':j=4;break;
case '(':j=5;break;
case ')':j=6;break;
case '#':j=7;
}
}
/*识别算法函数*/
void identify()
{
int t;
for(;;)
{
pop(); /*读取栈顶的字符存curtocmp中*/
curchar=shift->ch; /*读取链中的一个字符存curchar*/
printf("\t%c-->%c\n",curchar,curtocmp);
if(curtocmp=='#' && curchar=='#') break;
if(curtocmp=='A'||curtocmp=='B'||curtocmp=='E'||curtocmp=='T'||curtocmp=='F'){
if(curtocmp!='#'){ /*[1]未到栈底时，匹配字符*/
changchartoint();
if(table[i][j]){ /*[1.1]有产生式*/
t=10*i+j; /*计算产生式在数组中的位置*/
doforpush(t); /*找对应t的产生式，并入栈*/
continue;
}
else{ /*[1.2]没有产生式*/
right=0; /*出错*/
break;
}
}
else{ /*[2]到栈底，当前比较字符为'#'*/
if(curtocmp!=curchar){ /*输入行中最后一字符非'#'*/
right=0; /*出错*/
break;
}
else
break; /*正确*/
}
}
else{ /*若当前字符为终结符*/
if(curtocmp!=curchar){
right=0; /*出错*/
break;
}
else{
shift=shift->next; /*读取下一个字符*/
continue;
}
}
}/*end for*/
}
（4）调试
1.编译：在windows平台下，推荐用Turbo C 2编译连接生成后ana.exe；
2.输入表达式：在ana.exe程序同一目录下新建一文本文件(如：exp.txt)。往文本文件中输入要识别的表达式，表达式以“#”结束，可输入多行。同一行“#”以后的内容在识别过种中将自动丢弃。如将以下内容存入exp.txt文件中：
i+i#
(i+i)*i-i#
3.运行：打开MSDOS控制台，进入ana.exe程序所在的目录(如：C:\>)。
输入：[程序名] [存放表达式的文本文件名]，如:ana exp.txt
以上程序执行结果，如图2所示。
图2.实例运行结果图
4.异常操作结果注释：
a) 文件不存在or打不开时，提示“Can not open file [txtfile],or not exist it!”正常退出。
b) 打开文件成功，提示：Success open file [txtfile]
c) 若为空文件，提示：[txtfile] is a blank file!
d) 先检测文件中是否含有非法字符，若有，则统计并输出其个数：[errnum] Unindentify characters in file [txtfile]
e) 程序将分析每行的表达式，输出每行执行的结果，如上图。若为错误的表达式，则提示：[txtfile] Line [rownum]: error expression!
Tag: Any problem,leave word! ^_^ I will write back as soon as possible!
参考资料
关于题目的来源
* 编译原理实验二 递归下降语法分析 华南热带农业大学 计算机科学与技术系
关于LL（1）分析方法
* 何炎祥，编译原理，高等教育出版社，2004-8
关于指针线性链表代码实现思想
* 黄记瑶，编译实验(三)预测分析，2005-11-9
