c++前提:给定预测分析表,见教材 P76 表 4.1(对应文法为文法 4.2) 要求:构造出相关预测分析程序,并返回一个符号串的分析结果,如果是一个合法的符号串输出正确标志并返回 True,否则输出错误标志并返回 False。 参考:教材 P76-78 4.5 预测分析程序。
时间: 2023-12-10 10:39:24 浏览: 15
以下是一个简单的C++预测分析程序,可以分析给定的符号串是否符合文法4.2:
```c++
#include <iostream>
#include <stack>
#include <map>
#include <vector>
using namespace std;
// 定义文法
vector<string> grammar = {"E->E+T", "E->T", "T->T*F", "T->F", "F->(E)", "F->i"};
// 定义终结符和非终结符集合
vector<string> terminals = {"+", "*", "(", ")", "i", "$"};
vector<string> non_terminals = {"E", "T", "F"};
// 定义预测分析表
map<pair<string, string>, string> predict_table = {
{make_pair("E", "i"), "E->T"},
{make_pair("E", "("), "E->T"},
{make_pair("T", "i"), "T->F"},
{make_pair("T", "("), "T->F"},
{make_pair("F", "i"), "F->i"},
{make_pair("F", "("), "F->(E)"},
{make_pair("E", "+"), "E->E+T"},
{make_pair("T", "*"), "T->T*F"},
{make_pair("E", ")"), ""},
{make_pair("T", ")"), ""},
{make_pair("F", ")"), ""},
{make_pair("E", "$"), ""},
{make_pair("T", "$"), ""},
{make_pair("F", "$"), ""}
};
// 判断一个符号是否为终结符
bool is_terminal(string s)
{
for (string t : terminals) {
if (s == t) {
return true;
}
}
return false;
}
// 判断一个符号是否为非终结符
bool is_non_terminal(string s)
{
for (string t : non_terminals) {
if (s == t) {
return true;
}
}
return false;
}
// 预测分析函数
bool predict_analysis(string input)
{
stack<string> stk;
stk.push("$");
stk.push("E");
int i = 0;
while (!stk.empty()) {
string top = stk.top();
stk.pop();
if (is_terminal(top)) {
if (top == input.substr(i, 1)) {
i++;
} else {
return false;
}
} else if (is_non_terminal(top)) {
string prod = predict_table[make_pair(top, input.substr(i, 1))];
if (prod == "") {
return false;
}
// 将产生式右部逆序入栈
int pos = prod.find("->");
string rhs = prod.substr(pos + 2);
for (int j = rhs.length() - 1; j >= 0; j--) {
stk.push(rhs.substr(j, 1));
}
} else {
return false;
}
}
if (i == input.length()) {
return true;
} else {
return false;
}
}
int main()
{
string input;
cout << "请输入一个符号串:";
cin >> input;
if (predict_analysis(input)) {
cout << "符号串合法" << endl;
} else {
cout << "符号串不合法" << endl;
}
return 0;
}
```
使用该程序,可以输入一个符号串,程序将输出该符号串是否符合文法4.2。
需要注意的是,该程序中的文法、终结符、非终结符集合和预测分析表都是根据教材中的例子手动设置的,如果输入的符号串不符合该文法,程序将无法正确分析。同时,该程序中使用了 STL 中的 stack 和 map,需要在编译时加上 -std=c++11 选项。