针对文法:G[E]:E->E+T|T T->TF|F F->(E)|i 用c++编写程序利用LR(0)分析方法对该文法进行语法分析,构建i+ii句型分析过程中符号栈的变化过程并输出分析表的代码
时间: 2024-06-09 18:04:52 浏览: 10
以下是使用C++编写的LR(0)语法分析程序,该程序利用输入的分析表对输入的句子进行分析,并输出符号栈的变化过程:
```cpp
#include <iostream>
#include <stack>
#include <string>
#include <map>
using namespace std;
// 定义文法产生式
string productions[] = {
"E->E+T",
"E->T",
"T->TF",
"T->F",
"F->(E)",
"F->i"
};
// 定义文法符号集
string symbols[] = {"E", "T", "F", "+", "(", ")", "i", "$"};
// 定义分析表
int actionTable[6][8] = {
{2, 0, 0, 0, 5, 0, 4, 0},
{0, 0, 0, 3, 0, 0, 0, 1},
{0, 4, 2, 0, 0, 4, 0, 0},
{0, 6, 6, 0, 0, 6, 0, 0},
{2, 0, 0, 0, 5, 0, 4, 0},
{0, 0, 0, 6, 0, 0, 0, 0}
};
int gotoTable[6][4] = {
{1, 3, 2, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{1, 3, 2, 0},
{0, 0, 0, 0}
};
// 定义LR(0)分析器类
class LR0Parser {
private:
stack<int> stateStack;
stack<string> symbolStack;
string input;
map<string, int> symbolMap;
void reduce(int prodNumber) {
string prod = productions[prodNumber];
int rightLength = prod.length() - 3;
for (int i = 0; i < rightLength; i++) {
stateStack.pop();
symbolStack.pop();
}
int newState = gotoTable[stateStack.top()][symbolMap[prod.substr(0, 1)]];
stateStack.push(newState);
symbolStack.push(prod.substr(0, 1));
}
public:
LR0Parser(string input) {
this->input = input + "$";
for (int i = 0; i < 8; i++) {
symbolMap[symbols[i]] = i;
}
}
void parse() {
stateStack.push(0);
symbolStack.push("$");
int inputIndex = 0;
while (true) {
int curState = stateStack.top();
string curSymbol = input.substr(inputIndex, 1);
int action = actionTable[curState][symbolMap[curSymbol]];
if (action == 0) {
cout << "Error!" << endl;
break;
} else if (action == 1) {
cout << "Accepted!" << endl;
break;
} else if (action > 0) {
stateStack.push(action);
symbolStack.push(curSymbol);
inputIndex++;
} else if (action < 0) {
reduce(-action);
}
cout << "State Stack: ";
stack<int> tempStateStack = stateStack;
while (!tempStateStack.empty()) {
cout << tempStateStack.top() << " ";
tempStateStack.pop();
}
cout << endl;
cout << "Symbol Stack: ";
stack<string> tempSymbolStack = symbolStack;
while (!tempSymbolStack.empty()) {
cout << tempSymbolStack.top() << " ";
tempSymbolStack.pop();
}
cout << endl << endl;
}
}
};
int main() {
string input;
cout << "请输入要分析的句子: ";
cin >> input;
LR0Parser parser(input);
parser.parse();
return 0;
}
```
以上程序使用了LR(0)分析方法,其中`actionTable`和`gotoTable`分别为LR(0)分析表中的动作表和转移表。程序首先对输入的句子添加结束符`$`,然后依次读入输入的字符,并根据当前状态和输入字符查找分析表中的动作或转移。如果分析表中的动作为移进(shift)操作,则将输入字符入栈并转移到新状态;如果分析表中的动作为归约(reduce)操作,则将符号栈中相应的符号弹出,并根据产生式进行归约,并将新的符号入栈;如果分析表中的动作为接受(accept)操作,则分析成功。在分析过程中,程序会输出符号栈的变化过程。
以下是分析表的代码,其中`-`表示该项为空:
```cpp
// 动作表
int actionTable[6][8] = {
{2, 0, 0, 0, 5, 0, 4, 0},
{0, 0, 0, 3, 0, 0, 0, 1},
{0, 4, 2, 0, 0, 4, 0, 0},
{0, 6, 6, 0, 0, 6, 0, 0},
{2, 0, 0, 0, 5, 0, 4, 0},
{0, 0, 0, 6, 0, 0, 0, 0}
};
// 转移表
int gotoTable[6][4] = {
{1, 3, 2, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{1, 3, 2, 0},
{0, 0, 0, 0}
};
```
其中,动作表中的每一行表示一个状态,每一列表示一个文法符号。表中的每一项表示在该状态下,如果遇到该文法符号,应该进行的动作,其中:
- 如果该项为正整数,则表示进行移进操作,并将输入字符入栈;
- 如果该项为负整数,则表示进行归约操作,并将符号栈中相应的符号弹出,并根据产生式进行归约,并将新的符号入栈;
- 如果该项为0,则表示分析出错。
转移表中的每一行表示一个状态,每一列表示一个非终结符号。表中的每一项表示在该状态下,如果遇到该非终结符号,应该转移到哪一个状态。如果该项为空,则表示没有对应的转移。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)