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

班级: 学号: 姓名:

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

5

班级: 学号: 姓名:

{

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(\

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*/ {

6

班级: 学号: 姓名:

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));

7

班级: 学号: 姓名:

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(\for(;;)

{

if (temp!=NULL)

printf(\else break;

temp=temp->next; } }

}while(ch!='#');

p=p->next; /*消去第一个空头节点，并使头结点指向非空线性链表表头*//*如果输入正确，h不断的指向新输入的字符，而输入字符串的头位置被记录在p里面。*/ h=p; /*h重新指向头结点，以便后面识别操作*/ dosome();/*开始识别*/ if(right)

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

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

3． 测试数据及运行结果

8