发表更新编译原理21 分钟读完 (大约3207个字)0次访问

编译原理——LL(1)分析

LL(1)分析法是一种自顶向下的分析方法，从左向右扫描输入串，采用最左推导，每次推导向前看一个符号，确定应该选择的规则。

程序功能

  1. 设计目标

    给定文法以及输入串，自动构造分析表，输出分析过程。

  2. 开发环境

    我选择了Java来实现这次的LL(1)分析器，使用IntelliJ IDEA开发。

  3. 程序的输入输出

    该项目的输入分为两部分：

    • 文法输入

      文法通过文件读取的方式读入，文件结构：第一行为使用逗号分隔的非终结符，第二行为使用逗号分隔的终结符，其后是各个产生式，空串使用~表示。

    • 输入串

      输入串通过键盘输入，以#结尾。

    该项目输出包括当前文法、预测分析表、对当前输入串的分析过程。

主要数据结构

  1. Config.java

    Config类中定义了几个主要数据内容：

    类型名称内容
    ArrayList<production>productions产生式动态数组
    ArrayList<String>VT非终结符集
    ArrayList<String>VN终结符集
    Stringnullstr空串~

  2. Production.java

    Production类用来存储产生式，内部主要有两个变量：

    1
    2
    String head;
    String body[];

    顾名思义，head用于存储产生式左部，body数组用来存储当前head对应的所有右部。

  3. Set.java

    Set类用来存放FIRST集和FOLLOW集，同样用head存储非终结符，用动态数组body存放First集或者Follow集的内容。

  4. AnalysisTable.java

    AnalysisTable类用于自动生成分析表。分析表是一个String类型的二维数组，该数组中的[0, 0]位置为空，[0, 1][0, 终结符个数 + 1]存放终结符，[1, 0][非终结符个数 + 1]存放非终结符，其他位置存放产生式或者置空。

  5. AnalyzeStack.java

    AnalyzeStack类用于分析输入串。

    类型名称内容
    StringinputStr用户输入串
    Stack<String>stProduction产生式分析栈
    Stack<String>stInputStr输入串分析栈
    booleanstop是否停止分析
    StringcurrentPro当前使用的产生式

LL(1)分析中需要解决的几个问题

  1. 文法需要满足的条件

    进行LL(1)分析的文法应该满足无二义性、无左递归、无左公因子。

  2. 如何构造分析表

    构造分析表需要用到当前产生式的FIRST集和FOLLOW集，下面先介绍一下FIRST集和FOLLOW集的构造方法以及具体实现

    • FIRST集和FOLLOW集

      FIRST集合概念：对α∈(VT⋃VN)∗,有FIRST(α)＝{a|α⟹∗a⋅⋅⋅,a∈VT}

      特别地，若α⟹∗ε,则ε∈FIRST(α)。

      FOLLOW集合概念：对A∈VN，有FOLLOW(A)={a|S⟹∗⋅⋅⋅Aa⋅⋅⋅，a∈VT} 若S⟹∗⋅⋅⋅A，则规定#∈FOLLOW(A) 这里用#作为输入串的结束符。

    • 构造FIRST集的算法

      对G[S]，x∈Vn ∪ Vt，计算FIRST(x)

      ① 若x∈Vt

      则FIRST(x)={x}

      ②若x∈Vn，有x→aα(a∈Vt)或/和x→ε则a或/和ε∈FIRST(x)

      ③对x→Y1Y2 …….Yk (且Y1 ∈Vn)，反复使用以下直到每一个FIRST(x)不再增大为止：

      1. 若Y1∈Vn
        则把FIRST(Y1)-{ε}元素加入FIRST(x)中
      2. 若Y1、Y2、……Yi-1∈Vn (2≤i≤k)
        且ε ∈FIRST(Yj) (1≤j≤i-1)
        则把FIRST(Y i )-{ε}元素加入FIRST(x)中
      3. 若Y1、Y2、……Yk∈Vn
        且ε ∈FIRST(Yj)
        则把ε元素加入FIRST(x)中

      我们结合代码以及注释看一下First集的构造过程：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      class FirstSet {

          static Set getFirst(String str) {
              Set set = new Set(str);
      //        如果X∈VT，则FIRST(X)={X}
              if(Config.VT.contains(str)) {
                  set.addSet(str);
                  return set;
              }
      //        X∈VN
              for(Production production: Config.productions) {
      //            当前str与产生式匹配
                  if(production.head.equals(str)) {
                      for (int i = 0; i < production.body.length; i++) {
      //                    获取当前str对应第一个产生式的第一个字符
                          String firstCh = String.valueOf(production.body[i].charAt(0));
      //                    当前字符为终结字符
                          if(Config.VT.contains(firstCh)) {
                              set.addSet(firstCh);
                          }
      //                    当前字符为空串（~）且该产生式长度为1
                          else if (firstCh.equals(Config.nullstr) && 
                                   production.body[i].length() == 1) {
                              set.addSet(production.body[i]);
                          }
      //                    求该非终结符的first集并加入当前str的first集中
                          else {                        	         
                              set.addSet(getFirstFromN(production.body[i]));
                          }
                      }
                  }
              }
              return set;
          }

          private static Set getFirstFromN(String str) {
              boolean[] isEnd = new boolean[str.length()];
              Set set = new Set();
              for (int i = 0; i < str.length(); i++) {
                  String firstCh = String.valueOf(str.charAt(i));
      //          如果是终结符，则直接加入first集
                  if(Config.VT.contains(firstCh)) {
                      set.addSet(firstCh);
                      return set;
                  }

      //          不是终结符，继续获取该非终结符的first集
                  Set childSet = getFirst(firstCh);
      /*              若Y1、Y2、……Yi-1∈Vn(2≤i≤k)
                      且ε∈FIRST(Y j )
                      (1≤j≤i-1)
                      则把FIRST(Yi)-{ε}元素加入FIRST(x)中
       */
                  if (childSet != null) {
      //              当前非终结符的first集不含空串，则添加到first集中
                      if(!childSet.contains(Config.nullstr)) {
                          isEnd[i] = false;
                          set.addSet(childSet);
                          return set;
                      }
      //              含空串，则将该first集中的空串移除
                      else {
                          isEnd[i] = true;
                          childSet.remove(Config.nullstr);
                          set.addSet(childSet);
                      }
                  }
              }
      /*
                      若Y1、Y2、……Yk∈Vn
                      且ε∈FIRST(Yj)
                      则把ε元素加入FIRST(x)中
       */
              for (boolean anIsEnd : isEnd) {
                  if (anIsEnd) {
                      set.addSet(Config.nullstr);
                  }
              }
              return set;
          }
      }

    • 构造FOLLOW集的算法

      1. 令#∈FOLLOW(S) S为文法开始符号

      2. 对A→αBβ，且β≠ε
        则将 FIRST(β)-{ε}加入FOLLOW(B)中

      3. 反复，直至每一个FOLLOW(A)不再增大

        对A→ αB或A→ αBβ(且ε∈FIRST(β))

        则FOLLOW(A)中的全部元素加入FOLLOW(B)

      具体代码及注释如下：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      import java.util.ArrayList;

      class FollowSet {

          static Set getFollow(String str) {
              ArrayList<String> follow = new ArrayList<>();
              Set set = new Set(str);

      //        str是终结符
              if (Config.VT.contains(str)) {
                  return set;
              } else {
                  follow.add(str);
              }

      //        将#加入FOLLOW(文法开始符号)
              if (Config.productions.get(0).head.equals(str)) {
                  set.addSet(Config.endSyntax);
              }

              for (Production production : Config.productions) {
                  if(production.contains(str)) {
      //                获取该产生式中包含当前str的产生式
                      ArrayList<String> list = production.getBody(str);
                      for (String contain : list) {
                          int index = contain.indexOf(str);
      //                    对A->αB(且ε∈FIRST(β))
      //                    则FOLLOW(A)中的全部元素加入FOLLOW(B)
                          if (index == contain.length() - 1) {
                              if (!follow.contains(production.head)) {
                                  set.addSet(getFollow(production.head));
                              }
                          } else {
      //                        获取当前str的下一个字符
                              String nextCh = String.valueOf(contain.charAt(index + 1));
      //                        终结符，则直接加入Follow集中
                              if (Config.VT.contains(nextCh)) {
                                  set.addSet(nextCh);
                              }
      //                        非终结符
                              else {
      //                            获取该字符的First集
                                  Set subSet = FirstSet.getFirst(nextCh);
                                  if (subSet != null) {
                                      if (subSet.contains(Config.nullstr) &&
                                              !follow.contains(subSet.head)) {
                                          set.addSet(getFollow(subSet.head));
                                      }
                                      subSet.remove(Config.nullstr);
                                      set.addSet(subSet);
                                  }
                              }
                          }
                      }
                  }
              }
              return set;
          }
      }

    • 构造分析表

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      class AnalysisTable {

          String[][] table = new String[Config.VN.size() + 1][Config.VT.size() + 1];

          void generate() {

      //        将分析表初始化为空
              for (int i = 0; i < Config.VN.size() + 1; i++) {
                  for (int j = 0; j < Config.VT.size() + 1; j++) {
                      table[i][j] = "";
                  }
              }

      //        初始化分析表的第一行为终结符，第一列为非终结符
              for (int i = 1; i < Config.VT.size() + 1; i++) {
                  table[0][i] = Config.VT.get(i - 1);
              }
              for (int i = 1; i < Config.VN.size() + 1; i++) {
                  table[i][0] = Config.VN.get(i - 1);
              }

      //        对每一个产生式，分别进行分析
              for (Production production : Config.productions) {
                  for (int i = 0; i < production.body.length; i++) {
                      String head = production.head;
                      String pro = production.body[i];
                      Set tmpFirst = FirstSet.getFirst(head);
                      Set tmpFollow = FollowSet.getFollow(head);

      //                若该产生式右部第一项为终结符且该产生式不为空串，则直接将对应表格置为该产生式
                      if (Config.VT.contains(String.valueOf(production.body[i].charAt(0))) && !production.body[i].equals(Config.nullstr)) {
                          String str = String.valueOf(production.body[i].charAt(0));
                          ArrayList<Integer> tmp = getPos(head, str);
                          table[tmp.get(0)][tmp.get(1)] = pro;
                          continue;
                      }
      //                若该产生式为空串，直接将表格对应项置为该产生式
                      if (!production.body[i].equals("~")) {
                          for (String str : tmpFirst.body) {
                              ArrayList<Integer> tmp = getPos(head, str);
                              table[tmp.get(0)][tmp.get(1)] = pro;
                          }
                      }

      //                当前非终结符的First集含空串
                      if (tmpFirst.contains(Config.nullstr)) {
      //                    对于任一个b∈FOLLOW(A) b∈Vt或#，将A→ε规则填入M[A, b]
                          pro = "#";
                          for (String str : tmpFollow.body) {
                              if (str.equals("#"))
                                  str = "~";
                              ArrayList<Integer> tmp = getPos(head, str);
                              table[tmp.get(0)][tmp.get(1)] = pro;
                          }
                      }

                  }
              }
          }

      //    获取M[head, VT]的位置
          ArrayList<Integer> getPos (String head, String VT) {
              ArrayList<Integer> pos = new ArrayList<>();

              for (int i = 0; i < Config.VN.size() + 1; i++) {
                  if(table[i][0].equals(head)) {
                      pos.add(i);
                      break;
                  }
              }

              for (int i = 0; i < Config.VT.size() + 1; i++) {
                  if (table[0][i].equals(VT)) {
                      pos.add(i);
                      break;
                  }
              }

              return pos;
          }
      }

      输入串分析过程

  3. 首先，我们把输入串也放到一个栈中，方便输入串与分析栈匹配时的pop操作。分析栈栈底为#，初始化先将起始符号压入分析栈中，同时将输入串压入输入串栈中。

  4. 当分析栈栈顶不为#时，分析过程一直进行下去

  5. 若分析栈栈顶字符与输入串栈顶字符相同，则对两个栈都执行pop操作，否则用分析表中合适的产生式替换当前分析栈中非终结符。

    产生式的选择：

    根据当前分析栈栈顶的非终结符和当前输入串最左终结符确定产生式

    产生式=分析表[分析栈栈顶的非终结, 输入串最左终结符]

具体代码及注释如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
class AnalyzeStack {

    private String inputStr;
    private Stack<String> stProduction = new Stack<>();
    private Stack<String> stInputStr = new Stack<>();
    private boolean stop = false;
    private String currentPro;

//    获取输入串，初始化栈
    private void init() {
        Scanner scanner = new Scanner(System.in);
        if (scanner.hasNext()) {
            inputStr = scanner.next();
            System.out.println(inputStr);
        }

        scanner.close();
        int index = inputStr.length();
        while ( index > 0 ) {
            stInputStr.push(String.valueOf(inputStr.charAt(index - 1)));
            index--;
        }
        System.out.println("Stack\t\tInput\t\tProduction");
        stProduction.push("#");
        stProduction.push(Config.productions.get(0).head);
        outputStack();
    }

    void stack (AnalysisTable analysisTable) {
        init();
//        判断当前分析工作是否完成
        while ( !stProduction.peek().equals("#") ) {
            if (stProduction.peek().equals(stInputStr.peek())) {
                stProduction.pop();
                stInputStr.pop();
                currentPro = "Pop, Next";
            } else {
                nextProduction(analysisTable);
            }
            if (stop) {
                System.out.println("error");
                break;
            }
            outputStack();
        }

//        当分析栈栈顶与输入串栈顶均为#时，分析成功
        if (stProduction.peek().equals(stInputStr.peek()))
            System.out.println("Success!");
    }

    private void nextProduction(AnalysisTable analysisTable) {
        analysisTable.generate();
//        ch为当前输入串栈栈顶
        String ch = stInputStr.peek();
//        head为当前分析栈栈顶
        String head = stProduction.peek();
//        获取M[head, ch]在表中对应的位置
        ArrayList<Integer> pos = analysisTable.getPos(head,ch);
//        将当前分析栈栈顶的非终结符用合适产生式替换
        if (pos.size() == 2) {
            stProduction.pop();
            String production = analysisTable.table[pos.get(0)][pos.get(1)];
            currentPro = head + "->" + production;
            if (!production.equals("#")) {
                int index = production.length();
                while ( index > 0 ) {
                    stProduction.push(String.valueOf(production.charAt(index - 1)));
                    index--;
                }
            }
        } else if (FirstSet.getFirst(head).contains(Config.nullstr)) {
            stProduction.pop();
            currentPro = head + "->~";
        } else {
            stop = true;
        }
    }

    private void outputStack() {
        for (String aStProduction : stProduction) {
            System.out.print(aStProduction);
        }

        if (stProduction.size() < 4)
            System.out.print("\t");

        System.out.print("\t\t");

        for (int i = stInputStr.size(); i > 0; i-- ) {
            System.out.print(stInputStr.get(i - 1));
        }

        if (stInputStr.size() < 4)
            System.out.print("\t");

        System.out.print("\t\t" + currentPro);

        System.out.println();
    }

}

程序结构

  1. 项目结构

  2. 各文件结构以及函数

    • LL1.java

      main：入口函数

      readFromFIle：从文件中读取文法

      addVTandVN：将存放在String类型VT和VN数组中的非终结符和终结符添加到Config.java中的非终结符和终结符动态数组中

    • Production.java

      Production：构造函数，初始化产生式左部和右部

      getBody：得到当前产生式右部的动态数组

      contains：返回当前产生式右部是否包含传入参数

      outputPro：输出当前产生式

    • Set.java

      构造函数用于初始化该集合对应的非终结符并且初始化动态数组。

      addSet(String)：向集合中添加String类型未存在的元素

      addSet(Set)：向集合中添加Set类型元素，即添加新集合

      getSet：返回该集合的动态数组

      remove：删除集合中某元素

      outputSet：输出当前集合

      contains：判断当前集合中是否存在该元素

    • FirstSet.java

      getFirst：生成First集的入口函数

      getFirstFromN：当遇到非终结符时，求该非终结符的First集

    • FollowSet.java

      getFollow：生成Follow集

    • AnalysisTable.java

      generate：生成分析表

      getPos：返回当前产生式应当放置的位置

    • AnalyzeStack.java

      init：从键盘获取用户输入串，并且初始化输入串栈和分析栈

      stack：主要的分析函数

      nextProduction：调用下一个合适的产生式

      outputStack：输出当前栈内容

程序测试

  1. 测试用例

    测试文件内容为：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    E,e,T,t,F,A,M
    i,+,-,*,/,(,),~
    E->Te 
    e->ATe|~
    T->Ft
    t->MFt|~
    F->(E)|i
    A->+|-
    M->*|/

  2. 运行结果

    输入串为i*(i+i)时：

    输入串为i*(i+i时（错误情况）：

实验总结

LL(1)的分析过程并不是复杂，这个实验的主要复杂点在于自动构造分析表，构造的算法不是特别的难，但是很繁杂，因此耗费了我一些时间。通过这次的实验，我最大的体会是我写代码的能力还是需要提高，要通过多的练习提升自己将算法转化为实际代码的能力。

项目地址：https://github.com/Panda-0129/LL1

关注我

订阅更新

邮件订阅，更新早获取

分类

最新文章

归档

标签

Graphivz1
LeetCode26
Linux2
Python26
dot1
操作系统2
绘图1
进程控制1
×