实验4《算符优先分析法设计与实现》（java版）_实验4《算符优先分析法设计与实现》(java版)

任务描述

本关任务：加深对语法分析器工作过程的理解；加强对算符优先分析法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。

相关知识

为了完成本关任务，你需要掌握：用算符优先法编制语法分析程序。

自下而上的语法分析器

语法分析在编译中是一个重要的环节，语法分析可以分为自上而下分析和自下而上分析两种方式。

自下而上分析法是一种“移进－归约”法。这种方法的大意是，用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分替换成（归约为）该产生式的左部符号。

对于自下而上的分析法，边输入单词符号（移进符号栈），边归约。也就是在从左到右移进输入串的过程中，一旦发现栈顶呈现可归约串就立即进行归约。

在该类方法中有以下的几个处理：

• 移进：指把输入串的一个符号移进栈。

• 归约：指发现栈顶呈可归约串，并用适当的相应符号去替换这个串（这两个问题都还没有解决）。

• 接受：指宣布最终分析成功，这个操作可看作是“归约”的一种特殊形式。

• 出错处理：指发现栈顶的内容与输入串相悖，分析工作无法正常进行，此时需调用出错处理程序进行诊察和校正，并对栈顶的内容和输入符号进行调整。

算符优先法

算符优先分析法(Operator Precedence Parse)是一种移动归约分析方法，它是仿效四则运算的计算过程而构造的一种语法分析方法。算符优先分析法的关键是比较两个相继出现的终结符的优先级而决定应采取的动作。

算法优先关系构造的构造遵循以下的步骤：

首先对于优先关系进行如下定义：

• a的优先级低于b
a < b： 文法中有形如A→…aB…的产生式而B+b…或B+Cb…
• a的优先级等于b
  a = b： 文法中有形如A→…ab…或者A→…aBb…的产生式
• a的优先级高于b
  a > b： 文法中有形如A…Bb…的产生式,而B+…a或B+…aC
• 算符的优先关系是有序的
  如果a > b，不能推出b < a
  如果a > b，有可能b > a
  如果a > b， b > c，不一定a > c  根据这个大小关系的定义，我们知道为了确定两个终止符的优先关系，我们需要知道它的在所有的产生式中和前后非终止符的关系，那么我们做一个如步骤二的预处理。

定义并构造FIRSTVT和LASTVT两个集合

FIRSTVT(P)={a∣P⇒+a⋯或P⇒+Qa⋯}

LASTVT(P)={a∣P⇒+⋯a0​P⇒+…aQ}

1. FIRSTVT(P)直接根据定义递归的构造即可:

• 若有产生式 P→a⋯ 或 p→Qa⋯，则 a∈FIRSTVT(P)
• 若有产式 P→Q⋯，若 a∈FIRSTVT(Q)，则 a∈FIRSTVT(P)

1. LASTVT(P)直接根据定义递归的构造即可：

• 若有产生式 P→⋯ 或 p→⋯⋅a 则 a∈LASTVT(P)
• 若有产式 P→⋯, 若 a∈LASTVT(Q) 则 a∈LASTVT(P)

利用FIRSTVT和LASTVT集合构造算法优先关系表:

1. FOR 每个产生式 P->X1 X2 ……Xn
2. DO FOR i:=1 TO n-1 DO
3. IF X[i]和X[i+1]均为终结符
4. THEN 置 X[i]=X[i+1]
5. IF X[i]和X[i+2]均为终结符,X[i+1]为非终结符,i≤n-2,
6. THEN 置 X[i]=X[i+2]
7. IF X[i]为终结符, 但X[i+1]为非终结符
8. THEN FOR FIRSTVT(X[i+1])中的每个a
9. DO 置 X[i]<a
10. IF Xi为非终结符, 但X i+1 为终结符
11. THEN FOR LASTVT(X i )中的每个a
12. DO 置 a>X[i+1]

实验步骤

1. 对语法规则有明确的定义；
   该部分需要我们对输入文法进行构造，然后定义出算符之间的优先级，构造算符优先关系表，表的构造过程如上。
2. 编写的分析程序能够对测试用例进行正确的语法分析；
   该部分需要我们对于输入的字符串进行逐一判断，并给出相应的解析过程，该过程是一个移进，归约，接受及出错处理的操作过程。
3. 对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程；

编程要求

根据提示，在右侧编辑器Begin和End之间依次补充构造算符优先表getPriorityTables、构造firstvt,lastvtgetFirstVT等程序代码，点击测评，运行程序，进行结果对比。

测试说明

平台会对你编写的代码进行测试.

开始你的任务吧，祝你成功！

代码：

import java.util.ArrayList;
import java.util.Enumeration;
import java.util.Scanner;
import java.util.Stack;
public class main {
    public static final char[] T = { '+', '*', '^', 'i', '(', ')', '#' }; // 终结符
    public static int sizeOfTerminal = T.length; // 终结符的数目
    public static final char[] N = { 'E', 'T', 'F', 'P' }; // 非终结符
    public static int sizeOfNotTerminal = N.length; // 非终结符的数目
    public static String previousGrammar; // 前一个候选式
    public static String backGrammar; // 后一个候选式
    public static ArrayList normativeGrammar; // 存放规范文法的列表
    public static int sizeOfGrammar; // 文法的大小
    public static String inputString; // 用户输入的要分析的串
    public static int lengthOfInputString; // 输入串的长度
    public static Character[] stack = new Character[100]; // 存储终结符合非终结符的分析栈
    public static boolean[][] firstvt; // 存储FIRSTVT的二维数组
    public static boolean[][] lastvt; // 存储LASTVT的二维数组
    public static Character[][] priorityTables; // 存放算符优先文法的优先表
    public static int count = 0; // 用于判断步骤
    public static void main(String[] args) {
        getGrammar();
        getFirstVT();
        getPriorityTables();
        getInputString();
        parsingProcess();
    }
    /********Beign********/
    /*构造算符优先表*/
    public static void getPriorityTables() {
        priorityTables = new Character[sizeOfTerminal][sizeOfTerminal];
        for (int m = 0; m < sizeOfGrammar; m++) {
            String string = (String) normativeGrammar.get(m);
            for (int i = 2; i <= string.length() - 2; i++) {
                // 情形1
                if (judgeCharType(string.charAt(i)) == 'T' && judgeCharType(string.charAt(i + 1)) == 'T') {
                    // 首先分别获取这两个字符在终结符数组中的位置-----------
                    int pisition1 = 0, pisition2 = 0;
                    for (; pisition1 < sizeOfTerminal; pisition1++) {
                        if (string.charAt(i) ==