/*
SLR(1)語法分析
*/
//李慧，2017/12/12
#include<iostream>
#include<string>
#include <iomanip>
using namespace std;
/*
堆疊的定義
*/
typedef struct StackNode{
string data;
struct StackNode *next;
}StackNode, *LinkStack;
/*
函式宣告
*/
bool InitStack(LinkStack &S);
bool Push(LinkStack &S, string e);
bool Pop(LinkStack &S, string &e);
string GetTop(LinkStack S);
string out(LinkStack S);
int GetNum(LinkStack S);
bool fenxi();
int isT(string s);
int isN(string s);
int isZ(string s);
string change(char a);
int yu(string s);
string Chan(string s);
/*
運算式，分析表（ACTION表，和GOTO表）
*/
string BD[7] = {"S->E","E->E+T","E->T","T->T*F","T->F","F->(E)","F->i"};
string ACTION[12][6];
string GOTO[12][3];
void main(){
//分析表的初始化
for (int i = 0; i < 12; i++){
for (int j = 0; j < 6; j++){
ACTION[i][j] = " ";
}
for (int m = 0; m < 3; m++){
GOTO[i][m] = " ";
}
}
//賦值
ACTION[0][0] = "s5"; ACTION[0][3] = "s4";
ACTION[1][1] = "s6"; ACTION[1][5] = "acc";
ACTION[2][1] = "r2"; ACTION[2][2] = "r7"; ACTION[2][4] = "r2"; ACTION[2][5] = "r2";
ACTION[3][1] = "r4"; ACTION[3][2] = "r4"; ACTION[3][4] = "r4"; ACTION[3][5] = "r4";
ACTION[4][0] = "s5"; ACTION[4][3] = "s4";
ACTION[5][1] = "r6"; ACTION[5][2] = "r6"; ACTION[5][4] = "r6"; ACTION[5][5] = "r6";
ACTION[6][0] = "s5"; ACTION[6][3] = "s4";
ACTION[7][0] = "s5"; ACTION[7][3] = "s4";
ACTION[8][1] = "s6";ACTION[8][4] = "s4";
ACTION[9][1] = "r1"; ACTION[9][2] = "s7";ACTION[9][4] = "r1"; ACTION[9][5] = "r1";
ACTION[10][1] = "r3"; ACTION[10][2] = "r3"; ACTION[10][4] = "r3"; ACTION[10][5] = "r3";
ACTION[11][1] = "r5"; ACTION[11][2] = "r5"; ACTION[11][4] = "r5"; ACTION[11][5] = "r5";
GOTO[0][0] = "1"; GOTO[0][1] = "2"; GOTO[0][2] = "3";
GOTO[3][0] = "8"; GOTO[3][1] = "2"; GOTO[3][2] = "3";
GOTO[6][1] = "9"; GOTO[6][2] = "3";
GOTO[7][2] = "10";
cout << endl << endl << "SLR(1)語法分析 李慧 20153150 2017/12/12" << endl << endl;
//輸出
cout << "輸入的文法（此文法已擴充）：" << endl;
cout << " S->E E->E+T \n E->T T->T*F \n T->F F->(E) \n F->i" << endl;
cout << "UT: + , * , ( , ) , i" << endl;
cout << "UN: S , E , T , F" << endl;
cout << "每個非終結符對應的FOLLOW集：" << endl;
cout << "FOLLOW(S)={ # };" << endl;
cout << "FOLLOW(E)={ # , + , ) };" << endl;
cout << "FOLLOW(T)={ # , + , ) , * };" << endl;
cout << "FOLLOW(F)={ # , + , ) , * };" << endl;
cout << "此文法的分析表如圖：" << endl;
cout << " i + * ( ) # E T F" << endl;
for (int i = 0; i < 12; i++){
cout << i << " ";
for (int j = 0; j < 6; j++){
cout << ACTION[i][j] << " ";
if (j == 5){
for (int m = 0; m < 3; m++){
cout << GOTO[i][m]<< " ";
}
cout << endl;
}
}
}
bool flag = false;
flag=fenxi();
if (flag == true){
cout << endl << "ACCEPT!" << endl;
}
else{
cout << endl << "ERROR!" << endl;
}
}
bool fenxi(){
bool flag = false;
cout << "輸入以#結束的符號串：" << endl;
string juzi = "";
cin >> juzi;
int juzi_len = juzi.length();
//定義兩個堆疊，文法符號堆疊 和 相應的狀態堆疊
LinkStack F;//符號堆疊
LinkStack Z;//狀態堆疊
InitStack(F);//初始化
InitStack(Z);//初始化
cout << "輸出程序如下：" << endl;
cout <<"步驟 狀態堆疊 符號堆疊 輸入串 ACTION GOTO" << endl;
Push(Z, "0");
Push(F,"#");
//開始分析
int j = 0;
int i = 0;
while (i<juzi_len){
//輸出部分
cout << setw(8) << left << (j+1);
cout << setw(10) << left << out(Z);
cout << setw(10) << left << out(F);
cout << setw(15) << left << juzi.substr(i,juzi_len);
string fir = change(juzi.at(i));
int a = isZ(GetTop(Z));
int b = isT(fir);
string move = ACTION[a][b];
if (move.at(0) == 's'){
//輸出部分
cout << setw(10) << left << move << setw(5) << left << "0";
//移進
string z = change(move.at(1));
Push(F,fir);
Push(Z,z);
i++;
}
if (move.at(0) == 'r'){
//歸約
string z = change(move.at(1));//狀態
string db = BD[(z.at(0)-'0')];
int x = yu(db);//產生式右部有幾位
//兩個堆疊均出堆疊
for (int q = 0; q < x; q++){
string toF = GetTop(F);
string toZ = GetTop(Z);
Pop(F,toF);
Pop(Z,toZ);
}
Push(F, change(db.at(0)));//產生式左部進堆疊
string xiaZ = GOTO[isZ(GetTop(Z))][isN(change(db.at(0)))];
//輸出部分
cout << setw(10) << left << move << setw(5) << left << xiaZ;
//如果xiaZ是一位數
if (xiaZ.length() == 1){
Push(Z, xiaZ); }
//如果xiaZ是兩位數
//將兩位數置換，再入堆疊
if (xiaZ.length() == 2){
Push(Z, Chan(xiaZ));
}
}
if (move == "acc"){
//分析是否成功
if ((fir == "#") && (GetNum(F) == 2) && (GetTop(F) == "E")){
flag = true;
//輸出部分
cout << setw(10) << left << move << setw(5) << left << "0" << endl;
i++;
break;
}
}
if (move == " "){
//報錯
//cout << "出錯！無法識別某文法符號！" << endl;
break;
}
cout << endl;
j++;
}
return flag;
}
/*
兩位數位置交換
*/
string Chan(string s){
string ss = "";
ss = change(s.at(1)) + change(s.at(0));
return ss;
}
/*
char轉變為string
*/
string change(char a){
char x[] = "1";
x[0] = a;
return x;
}
//看產生式的右部有幾位
int yu(string s){
int x = 0;
for (unsigned int i = 3; i < s.length(); i++){
x++;
}
return x;
}
int isT(string s){//終結符
int x = -1;
if (s == "i"){
x = 0;
}
if (s == "+"){
x = 1;
}
if (s == "*"){
x = 2;
}
if (s == "("){
x = 3;
}
if (s == ")"){
x = 4;
}
if (s == "#"){
x = 5;
}
return x;
}
int isN(string s){//非終結符
int x = -1;
if (s == "E"){
x = 0;
}
if (s == "T"){
x = 1;
}
if (s == "F"){
x = 2;
}
return x;
}
int isZ(string s){
int x = 0;
if (s.length() == 1){
x = (s.at(0) - '0');
}
if (s.length() == 2){
x = (s.at(1) - '0') * 10 + (s.at(0) - '0');
}
return x;
}
/*-------------------堆疊的函式---------------------------------*/
//鏈堆疊的初始化
bool InitStack(LinkStack &S){
//構造一個空戰，堆疊頂指標置空
S = NULL;
return true; //代替return OK;
}
//入堆疊
bool Push(LinkStack &S, string e){
//在堆疊頂插入元素e
StackNode *p;
p = new StackNode;
p->data = e;
p->next = S;
S = p;
return true;
}
//出堆疊
bool Pop(LinkStack &S, string &e){
//洗掉S的堆疊頂元素，用e回傳其值
StackNode *p;
if (S == NULL){ return false; } //堆疊空
e = S->data;
p = S;
S = S->next;
delete p;
return true;
}
//取堆疊頂元素
string GetTop(LinkStack S){
//回傳S的堆疊頂元素，不修改堆疊頂指標
if (S != NULL)
{
return S->data;
}
else{
return 0;
}
}
//求堆疊中所有元素的個數
int GetNum(LinkStack S){
int num = 0;
num++;
while (S->next != NULL)
{
num++;
S = S->next;
}
return num;
}
//輸出整個堆疊的元素
string out(LinkStack S){
string str = "";
str += S->data;
while (S->next != NULL)
{
str += S->next->data;
S = S->next;
}
reverse(str.begin(), str.end());
return str;
}
uj5u.com熱心網友回復：
幫頂了
uj5u.com熱心網友回復：
多謝多謝多謝
uj5u.com熱心網友回復：
你是李慧？
uj5u.com熱心網友回復：
。。。。。。。。。。
uj5u.com熱心網友回復：
........
uj5u.com熱心網友回復：
為什么這么夸張~~~
uj5u.com熱心網友回復：
我不知道你是誰呀呀呀呀呀呀
uj5u.com熱心網友回復：
多了一個呀~
uj5u.com熱心網友回復：
老哥穩啊！！！uj5u.com熱心網友回復：
reverse?轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/11005.html
標籤：基礎類