#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <map>
#include <sstream>
using namespace std;
pair<string, string> words[100]; // 词法分析结果，每个pair的first如"identifier"，second如"a"
int total_of_words = 0; // words的数量
/*词法分析函数：读入一行字符串，词法分析后将结果保存至words*/
/*total_of_words终为words的长度，即单词数*/
void lexical_analysis()
{
cout << "Enter a statement, such as a1 * (3+c) or 5 * (3-1): " << endl;
string inputs;
cin >> inputs;
// 初始化词典
map<string, string> operators;
std::map<string, string>::iterator it;
operators["+"] = "plus";
operators["-"] = "minus";
operators["*"] = "times";
operators["/"] = "division";
operators[":="] = "equal";
operators["("] = "left_parentheses";
operators[")"] = "right_parentheses";
// 开始分析
int insize = inputs.length();
string word; // 输入符号，如"ab" "123"
for (int i = 0; i<insize; i++)
{
// 空白符跳过
while (inputs[i] == ' ' || inputs[i] == '\n')
i++;
// 标识符/基本字捕捉
if (isalpha(inputs[i])) {
// 拿出一个标识符/基本字
word = inputs[i++];
while (isalpha(inputs[i]) || isdigit(inputs[i]))
word += inputs[i++];
words[total_of_words++] = make_pair("identifier", word);
i--;
}
// 常数
else if (isdigit(inputs[i])) {
// 拿出常数
word = inputs[i++];
while (isdigit(inputs[i]))
word += inputs[i++];
words[total_of_words++] = make_pair("number", word);
//cout << "(number" << "," << word << ")" << endl;
i--;
}
// <、<=号
else if (inputs[i] == '<') {
word = inputs[i++];
if (inputs[i] == '>') {
word += inputs[i];
words[total_of_words++] = make_pair(operators[word], word);
// cout << "(" << operators[word] << "," << word << ")" << endl;
}
else if (inputs[i] == '=') {
word += inputs[i];
words[total_of_words++] = make_pair(operators[word], word);
// cout << "(" <<operators[word] << "," << word << ")" << endl;
}
else if (inputs[i] != ' ' || !isdigit(inputs[i]) || !isalpha(inputs[i])) {
words[total_of_words++] = make_pair(operators[word], word);
// cout << "(" << operators[word] << "," << word << ")" << endl;
}
else {
//cout << "error!" << endl;
}
i--;
}
// >、>=
else if (inputs[i] == '>') {
word = inputs[i++];
if (inputs[i] == '=') {
word += inputs[i];
words[total_of_words++] = make_pair(operators[word], word);
// cout<<"("<<operators[word]<<","<<word<<")"<<endl;
}
else if (inputs[i] != ' ' || !isdigit(inputs[i]) || !isalpha(inputs[i])) {
words[total_of_words++] = make_pair(operators[word], word);
// cout<<"("<<operators[word]<<","<<word<<")"<<endl;
}
else {
//cout<<"error!"<<endl;
}
i--;
}
//:=
else if (inputs[i] == ':') {
word = inputs[i++];
if (inputs[i] == '=') {
word += inputs[i];
words[total_of_words++] = make_pair(operators[word], word);
// cout<<"("<<operators[word]<<","<<word<<")"<<endl;
}
else {
//cout<<"error!"<<endl;
}
//i--;
}
//其它的基本字
else {
word = inputs[i];
it = operators.find(word);
if (it != operators.end()) {
words[total_of_words++] = make_pair(operators[word], word);
// cout<<"("<<operators[word]<<","<<word<<")"<<endl;
}
else {
//cout<<"error!"<<endl;
}
}
}
}
/**四元式结构**/
struct quad {
string result;
string arg1;
string arg2;
string op;
};
struct quad quad[50]; // 四元式数组
int total_of_quad = 0; // 四元式数组里面的四元式数量
//为quad结构类型重载<<运算
ostream & operator<<(ostream & out, struct quad & q) {
out << '(' << q.op << ',' <<q.arg1 << ',' << q.arg2 << ',' << q.result << ')' << endl;
return out;
}
/*发射一行四元式*/
void emit(string op, string arg1, string arg2, string result)
{
quad[total_of_quad].op = op;
quad[total_of_quad].arg1 = arg1;
quad[total_of_quad].arg2 = arg2;
quad[total_of_quad].result = result;
total_of_quad++;
}
int number_of_temp = 0; // 四元式中临时结果的编号，1,2,3,...
/*产生一个串，t1,t2,t3,...*/
string newT()
{
number_of_temp++;
stringstream ss;
ss << number_of_temp;
string ti = "t" + ss.str();
return ti;
}
/**非算术表达式的递归下降分析及四元式生成**/
// 指针前进
int sym = 0; // 正在处理的单词
void advance()
{
++sym;
if (sym > total_of_words) {
cout << "ERROR! The sym pointer is beyond the range! ";
exit(0);
}
}
string E();
string T();
string F();
/*因子分析*/
string F()
{
string arg;
if (words[sym].first == "identifier") {
arg = words[sym].second;
advance();
}
else if (words[sym].first == "number") {
arg = words[sym].second;
advance();
}
else if (words[sym].first == "left_parentheses") {
advance();
arg = E();
if (words[sym].first == "right_parentheses") {
advance();
}
else {
cout << "ERROR! Failure to match the right bracket! \n";
exit(0);
}
}
return arg;
}
/*项分析*/
string T()
{
string op, arg1, arg2, result;
arg1 = F();
while (words[sym].first == "times" || words[sym].first == "division") {
op = words[sym].second;
advance();
arg2 = F();
result = newT();
emit(op, arg1, arg2, result);
arg1 = result;
}
return arg1;
}
/*表达式分析*/
string E()
{
string op, arg1, arg2, result;
if (words[sym].first == "plus" || words[sym].first == "minus") {
advance();
}
arg1 = T();
while (words[sym].first == "plus" || words[sym].first == "minus") {
op = words[sym].second;
advance();
arg2 = T();
result = newT();
emit(op, arg1, arg2, result);
arg1 = result;
}
return arg1;
}
/**算术表达式的递归下降分析及四元式生成**/
int E_();
int T_();
int F_();
int F_()
{
int arg;
if (words[sym].first == "identifier") {
cout << "The arithmetic expression contains variables and cannot be calculated! \n";
exit(0);
}
else if (words[sym].first == "number") {
arg = atoi(words[sym].second.c_str());
advance();
}
else if (words[sym].first == "left_parentheses") {
advance();
arg = E_();
if (words[sym].first == "right_parentheses") {
advance();
}
else {
cout << "ERROR! Failure to match the right bracket! \n";
exit(0);
}
}
return arg;
}
int T_()
{
string op;
int arg1, arg2, result;
arg1 = F_();
while (words[sym].first == "times" || words[sym].first == "division") {
op = words[sym].second;
advance();
arg2 = F_();
if (op == "*") {
result = arg1 * arg2;
arg1 = result;
}
else {
if (arg2 != 0) {
result = arg1 / arg2;
arg1 = result;
}
else {
cout << "The divisor is 0, error! \n";
exit(0);
}
}
}
return arg1;
}
int E_()
{
string op;
int arg1, arg2, result;
if (words[sym].first == "plus" || words[sym].first == "minus") {
advance();
}
arg1 = T_();
while (words[sym].first == "plus" || words[sym].first == "minus") {
op = words[sym].second;
advance();
arg2 = T_();
if (op == "+") {
result = arg1 + arg2;
arg1 = result;
}
else {
result = arg1 - arg2;
arg1 = result;
}
}
return arg1;
}
int main()
{
lexical_analysis();
if (words[0].first == "number") {
cout << E_()<<endl;
}
else {
E();
for (int i = 0; i<total_of_quad; i++) {
cout << quad[i];
}
}
return 0;
}