c语言_递归下降分析程序实验_共13页

编译原理实验报告—递归下降分析法程序实验2.1 递归下降分析法一、实验目的1. 根据某一文法编制递归下降分析程序，以便对任意输入的符号串进行分析。

2. 本次实验的目的是加深对递归下降分析法的理解。

二、实验平台Windows + VC++6.0范例程序: “递归下降分析法.cpp ”三、实验内容对下列文法，用递归下降分析法对任意输入的符号串进行分析：（1）E→TG（2）G→+TG|-TG（3）G→ε（4）T→FS（5）S→*FS|/FS（6）S→ε（7）F→(E)（8）F→i1.程序功能:输入: 一个以# 结束的符号串(包括+ - * / （）i # )：例如：i+i*i-i/i#输出:(1) 详细的分析步骤，每一步使用的产生式、已分析过的串、当前分析字符、剩余串,第一步, 产生式E->TG的第一个为非终结字符,所以不输出分析串,此时分析字符为i,剩余字符i+i*i-i/i#;第二步，由第一步的E->TG的第一个为非终结字符T，可进行对产生式T->FS 分析，此时第一个仍为非终结字符F，所以不输出分析串，分析字符仍为i, 剩余字符i+i*i-i/i#;第三步，使用产生式F->i，此时的分析串为i,，分析字符为i,匹配成功，剩余字符串+i*i-i/i#;第四步，因为使用了产生式T->FS，F->i，第一个字符i匹配成功，接着分析字符+，使用产生式S->ε，进行下步；第五步，使用产生式G->+TG,此时的分析串包含i+,分析字符为+，剩余字符串+i*i-i/i#;第六步，重复对产生式T->FS，F->i的使用，对第二个i进行匹配，此时分析串i+i,分析字符为i,剩余串*i-i/i#;第七步，分析字符*，使用产生式S->*FS, 分析串i+i*,剩余串i-i/i#;第八步，字符*匹配成功后，使用产生式F->i，匹配第三个字符i,，此时剩余串-i/i#;第九步，分析字符-，只有产生式G->-TG可以产生字符-。

《编译原理》课程实验报告题目用递归下降法进行表达式分析专业班级学号姓名一.实验题目用递归下降法进行语法分析的方法二.实验日期三.实验环境（操作系统，开发语言）操作系统是Windows开发语言是C语言四.实验内容（实验要求）词法分析程序和语法分析程序已经提供。

此语法分析程序能够实现：正确的输入可以给出结果。

例：输入表达式串为：（13+4）*3则应给出结果为51。

要求：（1）读懂源代码，理解内容写入实验报告（语法分析及语法分析程序和词法分析程序的接口）（2）把语法分析中使用的yyval，用yytext实现。

（3）在语法分析程序用加入出错处理（尽量完整，包括出错的位置，出错的原因，错误的重定位）五.实验步骤1.生成lex.yy.c文件：将已给的mylexer.l文件打开，先理解，然后再在DOS环境下用flex运行此文件，这时会生成一个lex.yy.c文件。

2.创建工程：打开C-Free 5.0(注：用C-Free 4.0会出错)，在菜单栏中的“工程（project）”菜单下选择“新建”；在新建工程中选择“控制台程序”，添加工程名字为“myleb”和保存位置后点“确定”；第1步选择“空的程序”点“下一步”；第2步再点“下一步”；最后点击“完成”。

3.在创建的工程中添加文件：在Source files文件夹中添加之前生成的lex.yy.c文件和syn.c文件，然后找到parser.h文件，将其添加到新建工程中的Header files文件夹中，这时就能将三个文件组成一个类似于.exe文件类型的文件，最后运行。

如图：4.理解并修改syn.c文件：首先，将num = yyval.intval修改成num = atoi(yytext)；将num = yyval.fval修改成num = atof(yytext)。

可以这样修改的原因：在.l文件中所写的规则中，有{DIGIT}+ { yyval.intval = atoi(yytext);return INTEGER; }和{DIGIT}+"."{DIGIT}* {yyval.fval = atof(yytext); return DOUBLE; } 这两句代码，其中yyval.intval = atoi(yytext)和yyval.fval = atof(yytext)就说明两者可以相互替代。

编译方法实验报告实验名称:简单的语法分析程序设计实验要求1.功能:对简单的赋值语句进行语法分析随机输入赋值语句,输出所输入的赋值语句与相应的四元式2.采纳递归下降分析程序完成(自上而下的分析)3.确定各个子程序的功能并画出流程图4.文法如下:5.编码、调试通过采纳标准输入输出方式。

输入输出的样例如下:【样例输入】x:=a+b＊c/d-(e＋ｆ)【样例输出】(说明,语句和四元式之间用５个空格隔开)T1:=ｂ＊c (*,ｂ,c,T1)Ｔ2:=Ｔ1／ｄ(／,T1,d,T2)T３:=a+T2 (+,ａ,Ｔ2,T3)T４:=ｅ+f (+,ｅ,f,T４)T5:=T3—T４(-,T3,Ｔ4,T5)x:＝T５(:=,Ｔ５,-,ｘ)【样例说明】程序除能够正确输出四元式外,当输入的表达式错误时,还应能检测出语法错误,给出相应错误提示。

6.设计3-5个赋值语句测试实例,检验程序能否输出正确的四元式;当输入错误的句子时,检验程序能够给出语法错误的相应提示信息。

7.报告内容包括:递归程序的调用过程,各子程序的流程图和总控流程图,详细设计,３－5个测试用例的程序运行截图及相关说明,有详细注释的程序代码清单等、ﻬ目录1.语法分析递归下降分析算法 (4)1.1背景知识 (4)1.2消除左递归 (5)2.详细设计及流程图 (6)2.1 函数void V( ) // V -> a|b|c|d|e...|z.. (6)2.2 函数void A( ) // A -> V:=E (6)2.3 函数void E() //E -> TE' (7)2.4函数void T( ) // T -> FT' (7)2.5函数void E1( ) //E'-> +TE'|-TE'|null (8)2.6函数void T1() // T'-> *FT'|/FT'|null (8)3.测试用例及截图 (9)3.1测试用例1及截图 (9)3.2测试用例2及截图 (10)3.3测试用例3及截图 (11)代码清单 (11)1、语法分析递归下降分析算法1。

编译原理实验报告实验名称：实验二编写递归下降语法分析器实验类型：验证型实验指导教师：何中胜专业班级：13软件四姓名：丁越学号：13030504电子邮箱：862245792@实验地点：秋白楼B720实验成绩：日期：2016年4 月1 日一、实验目的通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。

通过本实验，应达到以下目标：1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。

2、掌握词法分析的实现方法。

3、上机调试编出的语法分析程序。

二、实验过程1、分析对象分析算术表达式的 BNF 定义如下：〈算术表达式〉→〈项〉|〈算术表达式〉＋〈项〉|〈算术表达式〉－〈项〉〈项〉→〈因式〉|〈项〉*〈因式〉|〈项〉／〈因式〉〈因式〉→〈变量〉│（〈算术表达式〉）〈变量〉→i用符号表示如下：E→T|E＋T|E-TT→F|T*F|T／FF→i│(E)递归下降分析程序实现思想简单易懂。

程序结构和语法产生式有直接的对应关系。

因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。

递归下降分析程序的实现思想是：识别程序由一组子程序组成。

每个子程序对应于一个非终结符号。

每一个子程序的功能是：选择正确的右部，扫描完相应的字。

在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。

自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。

分析速度慢。

而无回溯的自上向下分析技术，当选择某非终结符的产生时，可根据输入串的当前符号以及各产生式右部首符号而进行，效率高，且不易出错。

无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。

无左递归：既没有直接左递归，也没有间接左递归。

无回溯：对于任一非终结符号 U 的产生式右部x1|x2|…|xn，其对应的字的首终结符号两两不相交。

2. 递归下降语法分析流程图实验分为五个模块，分别是：E( )函数，E1( )函数，T( )函数，T1( )函数,F( )函数。

实验二：语法分析（递归下降法）一、实验目的1、掌握语法分析的基本原理；2、掌握递归下降的分析法；3、熟悉C语言程序设计。

二、实验准备微机CPU主频1.3G以上，128M内存，安装好C语言，PASCAL语言，或C++。

三、实验时间2学时四、实验内容已给语言文法，写出该文法的递归下降法语法分析器。

输入：源符号串。

输出：语法是否合法。

：文法：(1) <程序> ::= begin<语句串>end(2) <语句串> ::= <语句>{;<语句>}(3) <语句> ::= <赋值语句>(4) <赋值语句> ::= ID:=<表达式>(5) <表达式> ::= <项>{+<项>|-<项>}(6) <项> ::= <因子>{*<因子>|/<因子>}(7) <因子> ::= ID|NUM|(<表达式>)五:源程序：lrparser()对应 <程序>yucu() 对应 <语句串>statement() 对应 <语句>expression()对应 <表达式>term() 对应 <项>factor() 对应 <因子>关键字，数字，字母，符号对应码如下"begin", "if", "then", "while", "do", "end" 1——6字母 10 数字11+,-,*,/,:,:=,<,<>,<=,>,>=,=,;,(,),# 13——28,0factor()#include "stdio.h"#include "string.h"char prog[80], token[8];char ch;int syn, p, m, n, sum, kk=0;char *rwtab[6]={"begin", "if", "then", "while", "do", "end"};void scaner();void lrparser();void yucu();void statement();void expression();void term();void factor();void main(){p=0;printf("Please input string:\n");do{scanf("%c", &ch);prog[p++]=ch;}while(ch!='#'); //当遇到‘#’，结束输入p=0;scaner();lrparser();}void scaner(){for(n=0; n<8; n++) token[n]=NULL;ch=prog[p++];while(ch==' '||ch=='\n') ch=prog[p++];m=0;if((ch>='A'&&ch<='Z') || (ch>='a'&&ch<='z')){while((ch>='A'&&ch<='Z') || (ch>='a'&&ch<='z')||(ch>='0'&&ch<='9')){token[m++]=ch;ch=prog[p++];//将prog数组的字母复制到ch数组中}token[m++]='\0';//把token的末尾设置结束符\0p--;//标记到当前token数组中不是字母的当前位置syn=10; //标记字母的对应码for(n=0; n<6; n++){if(strcmp(token, rwtab[n])==0)//判断token对应rwtab中的哪一个,并进行对应赋对应码{syn=n+1;break;}}}else if(ch>='0'&&ch<='9'){sum=0;while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';//number用来记录所对应的数字ch=prog[p++];}p--;syn=11;//标记数字的对应码}else{switch(ch){case '<':m=0;token[m++]=ch;ch=prog[p++];if(ch=='>'){syn=21; //标记”<>”的对应码token[m++]=ch;}else if(ch=='='){syn=22; //标记”<=”的对应码token[m++]=ch;}else{syn=20; //标记”<”的对应码p--;}break;case '>':token[m++]=ch;ch=prog[p++];if(ch=='='){syn=24; //标记”>=”的对应码token[m++]=ch;}else{syn=23; //标记”>”的对应码p--;}break;case ':':token[m++]=ch;ch=prog[p++];if(ch=='='){syn=18; //标记”:=”的对应码token[m++]=ch;}else{syn=17; //标记”:”的对应码p--;}break;case '+':syn=13; //标记”+”的对应码token[m++]=ch;break;case '-':syn=14; //标记”-”的对应码token[m++]=ch;break;case '*':syn=15; //标记”*”的对应码token[m++]=ch;break;case '/':syn=16; //标记”/”的对应码token[m++]=ch;break;case '=':syn=25; //标记”=”的对应码token[m++]=ch;break;case ';':syn=26; //标记”；”的对应码token[m++]=ch;break;case '(':syn=27; //标记”（”的对应码token[m++]=ch;break;case ')':syn=28; //标记”）”的对应码token[m++]=ch;break;case '#':syn=0; //标记”#”的对应码token[m++]=ch;break;default:syn=-1; //当不是上述字母，数字，符号时，设置syn=-1 }token[m++]='\0';}}void factor()//因子{if(syn==10 || syn==11) //当扫描的是数字或字母时，继续扫描{scaner();}else if(syn==27) //当扫描的‘（’时，继续扫描{scaner();expression();if(syn==28) //当扫描的是‘）’时，继续扫描scaner();else{kk=1;printf("ERROR: )错误\n");//表达式缺乏‘）‘，出错}}else{kk=1;printf("ERROR: 表达式错误\n");//扫描表达式，表达式开头不是‘（‘，出错}}void term()//项{factor();while(syn==15 || syn==16) //当开头扫描的是’*’或’/’时，继续扫描{scaner();factor();}}void expression()//表达式{term();while(syn==13 || syn==14) //当开头扫描的是’+’或’-’时，继续扫描{scaner();term();}}void statement()//语句{if(syn==10) //当开头扫描的是字母时，继续扫描{scaner();if(syn==18) //扫描的是’:=’时，继续扫描{scaner();expression();}else{kk=1;printf("ERROR: 赋值号错误\n");//当扫描的是’:=’，出错}}else{kk=1;printf("ERROR: 语句错误\n");}}void yucu()//语句串{statement();while(syn==26) //当开始扫描到的是’；’，继续扫描{scaner();statement();}}void lrparser()//程序{if(syn==1) //当开头扫描的是‘begin‘时，继续扫描{scaner();yucu();if(syn==6){scaner();if(syn==0 && kk==0) //当数字串的最后扫描的是‘#‘，而且并无出错，分析成功printf("success!\n");else if(syn!=0 && kk==0){kk=1;printf("ERROR: END后未正常结束\n");//数字串的最后并没有扫描到符号‘#‘，出// 错}}else{if(kk!=1){kk=1;printf("ERROR: 缺少end\n");//程序分析结束并没有扫描到’end’，出错}}}else{kk=1;printf("ERROR: begin错误\n");//开始时并没有扫描到’begin’，出错}}。

编译原理之递归下降语法分析程序（实验）⼀、实验⽬的利⽤C语⾔编制递归下降分析程序,并对简单语⾔进⾏语法分析。

编制⼀个递归下降分析程序,实现对词法分析程序所提供的单词序列的语法检查和结构分析。

⼆、实验原理每个⾮终结符都对应⼀个⼦程序。

该⼦程序根据下⼀个输⼊符号(SELECT集)来确定按照哪⼀个产⽣式进⾏处理，再根据该产⽣式的右端:每遇到⼀个终结符，则判断当前读⼊的单词是否与该终结符相匹配，若匹配，再读取下⼀个单词继续分析；不匹配，则进⾏出错处理每遇到⼀个⾮终结符，则调⽤相应的⼦程序三、实验要求说明输⼊单词串，以“＃”结束，如果是⽂法正确的句⼦，则输出成功信息，打印“success”,否则输出“error”，并指出语法错误的类型及位置。

例如：输⼊begin a:=9;b:=2;c:=a+b;b:=a+c end #输出success输⼊a:=9;b:=2;c:=a+b;b:=a+c end #输出‘end' error四、实验步骤1．待分析的语⾔的语法（参考P90）2．将其改为⽂法表⽰，⾄少包含–语句–条件–表达式E -> E+T | TT -> T*F | FF -> (E) | i3. 消除其左递归E -> TE'E' -> +TE' | εT -> FT'T' -> *FT' | εF -> (E) | i4. 提取公共左因⼦5. SELECT集计算SELECT(E->TE) =FIRST(TE')=FIRSI(T)-FIRST(F)U{*}={(, i, *}SELECT(E'->+TE')=FIRST(+TE')={+}SELECT(E'->ε)=follow(E')=follow(E)={#, )}SELECT(T -> FT')=FRIST(FT')=FIRST(F)={(, i}SELECT(T'->*FT')=FRIST(*FT')={*}SELECT(T'->ε)=follow(T')=follow(T)={#, ), +}SELECT(F->(E))=FRIST((E)) ={(}SELECT(F->i)=FRIST(i) ={i}6. LL(1)⽂法判断 其中SELECT(E'->+TE')与SELECT(E'->ε)互不相交，SELECT(T'->*FT')与SELECT(T'->ε)互不相交，SELECT(F->(E))与SELECT(F->i)互不相交，故原⽂法为LL（1）⽂法。

编译原理实验报告实验名称：编写递归下降语法分析程序实验类型：验证型实验指导教师：专业班级：姓名：学号：电子邮件：实验地点：实验成绩：日期：201 年 5 月 25 日一、实验目的通过设计、调试递归下降语法分析程序，实现用词法分析从源程序中分出各种单词并对词法分析程序提供的单词序列进行语法检查和结构分析，熟悉并掌握常用的语法分析方法。

明确语法分析器的功能，在词法分析的基础上进一步分析程序；加深对课堂教学的理解；提高语法分析方法的实践能力；通过本实验，应达到以下目标：1、掌握递归下降的结构模型。

2、掌握语法分析的实现方法。

3、上机调试编出的语法分析程序。

二、实验过程有了第一次的经验，这次还是先画出流程图。

流程图如下：三、实验结果语法分析实验成功。

赋值时少写数字：缺少括号时：附（txt文档内容）：程序运行后写入的：四、讨论与分析这个程序是在实验一的基础上写的，用的递归下降的方法。

不止能识别，还能判断一些语法的正误。

刚看书上附录的代码时，头都大了，觉得自己完成不了。

但是真正一步一步看下去，画出了流程图，就很清晰明白了。

一个函数嵌套一个函数，一步一步往细处走，刚开始是大体轮廓，然后就深入，直到最低层的判断。

书上的程序还是有一些漏洞，比如要写多个语句时，if，for，while在语句内不能加括号，不然只能分析至第一个，遇到“｝”就结束了，所以在txt文件里写程序代码的时候要注意不能加｛｝，这样才可以全部printf出来。

五、附录：关键代码（给出适当注释，可读性高）全部代码附vc++，这里粘贴主程序，以及各类函数。

int TESTparse();int TESTscan();int program();int compound_stat();int statement();int expression_stat();int expression();int bool_expr();int additive_expr();int term();int factor();int if_stat();int while_stat();int for_stat();int write_stat();int read_stat();int declaration_stat();int declaration_list();int statement_list();int compound_stat();#include<stdio.h>#include<ctype.h>int TESTscan();int TESTparse();FILE *fin,*fout；void main(){int es=0;es=TESTscan();if(es>0)printf("词法分析有错！编译停止！\n");else{printf("词法分析成功！\n");}if(es==0){es=TESTparse();if(es==0)printf("语法分析成功！\n");elseprintf("语法分析错误！\n");}}六、实验者自评这个实验比第一个有难度，是在第一个完成的基础上进行的。

递归下降语法分析姓名：郝梦朔学号：日期：2010-1-17一、实验目的构造文法的语法分析程序，要求采用递归下降语法分析方法对输入的字符串进行语法分析，实现对词法分析程序所提供的单词序列的语法检查和结构分析，进一步掌握递归下降的语法分析方法。

二、实验内容编写为一上下文无关文法构造其递归下降语法分析程序，并对任给的一个输入串进行语法分析检查。

程序要求能对输入串进行递归下降语法分析，能判别程序是否符合已知的语法规则，如果不符合（编译出错），则输出错误信息。

三、实验要求利用C语言编制递归下降分析程序，并对语言进行语法分析。

（1）待分析的语言的语法。

用扩充额BNF表示如下。

①<程序>::=function<语言串>endfunc②<语言串>::=<语句>{;<语句>}③<语句>::=<赋值语句>④<赋值语句>::=ID=<表达式>⑤<表达式>::=<项>{+<项>|-<项>}⑥<项>::=<因子>{*<因子>|/<因子>}⑦<因子>::=ID|NUM|(<表达式>)（2）实验要求说明输入单词串以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”，具体例子如下。

输入functiona=9;x=2*3;b=a+x;endfunc#输出success又如，输入：x=a+b*cendfunc#输出error（3）语法分析程序的算法思想为翟玉庆老师上课所讲。

四、实验源程序#include<stdio.h>#include<string.h>char prog[80],token[8];char ch;int syn,p,m=0,n,sum,kk=0;char *rwtab[6]={"function","if","then","while","do","endfunc"};void scaner();void lrparser();void yucu();void statement();void expression();void term();void factor();void main(){p = 0;printf("please input the string:\n");do{ch = getchar();prog[p++] = ch;}while(ch != '#');p = 0;ch = prog[p++];scaner();lrparser();return;}void scaner(){for(n=0;n<8;n++)token[n]=NULL;//printf("\n%c in scaner()",ch);while(ch == ' ' || ch == '\n' )ch = prog[p++];//printf("\n%c in scaner()",ch);m = 0;if((ch<='z' && ch>='a') ||(ch<='Z' && ch>='A')){while((ch<='z' && ch>='a') ||(ch<='Z' && ch>='A')||(ch<='9' && ch>='0')){token[m++] = ch;ch = prog[p++];}syn=10;for(n=0;n<6;n++)if(strcmp(token,rwtab[n]) == 0){syn = n+1;//printf("\n%d in keyword",syn);break;}token[m++] = '\0';}else if(ch<='9' && ch>='0'){sum=0;while(ch<='9' && ch>='0'){sum = sum*10 + ch - '0';ch = prog[p++];}syn = 11;}else{switch(ch){case '<':m = 0;token[m++] = ch;ch = prog[++p];if(ch == '='){syn = 22;token[m++] = ch;}else{syn = 20;ch = prog[--p];}break;case '>':m = 0;token[m++] = ch;ch = prog[++p];if(ch == '='){syn = 24;token[m++] = ch;}else{syn = 23;ch = prog[--p];}break;case '=':m = 0;token[m++] = ch;ch = prog[++p];if(ch == '='){syn = 25;token[m++] = ch;}else{syn = 18;ch = prog[--p];}break;case '!':m = 0;token[m++] = ch;ch = prog[++p];if(ch == '='){syn = 22;token[m++] = ch;}elsesyn = -1;break;case '+':syn = 13;token[0] = ch;break;case '-':syn = 14;token[0] = ch;break;case '*':syn = 15;token[0] = ch;break;case '/':syn = 16;token[0] = ch;break;case ';':syn = 26;token[0] = ch;break;case '(':syn = 27;token[0] = ch;break;case ')':syn = 28;token[0] = ch;break;case '#':syn = 0;token[0] = ch;break;default:syn = -1;}ch = prog[p++];}}void lrparser(){if(syn ==1){//printf("\n%d",syn);scaner();//printf("\n%d",syn);yucu();/**/// printf("\n%d after yucu()",syn);if(syn == 6){scaner();//printf("\n%d in lrparser() after scaner()",syn);if(syn == 0 && kk == 0)printf("\nsuccess!\n");else{if(kk != 1){printf("error!need 'endfunc'");kk = 1;}}}else{printf("error!need 'function'");kk =1;}return;}void yucu(){//printf("\n%d in yucu() first",syn);statement();//printf("\n%d after statement() in yucu()",syn);while(syn == 26){scaner();//syn = 6;//printf("\n%d after scaner() in yucu()",syn);statement();}return;}void statement(){//printf("\n%d in statement() at first",syn);if(syn == 10){scaner();//printf("\n%d after scaner() in statement()",syn);if(syn == 18){scaner();// printf("\n%d after scaner when syn=18",syn);expression();// printf("\n%d after expression()",syn);else{printf("error! evaluate tag error");kk = 1;}}else if(syn == 6)return;else{printf("error! the statement error!");kk = 1;}return;}void expression(){// printf("\n%d in expression at first",syn);term();while(syn == 13 || syn == 14){scaner();term();}return;}void term(){// printf("\n%d in term() at first",syn);factor();while(syn == 15 || syn == 16){scaner();factor();}return;}void factor(){// printf("\n%d in factor() at first",syn);if(syn == 10 || syn == 11){scaner();}else{if(syn == 27){scaner();expression();if(syn == 28){scaner();}else{printf("error! need another ')'");kk = 1;}}else{printf("error! expression error!");}}}五、程序运行效果截图六、心得体会这个实验其实是上个实验的扩展，有个上个实验的基础做这个实验就比较轻松了。