实验二 递归下降语法分析程序设计

实验二 递归下降语法分析程序设计

实验二 递归下降语法分析程序设计

[实验目的]：

1．了解语法分析的主要任务。 2． 熟悉编译程序的编制。

[实验内容]：根据某文法，构造一基本递归下降语法分析程序。给出分析过程中所用的产生式序列。 [实验要求]：

1. 构造一个小语言的文法，例如，Pascal语言子集的文法，考虑其中的算术表达式文法：

G[<表达式>]：G[E]：

<表达式>→<表达式>+<项>|<表达式>-<项>|<项> E→E+T|T <项>→<项>*<因式>|<项>/<因式>|<因式> T→T*F|F <因式>→<标识符>|<无符号整数>|(<表达式>) F→i|(E) 2. 设计语法树的输出形式，例如：

产生式 ……

3. 编写递归下降语法分析程序

实现基本的递归下降分析器，能够分析任给的符号串是否为该文法所定义的合法算术表达式。实验报告中要说明分析使用的方法。 4. 生成并输出分析过程中所用的产生式序列：

1 产生式1 2 产生式2 ……

[实验步骤]：

1. 写出一个小语言的算术表达式文法。

2. 写出该小语言的算术表达式等价的LL(1)文法。例如：

G[E]： 其中

E→TG G为E’ E→+TG|^ ^为ε T→FS S为T’ T→*FS|^ F→i|(E)

3. 编写递归下降语法分析程序。 4. 调试运行程序。 5. 结果分析。 6. 撰写实验报告。

[实验报告]：每位同学撰写一份试验报告，并提交电子版。 1. 源程序。

2. 画出流程图。

3. 实验设计过程中出现的问题及解决的方法。 4. 实验设计过程中的体会。 5. 给出程序清单。 6. 给出测试结果。

实验二 递归下降语法分析程序设计

实验报告命名规则：

个人：2013-14（1）医智（1）1107505101蔡菲菲实验二 交各班课代表汇总后，由课代表打包后，发送至老师的邮箱 班级命名规则：2013-14医智（1）实验二 截止日期：第14周周五晚11点30分

测试的结果举例

源代码:

#include <stdio.h> #include <dos.h> #include <stdlib.h> #include <string.h>

char a[50],b[50],d[200],e[10],ch; /*数组a存输入串，数组d存推导式*/

int n1,i1=0,flag=1,n=5; /*flag=1处理非终结符，flag=0处理终结符*/ int total=0; /*步骤计数器*/ int E(),E1(),T(); int G();/*E’*/ int S();/*T’*/ int F();

void input(); void input1(); void output();

实验二 递归下降语法分析程序设计

void main() /*递归分析*/ { int f,p,j=0; char x; d[0]='E';d[1]='=';d[2]='>';d[3]='T';d[4]='G';d[5]='#'; printf("请输入字符串(长度<50,以#号结束）\n"); do { scanf("%c",&ch); a[j]=ch; j++; }while(ch!='#'); n1=j;/* n1输入串实际长度 */ ch=b[0]=a[0]; printf("步骤\t文法\t分析串\t\t分析字符\t剩余串\n"); f=E1(); {system("pause"); } if (f==0) return; /*有语法错误，失败退出*/ if (ch=='#') { printf("accept\n"); /*输入串是文法的句子*/ p=0; x=d[p]; while(x!='#') { printf("%c",x); p=p+1; x=d[p]; /*输出推导式*/ } } else { printf("error\n"); printf("回车返回\n"); getchar(); getchar(); return; } printf("\n"); printf("回车返回\n"); getchar();

实验二 递归下降语法分析程序设计

getchar(); }

int E1()/* 有语法错误函数返回值为0，否则为1*/ { int f,t; printf("%d\tE-->TG\t",total); total++; flag=1; input(); input1(); f=T(); if (f==0) return(0); t=G(); if (t==0) return(0); else return(1); }

int E() { int f,t; printf("%d\tE-->TG\t",total); total++; e[0]='E';e[1]='=';e[2]='>';e[3]='T';e[4]='G';e[5]='#'; output(); flag=1;input();input1(); f=T(); if (f==0) return(0); t=G(); if (t==0) return(0); else return(1); }

int T() { int f,t; printf("%d\tT-->FS\t",total); total++; e[0]='T';e[1]='=';e[2]='>';e[3]='F';e[4]='S';e[5]='#'; output(); flag=1;input();input1(); f=F();

实验二 递归下降语法分析程序设计

if (f==0) return(0); t=S(); if (t==0) return(0); else return(1); }

int G() { int f; if(ch=='+') { b[i1]=ch; printf("%d\tG-->+TG\t",total); total++; e[0]='G';e[1]='=';e[2]='>';e[3]='+';e[4]='T';e[5]='G';e[6]='#'; output(); flag=0;input();input1(); ch=a[++i1]; f=T(); if (f==0) return(0); G(); return(1); } printf("%d\tG-->^\t",total); total++; e[0]='G';e[1]='=';e[2]='>';e[3]='^';e[4]='#'; output(); flag=1; input(); input1(); return(1); }

int S() { int f,t; if(ch=='*') { b[i1]=ch; printf("%d\tS-->*FS\t",total); total++; e[0]='S';e[1]='=';e[2]='>';e[3]='*';e[4]='F';e[5]='S';e[6]='#'; output();

实验二 递归下降语法分析程序设计

flag=0;input();input1(); ch=a[++i1]; f=F(); if (f==0) return(0); t=S(); if (t==0) return(0); else return(1); } printf("%d\tS-->^\t",total); total++; e[0]='S';e[1]='=';e[2]='>';e[3]='^';e[4]='#'; output(); flag=1;a[i1]=ch;input();input1(); return(1); }

int F() { int f; if(ch=='(') { b[i1]=ch; printf("%d\tF-->(E)\t",total); total++; e[0]='F';e[1]='=';e[2]='>';e[3]='(';e[4]='E';e[5]=')';e[6]='#'; output(); flag=0;input();input1(); ch=a[++i1]; f=E(); if (f==0) return(0); if(ch==')') { b[i1]=ch; printf("%d\tF-->(E)\t",total); total++; flag=0; input(); input1(); ch=a[++i1]; } else { printf("error\n"); return(0);

实验二 递归下降语法分析程序设计

} } else if(ch=='i') { b[i1]=ch; printf("%d\tF-->i\t",total); total++; e[0]='F';e[1]='=';e[2]='>';e[3]='i';e[4]='#'; output(); flag=0;input();input1(); ch=a[++i1]; } else { printf("error\n"); return(0); } return(1); }

void input() { int j=0; for (;j<=i1-flag;j++) printf("%c",b[j]); /*输出分析串*/ printf("\t\t"); printf("%c\t\t",ch); /*输出分析字符*/ }

void input1() { int j; for (j=i1+1-flag;j<n1;j++) printf("%c",a[j]); /*输出剩余字符*/ printf("\n"); }

void output() /*推导式计算*/ { int m,k,j,q; int i=0; m=0;k=0;q=0; i=n; d[n]='=';d[n+1]='>';d[n+2]='#'; n=n+2; i=n; i=i-2; while(d[i]!='>'&&i!=0)

实验二 递归下降语法分析程序设计

i=i-1; i=i+1; while(d[i]!=e[0]) i=i+1; q=i;m=q;k=q; while(d[m]!='>') m=m-1; m=m+1; while(m!=q) { d[n]=d[m]; m=m+1; n=n+1; } d[n]='#'; for(j=3;e[j]!='#';j++) { d[n]=e[j]; n=n+1; } k=k+1; while(d[k]!='=') { d[n]=d[k]; n=n+1; k=k+1; } d[n]='#'; }

流程图：

实验二 递归下降语法分析程序设计

开始

输入符号串(#结束)

调用函数 E1

当前字符为#? Y 匹配成功 accept,输 出最左推导过程

N

匹配失败 error

结束 E、E1

INPUTSYM=”i”? Y T

N

INPUTSYM=”(“? Y

N

Error

G

出口

实验二 递归下降语法分析程序设计

T

INPUTSYM=”i”? Y F

N

INPUTSYM=”(“? Y

N

Error

S

出口 G

N

INPUTSYM=”+”? Y INPUTSYM=下一个符号

INPUTSYM=”i”? Y T

N

INPUTSYM=”(“? Y

N

Error

G

出口

实验二 递归下降语法分析程序设计

S

N

INPUTSYM=”*”? Y INPUTSYM=下一个符号

INPUTSYM=”i”? Y F

N

INPUTSYM=”(“? Y

N

Error

S

出口

F

INPUTSYM=”i”? Y

N

INPUTSYM=”(“? Y E

N

INPUTSYM=下一个符号

INPUTSYM=”)“? Y 出口

N

Error

实验二 递归下降语法分析程序设计

运行结果：

验证

i*i+i

验证

ik5

实验设计过程中出现的问题及解决的方法:

本次实验最难的问题就是画流程图，解决方法就是通过问同学和通过google和查看书本，了解LL(1) 文法是怎么实现的，然后在对每个非终结符进行递归下降的程序分析并画出流程图。

实验二 递归下降语法分析程序设计

实验设计过程中的体会:

这次实验比较成功的完成了,由于是C语言,理解上也不是很大问题,不是实验一的那样是C++,有些代码看都看不懂。不过这次实验的重点就是让我们了解LL（1）文法，更能让我们独自地去完成项目，为后面的大作业做准备。

本文来源：https://www.bwwdw.com/article/0pji.html