c++使用ll(1)分析表,构造出相关预测分析程序,并返回一个符号串的分析结果,如果是一个合法的符号串输出正确标志并返回 True,否则输出错误标志并返回 False。
时间: 2023-12-15 22:07:31 浏览: 74
LL(1)分析表是一种自顶向下的语法分析方法,它利用一个预测分析表(Parsing Table)来实现对输入符号串的分析。在预测分析表中,每一个非终结符号和终结符号组成了一个表格,其中行表示非终结符号,列表示终结符号,每个表格中的元素是一个产生式。该产生式就是表示在此行对应的非终结符号在接收此列对应的终结符号时应该采用的产生式。下面是一个简单的LL(1)分析表:
| | + | * | ( | ) | i | $ |
| --- | --- | --- | --- | --- | --- | --- |
| E | | | E->T E' | | E->T E' | |
| E' | E'->+ T E' | | | E'->ε | | E'->ε |
| T | | | T->F T' | | T->F T' | |
| T' | T'->ε | T'->* F T' | | T'->ε | T'->ε | T'->ε |
| F | | | ( E ) | | F->i | |
其中,终结符号包括 +、*、(、)、i和$(表示输入串的结束标记)。非终结符号包括E、E'、T和F。ε表示空串。
根据预测分析表,可以构造出相关预测分析程序。程序的基本思路是:根据当前输入符号和预测分析表中的对应关系,选择相应的产生式,将产生式右部的非终结符号依次压入分析栈中,直到最终将输入符号串分析完毕。如果在分析的过程中发现输入符号串不合法,则输出错误标志并返回False,否则输出正确标志并返回True。
下面是一个使用LL(1)分析表进行语法分析的示例程序:
```c++
#include <iostream>
#include <stack>
#include <map>
#include <vector>
using namespace std;
// 预测分析表
map<pair<char, char>, string> parsing_table{
{{'E', '('}, {"TE'"}},
{{'E', 'i'}, {"TE'"}},
{{'E\'', '+'}, {"+TE'"}},
{{'E\'', ')'}, {"ε"}},
{{'E\'', '$'}, {"ε"}},
{{'T', '('}, {"FT'"}},
{{'T', 'i'}, {"FT'"}},
{{'T\'', '+'}, {"ε"}},
{{'T\'', '*'}, {"*FT'"}},
{{'T\'', ')'}, {"ε"}},
{{'T\'', '$'}, {"ε"}},
{{'F', '('}, {"(E)"}},
{{'F', 'i'}, {"i"}}
};
// 非终结符号集合
vector<char> non_terminals{'E', 'E\'', 'T', 'T\'', 'F'};
// 终结符号集合
vector<char> terminals{'+', '*', '(', ')', 'i', '$'};
// 判断是否为终结符号
bool is_terminal(char c) {
return find(terminals.begin(), terminals.end(), c) != terminals.end();
}
// 获取产生式
string get_production(char non_terminal, char terminal) {
return parsing_table[{non_terminal, terminal}];
}
// 分析输入符号串
bool analyze(string input) {
stack<char> analysis_stack;
analysis_stack.push('$');
analysis_stack.push('E');
int i = 0;
while (!analysis_stack.empty()) {
char top = analysis_stack.top();
analysis_stack.pop();
char cur_input = input[i];
if (top == '$') {
if (cur_input == '$') {
cout << "符号串合法" << endl;
return true;
} else {
cout << "Error: 输入符号串非法" << endl;
return false;
}
} else if (is_terminal(top)) {
if (top == cur_input) {
i++;
} else {
cout << "Error: 输入符号串非法" << endl;
return false;
}
} else {
string production = get_production(top, cur_input);
if (production == "") {
cout << "Error: 输入符号串非法" << endl;
return false;
} else if (production != "ε") {
for (int j = production.size() - 1; j >= 0; j--) {
analysis_stack.push(production[j]);
}
}
}
}
}
int main() {
string input;
cout << "请输入要分析的符号串:";
cin >> input;
analyze(input + "$");
return 0;
}
```
在上面的程序中,我们定义了LL(1)分析表、终结符号集合、非终结符号集合等变量,并编写了is_terminal()、get_production()和analyze()等函数。其中,analyze()函数是整个程序的核心部分,它使用一个栈来模拟语法分析的过程。在每一次循环中,我们从栈顶取出一个符号,根据该符号是否为终结符号,以及当前输入符号是否与该符号匹配,来决定下一步应该执行的操作。如果在分析输入符号串的过程中,发现输入符号串不合法,则输出错误标志并返回false,否则输出正确标志并返回true。
总之,使用LL(1)分析表进行语法分析,可以在一定程度上简化语法分析的过程,提高程序的可读性和可维护性。
阅读全文