实验三 语法分析

实验目的

• 给出 PL/0 文法规范，要求编写 PL/0 语言的语法分析程序。
• 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析 程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用 的语法分析方法。
• 选择一种语法分析方法（递归子程序法、LL(1)分析法、算符优先分 析法、SLR(1)分析法）；选择常见程序语言都具备的语法结构，如赋 值语句，特别是表达式，作为分析对象。

主要思想：

我们使用LL(1)分析法进行语法分析。上一次实验我们已经获得了词法分析器，其结果是本次实验的输入，因此我们直接在上一次实验的基础上做改造。因为我们使用LL（1）进行语法分析，因此在本次实验中，我们首先计算出First集、Follow集、select集，然后根据select集画出预测分析表。

如下图所示，首先我们写出题目要求的最基本的文法：

s->add0
add0->add0 opt1 mul0|mul0
mul0->mul0 opt2 exp|exp
opt1->+|-
opt2->*|/
exp->(add0)|a

可以看出上述文法表示了一个四则运算的算数表达式。但是上述文法中存在诸如add0->add0的左递归，我们应当消除左递归。消除后文法如下：

s->add0
add0-> mul0 add1
add1->opt1 mul0 add1|空
mul0->exp mul1
mul1->opt2 exp mul1|空
opt1->+|-
opt2->*|/
exp->(add0)|a

根据该文法的表达式，我们可以计算三个集合，并且做出如下的预测分析表：

在上表中，各行分别代表状态为行索引的状态时，输入为各符号时下一个状态是什么。如第一行就代表了当前状态为初始态S时，当输入为符号alpha(也就是包括0-9与变量标识符)时，状态会变为add0；当遇到 ( 时，状态会变为add0。其余以此类推。

由此，我们只需要通过程序实现该表格即可。

主要代码

• 状态转移函数：重要的功能代码就是实现该表的状态转换，这一点用switch-case即可实现。由于该函数代码过长，截断其中三个case输出：

int stateChange(Symbol sym) { //返回状态有三种：-1代表匹配失败，0代表匹配成功且是非终结符，1代表匹配成功且是终结符
          switch (parsingStack.peek()) {
              case START:
                  switch (sym) {
                      case ALPHA:
                      case LPARN:
                          parsingStack.pop();
                          parsingStack.push(GRAMMAR.ADD0);
                          return 0;
                      default:
                          return -1;
                  }
              case ADD0:
                  switch (sym){
                      case ALPHA:
                      case LPARN:
                          parsingStack.pop();
                          parsingStack.push(GRAMMAR.ADD1);
                          parsingStack.push(GRAMMAR.MUL0);
                          return 0;
                      default:
                          return -1;
                  }
              case ADD1:
                  switch (sym) {
                      case RPARN:
                      case END:
                          parsingStack.pop();
                          parsingStack.push(GRAMMAR.BLANK);
                          return 0;
                      case OPT1:
                          parsingStack.pop();
                          parsingStack.push(GRAMMAR.ADD1);
                          parsingStack.push(GRAMMAR.MUL0);
                          parsingStack.push(GRAMMAR.OPT1);
                          return 0;
                      default:
                          return -1;
                  }

• 匹配函数。每次状态转移后，都应该检测是否转移到“终态”，即应当匹配缓冲串和状态是否一致，一致就都弹出，重新回到初态。

  boolean check(List<Symbol> input){
          parsingStack.push(GRAMMAR.START);
          int index = 0;
          while(index<input.size()&&!parsingStack.empty()){
              if (!parsingStack.empty()) {
                  //System.out.println("现在匹配：" + index + " INPUT为：" + input.get(index).name());
                  System.out.println(parsingStack);
              }
              int flag = stateChange(input.get(index));
              if(flag==-1) {
                  System.out.println("没有可用的语法，匹配失败");
                  return false;
              }
              else if(flag==0){//状态已经转变，可以继续下一次循环
                  continue;
              }
              else //flag == 1，比较栈顶和输入符号
              {
                  if(input.get(index).name().equals(parsingStack.peek().name())) {//说明栈顶和INPUT字符相等，可以消去
                      parsingStack.pop();
                      index++;
                  }
                  else {
                      System.out.println("栈顶和INPUT字符不相等，匹配失败");
                      return false;
                  }
              }
  
          }
          if(parsingStack.empty()&&index==input.size()-1&&input.get(index).name()=="END")
          {
              System.out.println("匹配成功");
              return true;
          }
          else
          {
              System.out.println("未同时为空，匹配失败");
              return false;}
  
      }
  

运行结果

测试样例：

3 + 5
a + 1 + 5+ num
12+23*3
((((1+1)*a)*4)/4)+4+2
a +
a
+
(3+3)*(4 +
+ 4 +s

运行结果：

匹配成功
accept
匹配成功
accept
匹配成功
accept
匹配成功
accept
没有可用的语法，匹配失败
deny
匹配成功
accept
没有可用的语法，匹配失败
deny
没有可用的语法，匹配失败
deny
没有可用的语法，匹配失败
deny

可以看到运行结果正确。