编译原理 语法分析—（1）递归下降分析法

编译原理 语法分析—（1）递归下降分析法

实验目的
根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行 分析。本次实验的目的主要是加深对递归下降分析法的理解。

实验环境
Microsoft Visual Studio 2019 Community

思路
为每一个产生式编写一个函数。按照产生式，如果是终结符则直接匹配输入的字符与要求的终结符是否匹配；若是非终结符，调用非终结符对应的函数，传入字符串与开始匹配的位置作为参数。其中任意一步发现不符合语法规则，就认为该字符串有错误。当递归全部终结都没发现错误后，还需要判断是否还有剩余的字符未匹配。如果还有未匹配字符，说明该字符串仍然是不符合语法规则的，因为从开始符无法转换到相应的状态。

产生式
（1）E->eBaA
（2）A->a|bAcB
（3）B->dEd|aC
（4）C->e|dC

//SyntaxAnalysis.h
#pragma once
#include <iostream>
#include <ostream>
#include <stack>
#include <fstream>
#include <vector>
#include <set>
#include <sstream>

using namespace std;

/// <summary>
/// 递归下降分析法词法分析
/// </summary>
class SyntaxAnalysis_RecursiveDescentParsing
{
	static bool E(string str, int& pos);
	static bool A(string str, int& pos);
	static bool B(string str, int& pos);
	static bool C(string str, int& pos);
public:
	static void SyntaxAnalyse_RecursiveDescentParsing(string str);
};

//SyntaxAnalysis.cpp
#include "SyntaxAnalysis.h"

using namespace std;

/// <summary>
/// 非终结符E
/// </summary>
/// <param name="str">要分析的字符串</param>
/// <param name="pos">开始分析的位置，下标从0开始</param>
/// <returns>该字符串是否符合文法</returns>
bool SyntaxAnalysis_RecursiveDescentParsing::E(string str, int& pos)
{
	char ch = str[pos];
	if (ch != 'e')
	{
		cout << "E：第" << pos + 1 << "个字符" << ch << "有错误" << endl;
		return false;
	}

	//使用产生式E -> eBaA
	cout << "E -> eBaA" << endl;

	//B
	pos++;
	if (SyntaxAnalysis_RecursiveDescentParsing::B(str, pos) == false)
	{
		return false;
	}

	//a
	pos++;
	ch = str[pos];
	if (ch != 'a')
	{
		cout << "E：第" << pos + 1 << "个字符" << ch << "有错误" << endl;
		return false;
	}

	//A
	pos++;
	if (SyntaxAnalysis_RecursiveDescentParsing::A(str, pos) == false)
	{
		return false;
	}

	//产生式已经匹配到底，但是字符串后面还有内容
	if (pos < str.length() - 1)
	{
		pos++;
		ch = str[pos];
		cout << "E：第" << pos + 1 << "个字符" << ch << "有错误" << endl;
		return false;
	}

	return true;
}


/// <summary>
/// 非终结符A
/// </summary>
/// <param name="str">要分析的字符串</param>
/// <param name="pos">开始分析的位置，下标从0开始</param>
/// <returns>该字符串是否符合文法</returns>
bool SyntaxAnalysis_RecursiveDescentParsing::A(string str, int& pos)
{
	//使用产生式A -> a
	char ch = str[pos];
	if (ch == 'a')
	{
		cout << "A -> a" << endl;
		return true;
	}
	if (ch != 'b')
	{
		cout << "A：第" << pos + 1 << "个字符" << ch << "有错误" << endl;
		return false;
	}

	//使用产生式A -> bAcB
	cout << "A -> bAcB" << endl;

	//A
	pos++;
	if (SyntaxAnalysis_RecursiveDescentParsing::A(str, pos) == false)
	{
		return false;
	}

	//c
	pos++;
	ch = str[pos];
	if (ch != 'c')
	{
		cout << "A：第" << pos + 1 << "个字符" << ch << "有错误" << endl;
		return false;
	}

	//B
	pos++;
	if (SyntaxAnalysis_RecursiveDescentParsing::B(str, pos) == false)
	{
		return false;
	}

	return true;
}


/// <summary>
/// 非终结符B
/// </summary>
/// <param name="str">要分析的字符串</param>
/// <param name="pos">开始分析的位置，下标从0开始</param>
/// <returns>该字符串是否符合文法</returns>
bool SyntaxAnalysis_RecursiveDescentParsing::B(string str, int& pos)
{
	char ch = str[pos];
	if (ch != 'a' && ch != 'd')
	{
		cout << "B：第" << pos + 1 << "个字符" << ch << "有错误" << endl;
		return false;
	}

	//使用产生式B -> aC
	if (ch == 'a')
	{
		cout << "B -> aC" << endl;

		//C
		pos++;
		if (SyntaxAnalysis_RecursiveDescentParsing::C(str, pos) == false)
		{
			return false;
		}
	}

	//使用产生式B -> dEd
	if (ch == 'd')
	{
		cout << "B -> dEd" << endl;

		//E
		pos++;
		if (SyntaxAnalysis_RecursiveDescentParsing::E(str, pos) == false)
		{
			return false;
		}

		//d
		pos++;
		if (str[pos] != 'd')
		{
			cout << "B：第" << pos + 1 << "个字符" << ch << "有错误" << endl;
			return false;
		}
	}

	return true;
}


/// <summary>
/// 非终结符C
/// </summary>
/// <param name="str">要分析的字符串</param>
/// <param name="pos">开始分析的位置，下标从0开始</param>
/// <returns>该字符串是否符合文法</returns>
bool SyntaxAnalysis_RecursiveDescentParsing::C(string str, int& pos)
{
	//使用产生式C -> e
	char ch = str[pos];
	if (ch == 'e')
	{
		cout << "C -> e" << endl;
		return true;
	}
	if (ch != 'd')
	{
		cout << "C：第" << pos + 1 << "个字符" << ch << "有错误" << endl;
		return false;
	}

	//使用产生式C -> dC
	cout << "C -> dC" << endl;

	//C
	pos++;
	if (SyntaxAnalysis_RecursiveDescentParsing::C(str, pos) == false)
	{
		return false;
	}

	return true;
}


/// <summary>
/// 递归下降分析法进行词法分析
/// </summary>
/// <param name="str">要分析的字符串</param>
void SyntaxAnalysis_RecursiveDescentParsing::SyntaxAnalyse_RecursiveDescentParsing(string str)
{
	if (*(--str.end()) != '#')//判断是否以#结尾
	{
		cout << "不以#结尾，不符合规则" << endl;
		return;
	}
	str.pop_back();//弹出最后的#
	int pos = 0;//初始时要从0开始分析
	if (SyntaxAnalysis_RecursiveDescentParsing::E(str, pos))
	{
		cout << str << "#符合规则" << endl;
	}
}

	cout << "------Syntax Analysis------" << endl;
	string str;
	cout << "输入要分析的字符串：";
	cin >> str;
	SyntaxAnalysis_RecursiveDescentParsing::SyntaxAnalyse_RecursiveDescentParsing(str);
	cout << "--------------------------" << endl << endl;

结果

最后

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

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