实验语法分析程序的设计和实现语言.doc

实验五 LL(1)文法辨认程序设计

一、实验目
通过LL(1)文法辨认程序设计理解自顶向下语法分析思想。
二、实验重难点
FIRST集合、FOLLOW集合、SELECT集合元素求解，预测分析表构造。
三、实验内容与规定
实验内容：
1． 阅读并理解实验案例中LL(1)文法鉴别程序实现；
2． 参照实验案例，完毕简朴LL(1)文法鉴别程序设计。
四、实验学时
4学时
五、实验设备与环境
C语言编译环境
六、实验案例
1． 实验规定
参照教材93页预测分析办法，94页 图5.11 预测分析程序框图，编写表达式文法辨认程序。规定对输入LL(1)文法字符串，程序能自动判断所给字符串与否为所给文法句子，并能给出分析过程。
表达式文法为：
EE+T|T
TT*F|F
Fi|(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"

/*定义链表这种数据类型参见：
*/
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\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;
}
}
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=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",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();
return 0;
}
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
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
+
-
*
/
(
)
#
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=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"

/*定义链表这种数据类型参见：
*/
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\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;
}
}
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",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();
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：
时间：