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

编译原理——OPG

这个实验花了我半天的时间完成，不算是很复杂。算符优先分析属于移进归约分析法的一种，算是最易实现的移进归约分析方法。

程序功能

  1. 设计目标

    给定算符优先文法及输入串，自动构造算符优先关系表并且输出分析过程。

  2. 开发环境

    系统：macOS High Sierra

    IDE: IntelliJ IDEA

    语言：Java

  3. 输入输出

    输入分两部分：

    • 文法

      文法通过文件读取，⽂件结构：第⼀⾏为使⽤逗号分隔的⾮终结符，第⼆⾏为使⽤逗号分隔的终结符，其后是各个产⽣式。

    • 输入串

      以#结尾，通过键盘输入

    输出包括当前文法的FIRSTVT集、LASTVT集、优先关系表、分析过程。

算符优先分析

算符优先分析的核心思想就是通过定义终结符之间的优先关系，根据这些优先关系，进行句柄的选取。终结符之间定义三种优先关系：<、=和>，我们可以通过FIRSTVT集和LASTVT集来构造算符优先关系。

  1. FIRSTVT集和LASTVT集

    U∈Vn

    ①FIRSTVT(U)={b|U=^+^>b…, 或U=^+^>Vb…, b∈Vt, V∈Vn}

    则形如W->…aU…的规则 a<b b∈FIRSTVT(U)

    ②LASTVT(U)={a|U=^+^>…a, 或U=^+^>…aV, a∈Vt, V∈Vn

    则形如W→…Ub…的规则 a>b a∈LASTVT(U)

  2. 构造FIRSTVT(U)和LASTVT(U)的算法

    • 找Firstvt的三条规则：

      如果要找A的Firstvt，A的候选式中出现：

      A->a…….，即以终结符开头，该终结符入Firstvt

      A->B…….，即以非终结符开头，该非终结符的Firstvt入A的Firstvt

      A->Ba…..，即先以非终结符开头，紧跟终结符，则终结符入Firstvt

      结合代码以及注释来看一下具体的实现过程：

      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
      class FirstVT {

          Set getFirstVt(String str) {
              Set set = new Set(str);
      //        已经求过的VN
              ArrayList<String> First = new ArrayList<>();

              First.add(str);

              for (Production production : Config.productions) {
                  if (production.head.equals(str)) {
                      for (String body : production.body) {
                          for (String vt : Config.VT) {
      //                        通过当前产生式中终结符的位置来判断该产生式属于算法中的哪种类型
                              if (body.contains(vt)) {
                                  int index = body.indexOf(vt);
      //                            A->a...和A->Ba...两种情况，直接加入集合
                                  if (index == 0 || index == 1) {
                                      set.addSet(vt);
                                  }
                              }
                          }
                          for (String vn : Config.VN) {
                              if (body.contains(vn)) {
                                  int index = body.indexOf(vn);
      //                            A->B...这种情况时，若当前FITSTVT(vn)未被加入当前FIRSTVT集，则加入
                                  if (index == 0 && !First.contains(vn)) {
                                      set.addSet(getFirstVt(vn));
                                  }
                              }
                          }
                      }
                  }
              }

              return set;
          }
      }

    • 找Lastvt的三条规则：

      如果要找A的Lastvt，A的候选式中出现：

      A->…….a，即以终结符结尾，该终结符入Lastvt          

      A->…….B，即以非终结符结尾，该非终结符的Lastvt入A的Lastvt          

      A->…..aB，即先以非终结符结尾，前面是终结符，则终结符入Lastvt

      结合代码注释看一下该算法的具体实现过程：

      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
      class LastVT {

          Set getLastVt(String str) {
              Set set = new Set(str);
              ArrayList<String> Last = new ArrayList<>();
              Last.add(str);
              
              for (Production production : Config.productions) {
                  if (production.head.equals(str)) {
                      for (String body : production.body) {
      //                    A->...a，即以终结符结尾，该终结符入Lastvt
                          if (Config.VT.contains(String.valueOf(body.charAt(body.length() - 1)))) {
                              set.addSet(String.valueOf(body.charAt(body.length() - 1)));
                          }
      //                    A->...B，即以非终结符结尾，该非终结符的Lastvt入A的Lastvt
                          if (Config.VN.contains(String.valueOf(body.charAt(body.length() - 1))) 
                                  && !Last.contains(String.valueOf(body.charAt(body.length() - 1)))) {
                              set.addSet(getLastVt(String.valueOf(body.charAt(body.length() - 1))));
                          }
      //                    A->...aB，即先以非终结符结尾，前面是终结符，则终结符入Lastvt
                          if (body.length() > 1 
                                  && Config.VN.contains(String.valueOf(body.charAt(body.length() - 1))) 
                                  && Config.VT.contains(String.valueOf(body.charAt(body.length() - 2)))) {
                              set.addSet(String.valueOf(body.charAt(body.length() - 2)));
                          }

                      }
                  }
              }
              return set;
          }

      }

  3. 根据FIRSTVT集和LASTVT集构造算符优先关系表

    构造算法：

    FOR 每条规则 U->X1X2…Xn DO

    ​ FOR i=1 TO n-1 DO

    ​ BEGIN

    ​ IF Xi和Xi+1均为终结符，THEN 置 Xi=Xi+1

    ​ IF i≤n-2，且Xi和Xi+2都为终结符号 但Xi+1为非终结符号

    ​ THEN 置 Xi=Xi+2

    ​ IF Xi为终结符号Xi+1为非终结符号 THEN

    ​ FOR FIRSTVT(Xi+1)中的每个b DO

    ​ 置Xi<b

    ​ IF Xi为非终结符号Xi+1为终结符号 THEN

    ​ FOR LASTVT(Xi)中的每个a DO

    ​ 置a>Xi+1

    ​ END

    具体实现：

    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
    void generateTable() {

    //        初始化当前表
        for (int i = 0; i < Config.VT.size() + 2; i++) {
            for (int j = 0 ; j < Config.VT.size() + 2; j++) {
                table[i][j] = "";
            }
        }

    //        设置表的第一列与第一行
        table[0][Config.VT.size() + 1] = "#";
        table[Config.VT.size() + 1][0] = "#";

        for (int i = 1; i < Config.VT.size() + 1; i++) {
            table[0][i] = Config.VT.get(i - 1);
            table[i][0] = Config.VT.get(i - 1);
        }

        for (Production production : Config.productions) {
            for (String body : production.body) {
                for (int i = 0; i < body.length() - 1; i++) {
    //                    产生式中有终结符相邻情况，则Xi=Xi+1
                    if (Config.VT.contains(String.valueOf(body.charAt(i))) 
                        && Config.VT.contains(String.valueOf(body.charAt(i + 1)))) {
                        ArrayList<Integer> tmpPos = getPos(String.valueOf(body.charAt(i)),
                                                           String.valueOf(body.charAt(i + 1)));
                        table[tmpPos.get(0)][tmpPos.get(1)] = "=";
                    }
    //                    产生式中有终结符非终结符终结符情况，则Xi=Xi+2
                    if (i <= body.length() - 3 
                        && Config.VT.contains(String.valueOf(body.charAt(i)))
                        && Config.VT.contains(String.valueOf(body.charAt(i + 2)))
                        && Config.VN.contains(String.valueOf(body.charAt(i + 1)))) {
                        ArrayList<Integer> tmpPos = getPos(String.valueOf(                  body.charAt(i)), String.valueOf(body.charAt(i + 2)));
                        if (tmpPos.size() == 2) {
                            table[tmpPos.get(0)][tmpPos.get(1)] = "=";
                        }
                    }
    //                    产生式中存在终结符后紧接着非终结符的情况
                    if (Config.VT.contains(String.valueOf(body.charAt(i))) 
                        && Config.VN.contains(String.valueOf(body.charAt(i + 1)))) {
    //                        当前非终结符的FIRSTVT集中的每个b，都置当前终结符<b
                        for (String b : firstVT.getFirstVt(String.valueOf(body.charAt(i + 1))).body) {
                            ArrayList<Integer> tmpPos = getPos(String.valueOf(body.charAt(i)), b);
                            table[tmpPos.get(0)][tmpPos.get(1)] = "<";
                        }
                    }
    //                    产生式中存在非终结符后紧接着终结符的情况
                    if (Config.VN.contains(String.valueOf(body.charAt(i))) 
                        && Config.VT.contains(String.valueOf(body.charAt(i + 1)))) {
    //                        当前非终结符符号LASTVT集中的每个a，置当前a>当前终结符
                            for (String a : lastVT.getLastVt(String.valueOf(body.charAt(i))).body) {
                                ArrayList<Integer> tmpPos = getPos(a, String.valueOf(body.charAt(i + 1)));
                                table[tmpPos.get(0)][tmpPos.get(1)] = ">";
                            }
                    }
                }
            }
        }

    //        对#的处理
    //        #<FIRSTVT(起始符号)
        for (int i = 0; i < firstVT.getFirstVt(Config.productions.get(0).head).body.size(); i++) {
            for (String a : firstVT.getFirstVt(Config.productions.get(0).head).body) {
                int tmp = getPosX(a);
                if (tmp >= 0)
                    table[Config.VT.size() + 1][tmp] = "<";
            }
        }
    //        #>LASTVT(起始符号)
        for (int i = 0; i < lastVT.getLastVt(Config.productions.get(0).head).body.size(); i++) {
            for (String a : lastVT.getLastVt(Config.productions.get(0).head).body) {
                int tmp = getPosY(a);
                if (tmp >= 0)
                    table[tmp][Config.VT.size() + 1] = ">";
            }
        }

    }

  4. 算符优先分析过程

    算符优先分析算法：

    while(true)

    ​ if #在栈顶且输入串下标指向# 则

    ​ return success;

    ​ else

    ​ 令a是栈最上面的终结符，b是当前输入串下标对应符号

    ​ if a<b 或 a=b

    ​ b入栈

    ​ 下标指向下一个输入符号

    ​ else if a>b

    ​ do

    ​ 出栈

    ​ while 栈顶终结符与<最近弹出的终结符

    ​ else error()

    具体实现：

    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
    void analyze () {
    //        初始化符号栈、获取输入串
        init();
    //        记录最近出栈符号
        String recentPop;
        while (true) {
    //            #在栈顶，且输入串下标指向#
            if (analyzeStack.peek().equals("#") && inputStack.get(cursorOfInput).equals("#")) {
                System.out.println("Success");
                return;
            } else {
    //                a<b 或 a=b
                if (isLess(analyzeStack.peek(), inputStack.get(cursorOfInput))
                    || isEqual(analyzeStack.peek(), inputStack.get(cursorOfInput))) {
                    analyzeStack.push(inputStack.get(cursorOfInput));
                    cursorOfInput++;
                    outputStack();
                }
    //                a>b
                else if (isLarger(analyzeStack.peek(),
                                  inputStack.get(cursorOfInput))) {
                    recentPop = analyzeStack.peek();
                    while ( !isLess(analyzeStack.peek(), recentPop) ) {
                        recentPop = analyzeStack.pop();
                    }
                    outputStack();
                } else {
                    System.out.println("Error");
                    return;
                }
            }
        }
        
    }

    测试

  5. 测试用例

    1
    2
    3
    4
    5
    E,T,F
    +,-,*,/,i,(,)
    E->E+T|E-T|T
    T->T*F|T/F|F
    F->(E)|i

  6. 运行结果

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

关注我

订阅更新

邮件订阅，更新早获取

分类

最新文章

归档

标签

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