语法分析-递归下降分析法

实验2-1 语法分析—递归下降法

一、实验目的

通过本实验，掌握自上而下语法分析的要求和特点，以及递归下降分析的原理和过程。调试一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。

二、实验内容

利用C语言完善递归下降分析程序，并对简单语言进行语法分析。

1、要点回顾

标识符ID=letter（letter| digit）*

整型常数NUM=digit digit *

2、待分析的简单语言的语法

用扩充的BNF表示如下：

（1）<程序>：：=begin<语句串>end

（2）<语句串>：：=<语句>{；<语句>}

（3）<语句>：：=<赋值语句>

（4）<赋值语句>：：=ID：=<表达式>

（5）<表达式>：：=<项>{+<项>|-<项>}

（6）<项>：：=<因子>{*<因子>|/<因子>}

（7）<因子>：：=ID| NUM|(<表达式>)

3、实验要求说明

输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。

三、完整源程序代码

#include

#include

#include

using namespace std;

char prog[80];//缓冲区

int p=0;//缓冲区prog的指针

char token[8];//单词

int m=0;//单词token的指针

char ch;//需要分析的字符

int syn=0;//单词的种别码

int sum=0;//计算整数

int n=0;//计数器

int kk=0;

char *rwtab[6]={"begin","if","then","while","do","end"};//关键字

void scaner();//扫描函数

void factor();//因子

void term();//项

void expression();//表达式

void statement();//语句

void yucu();//语句串

void lrparser();//语法分析

//扫描函数

void scaner()

{

for(n=0;n<8;n++)

{

token[n]=0;//初始化单词

}

ch=prog[p++];

while(ch==' ')

{

ch=prog[p++];//过滤空格。（也可用do……while）

}

if((ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z'))

{

m=0;

while ((ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z')||(ch>='0'&&ch<='9')) {

token[m++]=ch;//将当前字符存入单词

ch=prog[p++];//取下一个

}

token[m++]='\0';//结束符

p--;//指针归位

syn=10;//假定是变量

for (n=0;n<6;n++)

{

if (strcmp(token,rwtab[n])==0)

{

syn=n+1;//关键字！

break;

}

}

}

else

if(ch>='0'&&ch<='9')

{

sum=0;

while (ch>='0'&&ch<='9')

{

sum=sum*10+ch-'0';//计算数字

ch=prog[p++];

}

p--;//指针归位

syn=11;//是数字！

}

else

switch (ch)

{

case'>' :

m=0;

token[m++]=ch;

ch=prog[p++];

if (ch=='=')

{

syn=24;//是">="

token[m++]=ch;//将"="存入单词

}

else

{

syn=23;//是">"

p--;//指针归位

}

break;

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':':

m=0;

token[m++]=ch;

ch=prog[p++];

if (ch=='=')

{

syn=18;

token[m++]=ch;

}

else

{

syn=17;

p--;

}

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=28;

token[0]=ch;

break;

case')':

syn=27;

token[0]=ch;

break;

case'#':

syn=0;

token[0]=ch;

break;

default:syn=-1;

}

}

//因子

void factor()

{//问题---补充程序代码

if(syn==11||syn==10)//当扫描的是数字或字母时，继续扫描{

scaner();

}

else if(syn==28) //当扫描的'('时，继续扫描

{

scaner();

expression();

if(syn==27)//当扫描的是')'时，继续扫描

scaner();

else

{

cout<<"错误,表达式缺乏')'"<

kk=1;

}

}

else

{

cout<<"表达式错误,表达式开头不是'('"<

kk=1;

}

return;

}

//项

void term()

factor();

//问题---补充判断条件

while(syn==15 || syn==16)//当开头扫描的是'*'或'/'时，继续扫描{

scaner();

factor();

}

return;

}

//表达式

void expression()

{

//问题---补充程序代码

term();

while(syn==14 || syn==13)//当开头扫描的是'+'或'-'时，继续扫描{

scaner();

term();

}

return;

}

//语句

void statement()

{

//问题---补充判断条件

if(syn==10) //当开头扫描的是字母时，继续扫描

{

scaner();

if(syn==18)//赋值

{

scaner();//问题---补充执行语句

expression();

}

else

{

cout<<"缺:=错误！"<

kk=1;

}

}

else

{

cout<<"error!"<

kk=1;

}

}

//语句串

void yucu()

{

statement();

while(syn==26)//";"

{

scaner();

statement();

}

}

//语法分析

void lrparser()

{

if(syn==1)//begin

{

scaner();

yucu();

if(syn==6)//end

{

scaner();

//问题---补充判断条件

if(syn==0 && kk==0)//当串最后扫描的是'#'，而且并无出错，分析成功cout<<"success!"<

}

else

{

if(kk!=1)

cout<<"缺end错误!"<

kk=1;

}

}

else

{

cout<<"缺begin错误！"<

kk=1;

}

}

int main()

{

//接收用户输入

p=0;

cout<<"please input string:(以#结束)"<

do

{

scanf("%c",&ch);//识别空格

//cin>>ch;//不认识空格，当不存在

prog[p++]=ch;

} while (ch!='#'); //当遇到'#'，结束输入

cout<

p=0;

scaner();

lrparser();

system("pause");

return 0;

}

四、结果验证

（1）输入：begin_a:=9; x:=2*3; b:=a+x end#

输出：success!

（2）输入：x:=9;if x>0 then x:=2*x+1/3;end# 输出：缺begin错误!

（3）输入：begin x:=10;x:=x-3;a:=a+x*7 # 输出：缺end错误!

（4）输入：begin x=x+1;m<>9;end#

输出：缺:=错误!

（5）输入：begin x:=x*7;m:=m+(x*7;end# 输出：错误，表达式缺乏‘)’

五、收获（体会）

由于已经有实验一的基础，看懂程序没有很大问题。在填写补充内容时，必须要注意细节问题，稍有不慎，在运行时便会出各种很奇怪的问题。这次的补充内容是环环相扣的，错了前面的一个，后面的一个也不会正确。必须要弄清楚什么是因子、项、表达式等。

通过这次实验，我加深了自己对语法组成的理解，对于递归下降分析方法更加的得心应手了。

吴雨霜

1108140222

计算机111班

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

编译方法实验报告实验名称：简单的语法分析程序设计

实验要求 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及截图..................................... 错误!未定义书签。 代码清单................................................. 错误!未定义书签。

编译原理-编写递归下降语法分析器

学号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 #include 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;

实验三 递归下降分析程序实现

实验三递归下降分析法 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 程序比较复杂，需要利用到程序设计语言的知识和大量编程技巧，递归下降分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调 用的方法。 二、实验要求 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）如果右部为空，则不处理。

递归下降分析法

《编译原理》课程实验报告 实验名称：递归下降分析法 一．实验目的 1.理解递归下降语法分析方法的主要原理 2.理解递归下降分析法对文法的要求 3．熟练掌握Predict集合的求法 4.熟练掌握文法变换算法（消除左递归和消除公共前缀） 二．实验内容 #include char token[20]; char sym; int p; void S(); void T(); void U(); void Scanner(); void Error(); void S() { if (sym == 'a' || sym == '^') Scanner(); else if (sym == '(') { Scanner(); T(); if (sym == ')') Scanner(); else Error(); } else Error();

} 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; } 三．实验步骤 调试程序的结果：

实验三-递归下降法的语法分析器

魏陈强 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 } ．．．．．．．

实验三_递归下降法的语法分析器

魏陈强 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）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( )过程流程图

编译原理-实验报告2-递归下降分析法

计算机硬件实验室实验报告 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、实验要求： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （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 void E(); void T(); void E1(); void T1(); void F();

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 ′

递归下降分析算术表达式

递归下降分析算术表达式 计算机092—07 邹芬芬 ●实验目的： （1）掌握自上而下语法分析的要求与特点。 （2）掌握递归下降语法分析的基本原理和方法。 （3）掌握相应数据结构的设计方法。 ●实验内容： 编程实现给定算术表达式的递归下降分析器。 算术表达式文法如下：E→E+T | T T→T*F | F F→(E) | i ●设计分析 题目所给的文法不为LL(1)文法，应改写成如下文法： E →TE2 E2→+TE2 |∑ T →FT2 T2→*FT2 | ∑ F →(E) | i 采用递归下降分析法时，需要求出E2和T2 的FOLLOW集： FOLLOW(E2)={），#} FOLLOW(T2)={+,),#} 递归下降分析法是确定的自上而下分析法，基本思想是，对文法中的每个非终结符编写一个函数，每个函数的功能是识别由该非终结符所表示的语法成分。因此需要分别构造E,E2,T,T2,F函数来执行自己的识别功能，根据文法的内容顺序决定函数的识别功能。advance函数用于字符串的推进，input函数用于字符串的输入。 ●程序代码 #include using namespace std; char a[80]; // 字符串的存入 char sym; // 单个的判断字符 int i=0; // 字符串下标 void E(); // 功能识别函数 void E2(); // 功能识别函数 void T(); // 功能识别函数 void T2(); // 功能识别函数 void F(); // 功能识别函数 void input(); // 输入函数

编译原理课程设计---LL(1)递归下降分析器

编译原理课程设计课程设计题目：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表示分析时每

c++实现递归下降法的语法分析器

一、实习题目：递归下降分析 二、实习目的 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。另：程序开始变得复杂起来，需要利用到程序设计语言的知识和大量编程技巧，递归下降分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调用的方法。 三、程序算法描述 1.递归下降分析法功能 词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 2.递归下降分析法前提 改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法。 3.递归下降分析法算法 (1)若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。 (2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现。 4.对下列文法,用递归下降分析法对任意输入的符号串进行分析: (1)E->TG (2)G->+TG|-TG|ε (3)T->FS (4)S->*F S|/FS|ε (5)F->(E)|i 四、核心程序代码 #include #include #include using namespace std; char str[10]; int index = 0; int flag = 0; void E(); //E->TX; void E1(); //X->+TX | e void T(); //T->FY void T1(); //Y->*FY | e void F(); //F->(E) | i void E() { T(); E1(); } void E1()

递归下降语法分析设计原理与实现技术实验报告

递归下降语法分析设计原理与实现技术 实验报告 变更说明 日期版本变更位置变更说明作者2014/4/16 1、0 初稿生成房皓

一、实验目的: 本实验的目的在于在教师的引导下以问题回朔与思维启发的方式,使学生在不断的探究过程中掌握编译程序设计与构造的基本原理与实现技术,启迪学生的抽象思维、激发学生的学习兴趣、培养学生的探究精神与专业素养,从而提高学生发现问题、分析问题与解决问题的能力。 二、实验内容: [实验项目] 完成以下描述算术表达式的LL(1)文法的递归下降分析程序 G[E]: E→TE′ E′→ATE′|ε T→FT′ T′→MFT′|ε F→ (E)|i A→+|- M→*|/ [设计说明] 终结符号i 为用户定义的简单变量,即标识符的定义。 [设计要求] (1)输入串应就是词法分析的输出二元式序列,即某算术表达式“实验项目一”的输出结果,输出为输入串就是否为该文法定义的算术表达式的判断结果; (2)递归下降分析程序应能发现输入串出错; (3)设计两个测试用例(尽可能完备,正确与出错),并给出测试结果。 三、实验环境: 操作系统:Windows 7 软件: VC++6、0 四、程序功能描述: ●提供了两种输入方式:键盘与文件,有文件输入时需为二元式序列; ●能够对输入的字符串做出正确的递归下降分析判断,并给出判断结果; ●能发现输入串中的错误,包含非法字符,输入不匹配等; ●能够处理一些可预见性的错误,如文件不存在,用户输入非法等。

五、数据结构设计: 全局: 局部(main()中): 六、程序结构描述: ●设计方法: 本程序采用从键盘输入或文件读取两种输入方式,其中文件的内容需为二元式序列,然后按照递归下降分析的方法对输入的字符串进行分析判断,并输出判断结果,程序通过对输入串的检查能够发现输入串中的错误。程序规定的单词符号及其种别码见下表: 单词符号种别码单词符号种别码 ( 1 * 5 ) 2 / 6 + 3 i 7 - 4 # 8 ● advance():将下一个字符送入current;

递归下降分析法

实验报告 课程编译原理实验名称递归下降分析法 专业班级学号姓名 实验日期： 2015 年 5 月 20 日 一、实验目的 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、实验内容 1、递归下降分析法的功能：词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 三、实验环境 Visual c++ 6.0 四、实验步骤 代码： #include #include char t[20]; char sym; int p; void T(); void E(); void G() { if(sym=='+') { printf("G->+TG…………%c\n",sym); sym=t[p]; p++; T(); G(); } else if(sym=='-') {

printf("G->-TG…………%c\n",sym); sym=t[p]; p++; T(); G(); } else printf("S->ε…………%c\n",sym); } void F() { if(sym=='i') { printf("F->i…………%c\n",sym); sym=t[p]; p++; } else if(sym=='(') { printf("F->(E)…………%c\n",sym); sym=t[p]; p++; E(); if(sym==')') { sym=t[p]; p++; } else { printf("匹配不成功\n"); exit(0); } } else { printf("匹配不成功\n"); exit(0); } }

编译原理 递归下降分析法C语言

编 译 原 理 实 验 报 告 实验题目：递归子程序 姓名：柏顺顺 学号：540913100201 专业：软件工程JA V A技术班级：09——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)文法的条件能唯一地选择一个候选式进行推导。 实验结果

递归下降分析程序

一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、程序算法描述 这次的实习主要是根据以下文法实现一个递归下降分析器，依据文法如下：（1）E->TG （2）G->+TG|－TG|ε （3）T->FS （4）S->*FS|/FS|ε （5）F->(E)|i 在这个递归下降分析器程序中每一个非终结符E、G、T、S和F构造相应的递归函数，函数的名字表示文法左部的非终结符，函数中就是按文法中每个非终结符右部的候选式依次进行匹配，根据对输入串的分析如果非终结符可以用其中的一个候选式替代就返回1，否则返回0。因为该文法中有五个非终结符，所以定义了五个函数，分别为E（），G（），T()，S()和F（）。当输入一串字符串后，就对该字符串进行分析，首先从开始符号分析，所以首先调用E()函数，在E（）函数中会调用T（）和G(),就是每个非终结符的候选式中出现了哪个非终结符就调用哪个函数。所以，将字符串的第一个字符和E中的每个候选式匹配，如果成功就匹配输入字符串的下一个字符，当最后剩下的字符为’#’时，匹配成功。其实这个工程就是构造一个语法树。 程序总流程图如下： 图1 程序总流程图 三、关键性代码

这个工程的主要工作用五个非终结符生成的句子是否和输入字符串匹配，所以主要的工作是函数E（），G（），T()，S()和F（）的编写。 1. 对非终结符E处理的函数E() 这个函数主要是根据文法中的E->TG，在E（）中调用了T（）和G（）来进行递归分析，这个就是构造生成树的一个分支。 int E() { int f,t;//变量 printf("E-->TG\t");//输出根据的文法 flag=1; outDeduce ();//输出字符串 outputRemain ();//输出剩余字符 f=T(); if (f==0) return(0);//表示当前分析字符可由非终结符T推导出 t=G(); if (t==0) return(0);//表示当前分析字符可由非终结符G推导出 else return(1); } 2. 对非终结符G处理的函数G() 这个函数主要是根据文法中G->+TG|-TG|ε，在函数中调用了T()和G()函数。将当前字符和候选式的第一个字符进行匹配，如果匹配成功，就调用该候选式中涉及到得第一个非终结符对应的函数，一次递归嵌套调用。如果不是由第一个候选式推出然后依次匹配剩下的候选式。 int G() { int f; if(ch=='+') {//当前字符式‘+’ b[i1]=ch; printf("G-->+TG\t");//说明用的是第一个候选式 e[0]='G'; e[1]='='; e[2]='>'; e[3]='+'; e[4]='T'; e[5]='G'; e[6]='#'; Compute ();//计算推导式 flag=0; outDeduce ();//输出字符串 outputRemain ();//输出剩余字符 ch=a[++i1];//读取当前字符的下一个字符 if (f==0) return(0);//表示当前分析字符可由非终结符T推导出 t=G(); if (t==0) return(0); //表示当前分析字符可由非终结符G推导出 if(ch=='-') {//当前字符是‘-’ b[i1]=ch;

递归下降分析器

题目：编程识别由下列文法所定义的表达式的递归下降语法分析器。 E→E+T | E-T | T T→T*F | T/F |F F→(E) | i 输入：每行含一个表达式的文本文件。 输出：分析成功或不成功信息。 解答: （1）分析 a) ∵E=>E+T=>E+T*F=>E+T*(E)即有E=>E+T*(E)存在左递归。用直接改写法消除左递归，得到如下： E →TE’ E’ →+TE’ | ?TE’|ε T →FT’ T’ →*FT’ | /FT’|ε F → (E) | i b) 对于以上改进的方法。可得： 对于E’:FIRST( E’ )=FIRST(+TE’)∪FIRST(-TE’)∪{ε}={+，?，ε} 对于T’:FIRST( T’ )=FIRST(*FT’)∪FIRST(/FT’)∪{ε}={*，∕，ε} 而且：FIRST( E ) = FIRST( T ) = FIRST( F )=FIRST((E))∪ FIRST(i)={(，i } 由此我们容易得出各非终结符的FOLLOW集合如下： FOLLOW( E )= { )，#} FOLLOW(E’)= FOLLOW(E)={ )，#} FOLLOW( T )= FIRST(E’)\ε∪FOLLOW(E’)={+，?，)，#} FOLLOW( T’ ) = FOLLOW( T ) ={+，?，)，#} FOLLOW( F )=FIRST(T’)\ε∪FOLLOW(T’)={*，∕，+，?，)，#}由以上FOLLOW集可以我们可以得出SELECT集如下：

对E SELECT（E→TE’）=FIRST(TE’)=FIRST(T)={ (，i } 对E’ SELECT（E’ →+TE’）={ + } SELECT（E’ →?TE’）={ ? } SELECT（E’ →ε）={ε，)，#} 对T SELECT（T→FT’）={(，i} 对T’ SELECT（T’ →*FT’）={ * } SELECT（T’ →∕FT’）={ ∕ } SELECT（T’ →ε）={ε，+，?，)，#} 对F SELECT（F→(E) ）={ ( } SELECT（F→i）={ i } ∴SELECT(E’ →+TE’)∩SELECT（E’ →?TE’）∩SELECT（E’ →ε）=ΦSELECT(T’ →*FT’)∩SELECT（T’ →∕FT’）∩SELECT（T’ →ε）=Φ SELECT（F→(E) ）∩SELECT（F→i）= Φ 由上可知，有相同左部产生式的SELECT集合的交集为空，所以文法是LL （1）文法。因此，转化后的文法可以用递归下降分析法作语法分析。 （2）设计 这里采用递归下降分析法形象描述递归子程序。程序中将要用到的几个重要数据如下： 一个全局变量ch，存放由文件输入得到的字符。 一个函数宏READ(ch)，实现读取文件中的字符。 五个子函数：P(E)、P(E’)、P(T)、P(T’)、P(F)。 程序主要的子函数模块流程图如下：

递归下降语法分析器实验报告

编译原理实验报告 题目： 递归下降语法分析器 学 院 计算机科学与技术 专 业 xxxxxxxxxxxxxxxx 学 号 xxxxxxxxxxxx 姓 名 宁剑 指导教师 xx 20xx 年xx 月xx 日 递归下降语法分析器 装 订 线

一、实验目的 了解语法分析器的内部工作原理，通过在本次实验中运用一定的编程技巧，掌握对表达式进行处理的一种方法。 二、实验原理 算术表达式的文法可以是（可以根据需要适当改变）： E→E+E|E-E|E*E|E/E|(E)|i 根据递归下降分析法或预测分析法，对表达式进行语法分析，判断一个表达式是否正确。 三、实验步骤 (1) 准备：1. 阅读课本有关章节，确定算术表达式的文法；（设计出预测分析表）；2. 考虑好设计方案；3. 设计出模块结构、测试数据，初步编制好程序。 (2) 上机调试，发现错误，分析错误，再修改完善。教师根据学生的设计方案与学生进行探讨，以修改方案和代码。 (3)改造后的文法：E→E+T|E-T|T T→T*F|T/F|F F→F^|P P→c |id| (E) 四、实验环境 计算机VC++软件 五、实验程序 #include #include #include #include #include void error(); void terror(); void Scanner(); char sym=' '; int i=0; char strToken[30]={""}; FILE *in; void E(); void E1(); void F(); void Retract(char str[30]){ for(int j=0;j<30;j++){ str[j]=0; } } void Scanner(){ sym=fgetc(in);