实验5 LL1语法分析程序的设计与实现C语言Word下载.docx
- 文档编号:6871505
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:21
- 大小:26.59KB
实验5 LL1语法分析程序的设计与实现C语言Word下载.docx
《实验5 LL1语法分析程序的设计与实现C语言Word下载.docx》由会员分享,可在线阅读,更多相关《实验5 LL1语法分析程序的设计与实现C语言Word下载.docx(21页珍藏版)》请在冰点文库上搜索。
http:
//wenku。
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'
);
case11:
T'
);
+'
case20:
B'
F'
case23:
push(’B’);
push(’F’);
break;
case32:
*’);
case40:
push(’i'
case43:
push(’)’);
push(’E'
('
/*根据curchar和curtocmp转为数字以判断是否有产生式*/
voidchangchartoint()
switch(curtocmp)/*非终结符:
栈顶*/
case'
E'
:
i=0;
case’A'
i=1;
i=2;
B’:
i=3;
F’:
i=4;
switch(curchar)/*终结符:
待识别的表达式中*/
i’:
j=0;
case’+'
:
j=1;
*’:
j=2;
j=3;
)’:
j=4;
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*/
if(curtocmp==’A'
||curtocmp=='
B’||curtocmp=='
||curtocmp=='
||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;
/*出错*/
elseif(curtocmp!
=curchar)/*如果curtocmp不是终结符,并且是结束符,判断终结符链表字符是否也为终结符P94图5。
11圈1、1、5、6*/
/*出错*/
else
/*正确P94图5.11圈1、1、5、7*/
=curchar)/*如果curtocmp是终结符,并且不等于当前终结符链表中的终结符,则出错。
P94图5.11圈1、8、9*/
right=0;
else/*如果curtocmp是终结符,并且等于当前终结符链表中的终结符,则匹配成功,可以读取下一个链表头的终结符P94图5。
11圈10*/
h=h—〉next;
/*读取下一字符*/
intmain(void)
charch;
right=1;
base=(structLchar*)malloc(sizeof(Lchar));
/*初始化非终结符堆栈,栈底为#,栈顶为文法开始符号*/
base->
next=NULL;
base-〉char_ch=’#'
;
temp-〉next=base;
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始终指向输入终结符字符串的头位置,即前面开辟的空的链表空间。
temp=p-〉next;
/*如果输入错误,提示输入有错,请重新输入,让temp指向输入字符串的头部,并将前面正确输出的字符串再次输出*/
\nInputawrongchar!
Inputagain:
\n"
if(temp!
=NULL)
%c”,temp—>
char_ch);
temp=temp—>
}while(ch!
=’#’);
p=p—>
next;
/*消去第一个空头节点,并使头结点指向非空线性链表表头*//*如果输入正确,h不断的指向新输入的字符,而输入字符串的头位置被记录在p里面。
h=p;
/*h重新指向头结点,以便后面识别操作*/
dosome();
/*开始识别*/
if(right)
\n成功!
输入的表达式可以被该文法识别!
\n错误!
表示输入的表达式不可以被该文法识别!
getch();
return0;
3.测试数据及运行结果
七、简单LL
(1)文法判别程序设计
1、判断以下文法是不是LL
(1)文法,写出详细的判断过程:
EE+T|E—T|T
TT*F|T/F|F
Fi|(E)
(1)消除左递归,文法变为:
ETE'
E’+TE’|—TE'
|ε
TFT'
T’*FT’|/FT'
|ε
Fi|(E)
(2)可推出的非终结符表为:
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(ETE’)={(,i}
SELECT(E'
+TE'
)={+}
SELECT(E’—TE'
)={-}
SELECT(E’ε)={),#}
SELECT(TFT’)={(,i}
SELECT(T’*FT’)={*}
SELECT(T’/FT’)={/}
SELECT(T'
ε)={+,-,),#}
SELECT(F(E))={(}
SELECT(Fi)={i}
(6)有相同左部产生式的SELECT集合的交集是否为空?
该文法是否为LL
(1)文法?
(7)该文法的预测分析表为:
i
+
-
*
/
(
#
+TE’
TE’
E’
-TE’
ε
FT'
*FT’
/FT'
(E)
2、设计LL
(1)文法判别程序设计,源代码如下:
/*程序名称:
/*E—>
E+T|E—T/T*/
/*T-〉T*F|T/F/F*/
/*F—>
/*目的:
对输入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”
/*定义链表这种数据类型参见:
//wenku.baidu。
com/link?
url=_owQzf8PRZOt9H—5oXIReh4X0ClHo6zXtRdWrdSO5YBLpKlNvkCk0qWqvFFxjgO0KzueVwEQcv9aZtVKEEH8XWSQCeVTjXvy9lxLQ_mZXeS###*/
structLchar{
charchar_ch;
structLchar*next;
}Lchar,*p,*h,*temp,*top,*base;
/*p指向终结符线性链表的头结点,h指向动态建成的终结符线性链表节点,top和base分别指向非终结符堆栈的顶和底*/
charcurchar;
//存放当前待比较的字符:
//存放当前栈顶的字符:
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}};
voidpush(charpchar)/*入栈函数*/
temp=(structLchar*)malloc(sizeof(Lchar));
char_ch=pchar;
temp-〉next=top;
voidpop(void)/*出栈函数*/
char_ch;
top=top—>
voiddoforpush(intt)/*根据数组下标计算的值找对应的产生式,并入栈*/
case0:
push(’T'
case5:
push(’A'
T’);
push(’+’);
case12:
A’);
push(’—’);
case20:
push(’B'
F’);
case25:
case33:
*’);
case34:
push(’/'
case40:
i'
case45:
)'
case’B'
E’:
F’:
i=4;
switch(curchar)/*终结符:
j=0;
case’+’:
case’—'
case’*’:
/’:
case’('
j=5;
j=6;
case’#'
j=7;
for(;
/*读取栈顶的字符存curtocmp中*/
curchar=h->
/*读取输入字符链表h中一个字符存入curchar*/
\n%c\t%c”,curchar,curtocmp);
if(curtocmp=='
#’&&curchar=='
)/*如果都是终结符P94图5。
if(curtocmp==’A’||curtocmp==’B’||curtocmp==’E’||curtocmp=='
||curtocmp=='
)/*如果curtocmp不是终结符,也不是结束符,则根据预测分析表找到产生式并入栈P94图5。
changchartoint();
if(table[i][j])/*[1.1]有产生式P94图5.11圈2*/
/*计算产生式在数组中的位置*/
else/*[1。
2]没有产生式P94图5。
11圈4*/
/*出错*/
=curchar)/*如果curtocmp不是终结符,并且是结束符,判断终结符链表字符是否也为终结符P94图5。
/*正确P94图5。
11圈1、1、5、7*/
elseif(curtocmp!
=curchar)/*如果curtocmp是终结符,并且不等于当前终结符链表中的终结符,则出错。
/*出错*/
else/*如果curtocmp是终结符,并且等于当前终结符链表中的终结符,则匹配成功,可以读取下一个链表头的终结符P94图5。
h=h—〉next;
/*读取下一字符*/
continue;
charch;
base=(structLchar*)malloc(sizeof(Lchar));
/*初始化非终结符堆栈,栈底为#,栈顶为文法开始符号*/
base—>
temp—〉next=base;
temp-〉char_ch=’E’;
/*初始化非终结符堆栈,栈底为#,栈顶为文法开始符号E*/
/*初始化存放待识别的表达式(终结符)的线性链表头*/
h=(structLchar*)malloc(sizeof(Lchar));
h—>
p=h;
/*开辟了一个空的链表空间,p和h同时指向该空间,该空间将作为终结符链表的头部.*/
请输入要分析的字符串(#号结束)\n"
do{/*输入待识别的表达式*/
ch=getchar();
putchar(ch);
if(ch==’i’||ch==’+'
||ch=='
-'
||ch==’*'
||ch==’/'
(’||ch==’)’||ch=='
#’)
{/*将输入的ch存入链表*/
h-〉next=temp;
/*如果输入正确,h不断的指向新输入的字符,而p始终指向输入终结符字符串的头位置,即前面开辟的空的链表空间.*/
temp=p—〉next;
/*如果输入错误,提示输入有错,请重新输入,让temp指向输入字符串的头部,并将前面正确输出的字符串再次输出*/
printf(”\nInputawrongchar!
\n”);
%c"
temp->
=’#'
p=p-〉next;
/*消去第一个空头节点,并使头结点指向非空线性链表表头*//*如果输入正确,h不断的指向新输入的字符,而输入字符串的头位置被记录在p里面。
/*h重新指向头结点,以便后面识别操作*/
/*开始识别*/
printf(”\n成功!
\n”);
\n错误!
getch();
3、测试数据及运行结果,运行结果截图应包含姓名或学号信息。
截图应包含一个正例i*(i+i)-i/i#一个反例i*(i+i)-i—/i#
正例成功截图如下:
反例成功截图如下:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验5 LL1语法分析程序的设计与实现C语言 实验 LL1 语法分析 程序 设计 实现 语言
![提示](https://static.bingdoc.com/images/bang_tan.gif)