Liny_@NotePad

沉迷ACG中

递归下降语法分析

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

  一、功能描述：
构造文法的语法分析程序，要求采用递归下降语法分析方法对输入的字符串进行语法分析，进一步掌握递归下降的语法分析方法。
 
二、初始步骤：
 先将文法：
E-->E+T|T
T-->T*F|F
F-->(E)|i
 转换成LL(1)文法：
E-->TS
S-->+TS|ε
T-->FN
N-->*FN|ε
F-->(E)|i
得到
First(S) = { + } Follow(S) = { }, # }
First(N) = { * } Follow(N) = { +, }, # }
Fisrt(F) = { ( }
 
三、程序结构描述：
 全局变量：
set<char> firstS, firstN, firstF;  ——非终结符S、N、F的First集合
set<char> followS, followN;  ——非终结符S、N的Follow集合
string s;       ——输入的字符串
int i;        ——当前读到的位置
 
程序分成如下几个函数：
 void init() ——初始化函数：初始化各个非终结符的First集合和Follow集合。
 void printSuccess(); ——打印正确信息
 void printError() ;  ——打印错误信息
 bool getNext();  ——获得串中的下一个字符，如果已结束则返回false
 bool checkE(); ——匹配E文法，不匹配则返回false
 bool checkS(); ——匹配S文法，不匹配则返回false
 bool checkT(); ——匹配T文法，不匹配则返回false
 bool checkN(); ——匹配N文法，不匹配则返回false
 bool checkF(); ——匹配F文法，不匹配则返回false
 main ——主函数
处理输入串的部分，若输入为“.”则退出循环，否则对指定文件进行语法分析。
 
程序总体执行流程详见代码。
 
四、实验总结：
完成总使用四课时：
其中纸上时间一课时，编程两课时，调试一课时。
 
问题：
程序只适合固定的语法：代码重用性差。
 
 收获：
 了解到一些语法分析的知识。
  
五、程式源码：
  1. #include<iostream>
  2. #include<string>
  3. #include<set>
  4. using namespace std;
  5.  
  6. set<char> firstS, firstN, firstF;
  7. set<char> followS, followN;
  8.  
  9. bool checkE();
  10. bool checkS();
  11. bool checkT();
  12. bool checkN();
  13. bool checkF();
  14. void printError();
  15. void printSuccess();
  16.  
  17. string s;
  18. int i;
  19.  
  20. bool getNext(){
  21.         if(++i==s.size()){
  22.                 //cout<<"Finish!"<<endl;
  23.                 return false;
  24.         }
  25.         return true;
  26. }
  27.  
  28. void init(){
  29.         firstS.insert('+');
  30.         firstN.insert('*');
  31.         firstF.insert('(');
  32.  
  33.         followS.insert(')');
  34.         followS.insert('#');
  35.  
  36.         followN.insert('+');
  37.         followN.insert(')');
  38.         followN.insert('#');
  39. }
  40.  
  41. bool checkE(){
  42.         return(checkT()&&checkS());
  43. }
  44.  
  45. bool checkS(){
  46.         if(firstS.find(s[i])!=firstS.end()){        //  如果token属于FIRST(S):+
  47.                 return(getNext()&&checkT()&&checkS());
  48.         }else{
  49.                 if(followS.find(s[i])==followS.end()){  //        如果token不属于FOLLOW(S)则报错
  50.                         printError();
  51.                         return false;
  52.                 }
  53.         }
  54.         return true;
  55. }
  56.  
  57. bool checkT(){
  58.         return(checkF()&&checkN());
  59. }
  60.  
  61. bool checkN(){
  62.         if(firstN.find(s[i])!=firstN.end()){        //  如果token属于FIRST(N):*
  63.                 return(getNext()&&checkF()&&checkN());
  64.         }else{
  65.                 if(followN.find(s[i])==followN.end()){  //        如果token不属于FOLLOW(N)则报错
  66.                         printError();
  67.                         return false;
  68.                 }
  69.         }
  70.         return true;
  71. }
  72.  
  73. bool checkF(){
  74.         if(firstF.find(s[i])!=firstF.end()){        // 如果token属于FIRST(F):(
  75.                 if(!getNext())return false;
  76.                 if(!checkE())return false;
  77.                 if(s[i]==')'){
  78.                         return(getNext());
  79.                 }else{
  80.                         printError();
  81.                         return false;
  82.                 }
  83.         }else{
  84.                 if(s[i]=='i'){    //        如果token=='i'
  85.                         return(getNext());
  86.                 }else{
  87.                         printError();
  88.                         return false;
  89.                 }
  90.         }
  91. }
  92.  
  93. void printSuccess(){
  94.         cout<<"Success!"<<endl;
  95. }
  96.  
  97. void printError(){
  98.         cout<<"Error in Location["<<(i+1)<<"]: "<<s[i]<<endl;
  99. }
  100.  
  101. int main(){
  102.         char token;
  103.         init();
  104.        
  105.         cout<<"input string(end of '#', if u want to exit, just press '.'):"<<endl;
  106.  
  107.         while(cin>>s){
  108.                 if(s==".")break;
  109.                 i = -1;
  110.  
  111.                 if(getNext()&&checkE()){       
  112.                         printSuccess();
  113.                 }
  114.  
  115.                 cout<<endl;
  116.         }
  117.  
  118.         return 0;
  119. }

 

Small_feed 评论 (0)

登录 *


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