仲恺农业技术学院
编译原理课程设计课程设计题目：LL(1)递归下降分析器
姓名：
院（系）：
专业班级：
学号：
指导教师：
设计日期：
目录
1、需求分析 (1)
2、概要设计 (2)
3、详细设计 (3)
4、测试分析 (8)
5、用户手册 (9)
6、课程总结 (9)
7、参考文献 (10)
题目：LL （1）递归下降分析器
1、需求分析
语法分析是编译过程的核心部分。语法分析器的任务是识别和处理比单词更大的语法单位。如：程序设计语言中的表达式，各种说明和语句乃至全部源程序，指出其中的语法错误；必要时，可生成内部形式，便于下一阶段处理。
我们知道，语言的语法结构是用上下文无关文法描述的。按照语法分析树的建立方法，我们可以粗略地把语法分析办法分成两类，一类是自上而下分析，另一类是自下而上分析法。而自上而下这种方法是带“回溯”的，且存在许多困难和缺点。
首先，是文法的左递归性问题。一个文法是含有左递归的，如果存在非终结符P 且
α
P P +
?，含有左递归的文法使上述的自上而下的分析过程陷入无限循环。即，当试图用P
去匹配输入串时，我们会发现，在没有识别任何输入符号的情况下，有得重新要求P 去进行新的匹配。因此，使用自上而下分析法必须消除文法的左递归性。
其次，由于回溯，就碰到一大堆麻烦问题。如果我们走了一大段错路，最后必须回头，那么，就应把已经做的一大堆语义工作（指中间代码产生工作和各种表格的簿记工作）推倒重来。这些事情既麻烦又费时间，所以，最好应设法消除回溯。
第三，在自上而下分析过程中，当一个非终结符用某一候选匹配成功时，这种成功可能仅是暂时的。
第四，当最终报告分析不成功时，我们难于知道输入串中出错的确切位置。
最后，由于带回溯的自上而下分析实际上采用了一种穷尽一切可能的试探法，因此，效率很低，代价极高。严重的低效使得这种分析法只有理论意义，而在实践上价值不大。
由于上述原因，我们需要把原算术表达式改写为LL(1)文法，LL(1)文法的文法条件如下： 文法不含左递归。
对于文法中每一个非终结符A 的各个产生式的候选首集符两两不相交。即，若
n
A ααα|||21 →，则
()()φα
α=?j
i FIRST FIRST ()j i ≠
对文法中的每个非终结符A ，若它存在某个候选首符集包含ε，则
()()φ
=?A F O L L O W A F I R S T
LL(1)中的第一个L 表示从左到右扫描输入串，第二个L 表示最左推导，1表示分析时每
一步只需向前查看一个符号。当一个文法满足LL(1)条件时，我们就可以为它构造一个不带回溯的自上而下分析程序，这个分析程序是由一组递归过程组成的，每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。
2、概要设计
编程实现给定算术表达式的递归下降分析器。
算术表达式文法如下：
E-->E+T|E-T|T
T-->T*F|T/F|F
F-->(E)| i
首先改写文法为LL(1)文法；然后为每一个非终结符，构造相应的递归过程，过程的名字表示规则左部的非终结符；过程体按规则右部符号串的顺序编写。
上述算法表达式文法属于比较典型的递归下降语法分析。需要先将原算术表达式方法改写为LL(1)文法为：
E-->TE’
E’-->+TE’|-TE’| ε
T-->FT’
T’-->*FT’|/FT’| ε
F-->(E)| i
然后再为每个非终结符设计一个对应的函数，通过各函数之间的递归调用从而实现递归下降语法分析的功能。
具体方法为：
（1）当遇到终结符a时，则编写语句
If(当前读到的输入符号==a)读入下一个输入符号
（2）当遇到非终结符A时，则编写语句调用A()。
（3）当遇到A-->ε规则时，则编写语句
If(当前读到的输入符号不属于Follow(A)) error()
（4）当某个非终结符的规则有多个候选式时，按LL(1)文法的条件能唯一地选择一个候选式进行推导.
递归下降子程序流程图：
图1递归下降子程序流程图
3、详细设计
#include
char inputstream[50]; //存储输入句子 int temp=0; //数组下标
int right; //判断输出信息
void e();
void e1();
void t();
void t1();
void f();
void main()
{
right=1;
cout<<"---------------------------------------------------"< cout<<"请输入您要分析的字符串以#结束（^为空字符）:"< cin>>inputstream; cout<<"---------------------------------------------------"< cout< cout<<"开始进行语法分析"< e(); if((inputstream[temp]=='#')&&right) cout<<"分析成功"< else cout<<"分析失败"< } void e() { cout<<"E->TE'"< t(); e1(); } void e1() { if(inputstream[temp]=='+') { cout<<"E'->+TE'"< temp++; t(); e1(); } else if(inputstream[temp]=='-') { cout<<"E'->-TE'"< temp++; t(); e1(); } else if(inputstream[temp]!='#'||inputstream[temp]!=')') { cout<<"T'->^"< return; } else right=0; } void t() { cout<<"T->FT'"< f(); t1(); } void t1() { if(inputstream[temp]=='*') { cout<<"T'->*FT'"< temp++; f(); t1(); } else if(inputstream[temp]=='/') { cout<<"T'->/FT'"< temp++; f(); t1(); } else if(inputstream[temp]!='#'&&inputstream[temp]!=')'&&inputstream[temp]!='+'&&input stream[temp]!='-') { cout<<"T'->^"< right=0; } } void f() { if(inputstream[temp]=='i') { cout<<"F->i"< temp++; } else if(inputstream[temp]=='(') { cout<<"F->(E)"< temp++; e(); if(inputstream[temp]==')') { cout<<"F->(E)"< temp++; } else right=0; } else right=0; } 4、测试分析 图2 测试分析成功 图3 测试分析失败 5、用户手册 开发工具：visual c++ 6.0 开发环境：windows XP操作系统 运行环境：windows 9x,windows NT,Windows 2000,windows XP 注意：输入时，程序最多只能接受50个字符，输入完算术表达式后要以“#”号结束。 6、课程总结 通过一个星期的努力，终于把编译原理课程设计给完成了。我觉得编译原理这门课是一门非常难学的课程，它涉及文法、词法分析、语法分析属性文法和语义分析等等一系列内容，课本里的内容和定义也非常的抽象且枯燥。如果上课没有好好的认真听课，自己独自学习就感到非常的吃力，而且效果也不好。本人因为上课无法做到打醒十二分专心听课，经常会分神，所以学习的效果也不怎么好。这也给做编译原理课程设计带来了困难。 本次课程设计，我选的课程设计题目是LL(1)递归下降分析器，这个题目涉及的内容有关课本第四章语法分析——自上而下分析里面的内容。在开始动手对题目进行设计和编程之前，我重复的仔细认真的阅读和理解课本第四章里面的内容，弄懂自上而下分析面临的问题、何谓左递归，搞清楚如何消除左递归、如何消除回溯、提左因子，理解构造LL(1)文件需要什么条件。虽然这花费了一定的时间和精力，但那点付出也是值得的，通过复习让我加深理解了有关自上而下语法分析的内容，而且也为用高级语言实现递归下降分析器带来便利。 在用C++编程时，基本上没有遇到什么困难，只需把所有递归过程都写出就行了。但是要注意的是，在编写代码时，要根据LL(1)文法的工作原理去设计。通过本次课程设计清楚地了解到递归下降分析法的优缺点，其优点是简单、直观，易于构造分析程序。缺点是对文法要求高，必须是LL(1)文法，同时由于递归调用较多，影响分析器的效率。 课程设计虽然只有短短的一周，但让我认识到学习好编译原理，是对程序设计和编译的一个很好的进化桥梁和奠基石。今后学习的日子还很长，希望通过这次编译原理的课程设计，不仅对编程语言的进一步复习，还是对更深层次的学习作一个简单的准备。编程的能力不是一朝一夕能锻炼出来，坚持学习，坚持编程的学习，多看，多编是最好的学习和提高方法。 通过本次编译原理课程设计，对面向对象的定义又有了更深一步的理解，对编译程序有了进一步的理解，同时也认识到自己各方面知识的薄弱点，以后在学习中也能有针对性对这方面进行深入学习。学习更好的知识重在基础，编译原理的学习为我们提供非常好的桥梁和道路。 7、参考文献 《编译原理》机械工业出版社出版 Alfred V.Aho Ravi Sethi Jeffrey D,Ullman著 李建中姜守旭等译 《程序设计语言编译原理（第三版）》国防工业出版社出版 陈火旺刘春林谭庆平赵克佳刘越著 武汉工程大学计算机科学与工程学院 《编译原理》实验报告 专业班级实验地点 学生学号指导教师 学生姓名实验时间 实验项目实验二、算术表达式递归下降分析程序设计 实验类别操作性（）验证性（）设计性（√）综合性（）其它实 验目的及要求（1）掌握自上而下语法分析的要求与特点。（2）掌握递归下降语法分析的基本原理和方法。（3）掌握相应数据结构的设计方法。 成绩评定表 类别评分标准分值得分合计 上机表现积极出勤、遵守纪律 主动完成实验设计任务 30分 实验报告及时递交、填写规范 内容完整、体现收获 70分 说明： 评阅教师： 日期： 实验内容 一、实验目的 （1）掌握自上而下语法分析的要求与特点。 （2）掌握递归下降语法分析的基本原理和方法。 （3）掌握相应数据结构的设计方法。 二、实验内容 编程实现给定算术表达式的递归下降分析器。 算术表达式文法如下：E→E+T | T T→T*F | F F→(E) | i 设计说明：首先改写文法为LL(1)文法；然后为每一个非终结符，构造相应的递归函数，函数的名字表示规则左部的非终结符；函数体按规则右部符号串的顺序编写。 三、设计分析 （1）消去该文法左递归，得到文法： E→TE1 E1→+TE1|ε T→FT1 T1→*FT1|ε F→(E)| I （2）根据LL（1）文法的判断条件，计算这个文法的每个非终结符的FIRST 集和FOLLOW集，经验证，改后的文法已经是LL（1）文法。 （3）最后构造递归下降分析程序，每个函数名是相应的非终结符，函数体则是根据右部符号串的结构编写。 a.当遇到非终结符时，如：+。 则编写语句if(当读来的输入符号== +) 读下一个输入符号 b.当遇到非终结符时，例如：T。则编写语句调用T()。 c.当遇到非终结符→ε规则时，例如：T→ε。 则编写语句 if(当前读来的输入字符不属于FOLLOW(T)) error() d.当某个非终结符的规则有很多个候选式时。 按LL(1)文法的条件能唯一的选择一个候选式进行推导。 （4）递归下降分析法是确定的自上而下分析法，基本思想是，对文法中的每个非终结符编写一个函数，每个函数的功能是识别由该非终结符所表示的语法成分。因此需要分别构造E,E1,T,T1,F函数来执行自己的识别功能，根据文法的内容顺序决定函数的识别功能。Scaner函数用于字符串的推进，input函数用于字符串的输入。 课程设计任务书 学生姓名：赵旭林专业班级：计算机0801班 指导教师：陈天煌工作单位：计算机科学与技术学院 题目: WHILE循环语句的翻译程序设计（递归下降法、输出三地址表示）初始条件： 理论：学完编译课程，掌握一种计算机高级语言的使用。 实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） （1）写出符合给定的语法分析方法的文法及属性文法。 （2）完成题目要求的中间代码三地址表示的描述。 （3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。 （4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。 （5）设计报告格式按附件要求书写。课程设计报告书正文的内容应包括： 1 系统描述（问题域描述）； 2 文法及属性文法的描述； 3 语法分析方法描述及语法分析表设计； 4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计； 5 编译系统的概要设计； 6 详细的算法描述（流程图或伪代码）； 7 软件的测试方法和测试结果； 8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）； 9 参考文献（按公开发表的规范书写）。 时间安排： 设计安排一周：周1、周2：完成系统分析及设计。 周3、周4：完成程序调试及测试。 周5：撰写课程设计报告。 设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。 设计报告书收取时间：设计周的次周星期一上午10点。 指导教师签名： 2010年 11月 13日 系主任（或责任教师）签名： 2010年 11月 13日 学号107 成绩 编译原理上机报告 名称：编写递归下降语法分析器 学院：信息与控制工程学院 专业：计算机科学与技术 班级：计算机1401班 姓名：叶达成 2016年10月31日 一、上机目的 通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、基本原理和上机步骤 递归下降分析程序实现思想简单易懂。程序结构和语法产生式有直接的对应关系。因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。 每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。 自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，当选择某非终结符的产生时，可根据输入串的当前符号以及各产生式右部首符号而进行，效率高，且不易出错。 无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。 无左递归：既没有直接左递归，也没有间接左递归。 无回溯：对于任一非终结符号U的产生式右部x1|x2|…|x n，其对应的字的首终结符号两两不相交。 如果一个文法不含回路（形如P?+ P的推导），也不含以ε为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以ε为右部的产生式）。 三、上机结果 测试数据： (1)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (2)输出结果：i+i*i#为合法符号串 (3)输入一符号串如i+i*#,要求输出为“非法的符号串”。 程序清单： #include 编 译 原 理 实 验 报 告 姓名：关海超 学号：200807010209 专业：计算机科学与技术 班级：08—02班 递归下降分析法的实现 实验要求 递归下降分析法是确定的自上而下分析法，这种分析法要求文法是LL(1)文法。它的基本思想是，对文法中的每个非终结符编写一个函数（或子程序），每个函数（或子程序）的功能是识别由该非终结符所表示的语法成分。由于描述语言的文法通常是递归定义的，因此相应的这组函数（或子程序）必然一相互递归的方式进行调用，所以将此种分析方法称为递归下降分析法。 本实验要求构造下述文法的递归下降分析程序： 文法G[S]: S —> a | ^ | (T) T —> T,S | S 实验内容 首先，消去该文法左递归，得到文法G’[S]: S —> a | ^ | (T) T —> ST’ T’—> ,ST’ | 空串 然后，根据LL(1)文法的判断条件，对非终结符S和T’的不同产生式的SSELECT集进行考察，经验证改进后的文法已经是LL(1)文法。 最后构造递归下降分析程序。每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构编写。 （1）当遇到终结符a时，则编写语句 if (当前读来的输入符号== a) 读下一个输入符号 （2）当遇到非终结符A时，则编写语句调用A（）。 （3）当遇到A —> 空串规则时，则编写语句 if (当前读来的输入字符不属于FOLLOW(A) ) error() （4）当某个非终结符的规则有很多个候选式是，按LL(1)文法的条件能唯一地选择一个候选式进行推导。 实验结果 实验总结 这次实验内容比较简单。由于有固定的模式来构造程序，因此即使对于其他LL(1)文法也很容易构造其相应的递归下降分析程序。 这次实验我学习了如何将递归下降分析思想具体转化为程序来实现，同时也加深了产生式的Follow集在递归下降分析法中的应用，练习了通过SELECT集判断文法是否为LL(1)文法。 附录（源代码） #include 编译方法实验报告实验名称：简单的语法分析程序设计 实验要求 1.功能：对简单的赋值语句进行语法分析 随机输入赋值语句，输出所输入的赋值语句与相应的四元式 2.采用递归下降分析程序完成（自上而下的分析） 3.确定各个子程序的功能并画出流程图 4.文法如下： 5.编码、调试通过 采用标准输入输出方式。输入输出的样例如下： 【样例输入】 x:=a+b*c/d-(e+f) 【样例输出】(说明，语句和四元式之间用5个空格隔开) T1:=b*c (*,b,c,T1) T2:=T1/d (/,T1,d,T2) T3:=a+T2 (+,a,T2,T3) T4:=e+f (+,e,f,T4) T5:=T3-T4 (-,T3,T4,T5) x:=T5 (:=,T5,-,x) 【样例说明】程序除能够正确输出四元式外，当输入的表达式错误时，还应能检测出语法错误，给出相应错误提示。 6.设计3-5个赋值语句测试实例，检验程序能否输出正确的四元式；当输入错误 的句子时，检验程序能够给出语法错误的相应提示信息。 7.报告内容包括： 递归程序的调用过程，各子程序的流程图和总控流程图，详细设计，3-5个测试用例的程序运行截图及相关说明，有详细注释的程序代码清单等。 目录 1.语法分析递归下降分析算法............................... 错误!未定义书签。 背景知识............................................. 错误!未定义书签。 消除左递归........................................... 错误!未定义书签。 2.详细设计及流程图....................................... 错误!未定义书签。 函数void V( ) .|z ................................. 错误!未定义书签。 函数void A( ) 错误!未指定书签。错误!未指定书签。错误!未指定书签。错误!未指定书签。错误!未指定书签。试用例及截图........................ 错误!未定义书签。 测试用例1及截图..................................... 错误!未定义书签。 测试用例2及截图..................................... 错误!未定义书签。 测试用例3及截图..................................... 错误!未定义书签。 代码清单................................................. 错误!未定义书签。 魏陈强 204168 实验3 递归下降法的语法分析器 一、实验目的 学习用递归下降法构造语法分析器的原理，掌握递归下降法的编程方法。 二、实验内容 用递归下降法编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。 这里只要求实现部分产生式，文法的开始符号为program。（完整的源语言的文法定义见教材附录，p394） program→ block block→{stmts } stmts→stmt stmts | 。 stmt→id=expr; | if(bool)stmt | if( bool)stmt else stmt | while(bool)stmt | do stmt while(bool ) ; | break ; | block bool →expr < expr | expr <= expr | expr > expr | expr >= expr & | expr expr→ expr + term | expr - term | term term→ term * factor | term / factor | factor factor→ ( e xpr ) | id| num 三、实验要求 １．个人完成，提交实验报告。 ( ２．实验报告中给出采用测试源代码片断，及其对应的最左推导过程（形式可以自行考虑）。 测试程序片断： { i = 2; while (i <=100) { sum = sum + i; i = i + 2; } } 对应的推导过程为： # program block {stmts } {stmt stmts} {id=expr;stmts } {id=num;stmts } {id=num;stmt stmts } {id=num;while(bool)stmt stmts } {id=num;while(e xpr<= expr)stmt stmts } {id=num;while(id<= expr)stmt stmts } {id=num;while(id<= num)stmt stmts } {id=num;while(id<= num)block stmts } ， {id=num;while(id<= num){stmts }stmts } ．．．．．．． 编译原理课程设计报告 2011 年 12 月 2 日 设计题目 递归下降分析程序的实现 学 号 专业班级 计算机科学与技术 学生姓名 指导教师 一、实验目的: （1）掌握自上而下语法分析的要求与特点。 (2）掌握递归下降语法分析的基本原理和方法。 （3)掌握相应数据结构的设计方法。 二、实验内容: 递归下降分析程序的实现 设计内容及要求： 对文法 G： E→E+T｜Ｔ构造出G的递归下降分析程序。程序显示输出T→T*F|Ｆ匹配过程（即自上而下生成语法分析树的步骤， F→（E）|i 输出各匹配产生式序号即可）。 三、设计思路： (１)语法分析: 语法分析是编译程序的核心部分，任务是分析一个文法的句子结构。递归下降分析程序的实现的功能:按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子（合式程序）。 （2)自上而下分析: 从文法的开始符号出发,向下推导,推出句子。可分为带“回溯”的和不带回溯的递归子程序(递归下降)分析方法。 它的主旨是对任何输入串，试图用一切可能的办法,从文法开始符号(根结点）出发，自上而下地为输入串建立一棵语法树。或者说,为输入串寻找一个最左推导。也即从文法的开始符号出发，反复使用各种产生式，寻找"匹配＂的推导。 (3)递归下降分析法： 对每一语法变量(非终结符)构造一个相应的子程序,每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。 (４）分析过程中遇到的问题: a. 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时,不得不“回溯”。 b．文法左递归问题。含有左递归的文法将使自上而下的分析陷入无限循环。 (5)构造不带回溯的自上而下分析算法： ａ.要消除文法的左递归性：一个文法可以消除左递归的条件是①不含以 为右部的产生式②不含回路。 实验三递归下降分析法 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 程序比较复杂，需要利用到程序设计语言的知识和大量编程技巧，递归下降分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调 用的方法。 二、实验要求 1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。 3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 三、实验内容 程序输入/输出示例： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （1）E-TG （2）G-+TG|—TG （3）G-ε （4）T-FS （5）S-*FS|/FS （6）S-ε （7）F-(E) （8）F-i 输出的格式如下： (1)递归下降分析程序，编制人：姓名，学号，班级 (2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (3)输出结果：i+i*i#为合法符号串 备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。 引用也要改变）。 注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符I，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 3.对学有余力的同学，可以详细的输出推导的过程，即详细列出每一步使用的产生式。 四、实验学时 4学时 五、实验步骤 （一）准备： 1.阅读课本有关章节， 2.考虑好设计方案； 3.设计出模块结构、测试数据，初步编制好程序。 （二）上课上机： 将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。 （三）程序思路（仅供参考）： 0.定义部分：定义常量、变量、数据结构。 1.初始化：从文件将输入符号串输入到字符缓冲区中。 2.利用递归下降分析法分析，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。 六、实验预习提示 1、递归下降分析法的功能 词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 2、递归下降分析法的前提 改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法， 3、递归下降分析法实验设计思想及算法 为G的每个非终结符号U构造一个递归过程,不妨命名为U。 U的产生式的右边指出这个过程的代码结构： (1)若是终结符号，则和向前看符号对照， 若匹配则向前进一个符号；否则出错。 (2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现。 具体为： （1）对于每个非终结符号U-u1|u2|…|un处理的方法如下： U( ) { ch=当前符号; if(ch可能是u1字的开头) 处理u1的程序部分; else if(ch可能是u2字的开头)处理u2的程序部分; … else error() } （2）对于每个右部u1-x1x2…xn的处理架构如下： 处理x1的程序； 处理x2的程序； … 处理xn的程序； （3）如果右部为空，则不处理。 《编译原理》课程设计题目 设计题一：正规式r与正规文法G相互转换的程序设计 任意给定一个正规式，求出其对应的正规文法；任意给定一个正规文法，求出其对应的正规式。（参考教材P53～55） 设计题二：布尔表达式的递归下降翻译器 针对布尔表达式的文法： 〈布尔表达式〉∷＝〈布尔项〉{〈与运算符〉〈布尔项〉} 〈与运算符〉∷＝and 〈布尔项〉∷＝〈布尔因子〉{〈或运算符〉〈布尔因子〉} 〈或运算符〉∷＝or 〈布尔因子〉∷＝〈非运算符〉〈布尔因子〉｜〈布尔量〉 〈非运算符〉∷＝not 〈布尔量〉∷＝（〈布尔表达式〉）｜〈标识符〉〈关系运算符〉〈标识符〉｜ true｜false 〈关系运算符〉∷＝＞｜＜｜≥｜≤｜＝｜≠ 〈标识符〉∷＝〈字母〉{〈字母〉｜〈数字〉} 利用递归下降分析法编制、调试其语法及语义分析程序，生成的中间代码为逆波兰式。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（参考教材P92～93） 设计题三：正规式r与有穷自动机FA相互转换的程序设计 任意给定一个正规式，求出其对应的有穷自动机；任意给定一个有穷自动机，求出其对应的正规式。（参考教材P61～64） 设计题四：赋值语句的LR翻译程序 对教材P180中的赋值语句文法，给出该文法的属性文法，同时实现赋值语句的翻译，生成的中间代码为逆波兰式。（参考教材P179～181） 设计题五：正规文法G与有穷自动机FA相互转换的程序设计 任意给定一个正规文法，求出其对应的有穷自动机；任意给定一个有穷自 动机，求出其对应的正规文法。（参考教材P65～66） 设计题六：条件语句的LR翻译程序 对教材P187中的条件语句文法，给出该文法的属性文法，同时实现条件语句的翻译，生成的中间代码为四元式。（参考教材P186～189） 设计题七：NFA确定化为DFA及化简的程序设计 任意给定一个NFA，将其确定化为DFA，然后化简为最小的DFA。（参考教材P57～61） 设计题八：布尔表达式的LR翻译器 针对布尔表达式的文法： B →B and T | T T→T or F | F F→not F|true｜false |（B）| i rop i 利用LR分析法编制、调试其语法及语义分析程序，生成的中间代码为四元式。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（参考教材P181～182） 设计题九：生成预测分析表的算法实现 任意给定一个LL(1)文法，生成相应的LL(1)分析表。（参考教材P75第5章） 设计题十：while循环语句的LR翻译程序 对教材P187中的循环语句文法，给出该文法的属性文法，同时实现循环语句的翻译，生成的中间代码为四元式。（参考教材P186～189） 设计题十一：利用LEX自动生成词法分析程序 输入描述某种语言词法规则的正规式，利用LEX自动生成词法分析程序。（参考教材P66～68） 设计题十二：生成LR分析表的算法实现 任意给定一个LR文法，生成相应的LR分析表。（参考教材P123第7章） 设计题十三：布尔表达式翻译为逆波兰式的算法实现 针对布尔表达式的二义性文法： B → B and B | B or B | not B | ( B ) | true｜false| i rop i 将文法拓广为G’[B’]： (0) B’ → B 魏陈强 23020092204168 实验3 递归下降法的语法分析器 一、实验目的 学习用递归下降法构造语法分析器的原理，掌握递归下降法的编程方法。 二、实验内容 用递归下降法编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。 这里只要求实现部分产生式，文法的开始符号为program。（完整的源语言的文法定义见教材附录 A.1，p394） program→ block block→{stmts } stmts→stmt stmts | stmt→id=expr; | if(bool)stmt | if( bool)stmt else stmt | while(bool)stmt | do stmt while(bool ) ; | break ; | block bool →expr < expr | expr <= expr | expr > expr | expr >= expr | expr expr→ expr + term | expr - term | term term→ term * factor | term / factor | factor factor→ ( e xpr ) | id| num 三、实验要求 １．个人完成，提交实验报告。 ２．实验报告中给出采用测试源代码片断，及其对应的最左推导过程（形式可以自行考虑）。 测试程序片断： { i = 2; while (i <=100) { sum = sum + i; i = i + 2; } } 对应的推导过程为： program?block ?{stmts } ?{stmt stmts} ?{id=expr;stmts } ?{id=num;stmts } ?{id=num;stmt stmts } ?{id=num;while(bool)stmt stmts } ?{id=num;while(e xpr<= expr)stmt stmts } ?{id=num;while(id<= expr)stmt stmts } ?{id=num;while(id<= num)stmt stmts } ?{id=num;while(id<= num)block stmts } ?{id=num;while(id<= num){stmts }stmts } ?．．．．．．． 四、实验思路 之前编写的词法分析器，能够将语句中的每一个词素都识别出来，因此，在此基础上，定义一个二维字符串数组finaltable[100][20]，用于存放由词法分析器提取出来的每个词素，比如，i=2，则finaltable[0]=”id”， 《编译原理》课程实验报告 实验名称：递归下降分析法 一．实验目的 1.理解递归下降语法分析方法的主要原理 2.理解递归下降分析法对文法的要求 3．熟练掌握Predict集合的求法 4.熟练掌握文法变换算法（消除左递归和消除公共前缀） 二．实验内容 #include } void T() { S(); U(); } void U() { if (sym == ',') { Scanner(); S(); U(); } else if(sym != ')') Error(); } void Scanner() { sym = token[p++]; } void Error() { //exit(0); } int main() { printf("输入: "); gets(token); p = 0; Scanner(); S(); if (sym == '$') printf("Success!"); else printf("Fail!"); return 0; } 三．实验步骤 调试程序的结果： 计算机硬件实验室实验报告 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、实验要求： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （1）E->TG （2）G->+TG|—TG （3）G->ε （4）T->FS （5）S->*FS|/FS （6）S->ε （7）F->(E) （8）F->i 输出的格式如下： (1)递归下降分析程序，编制人：姓名，学号，班级 (2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (3)输出结果：i+i*i#为合法符号串 备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。 注意： 1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 三、实验过程： 程序设计： 1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。 程序编写： 1.定义部分：定义常量、变量、数据结构。 2.初始化：从文件将输入符号串输入到字符缓冲区中。 3.利用递归下降分析法，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。 四、实验结果 （1）程序流程图 （2）运行结果 示例程序： #include <> #include<> #include<> #include<> char a[50] ,b[50],d[500],e[10]; char ch; int n1,i1=0,flag=1,n=5; int E(); int E1(); int T(); int G(); 实验二递归下降分析器设计与实现 1、实验目的： （1）掌握自上而下语法分析的要求与特点。 （2）掌握递归下降语法分析的基本原理和方法。 （3）掌握相应数据结构的设计方法。 2、实验内容： 编程实现给定算术表达式的递归下降分析器。 算术表达式文法如下： E-->E+T|T T-->T*F|F F-->(E)|i 3、设计说明： 首先改写文法为LL(1)文法；然后为每一个非终结符，构造相应的递归过程，过程的名字表示规则左部的非终结符；过程体按规则右部符号串的顺序编写。4、设计分析 这个题目属于比较典型的递归下降语法分析。需要先将原算术表达式方法改写为LL(1)文法为： E-->TE' E'-->+TE'|ε T-->FT' T'-->*FT'|ε F-->(E)|i 然后再为每个非终结符设计一个对应的函数，通过各函数之间的递归调用从而实现递归下降语法分析的功能。具体方法为： （1）当遇到终结符a时，则编写语句 If(当前读到的输入符号==a)读入下一个输入符号 （2）当遇到非终结符A时，则编写语句调用A()。 （3）当遇到A-->ε规则时，则编写语句 If(当前读到的输入符号不属于Follow(A))error() （4）当某个非终结符的规则有多个候选式时，按LL(1)文法的条件能唯一地选择一个候选式进行推导. 5、程序代码 #include char s[100]; int i, SIGN; int main() { printf("请输入一个语句，以#号结束语句（直接输入#号推出）\n"); while( 1 ) { SIGN = 0; i=0; scanf("%s",&s); if( s[0] == '#') return 0; E(); if(s[i]=='#') printf("正确语句！\n"); printf("请输入一个语句，以#号结束语句\n"); } return 1; } void E() { if(SIGN==0) { T(); E1(); } } void E1() { if(SIGN==0) { 集美大学计算机工程学院实验报告 课程名称：编译原理 指导教师：付永钢 实验成绩： 实验编号： 实验二 实验名称：递归下降分析程序构造 班级：计算12 姓名： 学号： 上机实践日期：2014.11 上机实践时间： 4学时 一、实验目的 通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标： (1) 掌握从源程序文件中读取有效字符的方法和产生源程序内部表示文件的方法； (2)掌握语法分析的实现方法； (3)上机调试编出的语法分析程序。 二、实验环境 Windows7 x64、VC6.0 三、实验原理 递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终结符按其产生式结构构造相应语法分析子程序，其中终结符产生匹配命令，而非终结符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。 自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，可根据输入串的当前符号以及各产生式右部首符，选择某非终结符的产生式，效率高，且不易出错。 无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。即：假设A 的全部产生式为A →α1|α2|……|αn ，则必须满足如下条件才能保证可以唯一的选择合适的产生式 First(A →αi )∩First (A →αj )=Φ,当i≠j. 无左递归：既没有直接左递归，也没有间接左递归。 无回溯：对于人以非中介符号U 的产生式右部n x x x |...||21，其对应的字的首终结符号两两不相交。 如果一个文法不含回路（形如P P +?的推导），也不含以ε为右部的产生式，那么可以通过执行消除左递归的算法消除文法的一切左递归。 四、实验内容 完成以下描述算术表达式的LL(1)文法的递归下降分析程序构造 G[E]: E →TE ′ E ′→+TE ′|ε T →FT ′ 编译原理课程设计课程设计题目：LL(1)递归下降分析器 姓名： 院（系）： 专业班级： 学号： 指导教师： 设计日期： 目录 1、需求分析 (1) 2、概要设计 (2) 3、详细设计 (3) 4、测试分析 (8) 5、用户手册 (9) 6、课程总结 (9) 7、参考文献 (10) 题目：LL （1）递归下降分析器 1、需求分析 语法分析是编译过程的核心部分。语法分析器的任务是识别和处理比单词更大的语法单位。如：程序设计语言中的表达式，各种说明和语句乃至全部源程序，指出其中的语法错误；必要时，可生成内部形式，便于下一阶段处理。 我们知道，语言的语法结构是用上下文无关文法描述的。按照语法分析树的建立方法，我们可以粗略地把语法分析办法分成两类，一类是自上而下分析，另一类是自下而上分析法。而自上而下这种方法是带“回溯”的，且存在许多困难和缺点。 首先，是文法的左递归性问题。一个文法是含有左递归的，如果存在非终结符P 且αP P + ?，含有左递归的文法使上述的自上而下的分析过程陷入无限循环。即，当试图用P 去匹配输入串时，我们会发现，在没有识别任何输入符号的情况下，有得重新要求P 去进行新的匹配。因此，使用自上而下分析法必须消除文法的左递归性。 其次，由于回溯，就碰到一大堆麻烦问题。如果我们走了一大段错路，最后必须回头，那么，就应把已经做的一大堆语义工作（指中间代码产生工作和各种表格的簿记工作）推倒重来。这些事情既麻烦又费时间，所以，最好应设法消除回溯。 第三，在自上而下分析过程中，当一个非终结符用某一候选匹配成功时，这种成功可能仅是暂时的。 第四，当最终报告分析不成功时，我们难于知道输入串中出错的确切位置。 最后，由于带回溯的自上而下分析实际上采用了一种穷尽一切可能的试探法，因此，效率很低，代价极高。严重的低效使得这种分析法只有理论意义，而在实践上价值不大。 由于上述原因，我们需要把原算术表达式改写为LL(1)文法，LL(1)文法的文法条件如下： 文法不含左递归。 对于文法中每一个非终结符A 的各个产生式的候选首集符两两不相交。即，若n A ααα|||21 →，则()()φαα=?j i FIRST FIRST ()j i ≠ 对文法中的每个非终结符A ，若它存在某个候选首符集包含ε，则()()φ=?A F O L L O W A F I R S T LL(1)中的第一个L 表示从左到右扫描输入串，第二个L 表示最左推导，1表示分析时每 编译原理课程实验报告 班级学号：姓名： 实验名称：递归下降分析法 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、实验要求： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （1）E->TG （2）G->+TG|—TG （3）G->ε （4）T->FS （5）S->*FS|/FS （6）S->ε （7）F->(E) （8）F->i 输出的格式如下： (1)递归下降分析程序，编制人：姓名，学号，班级 (2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (3)输出结果：i+i*i#为合法符号串 备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。 注意： 1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 三、实验过程： 程序设计： 1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。 程序编写： 1.定义部分：定义常量、变量、数据结构。 2.初始化：从文件将输入符号串输入到字符缓冲区中。 3.利用递归下降分析法，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。 四、实验结果 （1）程序流程图 主函数main( )流程图 E( )过程流程图 T( )过程流程图 G( )过程流程图 F( )过程流程图 《编译原理》实验报告 实验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 实验前准备 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，而对于合法的表达式，递归程序最后分析的字符就是换行符，不合法的表达式在未分析到换行符就会停止分析，所以根据最后分析的字符是否为换行符进一步确定是否为合法的表达式。 编译方法实验报告 令狐采学 实验名称：简单的语法分析程序设计 实验要求 1.功能：对简单的赋值语句进行语法分析 随机输入赋值语句，输出所输入的赋值语句与相应的四元式 2.采用递归下降分析程序完成（自上而下的分析） 3.确定各个子程序的功能并画出流程图 4.文法如下： 5.编码、调试通过 采用标准输入输出方式。输入输出的样例如下： 【样例输入】 x:=a+b*c/d(e+f) 【样例输出】(说明，语句和四元式之间用5个空格隔开) T1:=b*c (*,b,c,T1) T2:=T1/d (/,T1,d,T2) T3:=a+T2 (+,a,T2,T3) T4:=e+f (+,e,f,T4) T5:=T3T4 (,T3,T4,T5) x:=T5 (:=,T5,,x) 【样例说明】程序除能够正确输出四元式外，当输入的表达式错误时，还应能检测出语法错误，给出相应错误提示。 6.设计35个赋值语句测试实例，检验程序能否输出正确的四 元式；当输入错误的句子时，检验程序能够给出语法错误的相应提示信息。 7.报告内容包括： 递归程序的调用过程，各子程序的流程图和总控流程图，详细设计，35个测试用例的程序运行截图及相关说明，有详细注释的程序代码清单等。 目录 1.语法分析递归下降分析算法5 1.1背景知识5 1.2消除左递归6 2.详细设计及流程图6 2.1 函数void V( ) // V > a|b|c|d|e...|z6 2.2 函数void A( ) // A > V:=E7 2.3 函数void E() //E > TE'7 2.4函数void T( ) // T > FT'8 2.5函数void E1( ) //E'> +TE'|TE'|null8 2.6函数void T1() // T'> *FT'|/FT'|null9 3.测试用例及截图9 3.1测试用例1及截图9 3.2测试用例2及截图10 3.3测试用例3及截图11 代码清单11 《编译原理》课程实验报告 欧阳光明（2021.03.07） 实验名称：递归下降分析法 姓名：彭国保 学号：540907010130 院系：计算机与通信工程学院 专业：计算机科学与技术 班级：09-1班 教师：韩丽 2012 年4月22日 一．实验目的 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。程序开始变得复杂起来，需要利用到程序设计语言的知识和大量编程技巧，递归下降分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调用的方法。 二．实验内容 递归下降分析法是确定的自上而下分析法，它要求文法是LL(1)文法。它的基本思想是：对文法中的每个非终结符编写一个函数或 子程序，每个函数或子程序的功能是识别由该非终结符所表示的语法成分。 2.1程序算法描述 2.1.1递归下降分析法的功能 词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 2.1.2递归下降分析法的前提 改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法， 2.1.3递归下降分析法实验设计思想及算法 为G的每个非终结符号U构造一个递归过程。U的产生式的右边指出这个过程的代码结构： (1)若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。 (2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现。 最后编写程序以实现上述功能。 三．实验步骤 根据上述算法描述，编写程序以实现相应的功能，该程序由C 语言编写，然后在VC运行环境下进行调试，并不断完善，直到能正确的实现递归下降分析功能，判断输入的字符串是否是一个文法的句子。 源程序代码如下：编译原理实验报告算术表达式递归下降分析程序设计
WHILE循环语句的翻译程序设计(递归下降法、输出三地址表示)
编译原理-编写递归下降语法分析器
编译原理-递归下降分析法的实现-内附源码
递归下降语法分析程序设计
实验三-递归下降法的语法分析器
编译原理-递归下降子程序-课程设计报告
实验三 递归下降分析程序实现
《编译原理》课程设计题目-2014
实验三_递归下降法的语法分析器
递归下降分析法
编译原理-实验报告2-递归下降分析法
递归下降分析器设计与实现
编译原理-实验二-递归下降分析程序构造
编译原理课程设计---LL(1)递归下降分析器
递归下降分析法
编译原理实验-递归下降分析资料报告器地设计(含源代码和运行结果)
递归下降语法分析程序设计
编译原理——递归下降语法分析之欧阳光明创编
相关主题
文本预览