《编译原理》实验报告——递归下降语法分析器的构建_输入:简单表达式计算的文法g1 输出: 递归下降语法分析同时输出表达式结果

作者：从前慢现在也慢 | 2024-05-30 00:35:46

踩

输入:简单表达式计算的文法g1 输出: 递归下降语法分析同时输出表达式结果

一、实验要求

运用递归下降法，针对给定的上下文无关文法，给出实验方案。预估实验中可能出现的问题。

二、实验方案

1、构造LL(1),通过设计、编制、调试递归下降语法分析程序，对输入的符号串进行分析匹配，观察输入符号串是否为给定文法的句子。

2、根据LL(1)写函数和程序

三、预估问题

应确保LL（1）构造成功，不然程序会出错

理论基础

递归下降分析程序实现思想简单易懂。程序结构和语法产生式有直接的对应关系。因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。

递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。

每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。

自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，当选择某非终结符的产生时，可根据输入串的当前符号以及各产生式右部首符号而进行，效率高，且不易出错。

无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。

无左递归：既没有直接左递归，也没有间接左递归。

无回溯：对于任一非终结符号U的产生式右部x1|x2|…|xn，其对应的字的首终结符号两两不相交。

如果一个文法不含回路（形如P⇒+ P的推导），也不含以ε为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以ε为右部的产生式）。

四、内容和步骤

1、针对4.8习题输入和输出的设计及代码

2、针对现场给定语法的设计和处理

【考虑简单算术表达式文法G:

E→E + T | T

T→T * F | F

F→(E) | id

试设计递归下降分析程序，以对任意输入的符号串进行语法分析。】

3、实验具体步骤

（1）输入字符串，后并加上$符号

（2）匹配字符，若成功，输出并换行，若遇到非终结符，输出空格，若遇到错误，输出字符和位置。

针对给定语法进行设计：


E->E+T|T
T->TF|F
F->(E)|id
E->TE’
E’->+TE’|ε
T->FT’
T’->FT’|ε
F->(E)|id
First(E)={(,id}
First(E’)={+, ε}
First(T)={(,id}
First(T’)={, ε}
First(F)={(,id}
Follow(E)={KaTeX parse error: Expected 'EOF', got '}' at position 3: ,)}̲ Follow(E’)={,)}
Follow(T)={+,KaTeX parse error: Expected 'EOF', got '}' at position 3: ,)}̲ Follow(T’)={+,,)}
Follow(F)={*,+,$,)}

五、实验结果

代码


#include<iostream> 
#include<string>
#include<math.h>
using namespace std;
string str;
int pos;
bool flag;
void lexp_seq();
void lexp_seq1();
char judge(char ch)
{
	if(ch >= '0' && ch <= '9') return 'n';
	else if((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z')) return 'a';
	else return ch;
}
void error(char ch)
{
	if (flag) return;
	else flag = false;
	cout<<endl<<"error:"<<ch<<",position:"<<pos;
}
 
void match(char kind, char ch)
{
	cout<<kind<<": "<<ch<<endl;
	pos++;
}
 
void atom()
{
	if(!flag) return;
	char ch= judge(str[pos]);
	if(ch=='n') match('n', str[pos]);
	else if(ch=='a') match('a', str[pos]);
	else if(ch=='$') cout<<"accept"<<endl;
	else error(ch);
}
void list()
{
	if(!flag) return;
	match('l', '(');
	cout<<" ";
	lexp_seq1();
	if(str[pos] == ')') match('r',')');
	else error(str[pos]);
}
 
void lexp()
{
	if(!flag) return;
	char ch= judge(str[pos]);
	if(ch == 'n' || ch == 'a'){cout<<" ";atom();}
	else if(ch == '('){cout<<" ";list();}
	else if(ch == '$' ) cout<<"accept"<<endl;
	else error(ch);
}
 
void lexp_seq1()
{
	if(!flag) return;
	char ch= judge(str[pos]);
	if(ch == 'n' || ch == 'a' || ch == '(') {
		cout<<" ";
		lexp();
		cout<<" ";
		lexp_seq1();
	}
	else if(ch == ')') match('r', ')');
	else if(ch == '$') cout<<"accept"<<endl;
	else error(ch);
}
 
int main()
{
	pos = 0;
	flag = true;
	cin>>str;
	str +='$';
	lexp_seq1();
	return 0;
}