Liny_@NotePad

沉迷ACG中

预测分析法

YOYO posted @ 2009年5月14日 21:08 in 【C/C++】 with tags 编译原理 语法分析 , 2500 阅读

一、功能描述:
构造文法的语法分析程序,要求采用预测分析法对输入的字符串进行语法分析。

二、程序结构描述:
 全局变量:

map<char,int> key;  —— 终结符、非终结符所代表的值
string sheet[10][10];  —— 预测分析表
string s;     —— 输入的字符串
int i;      —— 当前读到的位置

程序分成如下几个函数:

 void init() —— 初始化函数:构造预测分析表。

 void printSuccess(); —— 打印正确信息
 void printFail() ;  —— 打印失败信息

 bool getNext();  —— 获得串中的下一个字符,如果已结束则返回false

 bool check() —— 分析过程,不匹配则返回false

 main —— 主函数
处理输入串的部分,若输入为“.”则退出循环,否则对指定文件进行语法分析。

程序总体执行流程详见代码。

三、实验总结:
完成总使用四课时:
其中纸上时间一课时,编程两课时,调试一课时。

 收获:
了解到一些语法分析的知识。

四、程式源码:

  1. #include<iostream>
  2. #include<string>
  3. #include<stack>
  4. #include<map>
  5. using namespace std;
  6.  
  7. map<char,int> key;
  8. string sheet[10][10];
  9. string s;
  10. int i;
  11.  
  12. void init(){
  13.         //      设定终结符Key值
  14.         key['i'] = 0;
  15.         key['+'] = 1;
  16.         key['*'] = 2;
  17.         key['('] = 3;
  18.         key[')'] = 4;
  19.         key['#'] = 5;
  20.  
  21.         //      设定非终结符Key值
  22.         key['E'] = 10;
  23.         key['S'] = 11;
  24.         key['T'] = 12;
  25.         key['N'] = 13;
  26.         key['F'] = 14;
  27.  
  28.         //      初始化预测分析表
  29.         for(int i=0; i<5; i++){
  30.                 for(int j=0; j<6; j++){
  31.                         sheet[i][j] = "";
  32.                 }
  33.         }
  34.  
  35.         //      构造预测分析表
  36.         sheet[0][0] = "TS";          //   E->TS
  37.         sheet[0][3] = "TS";          //   E->TS
  38.         sheet[1][1] = "+TS";    //  S->+TS
  39.         sheet[1][4] = "0";            //    S->ε
  40.         sheet[1][5] = "0";            //    S->ε
  41.         sheet[2][0] = "FN";          //   T->FN
  42.         sheet[2][3] = "FN";          //   T->FN
  43.         sheet[3][1] = "0";            //    N->ε
  44.         sheet[3][2] = "*FN";    //  N->*FN
  45.         sheet[3][4] = "0";            //    N->ε
  46.         sheet[3][5] = "0";            //    N->ε
  47.         sheet[4][0] = "i";            //    F->i
  48.         sheet[4][3] = "(E)";    //  F->(E)
  49. }
  50.  
  51. void printSuccess(){
  52.         cout<<"Success!"<<endl;
  53. }
  54.  
  55. void printFail(){
  56.         cout<<"Fail!"<<endl;
  57. }
  58.  
  59. bool getNext(){
  60.         if(i==s.size()-1)return false;
  61.         i++;
  62.         return true;
  63. }
  64.  
  65. bool check(){
  66.         stack<char> st;
  67.         st.push('#');      // 初始时压入'#'
  68.         st.push('E');      // 起始符压栈
  69.         while(getNext()){
  70.                 char in = s[i];
  71.                 while(true){
  72.                         char top = st.top();
  73.                         string v;
  74.                         if(in==top){    //  栈顶与输入字符相等则弹出
  75.                                 bool flag = getNext();
  76.                                 in = s[i];
  77.                                 st.pop();
  78.                                 if(flag)continue;       //     如果未读完 则继续分析
  79.                                 else break;               //   否则退出
  80.                         }
  81.                         if((v = sheet[key[top]-10][key[in]])!=""){      //    预测分析表中有值
  82.                                 st.pop();
  83.                                 if(v=="0")continue;
  84.                                 for(int j=v.size()-1; j>=0; j--){              //     压栈
  85.                                         st.push(v[j]);
  86.                                 }
  87.                         }else{
  88.                                 st.push(in);
  89.                                 break;
  90.                         }
  91.                 }
  92.         }
  93.         return st.empty();      //    如果栈不为空 说明表达式不符合文法
  94. }
  95.  
  96. int main(){
  97.         init();
  98.  
  99.         cout<<"input string(end of '#', if u want to exit, just press '.'):"<<endl;
  100.  
  101.         while(cin>>s){
  102.                 if(s==".")break;
  103.                 i = -1;
  104.  
  105.                 if(check()){
  106.                         printSuccess();
  107.                 }else{
  108.                         printFail();
  109.                 }
  110.  
  111.                 cout<<endl;
  112.  
  113.         }
  114.         return 0;
  115. }

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter