下载文档原格式
编译原理实验报告—递归下降分析法程序实验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可以产生字符-。
递归下降分析器设计一、实验/实习过程内容：利用JavaCC生成一个MiniC的语法分析器；要求：1. 用流的形式读入要分析的C语言程序，或者通过命令行输入源程序。
2. 具有错误检查的能力，如果有能力可以输出错误所在的行号，并简单提示3. 如果输入的源程序符合MiniC的语法规范，输出该程序的层次结构的语法树具体实施步骤如下：1.把MiniC转换为文法如下<程序〉→ main()〈语句块〉〈语句块〉→{〈语句串〉}〈语句串〉→〈语句〉〈语句串〉|〈语句〉〈语句〉→〈赋值语句〉|〈条件语句〉|〈循环语句〉〈赋值语句〉→ ID =〈表达式〉；〈条件语句〉→ if〈条件〉〈语句块〉〈循环语句〉→ while〈条件〉〈语句块〉〈条件〉→（〈表达式〉〈关系符〉〈表达式〉）〈表达式〉→〈表达式〉〈运算符〉〈表达式〉|（〈表达式〉）|ID|NUM〈运算符〉→+|-|*|/〈关系符〉→＜|＜＝|＞|＞＝|＝＝|!=2.消除语句中的回溯与左递归3．在eclipse环境下完成JavaCC的插件安装后，写一个JavaCC文法规范文件(扩展名为jj)4.完成的功能包括词法分析，语法分析二、代码：options {JDK_VERSION = "1.5";}PARSER_BEGIN(eg1)public class eg1 {public static void main(String args[]) throws ParseException { eg1 parser = new eg1(System.in);parser.start();}}PARSER_END(eg1)SKIP :{" "| "\r"| "\t"| "\n"}TOKEN : /* OPERATORS */{< PLUS: "+" >| < MINUS: "-" >| < MULTIPLY: "*" >| < DIVIDE: "/" >}TOKEN :{<BIGGER:">"> |<SMALLER:"<"> |<NOTVOLUTION:"!="> |<SMALLEREQDD:"<="> |<BIGGEREE:">=" > |<DOUBLE:"==">TOKEN: //关键字{<MAIN:"main"> |<VOID:"void"> |<IF:"if"> |<INT:"int"> | <WHILE:"while"> |<CHAR:"char"> | <VOLUTION:"="> }TOKEN : //定义整型数{< INTEGER: ["0" - "9"]( <DIGIT> )+ >| < #DIGIT: ["0" - "9"] >}TOKEN : //数字{<NUMBER:(<DIGIT>)+ | (<DIGIT>)+"."| (<DIGIT>)+"."(<DIGIT>)+| "."(<DIGIT>)+>}TOKEN : //标记{<COMMA:","> | <SEMICOLON:";"> | <COLON:":"> | <LEFTPARENTHESES:"("> |<RIGHTPARENTHESES:")"> | <LEFTBRACE:"{"> | <RIGHTBRACE:"}"> }TOKEN : //标识符{<IDENTIFIER:<LETTER> |<LETTER>(<LETTER> | <DIGIT> )* >|<#LETTER:["a"-"z", "A"-"Z"]>}void start():{}{<MAIN> <LEFTPARENTHESES> <RIGHTPARENTHESES> block() }void block():{}{<LEFTBRACE> string() <RIGHTBRACE>}void string():{}{yuju() (string())?}void yuju():{}{fuzhiyuju() | tiaojianyuju() | xunhuanyuju()}void fuzhiyuju():{}{<IDENTIFIER> <VOLUTION> biaodashi() <SEMICOLON>}void tiaojianyuju():{}{<IF> tiaojian() block()}void xunhuanyuju():{}<WHILE> tiaojian() block()}void tiaojian():{}{<LEFTPARENTHESES> biaodashi() guanxifu() biaodashi()<RIGHTPARENTHESES>}void biaodashi():{}{( <LEFTPARENTHESES> biaodashi() <RIGHTPARENTHESES> biaodashi2()) |(<IDENTIFIER> biaodashi2() ) | ( <NUMBER> biaodashi2() )}void biaodashi2():{}{(yunsuanfu() biaodashi() biaodashi2() )?}void yunsuanfu():{}{< PLUS > | < MINUS > |< MULTIPLY> | < DIVIDE >}void guanxifu() :{}{<BIGGER> | <SMALLER> | <NOTVOLUTION><SMALLEREQDD> | <BIGGEREE> | <DOUBLE>}三、实验/实习总结本次实习，我使用javacc完成了包括词法分析，语法分析(输出语法树),能够读文件的功能，总的来说比较满意，通过本次实习掌握了javacc基本的使用。
编译原理递归下降分析法C语言编译原理是计算机科学中的一个重要领域，主要研究如何将高级语言程序转化为机器可执行的目标代码。
在编译原理中，递归下降分析法是一种常用的语法分析方法，它通过递归地从上至下对程序进行分析，最终确定程序的语法结构。
递归下降分析法是一种自顶向下的语法分析方法，基于产生式和预测分析表来实现对程序的语法分析。
该方法的基本思想是，每个非终结符对应一个处理过程，通过递归调用这些处理过程来分析整个程序。
在C语言的递归下降分析法中，需要定义对应C语言语法结构的处理过程，这些处理过程通常对应于C语言中的各种语句、表达式、声明等。
递归下降分析法的实现主要包括两个步骤：构造预测分析表和编写递归下降分析程序。
预测分析表是一个二维表格，行对应于非终结符，列对应于终结符，表格中的每个元素记录了该产生式的编号。
通过预测分析表，可以预测下一个分析符号，并选择相应的产生式进行语法分析。
编写递归下降分析程序时，首先需要确定递归下降分析程序的数据结构和接口。
一般来说，分析程序的数据结构包括符号栈、语法树等，接口包括初始化、语法分析、错误处理等。
接下来，根据语法规则编写对应的递归下降分析函数，每个函数对应一个非终结符的处理过程。
在实际编写过程中，通常使用递归调用来实现对程序的逐步分析，直到达到终结符。
递归下降分析法在C语言编译器中的应用非常广泛。
通过该方法，可以对C语言程序进行语法分析，检测代码中的语法错误，并生成相应的语法树。
在生成语法树之后，可以继续进行语义分析、中间代码生成、代码优化等编译过程。
总的来说，递归下降分析法是一种重要的语法分析方法，可以用于对C语言程序进行语法分析。
它通过自顶向下的递归调用，从上至下地解析语法规则，最终确定程序的语法结构。
递归下降分析法在实际编译器设计中有广泛应用，是理解和学习编译原理的重要内容。
学号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*#,要求输出为“非法的符号串”。
编译原理之递归下降语法分析程序（实验）⼀、实验⽬的利⽤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）⽂法。
编译原理---递归下降分析法所谓递归下降法 (recursive descent method)，是指对⽂法的每⼀⾮终结符号，都根据相应产⽣式各候选式的结构，为其编写⼀个⼦程序 (或函数)，⽤来识别该⾮终结符号所表⽰的语法范畴。
例如，对于产⽣式E′→+TE′，可写出相应的⼦程序如下：exprprime( ){if (match (PLUS)){advance( );term( );exprprime( );}}其中：函数match()的功能是，以其实参与当前正扫视的符号 (单词)进⾏匹配，若成功则回送true，否则回送false；函数advance()是⼀个读单词⼦程序，其功能是从输⼊单词串中读取下⼀个单词，并将它赋给变量Lookahead;term则是与⾮终结符号T相对应的⼦程序。
诸如上述这类⼦程序的全体，便组成了所需的⾃顶向下的语法分析程序。
应当指出，由于⼀个语⾔的各个语法范畴 (⾮终结符号)常常是按某种递归⽅式来定义的，此种特点也就决定了这组⼦程序必然以相互递归的⽅式进⾏调⽤，因此，在实现递归下降分析法时，应使⽤⽀持递归调⽤的语⾔来编写程序。
所以，通常也将上述⽅法称为递归⼦程序法。
例4 2对于如下的⽂法G［statements］:statements→expression; statements |εexpression→term expression′expression′→+term expression′ |εterm→factor term′term′→*factor term′ |εfactor→numorid | (expression)通过对其中各⾮终结符号求出相应的FIRST集和FOLLOW集 (计算FIRST集和FOLLOW集的⽅法后⾯再做介绍)，可以验证，此⽂法为⼀LL(1)⽂法，故可写出递归下降语法分析程序如程序41所⽰(其中，在⽂件lex.h⾥，将分号、加号、乘号、左括号、右括号、输⼊结束符及运算对象分别命名为SEMI，PLUS，TIMES，LP，RP，EOI及NUMORID，并指定了它们的内部码；此外，还对外部变量yytext，yyleng及yylineno进⾏了说明)。
编译原理实验报告实验名称：编写递归下降语法分析程序实验类型：验证型实验指导教师：专业班级：姓名：学号：电子邮件：实验地点：实验成绩：日期：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");}}六、实验者自评这个实验比第一个有难度，是在第一个完成的基础上进行的。
实验二：算术表达式递归下降分析程序设计LD1、实验目的：（1）掌握自上而下语法分析的要求与特点。
（2）掌握递归下降语法分析的基本原理和方法。
（3）掌握相应数据结构的设计方法。
2、实验内容：编程实现给定算术表达式的递归下降分析器。
算术表达式文法如下：E→E+T | TT→T*F | FF→(E) | i3、设计分析题目所给的文法不为LL(1)文法，应改写成如下文法：E →TE2E2→+TE2 |∑T →FT2T2→*FT2 | ∑F →(E) | i采用递归下降分析法时，需要求出E2和T2 的FOLLOW集：FOLLOW(E2)={），#}FOLLOW(T2)={+,),#}递归下降分析法是确定的自上而下分析法，基本思想是，对文法中的每个非终结符编写一个函数，每个函数的功能是识别由该非终结符所表示的语法成分。
因此需要分别构造E,E2,T,T2,F函数来执行自己的识别功能，根据文法的内容顺序决定函数的识别功能。
advance函数用于字符串的推进，input函数用于字符串的输入。
4、程序代码#include <iostream>using namespace std;char a[80]; // 字符串的存入char sym; // 单个的判断字符int i=0; // 字符串下标void E(); // 功能识别函数void E2(); // 功能识别函数void T(); // 功能识别函数void T2(); // 功能识别函数void F(); // 功能识别函数void input(); // 输入函数void advance(); // 字符串小标进一函数void main(){while(1){input();advance();E(); // 从首个推导式E开始if (sym=='#')cout<<"success"<<endl;elsecout<<"fail"<<endl;i=0; // 重新输入时，下标置0 }}void E(){T();E2();}void E2(){if(sym=='+'){advance();T();E2();}else if (sym != ')' && sym != '#'){cout<<"error!"<<endl;exit(0);}}void T(){F();T2();}void T2(){if(sym=='*'){advance();F();T2();}else if(sym!='+'&&sym!=')'&&sym!='#'){cout<<"error!"<<endl;exit(0);}}void F(){if(sym=='('){advance();E();if(sym==')')advance();else{cout<<"error!"<<endl;exit(0);}}else if(sym=='i'){advance();}else{cout<<"error!"<<endl;exit(0);}}void input(){cout<<"请输入需识别的句子:";cin>>a;}void advance(){sym=a[i];i++;}5、测试用例（1）只含有一个字符的形式：iaA(2) 含有‘+’的形式：i+ii+i+ii++++(3) 含有‘*’的形式：i*ii*i*ii***(4) 含有‘（’‘）’的形式：（i）（）（（i））(5) 综合形式：（i+i）*i(i+i)*(i+i)i+i*ii++i*(*i+(i+iii6、实验总结通过本次试验实践掌握了自上而下语法分析法的特点。
编译原理语法分析器编译原理语法分析器是编译器中的重要组成部分，它负责将源代码解析成抽象语法树，为后续的语义分析和代码生成做准备。
本文将介绍语法分析器的原理、分类和常用算法。
一、语法分析器的原理语法分析器的主要任务是根据给定的文法定义，将源代码解析成一个个语法单元，并构建出一棵抽象语法树。
它通过递归下降、预测分析和LR分析等算法来实现。
1. 递归下降法递归下降法是一种基于产生式的自顶向下分析方法。
它从文法的开始符号出发，通过不断地推导和回溯，逐步地构建抽象语法树。
递归下降法易于理解和实现，但对左递归和回溯有一定的局限性。
2. 预测分析法预测分析法也是自顶向下的分析方法，它通过预测下一个输入符号来选择适当的产生式进行推导。
为了提高效率，预测分析法使用预测分析表来存储各个非终结符和终结符的关系。
3. LR分析法LR分析法是一种自底向上的分析方法，它使用LR自动机和LR分析表来进行分析。
LR自动机是一个有限状态控制器，通过状态转移和规约动作来解析源代码。
LR分析表存储了状态转移和规约的规则。
二、语法分析器的分类根据语法分析器的特性和实现方式，可以将其分为LL分析器和LR 分析器。
1. LL分析器LL分析器是基于递归下降法和预测分析法的一类分析器。
它从左到右、从左到右地扫描源代码，并根据预测分析表进行推导。
常见的LL分析器有LL(1)分析器和LL(k)分析器。
2. LR分析器LR分析器是基于LR分析法的一类分析器。
它先通过移进-归约的方式建立一棵语法树，然后再进行规约操作。
LR分析器具有强大的语法处理能力，常见的LR分析器有LR(0)、SLR(1)、LR(1)和LALR(1)分析器。
三、常用的语法分析算法除了递归下降法、预测分析法和LR分析法，还有一些其他的语法分析算法。
1. LL算法LL算法是一种递归下降法的改进算法，它通过构造LL表和预测分析表实现分析过程。
LL算法具有很好的可读性和易于理解的特点。
2. LR算法LR算法是一种自底向上的分析方法，它通过建立LR自动机和构造LR分析表来进行分析。
实验二语法分析程序设计[实验目的]：1．了解语法分析的主要任务。
2．熟悉编译程序的编制。
[实验内容]：根据某文法，构造一基本递归下降语法分析程序。
给出分析过程中所用的产生式序列。
[实验要求]：1.选择一个文法，进行实验，可选的文法包括以下三个：P190 4.8P190 4.9P190 4.102.设计语法分析程序的输出形式（输出应为语法树或推导），一个可以参考的例子，可见图1。
3.编写递归下降语法分析程序（参考P148-149 Topdown parsing byrecursive-descent）,实现基本的递归下降分析器，能够分析任给的符号串是否为该文法所定义的合法句子。
实验报告中要说明分析使用的方法。
4.根据所作业题选项e所给出的input,生成并输出分析过程中所用的产生式序列(show the actions of parser)：1 产生式12 产生式2……5.自已设计一个不合法的句子，作为输出进行分析，给出结果。
[实验过程]本次实验选择的文法为P190 4.8lexp->atom|listatom->number|identifierlist->(lexp-seq)lexp-seq->lexp lexp-seq1.写出实现的算法，并画流程图。
本次实验采用递归下降算法，算法流程图如下图1-1：图1-1 算法流程图2.根据你选择的文法，分析左递归或左因子是否会影响本算法的结果。
会影响本算法的结果。
递归下降分析法要求的文法是LL(1)文法，需要消除左递归和左因子的影响。
如果存在左因子，对相同的字符跳转到不同的函数，无法实现递归。
3.列举实验设计过程中出现的问题及解决的方法（至少3条，选择实验中最困扰的问题）。
1).会多次输出accept/error结果解决方案：所有的递归函数返回类型为int，若accept返回1，error返回0，在main主函数中统一判断输出语句。
数学与软件科学学院实验报告学期：2015至2016第2学期2016年3月21日课程名称：编译原理专业：信息与计算科学2013级5班实验编号：2实验名称：递归下降分析器指导教师：王开端姓名：李丹学号：2013060510实验成绩：实验二递归下降分析器实验目的：通过设计、编制、调试递归下降语法分析程序，对输入的符号串进行分析匹配，观察输入符号串是否为给定文法的句子。
实验内容：根据文法G[E]设计递归下降分析器并分析输入串)(*321i i i +是否为文法的句子。
G[E]：E→E+T|TT→T*F|F F→(E)|i实验步骤：在进行递归下降分析法之前，必须对文法进行左递归和回溯的消除。
1消除左递归直接消除见诸于产生式中的左递归比较容易，其方法是引入一个新的非终结符，把含有左递归的产生式改为右递归。
文法G[E]经过消去直接左递归后得到文法G’[E]为：G’[E]：iE F FT T FT T TE E TE E |)(|'*''|'''→→→+→→εε2消除回溯回溯发生的原因在于候选式存在公共的左因子。
一般情况下，设文法中关于A 的产生式为ji i A ββδβδβδβ|...|||...||121+→，那么，可以把这些产生式改写为⎩⎨⎧→→+ij i A A A ββββδ|...|'|...||'11经过反复提取左因子，就能把每个非终结符（包括新引进者）的所有候选首字符集变为两两不相交（既不含有公共左因子）。
3什么是递归下降分析法递归下降分析法是一种自顶向下的分析方法，文法的每个非终结符对应一个递归过程（函数）。
分析过程就是从文法开始符出发执行一组递归过程（函数），这样向下推导直到推出句子；或者说从根节点出发，自顶向下为输入串寻找一个最左匹配序列，建立一棵语法树。
在不含左递归和每个非终结符的所有候选终结首字符集都两两不相交条件下，我们就可能构造出一个不带回溯的自顶向下的分析程序，这个分析程序是由一组递归过程（或函数）组成的，每个过程（或函数）对应文法的而一个非终结符。
实验三递归下降分析器设计与实现编译原理实验报告一、引言递归下降分析器是编译原理中常用的一种语法分析方法。
它根据文法规则和输入的源代码，递归地进行语法分析，判断源代码是否符合给定的文法规则。
本实验旨在通过设计与实现一个简单的递归下降分析器，加深对编译原理中语法分析的理解。
二、实验目的1.学习递归下降分析器的原理和设计方法；2.掌握使用递归下降分析器进行简单语法分析的过程；3.加深对编译原理中文法规则和语法分析的理解。
三、实验过程1.设计文法规则：根据实验要求，设计一个简单的算术表达式文法规则。
例如，我们可以采用以下文法规则：```E->E+T，E-T，TT->T*F，T/F，FF -> ( E ) ， num```2.设计分析器：根据设计的文法规则，设计递归下降分析器的结构和算法。
我们可以使用编程语言实现一个类，其中包含递归下降分析器所需要的方法和数据结构。
3. 实现分析器：根据设计的分析器结构和算法，使用编程语言实现递归下降分析器的代码。
可以选择常用的编程语言，如C++、Java、Python等。
4.进行语法分析：编写测试代码，使用实现的递归下降分析器对输入的算术表达式进行语法分析。
根据分析结果，判断输入的算术表达式是否符合给定的文法规则。
五、实验结果实验结果根据设计的分析器的实现和测试代码的编写而定。
例如，对于以下输入的算术表达式：(3+4)*5-2，经过递归下降分析器的分析，应该能正确判断其是否符合给定的文法规则。
六、实验总结递归下降分析器是编译原理中常用的一种语法分析方法。
通过实验三，我深入理解了递归下降分析器的原理和设计方法，并通过实现一个简单的递归下降分析器，加深了我对编译原理中文法规则和语法分析的理解。
在实验过程中，我学会了如何根据设计的文法规则来设计递归下降分析器的结构和算法。
我使用了编程语言实现了递归下降分析器的代码，并编写了相应的测试代码进行语法分析。
通过测试，我验证了递归下降分析器的正确性。
《编译原理》课程实验陈述之南宫帮珍创作实验名称：递归下降分析法姓名：彭国保学号：540907010130院系：计算机与通信工程学院专业：计算机科学与技术班级：09-1班教师：韩丽2012年4月22日一．实验目的根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。
本次实验的目的主要是加深对递归下降分析法的理解。
程序开始变得复杂起来，需要利用到程序设计语言的知识和大量编程技巧，递归下降分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。
通过练习，掌握函数间相互调用的方法。
二．实验内容递归下降分析法是确定的自上而下分析法，它要求文法是LL(1)文法。
它的基本思想是：对文法中的每个非终结符编写一个函数或子程序，每个函数或子程序的功能是识别由该非终结符所暗示的语法成分。
程序算法描述词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。
改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法，为G的每个非终结符号U构造一个递归过程。
U的发生式的右边指出这个过程的代码结构：(1)若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。
(2)若是非终结符号，则调用与此非终结符对应的过程。
当A的右部有多个发生式时,可用选择结构实现。
最后编写程序以实现上述功能。
三．实验步调根据上述算法描述，编写程序以实现相应的功能，该程序由C语言编写，然后在VC运行环境下进行调试，其实不竭完善，直到能正确的实现递归下降分析功能，判断输入的字符串是否是一个文法的句子。
源程序代码如下：#include<stdio.h>void S();void T();void error();void scaner();char sym;int main(){scaner();S();if(sym=='$') printf("是该文法的句子");else printf("不是该文法的句子");return 0;}void S(){if(sym=='a'||sym=='^') scaner();else if(sym=='('){scaner(); T();if(sym==')') scaner();else error();}else error();}void T(){T1();}void T1(){if(sym==','){scaner();S();T1();}else if(sym !=')')error();}void scaner(){scanf("%c",&sym);}void error(){printf("不是该文法的句子");}调试程序的结果：四．总结与回顾通过本次实验，我掌握了递归下降分析程序的构造过程，将一个文法编写为对应的子程序，如有左递归先消除左递归，再改写为相应的程序。
学号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<stdio.h>
#include<string>
char str[50];
int index=0;
void E(); //E->TX;
void X(); //X->+TX | e
void T(); //T->FY
void Y(); //Y->*FY | e
void F(); //F->(E) | i
int main() /*递归分析*/
{
int len;
int m;
printf("请输入要测试的次数：");
scanf("%d",&m);
while(m--)
{
printf("请输入字符串(长度<50>）:\n");
scanf("%s",str);
len=strlen(str);
//str[len]='#';
str[len+1]='\0';
E();
printf("%s为合法符号串!\n",str);
strcpy(str,"");
index=0;
} return 0;
}
void E()
{ T(); X();}
void X()
{
if(str[index]=='+')
{ index++;
T();
X();
} }
void T()
{ F(); Y(); }
void Y()
{ if(str[index]=='*') {
index++;
F();
Y();
} }
void F()
{
if(str[index]=='i')
{ index++; }
else if (str[index]=='(')
{
index++;
E();
if(str[index]==')')
{ index++; }else
{
printf("\n非法的符号串!\n");
exit (0);
} }
else
{
printf("非法的符号串!\n");
exit(0);
}
}
屏幕截图：
四、讨论与分析
通过本次实验对递归下降词法分析器的结构，过程有了更进一步的了解，通过学习书本和试验原理书上的内容，对它的工作原理，具体实行步骤有了进一步的掌握，由于本次试验是测试性试验，所以要求输出的结果是成功与否，输入一个句型，进过分析，判断它是否合法，主要内容在于其判断过程中。
本次试验不光提高了自己的编程能力，同时提高了对递归下降的了解。
