1. 首页
  2. 文章中心
  3. 编译原理

编译原理实验（2）——递归下降语法分析器

71 阅读 0 评论
我是靠谱客的博主 内向水壶，最近开发中收集的这篇文章主要介绍编译原理实验（2）——递归下降语法分析器，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

编译实验——递归下降语法分析器

实验内容：

根据课堂讲授的形式化算法，编制程序实现递归下降分析器，能对常见的语句进行分析。
要求实现以下语法的递归下降分析：
在这里插入图片描述

算法分析：

1. 算法设计：

  • 递归下降的语法分析首先应该消除左递归和提取左公因子，从逻辑上检测避免死循环和低效处理，得到产生式如下：

    program -> block
    block -> {stmts}
    stmts -> stmt stmts|null
    stmt -> id=expr;|if(bool)stmt stmt1|while(bool)stmt|do stmt while(bool)|break|block
    stmt1 -> null|else stmt
    bool -> expr bool1
    bool1 -> <expr|<=expr|>expr|>=expr|null
    epxr -> term expr1
    expr1 -> +term expr1|-term expr1|null
    term -> factor term1
    term1 -> *factor term1|/factor term1|null
    factor -> (expr)|id|num

  • 将实验一词法分析器的输出文件token.txt作为输入，逐个读入单词，采用每个产生式的左边的文法符号对应一个函数的形式，实现递归下降分析器。

  • 将最左推导的过程逐步完整输出，具体实现方式是将上一行的输出存储在一个字符串变量Ans中，每次用产生式的右部替换字符串最左非终结符再输出。
    这一步利用到了C++ stl中string头文件中定义的函数erase(),insert(),find()。
    以推导步骤stmts --> stmt stmts为例 ：
    在这里插入图片描述
    2. 输出展示：
    在这里插入图片描述

源代码

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<algorithm>
using namespace std;
int sym[10000];
string token[10000];
string Ans;
int Pos;
int p = 0;//p指向当前正在处理的单词
int flag = 0;
void error();
void program();
void block();
void stmts();
void stmt();
void stmt1();
void booL();
void booL1();
void expr();
void expr1();
void term();
void term1();
void factor();
/*
根据上一实验词法分析器规定：

保留字，一符一类，种类码0~21：
"if","else","while","do","break","main","int","float","double","return","const","void","continue","char","unsigned","enum","long","switch","case","unsigned","auto","static"

特殊符号，一符一类，种类码22~38，种类码39~44为==,!=,&&,||,>=,<=：
"+","-",",","/","=","<",">","{","}",";","(",")","&","!","#","[","]"

ID，种类码101

数字，种类码98~100(十进制，八进制，十六进制)
*/
int main()
{
	ifstream file("token.txt", ios::in);
	if (!file)
	{
		cerr << "文件打开失败！" << endl;
		exit(1);
	}
	char ch;
	string source="";
	file.get(ch);
	do {
		source += ch;
		file.get(ch);
	} while (!file.eof());
	stringstream ss(source);
	int i = 0;
	while (ss>>sym[i])
	{
		ss >> token[i];
		//cout << sym[i] << " " << token[i] << endl;
		i++;
	}
	program();
	if (flag == 0)
		cout << "n语法分析成功！" << endl;
	return 0;
}
void error()
{
	cout << "语法分析出错！" << endl;
}
void program()
{
	cout << "program";
	Ans = "--> blockn       ";
	cout << Ans;
	block();
}
void block()
{
	if (token[p++] == "{")
	{
		//cout << "block --> { stmts }" << endl;
		Pos = Ans.find("block");
		Ans.erase(Pos, 5);
		Ans.insert(Pos, "{stmts}");
		cout << Ans;
		stmts();
		if (flag == 1)
		{
			error();
			return;
		}
		if (token[p++] != "}")
			error();
	}
	else
		error();
}
void stmts()
{
	if (sym[p] == 101 || token[p] == "if" || token[p] == "while" || token[p] == "do" || token[p] == "break" || token[p] == "{")
	{
		//cout << "stmts --> stmt stmts" << endl;
		Pos = Ans.find("stmts");
		Ans.erase(Pos, 5);
		Ans.insert(Pos, "stmtstmts");
		cout << Ans;
		stmt();
		if (flag == 1) return;
		stmts();
		if (flag == 1) return;
	}
	else
	{
		//cout << "stmts --> null" << endl;
		Pos = Ans.find("stmts");
		Ans.erase(Pos, 5);
		Ans.insert(Pos, "");
		cout << Ans;
		return;
	}	
}
void stmt()
{
	if (sym[p] == 101)
	{
		//cout << "stmt --> id = expr ;" << endl;
		Pos = Ans.find("stmt");
		Ans.erase(Pos, 4);
		Ans.insert(Pos, "id=expr;");
		cout << Ans;
		p++;
		if (token[p++] == "=")
		{
			expr();
			if (flag == 1) return;
			if (token[p++] != ";")
				flag = 1;
		}
		else
			flag = 1;
	}
	else if (token[p] == "while")
	{
		//cout << "stmt --> while (bool) stmt" << endl;
		Pos = Ans.find("stmt");
		Ans.erase(Pos, 4);
		Ans.insert(Pos, "while(bool)stmt");
		cout << Ans;
		p++;
		if (token[p++] == "(")
		{
			booL();
			if (token[p++] == ")")
			{
				stmt();
				if (flag == 1) return;
			}
			else
				flag = 1;
		}
		else
			flag = 1;
	}
	else if (token[p] == "do")
	{
		//cout << "stmt --> do stmt while (bool)" << endl;
		Pos = Ans.find("stmt");
		Ans.erase(Pos, 4);
		Ans.insert(Pos, "dostmtwhile(bool)"); 
		cout << Ans;
		p++;
		stmt();
		if (flag == 1) return;
		if (token[p++] == "while" && token[p++] == "(")
		{
			booL();
			if (flag == 1) return;
			if (token[p++] != ")")
				flag = 1;
		}
		else
			flag = 1;
	}
	else if (token[p] == "break")
	{
		//cout << "stmt --> break" << endl;
		Pos = Ans.find("stmt");
		Ans.erase(Pos, 4);
		Ans.insert(Pos, "break");
		cout << Ans;
		p++;
	}
	else if (token[p] == "{")
	{
		//cout << "stmt --> block" << endl;
		Pos = Ans.find("stmt");
		Ans.erase(Pos, 4);
		Ans.insert(Pos, "block");
		cout << Ans;
		block();
	}
	else if (token[p++] == "if" && token[p++] == "(")
	{
		//cout << "stmt --> if (bool) stmt stmt1" << endl;
		Pos = Ans.find("stmt");
		Ans.erase(Pos, 4);
		Ans.insert(Pos, "if(bool)stmt stmt1");
		cout << Ans;
		stmt();
		if (flag == 1) return;
		stmt1();
		if (flag == 1) return;
	}
	else
		flag = 1;
}
void stmt1()
{
	if (token[p++] == "else")
	{
		//cout << "stmt1 --> else stmt" << endl;
		Pos = Ans.find("stmt1");
		Ans.erase(Pos, 5);
		Ans.insert(Pos, "else stmt");
		cout << Ans;
		stmt();
		if (flag == 1) return;
	}
	else
		return;
}
void booL()
{
	//cout << "bool --> expr bool1" << endl;
	Pos = Ans.find("bool");
	Ans.erase(Pos, 4);
	Ans.insert(Pos, "exprbool1");
	cout << Ans;
	expr();
	if (flag == 1) return;
	booL1();
	if (flag == 1) return;
}
void booL1()
{
	if (token[p] == "<" || token[p] == "<=" || token[p] == ">" || token[p] == ">=")
	{
		//cout << "bool1 --> " << token[p] << " expr" << endl;
		Pos = Ans.find("bool1");
		Ans.erase(Pos, 5);
		Ans.insert(Pos, token[p]+"expr");
		cout << Ans;
		p++;
		expr();
		if (flag == 1) return;
	}
}
void expr()
{
	//cout << "expr --> term expr1" << endl;
	Pos = Ans.find("expr");
	Ans.erase(Pos, 4);
	Ans.insert(Pos, "termexpr1");
	cout << Ans;
	term();
	if (flag == 1) return;
	expr1();
	if (flag == 1) return;
}
void expr1()
{
	if (token[p] == "+")
	{
		//cout << "expr1 --> + term" << endl;
		Pos = Ans.find("expr1");
		Ans.erase(Pos, 5);
		Ans.insert(Pos, "+term");
		cout << Ans;
		p++;
		term();
		if(flag == 1) return;
	}
	else if (token[p] == "-")
	{
		//cout << "expr1 --> - term" << endl;
		Pos = Ans.find("expr1");
		Ans.erase(Pos, 5);
		Ans.insert(Pos, "-term");
		cout << Ans;
		p++;
		term();
		if (flag == 1) return;
	}
	else
	{
		//cout << "expr1 --> null" << endl;
		Pos = Ans.find("expr1");
		Ans.erase(Pos, 5);
		Ans.insert(Pos, "");
		cout << Ans;
		return;
	}
}
void term()
{
	//cout << "term --> factor term1" << endl;
	Pos = Ans.find("term");
	Ans.erase(Pos, 4);
	Ans.insert(Pos, "factorterm1");
	cout << Ans;
	factor();
	if (flag == 1) return;
	term1();
	if (flag == 1) return;
}
void term1()
{
	if (token[p] == "*")
	{
		//cout << "term1 --> * factor" << endl;
		Pos = Ans.find("term1");
		Ans.erase(Pos, 5);
		Ans.insert(Pos, "*factor");
		cout << Ans;
		p++;
		factor();
		if (flag == 1) return;
	}
	else if (token[p] == "/")
	{
		//cout << "term1 --> / factor" << endl;
		Pos = Ans.find("term1");
		Ans.erase(Pos, 5);
		Ans.insert(Pos, "/factor");
		cout << Ans;
		p++;
		factor();
		if (flag == 1) return;
	}
	else
	{
		//cout << "term1 --> null" << endl;
		Pos = Ans.find("term1");
		Ans.erase(Pos, 5);
		Ans.insert(Pos, "");
		cout << Ans;
		return;
	}
}
void factor()
{
	if (token[p] == "(")
	{
		//cout << "factor --> (expr)" << endl;
		Pos = Ans.find("factor");
		Ans.erase(Pos, 6);
		Ans.insert(Pos, "(expr)");
		cout << Ans;
		p++;
		expr();
		if (flag == 1) return;
		if (token[p++] != ")")
			flag = 1;
	}
	else if (sym[p] == 101)
	{
		//cout << "factor --> id" << endl;
		Pos = Ans.find("factor");
		Ans.erase(Pos, 6);
		Ans.insert(Pos, "id");
		cout << Ans;
		p++;
	}
	else if (sym[p] >= 98 && sym[p] <= 100)
	{
		//cout << "factor --> num" << endl;
		Pos = Ans.find("factor");
		Ans.erase(Pos, 6);
		Ans.insert(Pos, "num");
		cout << Ans;
		p++;
	}
	else
		flag = 1;
}

最后

以上就是内向水壶为你收集整理的编译原理实验（2）——递归下降语法分析器的全部内容，希望文章能够帮你解决编译原理实验（2）——递归下降语法分析器所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(47)

相关文章

【编译原理】 基于递归下降法实现语法分析器
【编译原理】 基于递归下降法实现语法分析器
【编译原理】简明自顶向下分析算法总结：递归下降，LL(1)分析算法语法分析概念语法分析算法
【编译原理】简明自顶向下分析算法总结：递归下降，LL(1)分析算法语法分析概念语法分析算法
（原创）自顶向下分析法(递归下降分析程序构造)
（原创）自顶向下分析法(递归下降分析程序构造)
递归下降分析-实验报告实验四：语法分析实验
递归下降分析-实验报告实验四：语法分析实验
编译原理实验（2）——递归下降语法分析器
编译原理实验（2）——递归下降语法分析器
语法分析器——自顶向下的递归分析法
语法分析器——自顶向下的递归分析法
编译原理 语法分析—（1）递归下降分析法
编译原理 语法分析—（1）递归下降分析法
【Compile】递归下降语法分析(C++)
【Compile】递归下降语法分析(C++)

评论列表共有 0 条评论

立即
投稿
返回
顶部