【C++】编译原理+预测分析方式构造语法分析器

(代码在最后面)

一、实验目的

熟悉语法分析阶段的要求，掌握LL(1)语法分析的原理，利用预测分析方式构造语法分析器。

二、实验设备

硬件：PC 机一台

软件：Windows系统，高级语言集成开发环境

三、实验内容

用LL(1)预测分析法构造语法分析器。

四、实验要求及步骤

文法G(E):

E->TE’

E’->+TE’|$

T->FT’

T’->*FT’|$

G. >(E)|i

项目结构：

首先定义文法类：

exp4.h

编写文法类的方法

wf.cpp

然后求First集与Follow集：

first_and_follow.cpp

定义全局变量：

所求结果：

证明上述文法是LL（1）文法；

is_ll1.cpp

判断是否左递归：

构造预测分析表；

analysis_table.cpp

结果如下：

利用预测分析表实现以上文法的语法分析器；

Grammar_analyzer.cpp

结果如下：

测试

自设10个输入语句（每个语句多加一个#作为结束标记），展示这10个语句经该语法分析器分析后的结果，如果正确输出"Right"，错误输出"ERROR"并输出判错时指针所指符号。

i*(i+i)#

i#

ii#

i+(i*i)#

i+i#

i-i#

–i#

i*(i*i*i)#

i+i+i++#

++i#

分析

从代码量、时间复杂度、空间复杂度三方面，分析对比实验三与实验四两种语法分析器。

（可能有误，不确定正误）

• 实验3：
  • 代码量：
    • 215行

      包含三个文件：

      exp3.h

      exp3.cpp

      exp3_wenfa.cpp

    • 时间复杂度
      • 梯度下降语法分析器的时间复杂度为O(n^3)，其中n为输入句子的长度。

        由于在梯度下降算法中，需要对每个非终结符计算对它的梯度，实际上对于每个非终结符需要计算的梯度次数是O(n)，而对于一个语法规则的加权和，需要计算的梯度次数是O(n^2)。

      • 空间复杂度
        • 梯度下降文法分析器的空间复杂度为O(n+m)，其中n表示输入句子的长度，m表示分析栈大小。

          字符栈最大值为n，然后逐步将字符抛出减少。

          分析栈初始值为2，（即“E”与“#”），随后增加与减少。

        • 实验4：
          • 代码量：
            • 715行

              包含8个文件：

              exp4.h

              analysis_table.cpp

              first_and_follow.cpp

              is_ll1.cpp

              Grammar_analyzer.cpp

              main.cpp

              utils.cpp

              wf.cpp

            • 时间复杂度
              • 实现了预测分析表的语法分析器时间复杂度为O(n^2)，其中n为输入句子的长度。

                对于句子中的每个字符，在预测分析表中查询该单元格 ，判断是否能到达。如果不能到达，则直接结束，输出Error。如果能到达，则根据单元格的语句查找下一步骤，直到该字母消除。

                所以是O(n^2)。

              • 空间复杂度
                • 实现了预测分析表的语法分析器空间复杂度为O(n^m)+O(n)+O(m) = O(n^m)，其中n为输入句子的长度，m为文法中的非终结符个数。

                  用n*m储存预测分析表。

                  用n的空间作为字符栈的储存空间。

                  用m作为分析栈的储存空间。

                  附录：代码

                  exp4.h

                  #ifndef WF_H
                  #define WF_H
                  #include
                  using namespace std;
                  //wf.cpp
                  class WF
                  {
                  public:
                      string left;
                      set right;
                      vectorrights;
                      maptables;
                      WF(char s[]);
                      void print();
                      void insert(char s[]);
                      void get_rights();
                  };
                  //is_ll1
                  void is_ll1();
                  //first_and_follow
                  void make_first();
                  void make_follow();
                  void print_first();
                  void print_follow();
                  //analysis_table
                  void make_table();
                  void print_analyzer();
                  bool check_first(const string& text, char ch);
                  bool check_follow(const string& text, char ch);
                  //utils
                  stack Stringsplit(string str, char split);
                  void init();
                  const int MAX = 507;
                  extern map first;
                  extern map follow;
                  extern map VN_dic;
                  extern vector VN_set;
                  extern  bool used[MAX];
                  extern vector predict_table;
                  #endif // WF_H
                  

                  analysis_table.cpp

                  #include "exp4.h"
                  setletters;
                  string line = "\n";
                  void make_letters()
                  {
                  	for (auto wf : VN_set)
                  	{
                  		for (auto ch : wf.tables)
                  		{
                  			letters.insert(ch.first);
                  		}
                  	}
                  	letters.erase('$');
                  	for (int i = 0; i 
                  		line += "--";
                  	}
                  	line += "\n";
                  }
                  void make_table()
                  {
                  	make_letters();
                  	cout 
                  		cout 
                  		cout 
                  			if (i.tables.count(j) == 0)
                  			{
                  				cout 
                  				cout 
                  	if (used[x]) return;
                  	used[x] = 1;
                  	string left = VN_set[x].left;
                  	for (auto xx : VN_set[x].rights)
                  	{
                  		if (xx == "$")
                  		{
                  			first[left].insert('$');
                  			VN_set[x].tables['#'] = left + "-" + '$';
                  			continue;
                  		}
                  		for (int i = 0; i