编译原理实验（二）——LL（1）文法语法分析

小咪咪 2023-05-30 09:15 100阅读 0赞

编译原理实验（二）——LL（1）文法语法分析

      • 实验要求
      • 参考程序
        • 程序输入说明
        • 实验结果
          • 截图

实验要求

根据LL(1)分析法编写一个语法分析程序 直接输入根据已知文法构造的分析表M;对于输入的文法和符号串，所编制的语法分析程序应能正确判断此串是否为文法的句子，并要求输出分析过程。

参考程序

  1. #include <iostream>
  2. #include <string>
  3. #include <map>
  4. #include <stack>
  5. #include <vector>
  6. #include <iomanip>
  7. using namespace std;
  9. const int maxSize = 10; //定义分析表的最大大小
  10. const string errorstr = "你输入的语言该文法无法识别";
  11. const int outWidth = 30; //设置输出字符串所占宽度
  13. string LL1ForecastAnalysisTable[maxSize][maxSize]; //分析表的具体的内容
  14. int terminatorNum;                                 //输入终结符的数量
  15. int nonterminatorNum;                              //输入非终结符的数量
  16. map<char, int> terminatorSet;                      //输入终结符的集合，用map 映射表示在分析表的第几列
  17. map<char, int> nonterminatorSet;                   //输入非终结符的集合，用map 映射表示在分析表的第几行
  18. vector<char> analysisStack;                        //为了更好的输出栈中的内容，用vector数组模拟栈行为
  20. void analysisProcess(string); //对输入的语言用LL1预测分析表进行分析
  21. char S;
  23. int main()
  24. { 
  25.     cout << "请输入终结符的个数：";
  26.     cin >> terminatorNum;
  27.     char str;
  28.     cout << "请依次按照分析表输入终结符(包含结束符#)：" << endl;
  29.     for (int i = 1; i <= terminatorNum; ++i)
  30.     { 
  31.         cin >> str;
  32.         terminatorSet[str] = i;
  33.     }
  34.     cout << "请输入非终结符的个数：";
  35.     cin >> nonterminatorNum;
  36.     cout << "请依次按照分析表输入终结符：" << endl;
  37.     for (int i = 1; i <= nonterminatorNum; ++i)
  38.     { 
  39.         cin >> str;
  40.         nonterminatorSet[str] = i;
  41.     }
  42.     cout << "请输入开始符合：";
  43.     cin >> S;
  44.     cout << "请依次输入分析表的内容，对于出错错误的请输入单个英文字符_:\n";
  45.     for (int i = 1; i <= nonterminatorNum; ++i)
  46.     { 
  47.         for (int j = 1; j <= terminatorNum; ++j)
  48.         { 
  49.             cin >> LL1ForecastAnalysisTable[i][j];
  50.         }
  51.     }
  52.     cout << "请输入要分析语言: ";
  53.     string L;
  54.     cin >> L;
  55.     analysisProcess(L);
  56. }
  58. void analysisProcess(string str)
  59. { 
  60.     cout << " 步骤 分析栈 剩余输入串 所用产生式" << endl;
  61.     int i = 0, ip = 0;     //i代表进行到第几步 a是分析到输入语言字符串第几个
  62.     char X, a = str[ip];   //分析栈栈顶符号
  63.     str += "#";            //在语言末尾加入输入结束符
  64.     analysisStack.clear(); //使分析栈为空
  65.     analysisStack.push_back('#');
  66.     analysisStack.push_back(S); //初始化将’#’压入堆栈中，将开始符号S压入栈中
  67.     string outStack, outStr;
  68.     while (++i)
  69.     { 
  70.         X = analysisStack.back();
  71.         analysisStack.pop_back();
  72.         if (X == '#')
  73.         { 
  74.             if (X == a)
  75.             { 
  76.                 cout << setw(10) << setiosflags(ios::left) << i << setw(outWidth);
  77.                 cout << setiosflags(ios::left) << "#" << setw(outWidth) << setiosflags(ios::left) << "#"
  78.                      << "接受\n";
  79.             }
  80.             else
  81.             { 
  82.                 cout << errorstr << endl;
  83.             }
  84.             return;
  85.         }
  86.         else if (terminatorSet[X])
  87.         { 
  88.             if (X == a)
  89.             { 
  90.                 outStack = "";
  91.                 for (int i = 0; i < analysisStack.size(); ++i)
  92.                     outStack += analysisStack[i];
  93.                 outStack += X;
  94.                 cout << setw(10) << setiosflags(ios::left) << i << setw(outWidth) << setiosflags(ios::left) << outStack;
  95.                 outStr = "";
  96.                 for (int t = ip; t < str.size(); ++t)
  97.                     outStr += str[t];
  98.                 cout << setw(outWidth) << setiosflags(ios::left) << outStr << a << "匹配\n";
  99.                 a = str[++ip];
  100.             }
  101.             else
  102.             { 
  103.                 cout << errorstr << endl;
  104.                 return;
  105.             }
  106.         }
  107.         else
  108.         { 
  109.             int row = nonterminatorSet[X], col = terminatorSet[a];
  110.             string f = LL1ForecastAnalysisTable[row][col]; //获取文法产生式
  111.             if (f == "_")
  112.             { 
  113.                 cout << errorstr << endl;
  114.                 return;
  115.             }
  116.             outStack = "";
  117.             for (int i = 0; i < analysisStack.size(); ++i)
  118.                 outStack += analysisStack[i];
  119.             outStack += X;
  120.             cout << setw(10) << setiosflags(ios::left) << i << setw(outWidth) << setiosflags(ios::left) << outStack;
  121.             outStr = "";
  122.             for (int t = ip; t < str.size(); ++t)
  123.                 outStr += str[t];
  124.             cout << setw(outWidth) << setiosflags(ios::left) << outStr << X << "->" << f << endl;
  125.             if (f != "@")
  126.                 for (int j = f.size() - 1; j >= 0; --j)
  127.                     analysisStack.push_back(f[j]);
  128.         }
  129.     }
  130. }

程序输入说明

输入的终结符与终结符都为单个字符
空( ε \varepsilon ε)用@表示

实验结果

对于文法
E->TA
A->+TA|@
T->FB
B->*FB|@
F->(E)|i
分析表为
在这里插入图片描述
输入数据为

  1. 6 
  2. i + * (  ) #
  3. 5
  4. E A T B F
  5. E
  7. TA _ _ TA _ _ 
  8. _ +TA _ _ @ @
  9. FB _ _ FB _ _
  10. _ @ *FB _ @ @
  11. i _ _ (E) _ _
  13. i+i*i
截图

在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，100人围观）

还没有评论，来说两句吧...

相关阅读