实验3 算术表达式递归下降法

编译原理实验报告—递归下降分析法程序实验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可以产生字符-。

四则运算递归下降法递归下降法是一种常用于编写表达式解析器的技术，它将一个复杂的问题分解为一系列简单的子问题。

对于四则运算，可以通过递归下降法来解析表达式，例如，一个简单的表达式可以包含加法、减法、乘法和除法。

下面是一个简单的 Python 代码示例，演示了如何使用递归下降法来解析四则运算表达式：class Parser:def __init__(self, expression):self.tokens = self.tokenize(expression)self.current_token = 0def tokenize(self, expression):# 将表达式分解为标记（tokens）# 这里简单地将操作符和数字作为标记，实际的解析可能更复杂return expression.replace(' ', '').replace('+', ' + ').replace('-', ' - ').replace('*', ' * ').replace('/', ' / ').split()def parse_expression(self):return self.parse_addition_subtraction()def parse_addition_subtraction(self):left_expr = self.parse_multiplication_division()while self.current_token < len(self.tokens):operator = self.tokens[self.current_token]if operator in ('+', '-'):self.current_token += 1right_expr = self.parse_multiplication_division()if operator == '+':left_expr += right_exprelse:left_expr -= right_exprelse:breakreturn left_exprdef parse_multiplication_division(self):left_expr = self.parse_number()while self.current_token < len(self.tokens):operator = self.tokens[self.current_token] if operator in ('*', '/'):self.current_token += 1right_expr = self.parse_number()if operator == '*':left_expr *= right_exprelse:if right_expr != 0:left_expr /= right_exprelse:raise ValueError("Division by zero")else:breakreturn left_exprdef parse_number(self):if self.current_token < len(self.tokens):token = self.tokens[self.current_token]self.current_token += 1if token.isdigit() or (token[0] == '-' and token[1:].isdigit()):return int(token)else:raise ValueError(f"Invalid token: {token}")else:raise ValueError("Unexpected end of expression")# 示例用法expression = "3 + 5 * ( 2 - 8 ) / 4"parser = Parser(expression)result = parser.parse_expression()print(f"Result: {result}")在这个示例中，parse_expression是最顶层的解析函数，它调用parse_addition_subtraction来解析加法和减法，而后者又调用parse_multiplication_division来解析乘法和除法，依此类推。

递归下降法递归下降法是一种能够解决CFG（上下文无关文法）中文法制导翻译方法，它是程序设计语言翻译中常用的算法之一。

它是一种分析工具，可以将源程序转换成更简化的表示形式，有助于实现高效编译。

递归下降法本质上是一种递归算法，又被称为递归前行法。

它是一种将一个文法应用到有括号结构的句子中的一种方法，利用递归的概念，将文法的对应句子的分析过程反映到源程序中，实现源程序的分析。

首先，基于CFG，递归下降法使用了文法的结构体，其构成元素有符号表，文法规则，产生式，终结符号和非终结符号，等等。

递归下降法从高层次上分析文法，它将文法结构条件分解为可以分析的符号表，对每一个符号提出文法规则，由此可以实现编译器的分析和转换。

第二，递归下降法可以利用递归的概念，从高层次的文法分析过程得出底层符号的实现方式。

比如文法：A→BB，如果B仅仅是一个终结符号，可以将其分析为A→BC，将文法分解，再对终结符号进行分析，直到将所有的终结符号分析完毕。

再者，递归下降法能够找到源程序中不符合文法要求的语句，可以更精确地指出源程序中的错误。

比如在语法分析的过程中，如果碰到与文法不符的句子，就能发现错误，及时给出报错信息，从而纠正错误。

最后，递归下降法是一种全面的语法分析算法，不仅可以用于语法分析，也可以用于语义分析。

它利用文法规则来确认每一个单词语句结构，并检测单词是否符合文法，通过这种检测，可以有效率地进行语义分析，找出语法错误，有助于源程序翻译的准确性和正确性。

总之，递归下降法是一种非常有用的文法分析算法，它主要用于解决CFG中的文法制导翻译任务，能够解决句子的分析，语义分析，出错检测等问题，能够精确控制源程序的正确性和准确性，是程序设计翻译中必不可少的算法之一。

实验项目名称：递归下降语法分析实验学时： 6 同组学生姓名：实验地点：实验日期：实验成绩：批改教师：批改时间：一、实验目的和要求通过本实验，了解递归下降预测分析的原理和过程以及可能存在的回溯问题，探讨解决方法，为预测分析表方法的学习奠定基础。

分析递归下降子程序的优缺点。

二、实验仪器和设备硬件系统：586以上计算机、服务器要求内存256以上、Cpu 2.0GHz以上、Clinet内存128以上、CPU奔腾III以上，硬盘，光驱等软件系统：Visual Studio 2005中文版软件三、实验过程1、设计框架图1-1 递归下降程序框架图2、设计步骤1)给定文法：E→E+T｜TT→T*F｜FF→(E)｜i2)构造FIRST()集和FOLLOW()集表2-1 FIRST()集和FOLLOW()集3、程序源代码using System;using System.Collections.Generic;using System.Text;namespace递归下降语法分析{public class Program{public static char []a=new char[50];public static char []b=new char[50];public static char []d=new char[200];public static char []e=new char[10];public static char ch;public static int n1,i1=0,flag=1,n=5;public static int total=0;/*步骤计数器*/public static int E1(){int f,t;Console.Write(total);Console.Write("\tE-->TG\t");total++;flag=1;input();input1();f=T();if (f==0) return(0);t=G();if (t==0) return(0);else return(1);}public static int E(){int f,t;Console.Write(total);Console.Write("\tE-->TG\t");total++;e[0]='E';e[1]='=';e[2]='>';e[3]='T';e[4]='G';e[5]='#'; output();flag=1;input();f=T();if (f==0) return(0);t=G();if (t==0) return(0);else return(1);}public static int T(){int f,t;Console.Write(total);Console.Write("\tT-->FS\t");total++;e[0]='T';e[1]='=';e[2]='>';e[3]='F';e[4]='S';e[5]='#';output();flag=1;input();input1();f=F();if (f==0) return(0);t=S();if (t==0) return(0);else return(1);}public static int G(){int f;if(ch=='+') {b[i1]=ch;Console.Write(total);Console.Write("\tG-->+TG\t");total++;e[0]='G';e[1]='=';e[2]='>';e[3]='+';e[4]='T';e[5]='G';e[6]='#'; output();flag=0;input();input1();ch=a[++i1];f=T();if (f==0) return(0);G();return(1);}Console.Write(total);Console.Write("\tG-->^\t");total++;e[0]='G';e[1]='=';e[2]='>';e[3]='^';e[4]='#';output();input();input1();return(1);}public static int S(){int f,t;if(ch=='*') {b[i1]=ch;Console.Write(total);Console.Write("\tS-->*FS\t");total++;e[0]='S';e[1]='=';e[2]='>';e[3]='*';e[4]='F';e[5]='S';e[6]='#'; output();flag=0;input();input1();ch=a[++i1];f=F();if (f==0) return(0);t=S();if (t==0) return(0);else return(1);}Console.Write(total);Console.Write("\tS-->^\t");total++;e[0]='S';e[1]='=';e[2]='>';e[3]='^';e[4]='#';output();flag=1;a[i1]=ch;input();input1();return(1);}public static int F(){int f;if(ch=='(') {b[i1]=ch;Console.Write(total);Console.Write("\tF-->(E)\t");total++;e[0]='F';e[1]='=';e[2]='>';e[3]='(';e[4]='E';e[5]=')';e[6]='#'; output();flag=0;input();input1();ch=a[++i1];f=E();if (f==0) return(0);if(ch==')') {b[i1]=ch;Console.Write(total);Console.Write("\tF-->(E)\t");total++;flag=0;input();input1();ch=a[++i1];}else {Console.Write("error\n");return(0);}}else if(ch=='i') {b[i1]=ch;Console.Write(total);Console.Write("\tF-->i\t");total++;e[0]='F';e[1]='=';e[2]='>';e[3]='i';e[4]='#';output();flag=0;input();input1();ch=a[++i1];}else {Console.Write("error\n");return(0);}return(1);}public static void input(){int j=0;for (;j<=i1-flag;j++)Console.Write(b[j]); /*输出分析串*/Console.Write("\t\t");Console.Write("\t\t",ch); /*输出分析字符*/ }public static void input1(){int j;for (j=i1+1-flag;j<n1;j++)Console.Write(a[j]); /*输出剩余字符*/ Console.Write("\n");}public static void output(){ /*推导式计算*/int m,k,j,q;int i=0;m=0;k=0;q=0;i=n;d[n]='=';d[n+1]='>';d[n+2]='#';n=n+2;i=n;i=i-2;while(d[i]!='>'&&i!=0) i=i-1;i=i+1;while(d[i]!=e[0]) i=i+1;q=i;m=q;k=q;while(d[m]!='>') m=m-1;m=m+1;while(m!=q) {d[n]=d[m];m=m+1;n=n+1;}d[n]='#';for(j=3;e[j]!='#';j++){d[n]=e[j];n=n+1;}k=k+1;while(d[k]!='=') {d[n]=d[k];n=n+1;k=k+1;}d[n]='#';//system("pause");}static void Main(string[] args){ /*递归分析*/int f,p,j=0;char x;d[0]='E';d[1]='=';d[2]='>';d[3]='T';d[4]='G';d[5]='#';Console.Write("请输入字符串(长度<50,以#号结束）\n");do{ch=(char)Console.Read();a[j]=ch;j++;}while(ch!='#');n1=j;ch=b[0]=a[0];Console.Write("步骤\t文法\t分析串\t\t分析字符\t剩余串\n");f=E1();if (f==0) return;if (ch=='#'){Console.Write("accept\n");p=0;x=d[p];while(x!='#') {Console.Write(x);p=p+1;x=d[p]; /*输出推导式*/ }}else {Console.Write("error\n");Console.Write("回车返回\n");Console.ReadLine();Console.ReadLine();return;}Console.Write("\n");Console.Write("回车返回\n");Console.ReadLine();Console.ReadLine();}}}程序输入输出举例:1、输入“(i+i)*i”，分析如下图所示：2、输入“i#”，分析如下图所示：3、输入“i+i#”，分析如下图所示：四、实验结果与分析通过本次实验基本掌握了语法分析的原理和递归下降子程序分析方法，并且能将学到的知识学以致用，提高了对代码的分析能力，掌握了递归下降语法的构造，对自上再而下的语法分析模式有了更好的认识和理解。