实验5 LL1语法分析程序的设计与实现C语言.docx
《实验5 LL1语法分析程序的设计与实现C语言.docx》由会员分享，可在线阅读，更多相关《实验5 LL1语法分析程序的设计与实现C语言.docx（27页珍藏版）》请在冰点文库上搜索。
实验5LL1语法分析程序的设计与实现C语言
实验五LL
（1）文法识别程序设计
一、实验目的
通过LL
（1）文法识别程序的设计理解自顶向下的语法分析思想。
二、实验重难点
FIRST集合、FOLLOW集合、SELECT集合元素的求解，预测分析表的构造。
三、实验内容与要求
实验内容：
1．阅读并理解实验案例中LL
（1）文法判别的程序实现；
2．参考实验案例，完成简单的LL
（1）文法判别程序设计。
四、实验学时
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=E1=E'2=T3=T'4=F*/
/*0=i1=+2=*3=（4=）5=#*/
/************************************/
#include"iostream"
#include"stdio.h"
#include"malloc.h"
#include"conio.h"
/*定义链表这种数据类型参见：
structLchar{
charchar_ch;
structLchar*next;
}Lchar,*p,*h,*temp,*top,*base;
/*p指向终结符线性链表的头结点，h指向动态建成的终结符线性链表节点，top和base分别指向非终结符堆栈的顶和底*/
charcurchar;//存放当前待比较的字符:
终结符
charcurtocmp;//存放当前栈顶的字符：
非终结符
intright;
inttable[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表示无产生式。
*/
inti,j;
voidpush（charpchar）/*入栈函数*/
{
temp=（structLchar*）malloc（sizeof（Lchar））;
temp->char_ch=pchar;
temp->next=top;
top=temp;
}
voidpop（void）/*出栈函数*/
{
curtocmp=top->char_ch;
if（top->char_ch!
='#'）
top=top->next;
}
voiddoforpush（intt）/*根据数组下标计算的值找对应的产生式，并入栈*/
{
switch（t）
{
case0:
push（'A'）;push（'T'）;break;
case3:
push（'A'）;push（'T'）;break;
case11:
push（'A'）;push（'T'）;push（'+'）;break;
case20:
push（'B'）;push（'F'）;break;
case23:
push（'B'）;push（'F'）;break;
case32:
push（'B'）;push（'F'）;push（'*'）;break;
case40:
push（'i'）;break;
case43:
push（'）'）;push（'E'）;push（'（'）;
}
}
/*根据curchar和curtocmp转为数字以判断是否有产生式*/
voidchangchartoint（）
{
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;
}
}
/*识别算法*/
voiddosome（void）
{
intt;
for（;;）
{
pop（）;/*读取栈顶的字符存curtocmp中*/
curchar=h->char_ch;/*读取输入字符链表h中一个字符存入curchar*/
printf（"\n%c\t%c",curchar,curtocmp）;
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;
}
}
}
intmain（void）
{
charch;
right=1;
base=（structLchar*）malloc（sizeof（Lchar））;/*初始化非终结符堆栈，栈底为#，栈顶为文法开始符号*/
base->next=NULL;
base->char_ch='#';
temp=（structLchar*）malloc（sizeof（Lchar））;
temp->next=base;
temp->char_ch='E';
top=temp;/*初始化非终结符堆栈，栈底为#，栈顶为文法开始符号E*/
/*初始化存放待识别的表达式（终结符）的线性链表头*/
h=（structLchar*）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=（structLchar*）malloc（sizeof（Lchar））;
temp->next=NULL;
temp->char_ch=ch;
h->next=temp;
h=h->next;/*如果输入正确，h不断的指向新输入的字符，而p始终指向输入终结符字符串的头位置，即前面开辟的空的链表空间。
*/
}
else
{
temp=p->next;/*如果输入错误，提示输入有错，请重新输入，让temp指向输入字符串的头部，并将前面正确输出的字符串再次输出*/
printf（"\nInputawrongchar!
Inputagain:
\n"）;
for（;;）
{
if（temp!
=NULL）
printf（"%c",temp->char_ch）;
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（）;
return0;
}
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）该文法的预测分析表为:
i
+
-
*
/
（
）
#
E
+TE’
TE’
E’
+TE’
-TE’
ε
ε
T
FT’
T’
ε
ε
*FT’
/FT’
ε
ε
F
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=E1=E'2=T3=T'4=F*/
/*0=i1=+2=-3=*4=/5=（6=）7=#*/
/************************************/
#include"iostream"
#include"stdio.h"
#include"malloc.h"
#include"conio.h"
/*定义链表这种数据类型参见：
structLchar{
charchar_ch;
structLchar*next;
}Lchar,*p,*h,*temp,*top,*base;
/*p指向终结符线性链表的头结点，h指向动态建成的终结符线性链表节点，top和base分别指向非终结符堆栈的顶和底*/
charcurchar;//存放当前待比较的字符:
终结符
charcurtocmp;//存放当前栈顶的字符：
非终结符
intright;
inttable[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表示无产生式。
*/
inti,j;
voidpush（charpchar）/*入栈函数*/
{
temp=（structLchar*）malloc（sizeof（Lchar））;
temp->char_ch=pchar;
temp->next=top;
top=temp;
}
voidpop（void）/*出栈函数*/
{
curtocmp=top->char_ch;
if（top->char_ch!
='#'）
top=top->next;
}
voiddoforpush（intt）/*根据数组下标计算的值找对应的产生式，并入栈*/
{
switch（t）
{
case0:
push（'A'）;push（'T'）;break;
case5:
push（'A'）;push（'T'）;break;
case11:
push（'A'）;push（'T'）;push（'+'）;break;
case12:
push（'A'）;push（'T'）;push（'-'）;break;
case20:
push（'B'）;push（'F'）;break;
case25:
push（'B'）;push（'F'）;break;
case33:
push（'B'）;push（'F'）;push（'*'）;break;
case34:
push（'B'）;push（'F'）;push（'/'）;break;
case40:
push（'i'）;break;
case45:
push（'）'）;push（'E'）;push（'（'）;break;
}
}
/*根据curchar和curtocmp转为数字以判断是否有产生式*/
voidchangchartoint（）
{
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;
}
}
/*识别算法*/
voiddosome（void）
{
intt;
for（;;）
{
pop（）;/*读取栈顶的字符存curtocmp中*/
curchar=h->char_ch;/*读取输入字符链表h中一个字符存入curchar*/
printf（"\n%c\t%c",curchar,curtocmp）;
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;
}
}
}
intmain（void）
{
charch;
right=1;
base=（structLchar*）malloc（sizeof（Lchar））;/*初始化非终结符堆栈，栈底为#，栈顶为文法开始符号*/
base->next=NULL;
base->char_ch='#';
temp=（structLchar*）malloc（sizeof（Lchar））;
temp->next=base;
temp->char_ch='E';
top=temp;/*初始化非终结符堆栈，栈底为#，栈顶为文法开始符号E*/
/*初始化存放待识别的表达式（终结符）的线性链表头*/
h=（structLchar*）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=（structLchar*）malloc（sizeof（Lchar））;
temp->next=NULL;
temp->char_ch=ch;
h->next=temp;
h=h->next;/*如果输入正确，h不断的指向新输入的字符，而p始终指向输入终结符字符串的头位置，即前面开辟的空的链表空间。
*/
}
else
{
temp=p->next;/*如果输入错误，提示输入有错，请重新输入，让temp指向输入字符串的头部，并将前面正确输出的字符串再次输出*/
printf（"\nInputawrongchar!
Inputagain:
\n"）;
for（;;）
{
if（temp!
=NULL）
printf（"%c",temp->char_ch）;
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（
升级会员 