Simple “Come” Compiler
Final homework of CS101H (Programming Languages and Data Structures) – Advisor: Prof. Hao Chen, ShanghaiTech University
This homework is to design a basic compiler handling different inputs. For legal inputs (without syntax error), it will give the correct output and for illegal inputs (with syntax error), it will detect it and give an output as “error” and shows which type of error it is. Here is the source code:
// Created by Hongxiang Gao in December, 2015
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <map>
using namespace std;
class iden
{
public:
string name;
string value;
string type;
iden(string iname,string ivalue,string itype)
{
name = iname;
value = ivalue;
type = itype;
}
};
bool isnumber(string str)
{
bool is = true;
if (isdigit(str[0]) == true)
{
is = true;
}
else if (((str[0] == '+') or (str[0] == '-')) and (str.size() > 1))
{
is = true;
}
else
{
is = false;
}
if (is == true)
{
for (int i = 1;i < str.size();i++)
{
if (isdigit(str[i]) == false)
{
is = false;
break;
}
}
}
return is;
}
vector<string> split(string s)
{
istringstream iss(s);
vector<string> ss0;
do
{
string sub;
iss >> sub;
ss0.push_back(sub);
} while (iss);
if (ss0.back() == "")
{
ss0.pop_back();
}
return ss0;
}
//Declrations
map<string,iden> Declration(vector<string> dec1,map<string,iden> identifier)
{
//判断是否只是个var的开头
if (dec1.size() < 3)
{
cout<<"Error:"<<endl;
return identifier;
}
//判断是否有逗号，如果是的话，如果没有逗号，直接过
if (dec1.size() > 3)
{
if (dec1[dec1.size()-2] == ",")
{
cout<<"Error:"<<endl;
return identifier;
}
for (int i = 2;i < dec1.size() - 1;i = i + 2)
{
if (dec1[i] != ",")
{
cout<<"Error:"<<endl;
return identifier;
}
}
}
//判断identifier是否合法
for (int i = 1;i < dec1.size() - 1;i = i + 2)
{
if (dec1[i] == "var")
{
cout<<"Error:"<<endl;
return identifier;
}
//判断第一位是否是letter
if ((isalpha(dec1[i][0]) == false) and (dec1[i][0] != '_'))
{
cout<<"Error:"<<endl;
return identifier;
}
else
{
//判断每一位是否为digit或letter
for (int j = 1;j < dec1[i].size();j++)
{
if ((isdigit(dec1[i][j]) == false) and (isalpha(dec1[i][j]) == false) and (dec1[i][j] != '_'))
{
cout<<"Error:"<<endl;
return identifier;
}
}
}
}
//判断是否已存在
for (int i = 1;i < dec1.size() - 1;i = i + 2)
{
if (identifier.find(dec1[i]) != identifier.end())
//已经存在
{
cout<<"Error:"<<endl;
return identifier;
}
}
//判断最后一个是否是string或int
if (dec1[dec1.size()-1] == "string")
{
//如果是string，往vector里加新成员
for (int i = 1;i < dec1.size()-1;i = i + 2)
{
string str1 = "";
string str2 = "string";
iden newiden(dec1[i],str1,str2);
identifier.insert(pair<string,iden>(newiden.name,newiden));
}
}
else if (dec1[dec1.size()-1] == "int")
{
//如果是int，往vector里加新成员
for (int i = 1;i < dec1.size()-1;i = i + 2)
{
string str1 = "0";
string str2 = "int";
iden newiden(dec1[i],str1,str2);
identifier.insert(pair<string,iden>(newiden.name,newiden));
}
}
else
{
//如果都不是，错误
cout<<"Error:"<<endl;
return identifier;
}
return identifier;
}
//Expression
//Numbers
int calculate(vector<string> expression,map<string,iden> identifier)
{
if ((expression.size() == 1) and (isnumber(expression[0]) == false) and (identifier.find(expression[0]) == identifier.end()))
{
return 12345;
}
int left = 0;
int right = 0;
for (int i = 0;i < expression.size()-1;i++)
{
if ((expression[i] == "(") or (expression[i] == "+") or (expression[i] == "-") or (expression[i] == "*"))
{
if ((expression[i+1] == ")") or (expression[i+1] == "+") or (expression[i+1] == "-") or (expression[i+1] == "*"))
{
return 12345;
}
else if (expression[i] == "(")
{
left++;
}
}
else if (expression[i] == ")")
{
right++;
}
else if ((isnumber(expression[i]) == true ) or (identifier.find(expression[i]) != identifier.end()))
{
if ((isnumber(expression[i+1]) == true ) or (identifier.find(expression[i+1]) != identifier.end()))
{
return 12345;
}
}
if (left < right)
{
return 12345;
}
}
if (expression[expression.size()-1] == ")")
{
right++;
}
else if (expression[expression.size()-1] == "(")
{
left++;
}
if (left < right)
{
return 12345;
}
vector<string> stack;
vector<string> postfix;
for (int i = 0;i < expression.size();i++)
{
// cout<<expression[i]<<endl;
if (isnumber(expression[i]) == true)
{
postfix.push_back(expression[i]);
}
else if (expression[i] == ")")
{
while(true)
{
string temp = stack.back();
stack.pop_back();
if ((temp != "(") and (stack.empty() == false))
{
postfix.push_back(temp);
}
else if (temp == "(")
{
break;
}
else
{
return 12345;
}
}
}
else if ((expression[i] == "+") or (expression[i] == "-"))
{
if ((stack.empty() == false) and (stack.back() == "*"))
{
while((stack.empty() == false) and (stack.back() == "*"))
{
postfix.push_back(stack.back());
stack.pop_back();
}
stack.push_back(expression[i]);
}
else
{
stack.push_back(expression[i]);
}
}
else if ((expression[i] == "*") or (expression[i] == "("))
{
stack.push_back(expression[i]);
}
else
{
map<string,iden>::iterator iter;
iter = identifier.find(expression[i]);
if((iter != identifier.end()) and (iter->second.type == "int"))
{
postfix.push_back(iter->second.value);
}
else
{
return 12345;
}
}
}
while(stack.empty() == false)
{
if (stack.back() != "(")
{
postfix.push_back(stack.back());
stack.pop_back();
}
else
{
return 12345;
}
}
// for (int i = 0;i < postfix.size();i++)
// {
// cout<<postfix[i]<<endl;
// }
vector<int> temp;
for (int i = 0;i < postfix.size();i++)
{
if (isnumber(postfix[i]) == true)
{
temp.push_back(stoi(postfix[i]));
}
else if (postfix[i] == "+")
{
int temp1 = 0;
int temp2 = 0;
if (temp.empty() == false)
{
temp1 = temp.back();
temp.pop_back();
}
else
{
return 12345;
}
if (temp.empty() == false)
{
temp2 = temp.back();
temp.pop_back();
}
else
{
return 12345;
}
temp.push_back(temp1 + temp2);
}
else if (postfix[i] == "-")
{
int temp1 = 0;
int temp2 = 0;
if (temp.empty() == false)
{
temp1 = temp.back();
temp.pop_back();
}
else
{
return 12345;
}
if (temp.empty() == false)
{
temp2 = temp.back();
temp.pop_back();
}
else
{
return 12345;
}
temp.push_back(temp2 - temp1);
}
else if (postfix[i] == "*")
{
int temp1 = 0;
int temp2 = 0;
if (temp.empty() == false)
{
temp1 = temp.back();
temp.pop_back();
}
else
{
return 12345;
}
if (temp.empty() == false)
{
temp2 = temp.back();
temp.pop_back();
}
else
{
return 12345;
}
temp.push_back(temp1 * temp2);
}
}
if (temp.size() == 1)
{
return temp[0];
}
else
{
return 12345;
}
}
//Strings
string Plusstring(vector<string> expression,map<string,iden> identifier)
{
string temp = "";
int s = 0;
int add = 0;
int left = 0;
int right = 0;
for (int i = 0;i < expression.size()-1;i++)
{
if (expression[i] == "(")
{
if ((expression[i+1] == ")") or (expression[i+1] == "+"))
{
return "imstupid";
}
}
else if (((expression[i][0] == '\"') and (expression[i][expression[i].size()-1] == '\"') and (expression[i].size() >= 2)) or (identifier.find(expression[i]) != identifier.end()))
{
if (((expression[i+1][0] == '\"') and (expression[i+1][expression[i+1].size()-1] == '\"') and (expression[i+1].size() >= 2)) or (identifier.find(expression[i+1]) != identifier.end()))
{
return "imstupid";
}
}
else if (expression[i] == "+")
{
if ((expression[i+1] == ")") or (expression[i+1] == "+"))
{
return "imstupid";
}
}
}
for (int i = 0;i < expression.size();i++)
{
if (expression[i] == "(")
{
left++;
}
else if (expression[i] == ")")
{
right++;
}
else if (expression[i] == "+")
{
{
add++;
}
}
else if ((expression[i][0] == '\"') and (expression[i][expression[i].size()-1] == '\"') and (expression[i].size() >= 2))
{
for (int j = 1;j < expression[i].size()-1;j++)
{
if (expression[i][j] == '\"')
{
return "imstupid";
}
}
temp = temp + expression[i].substr(1,expression[i].size()-2);
s++;
}
else
{
map<string,iden>::iterator iter;
iter = identifier.find(expression[i]);
if((iter != identifier.end()) and (iter->second.type == "string"))
{
temp = temp + iter->second.value;
s++;
}
else
{
return "imstupid";
}
}
if (left < right)
{
return "imstupid";
}
}
if (left != right)
{
return "imstupid";
}
if (((add == 0) and (s > 1)) or ((add > 0) and (s != add + 1)))
{
return "imstupid";
}
return temp;
}
//assignment
map<string,iden> assignment(vector<string> expression,map<string,iden> identifier)
{
// vector<string>::temp iterator it = temp.begin();
string name = expression[0];
expression.erase(expression.begin());
expression.erase(expression.begin());
map<string,iden>::iterator iter;
iter = identifier.find(name);
if(iter == identifier.end())
{
cout<<"Error:"<<endl;
return identifier;
}
else if ((iter->second.type == "string"))
{
string value = Plusstring(expression,identifier);
if (value != "imstupid")
{
iter->second.value = value;
}
else
{
cout<<"Error:"<<endl;
return identifier;
}
}
else if ((iter->second.type == "int"))
{
int value = calculate(expression,identifier);
if (value != 12345)
{
stringstream ss;
ss<<value;
string s1 = ss.str();
iter->second.value = s1;
}
else
{
cout<<"Error:"<<endl;
return identifier;
}
}
else
{
cout<<"Error"<<endl;
return identifier;
}
return identifier;
}
//Short Declration
map<string,iden> Short(vector<string> expression,map<string,iden> identifier)
{
if ((identifier.find(expression[0]) != identifier.end()) and (identifier.empty() == false))
{
cout<<"Error:"<<endl;
return identifier;
}
else
{
//判断identifier是否合法
//判断第一位是否是letter
if ((isalpha(expression[0][0]) == false) and (expression[0][0] != '_'))
{
cout<<"Error:"<<endl;
return identifier;
}
else
{
//判断每一位是否为digit或letter
for (int j = 1;j < expression[0].size();j++)
{
if ((isdigit(expression[0][j]) == false) and (isalpha(expression[0][j]) == false) and (expression[0][j] != '_'))
{
cout<<"Error:"<<endl;
return identifier;
}
}
string name = expression[0];
expression.erase(expression.begin());
expression.erase(expression.begin());
string value1 = Plusstring(expression,identifier);
int value2 = calculate(expression,identifier);
if (value1 != "imstupid")
{
iden newiden(name,value1,"string");
identifier.insert(pair<string,iden>(newiden.name,newiden));
return identifier;
}
else if (value2 != 12345)
{
stringstream ss;
ss<<value2;
string valuess = ss.str();
iden newiden(name,valuess,"int");
identifier.insert(pair<string,iden>(newiden.name,newiden));
return identifier;
}
else
{
cout<<"Error:"<<endl;
return identifier;
}
}
}
}
int main()
{
string rawinput = "";
map<string,iden> identifier;
while (getline(cin,rawinput))
{
vector<string> input = split(rawinput);
// for (int i = 0;i < input.size();i++)
// {
// cout<<input[i]<<endl;
// }
if (input.size() > 0)
{
if ((input[0] == "var") and (input.size() >= 3))
//Declration
{
// cout<<"var"<<endl;
identifier = Declration(input,identifier);
}
else if ((input[1] == "=") and (input.size() >= 3))
//Assignment
{
// cout<<"ass"<<endl;
identifier = assignment(input,identifier);
}
else if ((input[1] == ":=") and (input.size() >= 3))
//Short Declration
{
// cout<<"short"<<endl;
identifier = Short(input,identifier);
}
else
//Expression
{
int value1 = calculate(input,identifier);
string value2 = Plusstring(input,identifier);
if (value1 != 12345)
{
cout<<value1<<endl;
}
else if (value2 != "imstupid")
{
cout<<"\""<<value2<<"\""<<endl;
}
else
{
cout<<"Error:"<<endl;
}
}
}
}
// cout<<Plusstring(ss)<<endl;
// if (calculate(ss) != 12345)
// {
// cout<<calculate(ss)<<endl;
// }
return 0;
}