编译原理LL1语法分析算法的实现（token转四元式）
?
#include <stdio.h>
#include <stack>
#include <vector>
#include <iostream>
#include <fstream>
#include <malloc.h>
using namespace std;
?
//token结构
?
struct token {
?? ?int code; //token的类别,code为1则是符号，为2则是数字
?? ?char value; //token的值
};
typedef struct token tokens;
vector<tokens> tokenBuffer; //用于存储token的缓冲区
stack<tokens> tokenBuffers;
?
//产生式结构
?
struct formula {
?? ?int id; //产生式编号
?? ?char left; //产生式左部
?? ?char right[256]; //产生式右部
?? ?int r_length; //产生式右部长度
};
typedef struct formula formulas;
formulas formulaBuffer[11]; //用于存储产生式的缓冲区
?
//四元式结构
?
struct expression {
?? ?char symbol; //操作符
?? ?char num1; //第一个操作数
?? ?char num2; //第二个操作数
?? ?char result; //结果变量
};
typedef struct expression expressions;
vector<expressions> expressionBuffer; //用于存储四元式的缓冲区
int expressionCount = 0; //四元式个数
?
//分析表中每一项的结构
?
struct analysisTable {
?? ?char currentState; //分析栈的栈顶符号
?? ?char currentToken; //当前字符
?? ?int expressionNum; //对应的产生式编号
};
typedef struct analysisTable analysisTables;
vector<analysisTables> analysisTableBuffer; //LL1分析表的缓冲区
stack<char> analysisStack; //分析栈
stack<char> sematicStack; //语义栈
?
//初始化LL1分析表
void initialAnalysisTableBuffer() {
?? ?analysisTables* temp1a = new analysisTable;
?? ?analysisTables* temp1b = new analysisTable;
?? ?analysisTables* temp1c = new analysisTable;
?? ?analysisTables* temp2 = new analysisTable;
?? ?analysisTables* temp3 = new analysisTable;
?? ?analysisTables* temp4 = new analysisTable;
?? ?analysisTables* temp5 = new analysisTable;
?? ?analysisTables* temp6 = new analysisTable;
?? ?analysisTables* temp7a = new analysisTable;
?? ?analysisTables* temp7b = new analysisTable;
?? ?analysisTables* temp7c = new analysisTable;
?? ?analysisTables* temp8 = new analysisTable;
?? ?analysisTables* temp9 = new analysisTable;
?? ?analysisTables* temp10 = new analysisTable;
?? ?analysisTables* temp11 = new analysisTable;
?? ?analysisTables* temp12 = new analysisTable;
?? ?analysisTables* temp13 = new analysisTable;
?? ?analysisTables* temp14 = new analysisTable;
?? ?analysisTables* temp15a = new analysisTable;
?? ?analysisTables* temp15b = new analysisTable;
?? ?analysisTables* temp15c = new analysisTable;
?? ?analysisTables* temp16 = new analysisTable;
?
?? ?temp1a->expressionNum = 1;
?? ?temp1a->currentState = 'E';
?? ?temp1a->currentToken = 'a';
?
?? ?temp1b->expressionNum = 1;
?? ?temp1b->currentState = 'E';
?? ?temp1b->currentToken = 'b';
?
?? ?temp1c->expressionNum = 1;
?? ?temp1c->currentState = 'E';
?? ?temp1c->currentToken = 'c';
?
?? ?temp2->expressionNum = 1;
?? ?temp2->currentState = 'E';
?? ?temp2->currentToken = '(';
?
?? ?temp3->expressionNum = 2;
?? ?temp3->currentState = 'L';
?? ?temp3->currentToken = '+';
?
?? ?temp4->expressionNum = 3;
?? ?temp4->currentState = 'L';
?? ?temp4->currentToken = '-';
?
?? ?temp5->expressionNum = 4;
?? ?temp5->currentState = 'L';
?? ?temp5->currentToken = ')';
?
?? ?temp6->expressionNum = 4;
?? ?temp6->currentState = 'L';
?? ?temp6->currentToken = '#';
?
?? ?temp7a->expressionNum = 5;
?? ?temp7a->currentState = 'T';
?? ?temp7a->currentToken = 'a';
?
?? ?temp7b->expressionNum = 5;
?? ?temp7b->currentState = 'T';
?? ?temp7b->currentToken = 'b';
?
?? ?temp7c->expressionNum = 5;
?? ?temp7c->currentState = 'T';
?? ?temp7c->currentToken = 'c';
?
?
?
?? ?temp8->expressionNum = 5;
?? ?temp8->currentState = 'T';
?? ?temp8->currentToken = '(';
?
?? ?temp9->expressionNum = 8;
?? ?temp9->currentState = 'M';
?? ?temp9->currentToken = '+';
?
?? ?temp10->expressionNum = 8;
?? ?temp10->currentState = 'M';
?? ?temp10->currentToken = '-';
?
?? ?temp11->expressionNum = 6;
?? ?temp11->currentState = 'M';
?? ?temp11->currentToken = '*';
?
?? ?temp12->expressionNum = 7;
?? ?temp12->currentState = 'M';
?? ?temp12->currentToken = '/';
?
?? ?temp13->expressionNum = 8;
?? ?temp13->currentState = 'M';
?? ?temp13->currentToken = ')';
?
?? ?temp14->expressionNum = 8;
?? ?temp14->currentState = 'M';
?? ?temp14->currentToken = '#';
?
?? ?temp15a->expressionNum = 9;
?? ?temp15a->currentState = 'F';
?? ?temp15a->currentToken = 'a';
?
?? ?temp15b->expressionNum = 9;
?? ?temp15b->currentState = 'F';
?? ?temp15b->currentToken = 'b';
?
?? ?temp15c->expressionNum = 9;
?? ?temp15c->currentState = 'F';
?? ?temp15c->currentToken = 'c';
?
?? ?temp16->expressionNum = 10;
?? ?temp16->currentState = 'F';
?? ?temp16->currentToken = '(';
?
?? ?analysisTableBuffer.push_back(*temp1a);
?? ?analysisTableBuffer.push_back(*temp1b);
?? ?analysisTableBuffer.push_back(*temp1c);
?? ?analysisTableBuffer.push_back(*temp2);
?? ?analysisTableBuffer.push_back(*temp3);
?? ?analysisTableBuffer.push_back(*temp4);
?? ?analysisTableBuffer.push_back(*temp5);
?? ?analysisTableBuffer.push_back(*temp6);
?? ?analysisTableBuffer.push_back(*temp7a);
?? ?analysisTableBuffer.push_back(*temp7b);
?? ?analysisTableBuffer.push_back(*temp7c);
?? ?analysisTableBuffer.push_back(*temp8);
?? ?analysisTableBuffer.push_back(*temp9);
?? ?analysisTableBuffer.push_back(*temp10);
?? ?analysisTableBuffer.push_back(*temp11);
?? ?analysisTableBuffer.push_back(*temp12);
?? ?analysisTableBuffer.push_back(*temp13);
?? ?analysisTableBuffer.push_back(*temp14);
?? ?analysisTableBuffer.push_back(*temp15a);
?? ?analysisTableBuffer.push_back(*temp15b);
?? ?analysisTableBuffer.push_back(*temp15c);
?? ?analysisTableBuffer.push_back(*temp16);
}
?
//由于本次实验主要是考察语法分析和语义分析，所以为了节省时间不采用查表的方式获取token，而是直接初始化token的值。
//初始化token缓冲区
void initialTokenBuffer() {
?? ?ifstream fin("tokens.txt");
?? ?char temp[10][5];
?? ?int i = 0;
?? ?while (!fin.eof()) {
?? ? ? ?fin.getline(temp[i], 4);
?? ? ? ?i++;
?? ?}
?? ?fin.close();
?? ?do {
?? ? ? ?i--;
?? ? ? ?tokens *token_temp = new tokens();
?? ? ? ?token_temp->code = atoi(&temp[i][0]);
?? ? ? ?token_temp->value = temp[i][2];
?? ? ? ?tokenBuffer.push_back(*token_temp);
?? ? ? ?tokenBuffers.push(*token_temp);
?
?? ?} while (i != 0);
?? ?// ? ?tokens* t1 = new tokens();
?? ?// ? ?tokens* t2 = new tokens();
?? ?// ? ?tokens* t3 = new tokens();
?? ?// ? ?tokens* t4 = new tokens();
?? ?// ? ?tokens* t5 = new tokens();
?? ?// ? ?tokens* t6 = new tokens();
?? ?// ? ?t1->code = 2;
?? ?// ? ?t1->value = 'a';
?? ?// ? ?t2->code = 1;
?? ?// ? ?t2->value = '+';
?? ?// ? ?t3->code = 2;
?? ?// ? ?t3->value = 'b';
?? ?// ? ?t4->code = 1;
?? ?// ? ?t4->value = '*';
?? ?// ? ?t5->code = 2;
?? ?// ? ?t5->value = 'c';
?? ?// ? ?t6->code = 1;
?? ?// ? ?t6->value = '#';
?
?? ?// ? ?tokenBuffer.push_back(*t1);
?? ?// ? ?tokenBuffer.push_back(*t2);
?? ?// ? ?tokenBuffer.push_back(*t3);
?? ?// ? ?tokenBuffer.push_back(*t4);
?? ?// ? ?tokenBuffer.push_back(*t5);
?? ?// ? ?tokenBuffer.push_back(*t6);
?? ?//
?? ?// ? ?tokenBuffers.push(*t6);
?? ?// ? ?tokenBuffers.push(*t5);
?? ?// ? ?tokenBuffers.push(*t4);
?? ?// ? ?tokenBuffers.push(*t3);
?? ?// ? ?tokenBuffers.push(*t2);
?? ?// ? ?tokenBuffers.push(*t1);
}
?
//初始化产生式缓冲区
void initialFormulaBuffer() {
?? ?formulas *fTemp1 = new formula;
?? ?formulas *fTemp2 = new formula;
?? ?formulas *fTemp3 = new formula;
?? ?formulas *fTemp4 = new formula;
?? ?formulas *fTemp5 = new formula;
?? ?formulas *fTemp6 = new formula;
?? ?formulas *fTemp7 = new formula;
?? ?formulas *fTemp8 = new formula;
?? ?formulas *fTemp9 = new formula;
?? ?formulas *fTemp10 = new formula;
?? ?fTemp1->id = 1;
?? ?fTemp1->left = 'E';
?? ?fTemp1->r_length = 2;
?? ?fTemp1->right[0] = 'T';
?? ?fTemp1->right[1] = 'L';
?? ?fTemp1->right[2] = '\0';
?
?? ?fTemp2->id = 2;
?? ?fTemp2->left = 'L';
?? ?fTemp2->r_length = 4;
?? ?fTemp2->right[0] = '+';
?? ?fTemp2->right[1] = 'T';
?? ?fTemp2->right[2] = 'Y';
?? ?fTemp2->right[3] = 'L';
?? ?fTemp2->right[4] = '\0';
?
?? ?fTemp3->id = 3;
?? ?fTemp3->left = 'L';
?? ?fTemp3->r_length = 4;
?? ?fTemp3->right[0] = '-';
?? ?fTemp3->right[1] = 'T';
?? ?fTemp3->right[2] = 'U';
?? ?fTemp3->right[3] = 'L';
?? ?fTemp3->right[4] = '\0';
?
?? ?fTemp4->id = 4;
?? ?fTemp4->left = 'L';
?? ?fTemp4->r_length = 0;
?? ?//fTemp->right[0] = "N";
?
?? ?fTemp5->id = 5;
?? ?fTemp5->left = 'T';
?? ?fTemp5->r_length = 2;
?? ?fTemp5->right[0] = 'F';
?? ?fTemp5->right[1] = 'M';
?
?? ?fTemp6->id = 6;
?? ?fTemp6->left = 'M';
?? ?fTemp6->r_length = 4;
?? ?fTemp6->right[0] = '*';
?? ?fTemp6->right[1] = 'F';
?? ?fTemp6->right[2] = 'I';
?? ?fTemp6->right[3] = 'M';
?
?? ?fTemp7->id = 7;
?? ?fTemp7->left = 'M';
?? ?fTemp7->r_length = 4;
?? ?fTemp7->right[0] = '/';
?? ?fTemp7->right[1] = 'F';
?? ?fTemp7->right[2] = 'O';
?? ?fTemp7->right[3] = 'M';
?
?? ?fTemp8->id = 8;
?? ?fTemp8->left = 'M';
?? ?fTemp8->r_length = 0;
?
?? ?fTemp9->id = 9;
?? ?fTemp9->left = 'F';
?? ?fTemp9->r_length = 2;
?? ?fTemp9->right[0] = 'i';
?? ?fTemp9->right[1] = 'P';
?
?? ?fTemp10->id = 10;
?? ?fTemp10->left = 'F';
?? ?fTemp10->r_length = 3;
?? ?fTemp10->right[0] = '(';
?? ?fTemp10->right[1] = 'E';
?? ?fTemp10->right[2] = ')';
?
?? ?formulaBuffer[0] = *fTemp1;
?? ?formulaBuffer[1] = *fTemp2;
?? ?formulaBuffer[2] = *fTemp3;
?? ?formulaBuffer[3] = *fTemp4;
?? ?formulaBuffer[4] = *fTemp5;
?? ?formulaBuffer[5] = *fTemp6;
?? ?formulaBuffer[6] = *fTemp7;
?? ?formulaBuffer[7] = *fTemp8;
?? ?formulaBuffer[8] = *fTemp9;
?? ?formulaBuffer[9] = *fTemp10;
?
?
}
?
?
//入语义栈操作
void accept(tokens temp) {
?? ?if (temp.code == 1) {
?? ? ? ?cout << temp.value << "匹配成功" << endl;
?? ? ? ?return;
?? ?}
?? ?cout << temp.value << " ? ?匹配成功" << endl;
?? ?cout << temp.value << " ? ?进入语义栈" << endl;
?? ?sematicStack.push(temp.value);
}
?
//产生四元式并添加到四元式缓冲区中
void produceExpression(char temp) {
?? ?expressions *eTemp = new expressions;
?? ?eTemp->num2 = sematicStack.top();
?? ?sematicStack.pop();
?? ?eTemp->num1 = sematicStack.top();
?? ?sematicStack.pop();
?? ?eTemp->symbol = temp;
?? ?eTemp->result = (char) ((int) 'u' + expressionCount);
?? ?sematicStack.push(eTemp->result);
?? ?expressionBuffer.push_back(*eTemp);
?? ?expressionCount++;
}
?
//输出四元式
void printExpression() {
?? ?for (vector<expressions>::iterator i = expressionBuffer.begin(); i != expressionBuffer.end(); i++) {
?? ? ? ?cout << "四元式:" << i->symbol << " " << (char) (i->num1) << " " << (char) (i->num2) << " " << i->result << endl;
?? ?}
}
?
//输出读取到的token
void printTokens() {
?? ?for (vector<tokens>::iterator i = tokenBuffer.begin(); i != tokenBuffer.end(); i++) {
?? ? ? ?cout << "token：" << i->code << " " << i->value << endl;
?? ?}
}
?
//查找分析表将相应产生式压入分析栈
bool searchAnalysiTable(char cState, tokens cToken) {
?? ?formulas *fTemp = new formula;
?? ?//查分析表，获取对应的产生式编号
?? ?int e_num;
?? ?vector<analysisTables>::iterator i;
?? ?for (i = analysisTableBuffer.begin(); i != analysisTableBuffer.end(); i++) {
?? ? ? ?if (i->currentState == cState && i->currentToken == cToken.value) {
?? ? ? ? ? ?e_num = i->expressionNum;
?? ? ? ? ? ?break;
?? ? ? ?}
?? ?}
?? ?if (i == analysisTableBuffer.end()) {
?? ? ? ?cout << "parse error" << endl;
?? ? ? ?return false;
?? ?}
?? ?cout << "产生式编号：" << e_num << endl;
?? ?//查找产生式缓冲区获得对应产生式
?? ?fTemp = &formulaBuffer[e_num - 1];
?? ?cout << analysisStack.top() << "出栈" << endl;
?? ?analysisStack.pop();
?? ?//将产生式右部逆序压栈
?? ?if (e_num == 9)
?? ? ? ?fTemp->right[0] = cToken.value;
?? ?int j = fTemp->r_length;
?? ?for (int i = 0; i < fTemp->r_length; i++) {
?? ? ? ?cout << fTemp->right[j - 1] << "进入分析栈" << endl;
?? ? ? ?analysisStack.push(fTemp->right[j - 1]);
?? ? ? ?j--;
?? ?}
?? ?return true;
}
int main(int argc, char *argv[]) {
?? ?initialAnalysisTableBuffer();
?? ?initialTokenBuffer();
?? ?initialFormulaBuffer();
?? ?printTokens();
?? ?analysisStack.push('#');
?? ?analysisStack.push('E');
?? ?bool b_temp;
?? ?while (!analysisStack.empty()) {
?? ? ? ?tokens currentToken = tokenBuffers.top();
?? ? ? ?if (currentToken.value == analysisStack.top()) {
?? ? ? ? ? ?accept(currentToken);
?? ? ? ? ? ?tokenBuffers.pop();
?? ? ? ? ? ?cout << analysisStack.top() << "出栈" << endl;
?? ? ? ? ? ?analysisStack.pop();
?? ? ? ? ? ?continue;
?? ? ? ?}
?? ? ? ?cout << "current state:" << analysisStack.top() << endl;
?? ? ? ?cout << "current token:" << currentToken.value << endl;
?? ? ? ?switch (analysisStack.top()) {
?? ? ? ? ? ?case 'Y':
?? ? ? ? ? ? ? ?produceExpression('+');
?? ? ? ? ? ? ? ?analysisStack.pop();
?? ? ? ? ? ? ? ?break;
?? ? ? ? ? ?case 'U':
?? ? ? ? ? ? ? ?produceExpression('-');
?? ? ? ? ? ? ? ?analysisStack.pop();
?? ? ? ? ? ? ? ?break;
?? ? ? ? ? ?case 'I':
?? ? ? ? ? ? ? ?produceExpression('*');
?? ? ? ? ? ? ? ?analysisStack.pop();
?? ? ? ? ? ? ? ?break;
?? ? ? ? ? ?case 'O':
?? ? ? ? ? ? ? ?produceExpression('/');
?? ? ? ? ? ? ? ?analysisStack.pop();
?? ? ? ? ? ? ? ?break;
?? ? ? ? ? ?case 'P':
?? ? ? ? ? ? ? ?analysisStack.pop();
?? ? ? ? ? ? ? ?cout << "P出栈" << endl;
?? ? ? ? ? ? ? ?break;
?? ? ? ? ? ?case '#':
?? ? ? ? ? ? ? ?analysisStack.pop();
?? ? ? ? ? ? ? ?break;
?? ? ? ? ? ?case 'E':
?? ? ? ? ? ?case 'F':
?? ? ? ? ? ?case 'L':
?? ? ? ? ? ?case 'M':
?? ? ? ? ? ?case 'N':
?? ? ? ? ? ?case 'T':
?? ? ? ? ? ? ? ?b_temp = searchAnalysiTable(analysisStack.top(), currentToken);
?? ? ? ? ? ? ? ?break;
?? ? ? ? ? ?default:
?? ? ? ? ? ? ? ?cout << "error" << endl;
?? ? ? ? ? ? ? ?getchar();
?? ? ? ?}
?? ? ? ?if (!b_temp)
?? ? ? ? ? ?return 0;
?? ?}
?? ?printExpression();
?? ?return 0;
}
