实验5LL(1)语法分析程序的设计与实现(C语言)之令狐文艳创作

令狐文艳创作

令狐文艳

一、实验目的

通过LL(1)文法识别程序的设计理解自顶向下的语法分析思想。 二、实验重难点

FIRST集合、FOLLOW集合、SELECT集合元素的求解，预测分析表的构造。 三、实验内容与要求

实验内容：

1． 阅读并理解实验案例中

LL(1)文法判别的程序实现；

LL(1)文法判别程序设

2． 参考实验案例，完成简单的

计。

四、实验学时

4课时

五、实验设备与环境

C语言编译环境 六、实验案例

1． 实验要求

参考教材93页预测分析方法，94页 图5.11 预测分析程序框图，编写表达式文法的识别程序。要求对输入的LL(1)文法字符串，程序能自动判断所给字符串是否为所给文法的句子，并能给出分析过程。

表达式文法为： EE+T|T

令狐文艳创作

令狐文艳创作

TT*F|F Fi|(E)

2． 参考代码

为了更好的理解代码，建议将图5.11做如下标注： /* 程序名称： LL(1)语法分析程序 */ /* E->E+T|T */ /* T->T*F|F */ /* F->(E)|i */

/*目 的: 对输入LL(1)文法字符串，本程序能自动判断所给字符串是否为所给文法的句子，并能给出分析过程。

/********************************************/ /* 程序相关说明 */ /* A=E' B=T' */

/* 预测分析表中列号、行号 */ /* 0=E 1=E' 2=T 3=T' 4=F */ /* 0=i 1=+ 2=* 3=( 4=) 5=# */

/************************************/ #include\"iostream\" #include \"stdio.h\" #include \"malloc.h\" #include \"conio.h\"

/*定义链表这种数据类型参见：

令狐文艳创作

令狐文艳创作

http://wenku.baidu.com/link?url=_owQzf8PRZOt9H-5oXIReh4X0ClHo6zXtRdWrdSO5YBLpKlNvkCk0qWqvFFxjgO0KzueVwEQcv9aZtVKEEH8XWSQCeVTjXvy9lxLQ_mZXeS###*/ struct Lchar{ char char_ch;

struct Lchar *next;

}Lchar,*p,*h,*temp,*top,*base;

/*p指向终结符线性链表的头结点，h指向动态建成的终结符线性链表节点，top和base分别指向非终结符堆栈的顶和底*/

char curchar; //存放当前待比较的字符:终结符 char curtocmp; //存放当前栈顶的字符：非终结符 int right;

int table[5][6]={{1,0,0,1,0,0}, {0,1,0,0,1,1}, {1,0,0,1,0,0}, {0,1,1,0,1,1},

{1,0,0,1,0,0}};/*存放预测分析表，1表示有产生式，0表示无产生式。*/ int i,j;

void push(char pchar) /*入栈函数*/ {

temp=(struct Lchar*)malloc(sizeof(Lchar));

令狐文艳创作

令狐文艳创作

temp->char_ch=pchar; temp->next=top; top=temp; }

void pop(void)/*出栈函数*/ {

curtocmp=top->char_ch; if(top->char_ch!='#') top=top->next; }

void doforpush(int t) /*根据数组下标计算的值找对应的产生式，并入栈*/ {

switch(t) {

case 0:push('A');push('T');break; case 3:push('A');push('T');break;

case 11:push('A');push('T');push('+');break; case 20:push('B');push('F');break; case 23:push('B');push('F');break;

case 32:push('B');push('F');push('*');break; case 40:push('i');break;

case 43:push(')');push('E');push('(');

令狐文艳创作

令狐文艳创作

} }

/*根据curchar和curtocmp转为数字以判断是否有产生式*/

void changchartoint() {

switch(curtocmp)/*非终结符：栈顶*/ {

case 'E':i=0;break; case 'A':i=1;break; case 'T':i=2;break; case 'B':i=3;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; }

令狐文艳创作

令狐文艳创作

}

/*识别算法*/ void dosome(void) { int t; for(;;) {

pop();/*读取栈顶的字符存curtocmp中*/

curchar=h->char_ch; /*读取输入字符链表h中一个字符存入curchar*/

printf(\"\\n%c\%c\

if(curtocmp=='#' && curchar=='#') /*如果都是终结符 P94 图5.11圈1、圈5、圈7*/

break;

if(curtocmp=='A'||curtocmp=='B'||curtocmp=='E'||curtocmp=='T'||curtocmp=='F')/*如果curtocmp不是终结符 P94 图5.11圈1*/ {

if(curtocmp!='#') /*如果curtocmp不是终结符，也不是结束符，则根据预测分析表找到产生式并入栈 P94 图5.11圈1*/ {

changchartoint();

令狐文艳创作

令狐文艳创作

if(table[i][j])/*[1.1]有产生式P94 图5.11圈2*/ {

t=10*i+j; /*计算产生式在数组中的位置*/ doforpush(t); /*找对应t的产生式并入栈P94 图5.11圈3*/ continue; }

else/*[1.2]没有产生式P94 图5.11圈4*/ {

right=0; /*出错*/ break; } }

elseif(curtocmp!=curchar) /*如果curtocmp不是终结符，并且是结束符，判断终结符链表字符是否也为终结符P94 图5.11圈1、1、5、6*/ {

right=0; /*出错*/ break; } else

break; /*正确P94 图5.11圈1、1、5、7*/

令狐文艳创作

令狐文艳创作

}

elseif(curtocmp!=curchar) /*如果curtocmp是终结符,并且不等于当前终结符链表中的终结符，则出错。P94 图5.11圈1、8、9*/ {

right=0; /*出错*/ break; }

else /*如果curtocmp是终结符,并且等于当前终结符链表中的终结符，则匹配成功，可以读取下一个链表头的终结符P94 图5.11圈10*/ {

h=h->next; /*读取下一字符*/ continue; } } }

int main(void) {

char ch; right=1;

base=(struct Lchar*)malloc(sizeof(Lchar)); /*初始化非终结符堆栈，栈底为#，栈顶为文法开始符号*/

令狐文艳创作

令狐文艳创作

base->next=NULL; base->char_ch='#';

temp=(struct Lchar*)malloc(sizeof(Lchar)); temp->next=base; temp->char_ch='E';

top=temp;/*初始化非终结符堆栈，栈底为#，栈顶为文法开始符号E*/

/*初始化存放待识别的表达式（终结符）的线性链表头*/ h=(struct Lchar*)malloc(sizeof(Lchar)); h->next=NULL;

p=h;/*开辟了一个空的链表空间,p和h同时指向该空间,该空间将作为终结符链表的头部。*/

printf(\"请输入要分析的字符串(#号结束)\\n\"); do{ /*输入待识别的表达式*/

ch=getch();

putch(ch); //在屏幕上输出一个字符

if(ch=='i'||ch=='+'||ch=='*'||ch=='('||ch==')'||ch=='#')

{ /*将输入的ch存入链表*/

temp=(struct Lchar*)malloc(sizeof(Lchar)); temp->next=NULL; temp->char_ch=ch; h->next=temp;

令狐文艳创作

令狐文艳创作

h=h->next;/*如果输入正确，h不断的指向新输入的字符，而p始终指向输入终结符字符串的头位置，即前面开辟的空的链表空间。*/ } else

{

temp=p->next;/*如果输入错误，提示输入有错，请重新输入，让temp指向输入字符串的头部，并将前面正确输出的字符串再次输出*/

printf(\"\\nInput a wrong char!Input again:\\n\"); for(;;)

{

if (temp!=NULL)

printf(\"%c\ else break;

temp=temp->next; } }

}while(ch!='#');

p=p->next; /*消去第一个空头节点，并使头结点指向非空线性链表表头*//*如果输入正确，h不断的指向新输入的字符，而输入字符串的头位置被记录在p里面。*/

令狐文艳创作

令狐文艳创作

h=p; /*h重新指向头结点，以便后面识别操作*/ dosome();/*开始识别*/ if(right)

printf(\"\\n成功! 输入的表达式可以被该文法识别！\\n\"); else

printf(\"\\n错误!表示输入的表达式不可以被该文法识别！\\n\"); getch(); return 0; }

3． 测试数据及运行结果

七、简单LL(1)文法判别程序设计

1、判断以下文法是不是LL（1）文法，写出详细的判断过程：

EE+T|E-T|T TT*F|T/F|F Fi|(E)

（1）

消除左递归，文法变为：

ETE’

E’+TE’ | -TE’ | ε TFT’

T’*FT’ | /FT’ |ε Fi | (E)

令狐文艳创作

令狐文艳创作

（2）

可推出的非终结符表为：

E 否 E’ 是 T 否 T’ 是 F 否 （3）

各非终结符的FIRST集合为：

FIRST(E) = {(,i} FIRST(E’) ={+,-,ε} FIRST(T)={(,i}

FIRST(T’) ={*,/,ε} FIRST(F) ={(,i}

（4）

各非终结符的FOLLOW集合为：

FOLLOW(E) = {）,#} FOLLOW(E’)= {）,#} FOLLOW(T) = {）,#,+,-} FOLLOW(T’)= {）,#,+,-} FOLLOW(F) = {*,/,+,-,）,#}

（5）

各产生式的SELECT集合为：

SELECT(ETE’)={(,i} SELECT(E’+TE’)={+} SELECT(E’-TE’)={-} SELECT(E’ε)={）,#} SELECT(TFT’)={(,i} SELECT(T’*FT’)={*} SELECT(T’/FT’)={/} SELECT(T’ε)={+,-,）,#}

令狐文艳创作

令狐文艳创作

SELECT(F(E))={(} SELECT(Fi)={i}

（6）

有相同左部产生式的SELECT集合的交集是否为空？

该文法是否为LL（1）文法？

（7）

E E’ T T’ F 该文法的预测分析表为:

i + +TE’ +TE’ FT’ - * / ( -TE’ ε TE’ ) # ε ε  ε *FT’ /FT’ ε ε i (E) 2、设计LL(1)文法判别程序设计，源代码如下：

/* 程序名称： LL(1)语法分析程序 */ /* E->E+T|E-T/T */ /* T->T*F|T/F/F */ /* F->(E)|i */

/*目 的: 对输入LL(1)文法字符串，本程序能自动判断所给字符串是否为所给文法的句子，并能给出分析过程。

/********************************************/ /* 程序相关说明 */ /* A=E' B=T' */

/* 预测分析表中列号、行号 */ /* 0=E 1=E' 2=T 3=T' 4=F */

/* 0=i 1=+ 2=- 3=* 4=/ 5=( 6=) 7=# */ /************************************/ #include\"iostream\" #include \"stdio.h\" #include \"malloc.h\" #include \"conio.h\"

/*定义链表这种数据类型参见：

http://wenku.baidu.com/link?url=_owQzf8PRZOt9H-5oXIReh4X0ClHo6zXtRdWrdSO5YBLpKlNvkCk0qWqvFFxjgO0KzueVwEQcv9aZtVKEEH8XWSQCeVTjXvy9lxLQ_mZXeS###*/

令狐文艳创作

令狐文艳创作

struct Lchar{ char char_ch;

struct Lchar *next;

}Lchar,*p,*h,*temp,*top,*base;

/*p指向终结符线性链表的头结点，h指向动态建成的终结符线性链表节点，top和base分别指向非终结符堆栈的顶和底*/

char curchar; //存放当前待比较的字符:终结符 char curtocmp; //存放当前栈顶的字符：非终结符 int right;

int table[5][8]={{1,0,0,0,0,1,0,0}, {0,1,1,0,0,0,1,1}, {1,0,0,0,0,1,0,0}, {0,1,1,1,1,0,1,1},

{1,0,0,0,0,1,0,0}};/*存放预测分析表，1表示有产生式，0表示无产生式。*/

int i,j;

void push(char pchar) /*入栈函数*/ {

temp=(struct Lchar*)malloc(sizeof(Lchar)); temp->char_ch=pchar; temp->next=top; top=temp; }

void pop(void) /*出栈函数*/ {

curtocmp=top->char_ch; if(top->char_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('(');break; } }

/*根据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 dosome(void) {

int t; for(;;) {

pop();/*读取栈顶的字符存curtocmp中*/

curchar=h->char_ch; /*读取输入字符链表h中一个字符存入curchar*/

printf(\"\\n%c\%c\

if(curtocmp=='#' && curchar=='#') /*如果都是终结符 P94 图5.11圈1、圈5、圈7*/

break;

if(curtocmp=='A'||curtocmp=='B'||curtocmp=='E'||curtocmp=='T'||curtocmp=='F') /*如果curtocmp不是终结符 P94 图5.11圈1*/

{

if(curtocmp!='#') /*如果curtocmp不是终结符，也不是结束符，则根据预测分析表找到产生式并入栈 P94 图5.11圈1*/

{

changchartoint();

if(table[i][j]) /*[1.1]有产生式P94 图5.11圈2*/ {

t=10*i+j; /*计算产生式在数组中的位置*/

doforpush(t); /*找对应t的产生式并入栈P94 图5.11圈3*/

continue; }

else/*[1.2]没有产生式P94 图5.11圈4*/ {

right=0; /*出错*/ break; }

令狐文艳创作

令狐文艳创作

}

else if(curtocmp!=curchar) /*如果curtocmp不是终结符，并且是结束符，判断终结符链表字符是否也为终结符P94 图5.11圈1、1、5、6*/

{

right=0; /*出错*/ break; }

else

break; /*正确P94 图5.11圈1、1、5、7*/ }

else if(curtocmp!=curchar) /* 如果curtocmp是终结符,并且不等于当前终结符链表中的终结符，则出错。P94 图5.11圈1、8、9*/

{

right=0; /*出错*/ break; }

else /*如果curtocmp是终结符,并且等于当前终结符链表中的终结符，则匹配成功，可以读取下一个链表头的终结符P94 图5.11圈10*/

{

h=h->next; /*读取下一字符*/ continue; } } }

int main(void) {

char ch; right=1;

base=(struct Lchar*)malloc(sizeof(Lchar)); /*初始化非终结符堆栈，栈底为#，栈顶为文法开始符号*/

base->next=NULL; base->char_ch='#';

令狐文艳创作

令狐文艳创作

temp=(struct Lchar*)malloc(sizeof(Lchar)); temp->next=base; temp->char_ch='E';

top=temp; /*初始化非终结符堆栈，栈底为#，栈顶为文法开始符号E*/

/*初始化存放待识别的表达式（终结符）的线性链表头*/

h=(struct Lchar*)malloc(sizeof(Lchar)); h->next=NULL;

p=h; /*开辟了一个空的链表空间,p和h同时指向该空间,该空间将作为终结符链表的头部。*/

printf(\"请输入要分析的字符串(#号结束)\\n\"); do{ /*输入待识别的表达式*/ ch=getchar();

putchar(ch); //在屏幕上输出一个字符 if(ch=='i'||ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')

{ /*将输入的ch存入链表*/

temp=(struct Lchar*)malloc(sizeof(Lchar)); temp->next=NULL; temp->char_ch=ch; h->next=temp;

h=h->next;/*如果输入正确，h不断的指向新输入的字符，而p始终指向输入终结符字符串的头位置，即前面开辟的空的链表空间。*/

}

else {

temp=p->next; /*如果输入错误，提示输入有错，请重新输入，让temp指向输入字符串的头部，并将前面正确输出的字符串再次输出*/

printf(\"\\nInput a wrong char!Input again:\\n\"); for(;;) {

if (temp!=NULL)

令狐文艳创作

令狐文艳创作

printf(\"%c\ else break;

temp=temp->next; } }

}while(ch!='#');

p=p->next; /*消去第一个空头节点，并使头结点指向非空线性链表表头*//*如果输入正确，h不断的指向新输入的字符，而输入字符串的头位置被记录在p里面。*/

h=p; /*h重新指向头结点，以便后面识别操作*/ dosome();/*开始识别*/ if(right)

printf(\"\\n成功! 输入的表达式可以被该文法识别！\\n\");

else

printf(\"\\n错误! 表示输入的表达式不可以被该文法识别！\\n\");

getch(); return 0; }

3、测试数据及运行结果,运行结果截图应包含姓名或学号信息.

截图应包含一个正例 i*(i+i)-i/i# 一个反例i*(i+i)-i-/i#

令狐文艳创作

令狐文艳创作

正例成功截图如下： 反例成功截图如下： 4、实验总结、心得体会

在进行此次实验上机前应该做好准备：①按照老师提供的教材P93

页的图4.11预测分析程序的流程图熟悉预测分析的工作过程。②计算出要分析的文法的FIRST集合、FOLLOW集合和SELECT集合。③根据②得出的各个集合得出构造预测分析表。在老师讲解其实验目的、要求和分析后，选择相应的数据，使用C语言参照算法中的流程编写词法分析的程序。将编写好的程序上次调试（包括正例和反例）。通过此次程序设计，更加清楚的明白了LL(1)分析法的过程，从而也比较熟练掌握了自上而下语法分析的基本思想，此

令狐文艳创作

令狐文艳创作

外，在老师的讲解下初步认识了数据结构的知识，加上自己的理解，与所学知识加以联系，将知识归纳在系统中。在实现和调试时采取模块化的思想，是的本次课程设计比较顺利，增强了自己的信心，提高了自己的编程能力和动手能力以及分析问题、解决问题的能力和综合运用所学知识的能力。

5.思考：词法分析与语法分析的不同

区别：顾名思义，词法分析器检查的是词法，语法分析器分析的是语法，什么是词法，什么是语法。 所谓词法，源代码由字符流组成，字符流中包括关键字，变量名，方法名，括号等等符号，其中变量名要满足不能包括标点符号，不能以数字开头的数字与字母的字符串这个条件，对于括号要成对出现等等，这就是词法;而语法，词法没有问题才能进入语法分析，语法就是词排列的方法，字面意义， 语法分析器就是分析类似这样的语法的。

教师评语： 是否完成实验程序的预备设计？是：不是： 程序能否正常运行？是：不是： 有无测试数据及结果分析是：不是： 是否在本次规定时间完成所有项目？是：不是： 实验成绩等级： 教师签名： N0: 时间： 令狐文艳创作