实验5 LL(1)语法分析程序的设计与实现（C语言） - 图文

班级: 学号: 姓名:

七、简单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集合为：

9

班级: 学号: 姓名:

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’ ?+TE’ ?-TE’ ?ε ?ε ?FT’ ? ?ε ?ε ?*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)文法字符串，本程序能自动判断所给字符串是否为所给文法的句子，并能给出分析过程。

/********************************************/

10

班级: 学号: 姓名:

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

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

/* 0=i 1=+ 2=- 3=* 4=/ 5=( 6=) 7=# */ /************************************/ #include\#include \#include \#include \

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

http://wenku.http://www.china-audit.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));

11

班级: 学号: 姓名:

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) /*非终结符：栈顶*/ {

12