实验内容
词法分析器
中型模拟
整数 $[1-9]^{\ast}[0-9]^{\ast}$
浮点 $([1-9]^{+}[0-9]^{\ast}\space \vert \space [0-9]^{+}).[0-9]^{+}$
变量 $[symbol]^{+}([0-9]\space \vert \space [symbol])^*$
所用数据结构
struct rec
{
string typ;
string str;
int line;
rec(string a,string b,int c)
{
str=a;
typ=b;
line=c;
}
};
int line_counter=0;
set<string> id= {"int","float","double","char","return","main","std","include"};
set<char> sym= {'+','-','*','/','%','=','#','!','|','{','}','(',')','&','^'};
bool flag_first=1;
char previous=0;
vector<rec> stk;
自定义函数集
bool check_num(string num)
{
for(auto &it: num)
{
if(it<'0'||it>'9')
return 0;
}
return 1;
}
bool is_id(string id_new)
{
if(id.count(id_new)!=0)
return 1;
else
return 0;
}
bool is_sym(char id_new)
{
if(sym.count(id_new)!=0)
return 1;
else
return 0;
}
输入与分词
while(getline(std::cin,line_str))
{
line_counter++;
string buf="";
for(int i=0; i<line_str.size(); i++)
{
if(!(line_str[i]>='0'&&line_str[i]<='9')&&isalpha(line_str[i])==0&&line_str[i]!='.')
{
if(buf=="")
{
if(is_sym(line_str[i]))
{
buf+=line_str[i];
}
else
continue;
}
else if (line_str[i]==' ')
{
check(buf);
buf="";
}
else
{
if(line_str[i]=='.')
{
if(check_num(buf))
{
buf+=".";
continue;
}
else
{
{
check(buf);
buf="";
}
}
}
else
{
if(is_sym(line_str[i]))
{
if(is_sym(line_str[i-1]))
buf+=line_str[i];
else
{
check(buf);
buf=line_str[i];
}
}
else
{
check(buf);
buf="";
}
}
}
//buf="";
}
else
{
if(is_sym(buf[buf.size()-1])&&isalpha(line_str[i])!=0&&(line_str[i]>='0'&&line_str[i]<='9'))
{
check(buf);
buf="";
}
buf+=line_str[i];
}
}
}
检验正则式函数
void check(string buf)
{
if(buf.size()==1)
{
if(is_sym(buf[0]))
{
stk.push_back(rec(buf,"Symbol",line_counter));
}
else if(buf[0]>='0'&&buf[0]<='9')
{
stk.push_back(rec(buf,"Int",line_counter));
}
else if(isalpha(buf[0])!=0)
{
stk.push_back(rec(buf,"Name",line_counter));
}
else
{
stk.push_back(rec(buf,"Invalid Name",line_counter));
}
}
else if(check_num(buf)||std::count(buf.begin(),buf.end(),'.')==1)
{
if(std::count(buf.begin(),buf.end(),'.')==1)
{
if(buf[buf.size()-1]!='.')
stk.push_back(rec(buf,"Float",line_counter));
else
stk.push_back(rec(buf,"Invalid Name",line_counter));
}
else if(check_num(buf))
stk.push_back(rec(buf,"Int",line_counter));
}
else
{
if(is_sym(buf[0]))
{
stk.push_back(rec(buf,"Symbol",line_counter));
}
else if(buf[0]<='9'&&buf[0]>='0')
{
stk.push_back(rec(buf,"Invalid Name",line_counter));
}
else if(is_id(buf))
{
stk.push_back(rec(buf,"Identifier",line_counter));
}
else
{
stk.push_back(rec(buf,"Name",line_counter));
}
}
}
自顶向下的基于递归子程序的语法分析
暴力DFS遍历语法树，在叶子节点时直接字符串判别，相等则return 1; 反之return 0;
所用数据结构
map<char,set<string>> table;
vector<string> vec;
int num;
DFS
bool dfs(string now)
{
if(now.size()>vec[num].size())
{
return 0;
}
bool flag=0;
for(int i=0;i<now.size();i++)
{
if(isupper(now[i]))
{
for(auto &it : table[now[i]])
{
string nxt=now.substr(0,i)+it+now.substr(i+1,now.size()-i-1);
if(nxt==vec[num]) return 1;
if(dfs(nxt)) flag=1;
}
}
}
return flag;
}
处理生成式与建立映射
int n;
cin>>n;
for(int i=0;i<n;i++)
{
string ans;
cin>>ans;
string tmp="";
for(int j=3;j<ans.size();j++)
{
tmp+=ans[j];
}
table[ans[0]].insert(tmp);
}
