下载文档原格式
c语⾔递归算法实验报告,递归算法的设计与实现实验报告-read.doc递归算法的设计与实现实验报告-read递归算法的设计与实现实验报告⼀、实验⽬的：a)掌握递归算法的基本思想及其与数学归纳法的关系;b)掌握递归算法设计与实现。
⼆、实验内容a)⽤递归算法计算n!；b)⽤递归⽅法求⾮负整数a和b(a,b不全为0)的最⼤公约数。
三、实验要求a)⽤伪代码计算n!和求⾮负整数a,b(a,b不全为零)的最⼤公约数的递归算法；b)⽤C＋＋语⾔实现算法并测试通过；c)⽐较采⽤欧⽒算法和递归算法求⾮负a,b(a,b不全为零)的最⼤公约数的执⾏效率。
四、(⼀)使⽤递归算法求n!的伪代码表⽰：1.Procedurefactorial (n)2. if n= = 0 then3. return (1)4. return (n * factorial (n-1))5. end(⼆)使⽤递归算法求⾮负整数a和b(a,b不全为0)的最⼤公约数的伪代码表⽰：输⼊：a和b(不全为0的⾮负整数)输出：a和b的最⼤公约数1. Procedure gcd_recurs (a, b)2. if a3. swap (a, b)4. if b = 0 then5. return (a)6. a 除以 b 得到 a = bq + r ，0 ￡ r < b7. redurn (gcd_recurs (b, r))8. end gcd_recurs五、(⼀)使⽤递归算法求n!的C语⾔实现：#include"stdio.h"long fac(int n){long result;if(n==0||n==1)result=1;elseresult=n*fac(n-1);return result;}main(){int x;long f;printf("please input one numbers: ");scanf("%d",&x);if(x<=0)printf("ERROR!\n");else{f=fac(x);printf("%d!=%ld\n",x,f);}}结果截图：(⼆)使⽤递归算法求⾮负整数a和b(a,b不全为0)的最⼤公约数的C语⾔实现：#include"stdio.h"int gcd(int a,int b){int temp,c;if(a{temp=a;a=b;b=temp;}if(b==0)return a;else{c=a%b;return(gcd(b,c));}}main(){int a,b;printf("please input two numbers:\n");scanf("%d%d",&a,&b);printf("gcd(%d,%d)=%d\n",a,b,gcd(a,b));}结果截图：六、⽐较采⽤欧⽒算法和递归算法求⾮负a,b(a,b不全为零)的最⼤公约数的执⾏效率。
学年第学期《编译原理》实验报告学院（系）：计算机科学与工程学院班级：11303070A学号：***********姓名：无名氏指导教师：保密式时间：2016 年7 月目录1．实验目的 (1)2．实验内容及要求 (1)3．实验方案设计 (1)3.1 编译系统原理介绍 (1)3.1.1 编译程序介绍 (2)3.1.2 对所写编译程序的源语言的描述 (2)3.2 词法分析程序的设计 (3)3.3 语法分析程序设计 (4)3.4 语义分析和中间代码生成程序的设计 (4)4. 结果及测试分析 (4)4.1软件运行环境及限制 (4)4.2测试数据说明 (5)4.3运行结果及功能说明 (5)5．总结及心得体会 (7)1．实验目的根据Sample语言或者自定义的某种语言，设计该语言的编译前端。
包括词法分析，语法分析、语义分析及中间代码生成部分。
2．实验内容及要求（1）词法分析器输入源程序，输出对应的token表，符号表和词法错误信息。
按规则拼单词，并转换成二元形式；滤掉空白符，跳过注释、换行符及一些无用的符号；进行行列计数，用于指出出错的行列号，并复制出错部分；列表打印源程序；发现并定位词法错误；（2）语法分析器输入token串，通过语法分析，寻找其中的语法错误。
要求能实现Sample 语言或自定义语言中几种最常见的、基本的语法单位的分析：算术表达式、布尔表达式、赋值语句、if语句、for语句、while语句、do while语句等。
（3）语义分析和中间代码生成输入token串，进行语义分析，修改符号表，寻找其中的语义错误，并生成中间代码。
要求能实现Sample语言或自定义语言中几种最常见的、基本的语法单位的分析：算术表达式、布尔表达式、赋值语句、if语句、for语句、while 语句、do while语句等。
实验要求：功能相对完善，有输入、输出描述，有测试数据，并介绍不足。
3．实验方案设计3.1 编译系统原理介绍编译器逐行扫描高级语言程序源程序，编译的过程如下：(1).词法分析识别关键字、字面量、标识符(变量名、数据名)、运算符、注释行(给人看的，一般不处理)、特殊符号(续行、语句结束、数组)等六类符号，分别归类等待处理。
专题3_LL(1)语法分析设计原理与实现李若森 13281132 计科1301一、理论传授语法分析的设计方法和实现原理；LL(1) 分析表的构造；LL(1)分析过程；LL(1)分析器的构造。
二、目标任务实验项目实现LL(1)分析中控制程序（表驱动程序）；完成以下描述算术表达式的 LL(1)文法的LL(1)分析程序。
G[E]:E→TE’E’→ATE’|εT→FT’T’→MFT’|εF→(E)|iA→+|-M→*|/设计说明终结符号i为用户定义的简单变量，即标识符的定义。
加减乘除即运算符。
设计要求(1)输入串应是词法分析的输出二元式序列，即某算术表达式“专题 1”的输出结果，输出为输入串是否为该文法定义的算术表达式的判断结果；(2)LL(1)分析程序应能发现输入串出错；(3)设计两个测试用例（尽可能完备，正确和出错），并给出测试结果。
任务分析重点解决LL(1)表的构造和LL(1)分析器的实现。
三、实现过程实现LL(1)分析器a)将#号放在输入串S的尾部b)S中字符顺序入栈c)反复执行c)，任何时候按栈顶Xm和输入ai依据分析表，执行下述三个动作之一。
构造LL(1)分析表构造LL(1)分析表需要得到文法G[E]的FIRST集和FOLLOW集。
构造FIRST(α)构造FOLLOW(A)构造LL(1)分析表算法根据上述算法可得G[E]的LL(1)分析表，如表3-1所示：表3-1 LL(1)分析表主要数据结构pair<int, string>:用pair<int, string>来存储单个二元组。
该对照表由专题1定义。
map<string, int>:存储离散化后的终结符和非终结符。
vector<string>[][]:存储LL(1)分析表函数定义init:void init();功能：初始化LL(1)分析表，关键字及识别码对照表，离散化（非）终结符传入参数：（无）传出参数：（无）返回值：（无）Parse:bool Parse( const vector<PIS> &vec, int &ncol )；功能：进行该行的语法分析传入参数：vec:该行二元式序列传出参数：emsg:出错信息epos:出错标识符首字符所在位置返回值：是否成功解析。
编译原理实验报告实验一词法分析设计一、实验功能：1、对输入的txt文件内的内容进行词法分析：2、由文件流输入test.txt中的内容，对文件中的各类字符进行词法分析3、打印出分析后的结果；二、程序结构描述：（源代码见附录）1、分别利用k[],s1[],s2[],s3[]构造关键字表，分界符表，算术运算符表和关系运算符表。
2、bool isletter(){} 用来判断其是否为字母，是则返回true，否则返回false；bool isdigit(){} 用来判断其是否为数字，是则返回true，否则返回false；bool iscalcu(){} 用来判断是否为算术运算符，是则返回true，否则返回false；bool reserve(string a[]){} 用来判断某字符是否在上述四个表中，是则返回true，否则返回false；void concat(){} 用来连接字符串；void getn(){} 用来读取字符；void getb(){} 用来对空格进行处理；void retract(){}某些必要的退格处理；int analysis(){} 对一个单词的单词种别进行具体判断；在主函数中用switch决定输出。
三、实验结果四、实验总结词法分析器一眼看上去很复杂，但深入的去做就会发现并没有一开始想象的那么困难。
对于一个字符的种别和类型可以用bool函数来判断，对于关键字和标示符的识别（尤其是3b）则费了一番功夫，最后对于常数的小数点问题处理更是麻烦。
另外，这个实验要设定好时候退格，否则将会导致字符漏读甚至造成字符重复读取。
我认为，这个实验在程序实现上大体不算困难，但在细节的处理上则需要好好地下功夫去想，否则最后的程序很可能会出现看上去没有问题，但实际上漏洞百出的状况。
将学过的知识应用到实际中并不简单，只有自己不断尝试将知识转化成程序才能避免眼高手低，对于知识的理解也必将更加深刻。
实验二LL(1)分析法一、实验原理：1、写出LL（1）分析法的思想：当一个文法满足LL(1)条件时，我们就可以为它构造一个不带回溯的自上而下的分析程序，这个分析程序是有一组递归过程组成的，每个过程对应文法的一个非终结符。
编译原理实验报告实验名称消除文法的左递归实验时间2013年11月12日院系计算机科学与电子技术系班级11计算机软件学号JV114001 JV114095 JP114065 姓名唐茹韩强强徐思维1.试验目的：输入：任意的上下文无关文法。
输出：消除了左递归的等价文法。
2.实验原理：1．直接左递归的消除消除产生式中的直接左递归是比较容易的。
例如假设非终结符P 的规则为：P →P α / β其中，β是不以P 开头的符号串。
那么，我们可以把P 的规则改写为如下的非直接左递归形式： P →βP ’P ’→αP ’ / ε这两条规则和原来的规则是等价的，即两种形式从P 推出的符号串是相同的。
设有简单表达式文法G[E]： E →E+T/ T T →T*F/ F F →（E ）/ I经消除直接左递归后得到如下文法： E →TE ’E ’ →+TE ’/ ε T →FT ’T ’ →*FT ’/ εF →（E ）/ I考虑更一般的情况，假定关于非终结符P 的规则为P →P α1 / P α2 /…/ P αn / β1 / β2 /…/βm其中，αi （I ＝1，2，…，n ）都不为ε，而每个βj （j ＝1，2，…，m ）都不以P 开头，将上述规则改写为如下形式即可消除P 的直接左递归：P →β1 P ’ / β2 P ’ /…/βm P ’P ’ →α1P ’ / α2 P ’ /…/ αn P ’ /ε 2．间接左递归的消除直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。
然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。
有些文法虽然表面上不存在左递归，但却隐藏着左递归。
例如，设有文法G[S]：S →Qc/ c Q →Rb/ b R →Sa/ a虽不具有左递归，但S 、Q 、R 都是左递归的，因为经过若干次推导有 S ⇒Qc ⇒Rbc ⇒SabcQ ⇒Rb ⇒Sab ⇒Qcab R ⇒Sa ⇒Qca ⇒Rbca就显现出其左递归性了，这就是间接左递归文法。
专业资料 word完美格式 《编译原理》实验报告 实验3 递归下降分析器的设计
姓名 学号 班级 计科1001班 时间： 2012/4/15 地点:文波 同 组 人：无 指导教师：朱少林
实验目的
使用递归子程序法设计一个语法分析程序，理解自顶向下分析方法的原理，掌握手工编写递归下降语法分析程序的方法。
实验内容 a. 运用所学知识，编程实现递归下降语法分析程序。使用递归下降分析算法分析表达式是否符合下文法： exp → exp addop term | term Addop →+ | - term→ term mulop factor | factor mulop → * | / factor → (exp) | id | number 其中number可以是多位的十进制数字串（整数即可），因此这里还需要一个小的词法分析器来得到id 和number的值。 b. 从数据文件中读出符号串，输出表达式并给出其正误评判。 实验数据文件中应该有多个表达式，可能有正确的也应该有错误的表达式；表达式有形式简单的也应该有复杂的。每个表达式写在一行，以回车结束。
实验环境
软件：VC++6.0 专业资料 word完美格式 实验前准备 1、 方案设计： ① 准备模拟数据：本实验中使用 “work..cpp” ② 程序思想： 为了使用递归向下的分析，为每个非终结符根据其产生式写一个分析程序，由于写入读出的操作频繁。所以程序中还有一个match(char t)函数，该函数是将字符写入文件打印输出同时从文件中读取下一个字符，而由于id和number可能是多个字符构成，故写了number()和id（）来分析数字和标识符，它们的功能仅仅是把整个number或id完整的读取出来并写入文件，打印输出。 由于分析的文件中可能出现非法字符，而一旦发现非法字符就无需再接着分析，所以在每次读取一个字符时调用islegal函数判断是否是合法字符，并返回0或1. 在main()函数中，while((lookahead=='\n'||lookahead==' ')&&lookahead!=EOF) fscanf(resource,"%c",&lookahead); 是为了忽略分析文件中的换行或空格，之后进入分析阶段，根据返回值判断是否是合法的表达式。在该程序中只有发现了非法字符才会返回0，否则就返回1，而对于合法的表达式，递归程序最后分析的字符就是换行符，不合法的表达式在未分析到换行符就会停止分析，所以根据最后分析的字符是否为换行符进一步确定是否为合法的表达式。
实验步骤
首先将上述文法改写成LL（1）文法 ① 消除左递归： exp →term texp texp → addop term texp | ε Addop →+ | - term→factor tterm tterm →mulop factor tterm|ε mulop → * | / factor → (exp) | id | number ② 求出每个非终结符的FIRST集合和FOLLOW集合： FIRST(exp)= FIRST(term)= FIRST(factor)={id, number, ( } FIRST(texp)={ ε,+, - } FIRST(Addop)={+, - } FIRST(tterm)={ ε,*, / } FIRST(mulop)={*, / } 求出每个非终结符的FOLLOW集合： FOLLOW(exp)=FOLLOW(texp)={#, ）} 专业资料 word完美格式 FOLLOW(Addop)=FOLLOW(mulop)={id, number, ( } FOLLOW(term)=FOLLOW(tterm)={+, -,#, ) } FOLLOW(factor)={ *,/,+,-,#,) } 对于texp → addop term texp | ε：FIRST（Addop term texp）∩FOLLOW(texp)= φ； 对于tterm →mulop factor tterm|ε：FIRST(mulop factor tterm)∩FOLLOW(tterm)= φ； 而Addop →+ | - mulop → * | / factor → (exp) | id | number 显然也是符合LL（1）文法要求的，所以改写后的文法符合LL（1）文法，可以用自上而下的递归分析方法。 ③ 为每个非终结符根据其产生式写一个分析子程序； ④ 编写数字和字母识别程序，以便分离数字和标识符。； ⑤ 主函数调用递归程序进行分析，根据分析结果判断是否是合法表达式，并将所有识别到的表达式输出。 程序设计： #include #include
number(); id();
int exp(); int texp(); int addop(); int term(); int tterm(); int mulop(); int factor();
int islegal(); void match(char t);
FILE *resource;//测试文件 FILE *result;//结果文件 char lookahead;//全局变量 专业资料 word完美格式 void match(char t)//写入result文件,打印输出，并读取下一个 {
fprintf(result,"%c",lookahead);//向result写入 printf("%c",lookahead); fscanf(resource,"%c",&lookahead);//读数据
} number()//识别数字，如果遇到数字就一直接着读直到不是数字 {
while('0'<=lookahead&&lookahead<='9') { fprintf(result,"%c",lookahead);//写入 printf("%c",lookahead); fscanf(resource,"%c",&lookahead);//读出 }
}
id() {//识别标识符
while((lookahead<='z'&& lookahead>='a')||(lookahead>='A'&& lookahead<='Z')||lookahead=='_') { while((lookahead<='z'&& lookahead>='a')||(lookahead>='A'&& lookahead<='Z')||lookahead=='_' ||lookahead>='0'&&lookahead<='9') { fprintf(result,"%c",lookahead);//写入 printf("%c",lookahead); fscanf(resource,"%c",&lookahead);//读 }
} } 专业资料 word完美格式 int addop()//Addop →+ | - { //分析+，- int i;
if(lookahead=='+')//+ { match('+'); i=islegal();//判断下一个是否是合法字符，如果不是则返回0 if(i) return 1; else return 0; } else if(lookahead=='-')//- { match('-'); i=islegal(); if(i) return 1; else return 0; } else return 0; } int mulop()//mulop → * | / { //分析*，/ int i; if(lookahead=='*') { match('*'); i=islegal(); if(i) return 1; else return 0; } else if(lookahead=='/') { match('/'); i=islegal(); if(i) 专业资料 word完美格式 return 1; else return 0; } else return 0;
} int exp()//exp →term texp {
int i,j; while(!feof(resource)) { if(lookahead=='('||'0'<=lookahead&&lookahead<='9'|| (lookahead<='z'&& lookahead>='a')||(lookahead>='A'&& lookahead<='Z')||lookahead=='_') //FIRST(term)={id, number, ( } { i=term(); if(i) { j=texp(); if(j) {
return 1;//当且仅当term和texp都返回1时才返回1 } else {
return 0; } } else {
return 0; } } else { return 0;; }
