《编译原理》实验三：自下而上语法分析（算符优先分析法）

  1 #include <iostream>
  2 #include <string>
  3 #include <vector>
  4 #include <map>
  5 #include <stack>
  6 #include <set>
  7 using namespace std;
  8 
  9 const int nt_num=10;    // 非终结符数目
 10 const int t_num=10;     // 终结符数目
 11 
 12 vector<string> grammer;   // 文法
 13 vector<vector<char> > FirstVT(nt_num,vector<char>(0));
 14 vector<vector<char> > LastVT(nt_num,vector<char>(0));   // FirstVT集和LastVT集
 15 vector<vector<string> > input;   // 输入（','两边）
 16 
 17 vector<char> nonterminal,terminal;   // 非终结符数组 终结符数组
 18 map<char,int> ntchar2idx;   // 非终结符转下标
 19 map<char,int> tchar2idx;   // 终结符转下标
 20 vector<vector<int> > table(nt_num,vector<int>(nt_num,-5));   // 优先关系表：>为1；=为0；<为-1；5为error
 21 stack<char> s1,s2;   // s2作为临时存储
 22 
 23 void getNonterminal(string s)   // 得到非终结符
 24 {
 25     nonterminal.push_back(s[0]);   // 文法的首字母一定为非终结符，且'->'后不用考虑
 26 }
 27 
 28 void getTerminal(string s,set<char>& temp_terminal)   // 得到终结符，当s="over"时说明可将临时set存入永久vector了
 29 {
 30     if (s=="over")
 31     {
 32         for (set<char>::iterator it=temp_terminal.begin();it!=temp_terminal.end();++it)
 33         {
 34             terminal.push_back(*it);
 35         }
 36         terminal.push_back('#');
 37     }
 38     else
 39     {
 40         for (int i=3;i<(int)s.size();++i)   // '->'后除'|'和非终结符的均为终结符
 41         {
 42             if (s[i]!='|' && (s[i]<'A' || s[i]>'Z'))
 43             {
 44                 temp_terminal.insert(s[i]);
 45             }
 46         }
 47     }
 48     return;
 49 }
 50 
 51 bool isTerminal(const char& ch)   // 判断是否为终结符
 52 {
 53     for (int i=0;i<(int)terminal.size();++i)
 54     {
 55         if (ch==terminal[i])
 56         {
 57             return true;
 58         }
 59     }
 60     return false;
 61 }
 62 
 63 void char2idx()   // （非）终结符转下标
 64 {
 65     char ch;
 66     for (int i=0;i<(int)nonterminal.size();++i)
 67     {
 68         ch=nonterminal[i];
 69         ntchar2idx[ch]=i+1;
 70     }
 71     for (int i=0;i<(int)terminal.size();++i)
 72     {
 73         ch=terminal[i];
 74         tchar2idx[ch]=i+1;
 75     }
 76 }
 77 
 78 void createTable()   // 创建优先关系表
 79 {
 80     if (isTerminal('(') && isTerminal(')'))   // 存在终结符'('和'）'，则优先关系表中为=，0
 81     {
 82         table[tchar2idx['(']][tchar2idx[')']]=0;
 83     }
 84     for (int i=0;i<grammer.size();++i)
 85     {
 86         for (int j=3;j<grammer[i].size();++j)
 87         {
 88             if (grammer[i].size()>4 && isTerminal(grammer[i][j]))
 89             {
 90                 int id=tchar2idx[grammer[i][j]];
 91                 if (!isTerminal(grammer[i][j-1]))   // 前一个字符为非终结符，考虑LASTVT集，>，1
 92                 {
 93                     char ch1=grammer[i][j-1];
 94                     for (int k=0;k<LastVT[ntchar2idx[ch1]].size();++k)
 95                     {
 96                         char ch2=LastVT[ntchar2idx[ch1]][k];
 97                         table[tchar2idx[ch2]][id]=1;
 98                     }
 99                 }
100                 if (!isTerminal(grammer[i][j+1]))   // 后一个字符为非终结符，考虑FIRSTVT集，<，-1
101                 {
102                     char ch1=grammer[i][j+1];
103                     for (int k=0;k<FirstVT[ntchar2idx[ch1]].size();++k)
104                     {
105                         char ch2=FirstVT[ntchar2idx[ch1]][k];
106                         table[id][tchar2idx[ch2]]=-1;
107                     }
108                 }
109             }
110         }
111     }
112     char head=grammer[0][0];   // 起始符
113     // '#'
114     table[tchar2idx['#']][tchar2idx['#']]=0;
115     int id=ntchar2idx[head];
116     for (int i=0;i<LastVT[id].size();++i)
117     {
118         char ch=LastVT[id][i];
119         table[tchar2idx[ch]][tchar2idx['#']]=1;
120     }
121     for (int i=0;i<FirstVT[id].size();++i)
122     {
123         char ch=FirstVT[id][i];
124         table[tchar2idx['#']][tchar2idx[ch]]=-1;
125     }
126     return;
127 }
128 
129 bool ERROR(int pos)
130 {
131 //    cout<<"wrong_pos = "<<pos<<endl;
132     return false;
133 }
134 
135 bool opPriorityAnalyse()   // 算符优先分析程序
136 {
137     s1.push('#');
138     int i=0;
139     string t0;
140     char t1;
141     while (!s1.empty() && i<(int)input.size())
142     {
143         t0=input[i][0];
144         if (t0=="ident")
145         {
146             t1='b';
147         }
148         else if (t0=="number")
149         {
150             t1='z';
151         }
152         else
153         {
154             t1=input[i][1][0];   //非number，右边一定只有一个字符，取[0]即可
155         }
156 
157         if (!isTerminal(s1.top()))   // 栈顶为非终结符，则要跳过它（即压入临时栈s2）
158         {
159             s2.push(s1.top());
160             s1.pop();
161         }
162         int x=tchar2idx[s1.top()],y=tchar2idx[t1];
163         if (table[x][y]==-1 || table[x][y]==0)   // < 或 =，进栈，++i
164         {
165             if (!s2.empty())
166             {
167                 s1.push(s2.top());
168                 s2.pop();
169             }
170             s1.push(t1);
171             ++i;
172         }
173         else if (table[x][y]==1)   // >，归约
174         {
175             int last=x,cur=y;
176             while (table[last][cur]!=-1)   // 直到找到<
177             {
178                 if (table[last][cur]==5) return ERROR(0);   // 找到了ERROR
179                 s2.push(s1.top());
180                 s1.pop();
181                 if (!isTerminal(s1.top()))   // 栈顶为非终结符，则要跳过它（即压入临时栈s2）
182                 {
183                     s2.push(s1.top());
184                     s1.pop();
185                 }
186                 cur=last,last=tchar2idx[s1.top()];
187             }
188             // 对s2中的符号归约
189             string str="";
190             while (!s2.empty())
191             {
192                 str+=s2.top();
193                 s2.pop();
194             }
195             if (str.size()==3 && (str[1]=='+' || str[1]=='-'))
196             {
197                 s1.push('E');
198             }
199             else if (str.size()==3 && (str[1]=='*' || str[1]=='/'))
200             {
201                 s1.push('T');
202             }
203             else if ((str.size()==3 && str[0]=='(') || (str.size()==1 && (str[0]=='b' || str[0]=='z')))
204             {
205                 s1.push('F');
206             }
207             else
208             {
209                 return ERROR(1);
210             }
211         }
212         else   // ERROR
213         {
214             return ERROR(5);
215         }
216     }
217     if (s1.size()==3 && s2.empty())
218     {
219         return true;
220     }
221     else
222     {
223         return ERROR(2);
224     }
225 }
226 
227 vector<char> getFirstVT(char head)   // 求非终结符head的FIRSTVT
228 {
229     if (FirstVT[ntchar2idx[head]].size())
230     {
231         return FirstVT[ntchar2idx[head]];   // 已经求过了，直接返回
232     }
233     set<char> vt;
234     for (int i=0;i<grammer.size();++i)
235     {
236         if (grammer[i][0]==head)
237         {
238             if (grammer[i].size()==4 && grammer[i][3]>='A' && grammer[i][3]<='Z')   // 非终结符->非终结符
239             {
240                 vector<char> temp=getFirstVT(grammer[i][3]);
241                 for (int j=0;j<temp.size();++j)   // 存入
242                 {
243                     vt.insert(temp[j]);
244                 }
245             }
246             else if (grammer[i].size()==4)   // 非终结符->终结符
247             {
248                 vt.insert(grammer[i][3]);
249             }
250             else   // 非终结符->终结符与非终结符的组合
251             {
252                 for (int j=3;j<grammer[i].size();++j)
253                 {
254                     if (isTerminal(grammer[i][j]))
255                     {
256                         vt.insert(grammer[i][j]);
257                         break;
258                     }
259                 }
260             }
261         }
262     }
263     vector<char> ret;
264     for (set<char>::iterator it=vt.begin();it!=vt.end();++it)
265     {
266         ret.push_back(*it);
267     }
268     return ret;
269 }
270 
271 vector<char> getLastVT(char head)   // 求非终结符head的LASTVT
272 {
273     if (LastVT[ntchar2idx[head]].size())
274     {
275         return LastVT[ntchar2idx[head]];   // 已经求过了，直接返回
276     }
277     set<char> vt;
278     for (int i=0;i<grammer.size();++i)
279     {
280         if (grammer[i][0]==head)
281         {
282             if (grammer[i].size()==4 && grammer[i][3]>='A' && grammer[i][3]<='Z')   // 非终结符->非终结符
283             {
284                 vector<char> temp=getLastVT(grammer[i][3]);
285                 for (int j=0;j<temp.size();++j)   // 存入
286                 {
287                     vt.insert(temp[j]);
288                 }
289             }
290             else if (grammer[i].size()==4)   // 非终结符->终结符
291             {
292                 vt.insert(grammer[i][3]);
293             }
294             else   // 非终结符->终结符与非终结符的组合
295             {
296                 for (int j=grammer[i].size()-1;j>=3;--j)
297                 {
298                     if (isTerminal(grammer[i][j]))
299                     {
300                         vt.insert(grammer[i][j]);
301                         break;
302                     }
303                 }
304             }
305         }
306     }
307     vector<char> ret;
308     for (set<char>::iterator it=vt.begin();it!=vt.end();++it)
309     {
310         ret.push_back(*it);
311     }
312     return ret;
313 }
314 
315 void inputGrammer()   // 输入文法
316 {
317     string s,str="";
318     set<char> temp_terminal;   // 临时的termina数组，定义为set防止重复
319     cout<<"请输入文法句数：";
320     int T;cin>>T;
321     cout<<"请输入文法："<<endl;
322     while (T--)
323     {
324         cin>>s;
325         getNonterminal(s),getTerminal(s,temp_terminal);   // 对每句文法分析得到非终结符和终结符
326         char head=s[0];
327         for (int i=3;i<s.size();++i)   // 将'|'左右的子文法拆开
328         {
329             if (s[i]=='|')
330             {
331                 str="->"+str;
332                 str=head+str;
333 //                cout<<"str="<<str<<endl;
334                 grammer.push_back(str);
335                 str="";
336                 continue;
337             }
338             str+=s[i];
339         }
340         str="->"+str;
341         str=head+str;
342 //        cout<<"str="<<str<<endl;
343         grammer.push_back(str);
344         str="";
345     }
346     getTerminal("over",temp_terminal);
347 
348     char2idx();
349 
350     int id;
351     vector<char> v;
352     for (int i=0;i<nonterminal.size();++i)   // 逐个非终结符求FIRSTVT集和LASTVT集
353     {
354         cout<<nonterminal[i]<<endl;
355         id=ntchar2idx[nonterminal[i]];
356         v=getFirstVT(nonterminal[i]);
357         for (int j=0;j<v.size();++j)
358         {
359             FirstVT[id].push_back(v[j]);
360         }
361         v=getLastVT(nonterminal[i]);
362         for (int j=0;j<v.size();++j)
363         {
364             LastVT[id].push_back(v[j]);
365         }
366     }
367     createTable();
368     return;
369 }
370 
371 int main()
372 {
373     inputGrammer();
374 
375     cout<<"请输入词法分析的结果："<<endl;
376     string str;
377     vector<string> vec;
378     while (cin>>str)
379     {
380         int pos=str.find(',');
381         vec.clear();
382         vec.push_back(str.substr(1,pos-1));
383         vec.push_back(str.substr(pos+1,str.size()-pos-2));
384         input.push_back(vec);
385     }
386     vec.clear();
387     vec.push_back("#");vec.push_back("#");
388     input.push_back(vec);
389 
390     if (opPriorityAnalyse())
391     {
392         cout<<"Yes,it is correct."<<endl;
393     }
394     else
395     {
396         cout<<"No,it is wrong."<<endl;
397     }
398 
399     return 0;
400 }