任务描述

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

相关知识

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

自上而下的语法分析器

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

自上而下分析法是从文法开始符号开始，不断进行推导，直到推导所得的符号串与输入串相同为止。简单来解释这句话：我们有一个既定的文法，和一个需要分析的符号串。接下来我们从文法的开始符号出发，反复地使用文法规定的一些产生式匹配符号串的每一个符号，直到所得的符号串和待分析的符号串相同，则为分析成功，反之匹配不成功。

下面我们举例来进行说明：
我们有文法G(E)：

E→aF
F→b|c 

以及待输入的字符 ab，从文法开始符号E出发，E→aF，a匹配成功后，指针指向F，找非终结符F的产生式合适的候选式 b匹配，于是匹配成功。

想要对一个文法进行自上而下的分析，要消除文法的二义性，消除左递归，提取左公共因子，计算FIRST集合和FOLLOW集合，判断文法是否为LL(1)型文法，一个文法经过这些步骤，并且是LL(1)文法，则可以用LL(1)分析法的具体实现去分析。我们在后续的实验步骤中会进行该过程的一一实验。

预测分析法

预测分析法是LL(1)分析法的一种实现方法，它通过一张表来关联非终结符和终结符，这张表就是预测分析表，预测分析表可以说是预测分析法的核心部分。我们在进行该方法时，首先要构建预测分析表。

首先介绍一下预测分析表的结构，简单来说他就是一张表，表的两个属性分别是非终结符和终结符（包括‘#’），形如：
其中对应的内容是产生式的形式，若是没有产生式则可以写入标记来表示其匹配不到具体的产生式，进入报错处理程序。

在根据文法构造预测分析表时需要扫描全部产生式：

计算产生式的右部的FIRST集合，如果求出来的FIRST集合中包含终结符，那么就把这条产生式放入对应非终结符和终结符的格子中
如果ε在FIRST集合中，则计算该非终结符的FOLLOW集合，如果求出来的FOLLOW集合中包含终结符，那么就把这条产生式放入对应的非终结符和终结符的格子中
当预测分析表构造完成后，我们便可以运用预测分析法进行语法分析了。我们使用用一个栈来存放过程数据，主要步骤如下：

获取栈顶的元素A，获取输入串目前指针指向的元素a
若A = ‘#’ ,a = ‘#’ 则匹配成功
若A = a 但是A和a不为’#’，则pop栈顶元素，输入串指针+1
若A为非终结符，这查询预测分析表，把由A和a确定的产生式的右部从右往左依次压入到栈中，若右部是ε，那就不做操作
查找预测分析表得到预设的出错字符则调用error()

实验步骤

根据语法分析器的一般功能，我们的程序应具有如下的要求及实验步骤：

定义目标语言的语法规则；
求解预测分析方法需要的符号集和分析表；
依次读入测试用例，根据预测分析的方法进行语法分析，直到源程序结束；该部分具体见上。
对遇到的语法错误做出错误处理。
下面我们对步骤1，2进行说明。

目标语言的语法规则

该部分重点在于消除文法的二义性，消除左递归，提取左公共因子。想要让程序自动地消除左递归，具体的做法如下：
1.把文法的所有非终结符进行排序S = [‘A’,‘B’,…]
2.做一个嵌套循环：
其中S[k]为排在S[j]之后的非终结符,bunch_i为非终结符和终结符组成的串

for j in range(len(s)):
        for k in range(j):
            原产生式中:S[j]→S[k]bunch_1的S[k]用其对应的产生式代替
            S[k]→bunch_2|bunch_3|...
            推出：S[j]→bunch_2 bunch_1|bunch_3 bunch_1|...
            如此，做完循环后该文法若有间接左递归，就将其转换成直接左递归了
            消除直接左递归，具体做法见上文
循环结束后删除无用产生式 

求解预测分析方法需要的符号集和分析表

符号集主要是构造FIRST集和FOLLOW集，其主要目的是为了消除回溯，也就是选择候选式的时候能够更加准确，当然，这些集合在别的地方也有用处。

构造FIRST集: 扫描所有的产生式，对于每一个X，连续使用以下规则，直至每个集合的FIRST集合不再增大为止，每一遍扫描所有产生式如果有FIRST集合变化则重新扫描：

如果X是终结符，则FIRST(X) = {X}.
如果X是非终结符 ，且有产生式 X → a… 则把a加入到FIRST集合中. 若 X → ε也是其中一条产生式，则把ε也加入到FIRST集合中.
如果X是非终结符，且X → Y…是一条产生式，其中Y是非终结符，那么则把FIRST(Y) \ {ε}（即FIRST集合去除ε）加入到FIRST(X)中.
构造FOLLOW集: 扫描所有产生式.对于文法G的每一个非终结符A构造FOLLOW(A)可以连续使用以下规则，直至每一个FOLLOW集合不在增大为止：

对于文法的开始符号S，置#于FOLLOW(S)中.
若有产生式 A → αBβ，其中α和β是非终结符和终结符构成的串，B为非终结符，则把FIRST(β) \ {ε}加入到FOLLOW(B)中.
若有产生式 A → αB 或 A → αBβ,ε∈FIRST(β) ，则把FOLLOW(A)加入到FOLLOW(B)中.
分析表的构成见上所述。

编程要求

根据提示，在右侧编辑器Begin和End之间依次完成划分产生式、消除左递归、计算FIRST集、计算follow集、构建LL(1)分析表等代码，然后点击测评，运行程序，进行结果对比。

测试说明

测试输入的格式为：

E T F
+ * ( ) i
E->E+T|T
T->T*F|F
F->(E)|i
(i)*i
(i)*iii

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

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

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class ex2 {
    //非终结符集
    static List<String> noTerminal = new ArrayList<>();
    //终结符集
    static List<String> terminal = new ArrayList<>();
    //语法规则存储
    static String[][] grammarRules;
    //消除左递归后语法规则存储
    static String[][] grammar_rules;
    static String[][] newGrammer;
    //文法开始符号
    static String init;
    //FIRST集
    static String[][] firstSet;
    //FOLLOW集
    static String[][] followSet;
    //LL(1)分析表
    static int[][] analysis;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        //读入非终结符
        //System.out.println("请输入非终结符: ");
        String noTer = new String("ETF");
        for (int i = 0; i < noTer.length(); i++){
            noTerminal.add(String.valueOf(noTer.charAt(i)));
        }
        //读入终结符
        terminal.add("#");
        //System.out.println("请输入终结符: ");
        String ter = new String("+*()i");
        for (int i = 0; i < ter.length(); i++){
            terminal.add(String.valueOf(ter.charAt(i)));
        }
        //初始化
        grammarRules = new String[noTer.length()][2];
        grammar_rules = new String[noTer.length() * 2][2];
        newGrammer = new String[noTerminal.size() * 5][3];
        //输入语法规则
        //System.out.println("请输入语法规则：");
        String grammar = new String("E->E+T|T");
        init = String.valueOf(grammar.charAt(0));
        divide(grammar);
        eliminate(grammar);

        String grammar1 = new String("T->T*F|F");
        divide(grammar1);
        eliminate(grammar1);

        String grammar2 = new String("F->(E)|i");
        divide(grammar2);
        eliminate(grammar2);
        //请输入测试用例
        System.out.println("请输入测试用例：");
        String test = input.nextLine();
        //输出信息
        System.out.println("------------------基本信息-----------------------");
        System.out.println("产生式：");
        output(grammarRules);
        System.out.println("终结符：");
        for (int i = 0; i < terminal.size(); i++){
            System.out.print(terminal.get(i) + "     ");
        }
        System.out.println();
        System.out.println("非终结符：");
        for (int i = 0; i < noTerminal.size(); i++){
            System.out.print(noTerminal.get(i) + "     ");
        }
        System.out.println();
        System.out.println("读取测试：");
        System.out.println(test);
        System.out.println("-------------------消除左递归---------------------");
        System.out.println("产生式：");
        output(grammar_rules);
        System.out.println("----------------FIRST集和FOLLOW集-----------------");
        firstSet = new String[noTerminal.size()][terminal.size()];
        for (int i = 0; i < noTerminal.size(); i++){
            first(noTerminal.get(i));
            System.out.print("FIRST(" + noTerminal.get(i) + ") = " );
            for (int j = 0; j < terminal.size(); j++){
                if (firstSet[i][j] != null){
                    System.out.print(firstSet[i][j] + " ");
                }
            }
            System.out.println();
        }
        followSet = new String[noTerminal.size()][terminal.size()];
        for (int i = 0; i < noTerminal.size(); i++){
            follow(noTerminal.get(i));
            System.out.print("FOLLOW(" + noTerminal.get(i) + ") = ");
            for (int j = 0; j < terminal.size(); j++){
                if (followSet[i][j] != null){
                    System.out.print(followSet[i][j] + " ");
                }
            }
            System.out.println();
        }
        System.out.println("----------------LL(1)分析表-----------------");
        analysis = new int[noTerminal.size()][terminal.size()];
        table();
        System.out.print("      ");
        for (int i = 0; i < terminal.size(); i++){
            System.out.print(terminal.get(i) + "     ");
        }
        System.out.println();
        for (int i = 0; i < noTerminal.size(); i++){
            System.out.print(noTerminal.get(i) + "     ");
            for (int j = 0; j < terminal.size(); j++){
                if (analysis[i][j] != 0) {
                    System.out.print(analysis[i][j] + "     ");
                }else{
                    System.out.print("      ");
                }
            }
            System.out.println();
        }
        System.out.println("--------------------分析栈-------------------");
        System.out.println(String.format("%-10s","分析栈") + String.format("%-10s","剩余字符串"));
        analysisStack(test);
    }

	/********Beign********/
    /*** 划分出产生式*/
    static void divide(String grammar){

    }
    /********End********/

	/********Beign********/
    /*** 消除左递归*/
    static void eliminate(String grammar){

    }
    /********End********/

    /*** 输出产生式*/
    static void output(String[][] array){
        int k = 0;
        for (int i = 0; i < array.length; i++){
            for (int j = 0; j < array[i].length; j++){
                if (array[i][j] != null) {
                    newGrammer[k][0] = String.valueOf(k+1);
                    newGrammer[k][1] = noTerminal.get(i);
                    newGrammer[k][2] = array[i][j];
                    System.out.println(newGrammer[k][0] + "     " + newGrammer[k][1] + "     " + newGrammer[k][2]);
                    k++;
                }
            }
        }
    }

	/********Beign********/
    /*** 计算FIRST集*/
    static void first(String noTer){
        
    }
    /********End********/

    /********Beign********/
    /*** 计算follow集*/
    static void follow(String noTer){
        
    }
	/********End********/

    /********Beign********/
    /*** 构建LL(1)分析表*/
    static void table(){
        
    }
	/********End********/

    /*** 输出分析栈*/
    static void analysisStack(String test){
        List<String> stack = new ArrayList<>();
        stack.add("#");
        stack.add("E");
        String outStack = test + "#";
        boolean flag = true;
        while (flag){
            String inStack = "";
            for (int i = 0; i < stack.size(); i++){
                inStack = inStack + stack.get(i);
            }
            System.out.println(String.format("%-10s",inStack) + String.format("%-10s",outStack));
            String NT = stack.get(stack.size()-1);
            String T = String.valueOf(outStack.charAt(0));
            if (NT.equals(T) && NT.equals("#")){
                System.out.println("分析成功");
                break;
            } else if (NT.equals(T)){
                stack.remove(stack.size()-1);
                outStack = outStack.substring(1);
            } else {
                if (analysis[noTerminal.indexOf(NT)][terminal.indexOf(T)] > 0){
                    int num = analysis[noTerminal.indexOf(NT)][terminal.indexOf(T)];
                    String s = newGrammer[num-1][2];
                    stack.remove(stack.size()-1);
                    for (int i = s.length()-1; i >= 0; i--){
                        if (!s.equals("-")) {
                            stack.add(String.valueOf(s.charAt(i)));
                        }
                    }
                }else {
                    System.out.println("ERROR: 分析出错");
                }
            }
        }
    }
}

通关代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class ex2 {
    //非终结符集
    static List<String> noTerminal = new ArrayList<>();
    //终结符集
    static List<String> terminal = new ArrayList<>();
    //语法规则存储
    static String[][] grammarRules;
    //消除左递归后语法规则存储
    static String[][] grammar_rules;
    static String[][] newGrammer;
    //文法开始符号
    static String init;
    //FIRST集
    static String[][] firstSet;
    //FOLLOW集
    static String[][] followSet;
    //LL(1)分析表
    static int[][] analysis;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        //读入非终结符
        //System.out.println("请输入非终结符: ");
        String noTer = new String("ETF");
        for (int i = 0; i < noTer.length(); i++){
            noTerminal.add(String.valueOf(noTer.charAt(i)));
        }
        //读入终结符
        terminal.add("#");
        //System.out.println("请输入终结符: ");
        String ter = new String("+*()i");
        for (int i = 0; i < ter.length(); i++){
            terminal.add(String.valueOf(ter.charAt(i)));
        }
        //初始化
        grammarRules = new String[noTer.length()][2];
        grammar_rules = new String[noTer.length() * 2][2];
        newGrammer = new String[noTerminal.size() * 5][3];
        //输入语法规则
        //System.out.println("请输入语法规则：");
        String grammar = new String("E->E+T|T");
        init = String.valueOf(grammar.charAt(0));
        divide(grammar);
        eliminate(grammar);
        String grammar1 = new String("T->T*F|F");
        divide(grammar1);
        eliminate(grammar1);
        String grammar2 = new String("F->(E)|i");
        divide(grammar2);
        eliminate(grammar2);
        //请输入测试用例
        System.out.println("请输入测试用例：");
        String test = input.nextLine();
        //输出信息
        System.out.println("------------------基本信息-----------------------");
        System.out.println("产生式：");
        output(grammarRules);
        System.out.println("终结符：");
        for (int i = 0; i < terminal.size(); i++){
            System.out.print(terminal.get(i) + "     ");
        }
        System.out.println();
        System.out.println("非终结符：");
        for (int i = 0; i < noTerminal.size(); i++){
            System.out.print(noTerminal.get(i) + "     ");
        }
        System.out.println();
        System.out.println("读取测试：");
        System.out.println(test);
        System.out.println("-------------------消除左递归---------------------");
        System.out.println("产生式：");
        output(grammar_rules);
        System.out.println("----------------FIRST集和FOLLOW集-----------------");
        firstSet = new String[noTerminal.size()][terminal.size()];
        for (int i = 0; i < noTerminal.size(); i++){
            first(noTerminal.get(i));
            System.out.print("FIRST(" + noTerminal.get(i) + ") = " );
            for (int j = 0; j < terminal.size(); j++){
                if (firstSet[i][j] != null){
                    System.out.print(firstSet[i][j] + " ");
                }
            }
            System.out.println();
        }
        followSet = new String[noTerminal.size()][terminal.size()];
        for (int i = 0; i < noTerminal.size(); i++){
            follow(noTerminal.get(i));
            System.out.print("FOLLOW(" + noTerminal.get(i) + ") = ");
            for (int j = 0; j < terminal.size(); j++){
                if (followSet[i][j] != null){
                    System.out.print(followSet[i][j] + " ");
                }
            }
            System.out.println();
        }
        System.out.println("----------------LL(1)分析表-----------------");
        analysis = new int[noTerminal.size()][terminal.size()];
        table();
        System.out.print("      ");
        for (int i = 0; i < terminal.size(); i++){
            System.out.print(terminal.get(i) + "     ");
        }
        System.out.println();
        for (int i = 0; i < noTerminal.size(); i++){
            System.out.print(noTerminal.get(i) + "     ");
            for (int j = 0; j < terminal.size(); j++){
                if (analysis[i][j] != 0) {
                    System.out.print(analysis[i][j] + "     ");
                }else{
                    System.out.print("      ");
                }
            }
            System.out.println();
        }
        System.out.println("--------------------分析栈-------------------");
        System.out.println(String.format("%-10s","分析栈") + String.format("%-10s","剩余字符串"));
        analysisStack(test);
    }
    /********Beign********/
    /*** 划分出产生式*/
    static void divide(String grammar){
        int fla = grammar.indexOf("|");
        int flag = grammar.indexOf(">");
        String a = String.valueOf(grammar.charAt(0));
        if (fla != -1){
            grammarRules[noTerminal.indexOf(a)][0] = grammar.substring(flag+1, fla);
            grammarRules[noTerminal.indexOf(a)][1] = grammar.substring(fla+1);
        } else {
            grammarRules[noTerminal.indexOf(a)][0] = grammar.substring(flag+1);
        }
    }
    /********End********/
    /********Beign********/
    /*** 消除左递归*/
    static void eliminate(String grammar){
        int fla = grammar.indexOf("|");
        int flag = grammar.indexOf(">");
        //如果存在左递归
        if (grammar.charAt(0) == grammar.charAt(flag+1)){
            String a = String.valueOf(Character.toLowerCase(grammar.charAt(0)));
            noTerminal.add(a);
            if (!terminal.contains("-")){
                terminal.add("-");
            }
            String s = "";
            for (int i = flag; i < grammar.length(); i++){
                s = String.valueOf(grammar.charAt(i));
                flag = terminal.indexOf(s);
                if (flag != -1) {
                    flag = grammar.indexOf(s);
                    break;
                }
            }
            s = s + grammar.substring(flag+1, fla) + a;
            grammar_rules[noTerminal.indexOf(a)][0] = s;
            grammar_rules[noTerminal.indexOf(a)][1] = "-";
            grammar_rules[noTerminal.indexOf(String.valueOf(grammar.charAt(0)))][0] = grammar.substring(fla+1) + a;
        } else {
            grammar_rules[noTerminal.indexOf(String.valueOf(grammar.charAt(0)))][0] = grammarRules[noTerminal.indexOf(String.valueOf(grammar.charAt(0)))][0];
            grammar_rules[noTerminal.indexOf(String.valueOf(grammar.charAt(0)))][1] = grammarRules[noTerminal.indexOf(String.valueOf(grammar.charAt(0)))][1];
        }
    }
    /********End********/
    /*** 输出产生式*/
    static void output(String[][] array){
        int k = 0;
        for (int i = 0; i < array.length; i++){
            for (int j = 0; j < array[i].length; j++){
                if (array[i][j] != null) {
                    newGrammer[k][0] = String.valueOf(k+1);
                    newGrammer[k][1] = noTerminal.get(i);
                    newGrammer[k][2] = array[i][j];
                    System.out.println(newGrammer[k][0] + "     " + newGrammer[k][1] + "     " + newGrammer[k][2]);
                    k++;
                }
            }
        }
    }
    /********Beign********/
    /*** 计算FIRST集*/
    static void first(String noTer){
        String s = "";
        int flag = noTerminal.indexOf(noTer);
        for (int i = 0; i < 2; i++){
            if (grammar_rules[flag][i] != null) {
                String str = grammar_rules[flag][i];
                String initials = String.valueOf(str.charAt(0));
                if (noTerminal.contains(initials)){
                    first(initials);
                    for (int j = 0; j < terminal.size(); j++){
                        int temp = noTerminal.indexOf(initials);
                        if (firstSet[temp][j] != null){
                            firstSet[flag][j] = firstSet[temp][j];
                        }
                    }
                } else {
                    firstSet[flag][terminal.indexOf(initials)] = String.valueOf(str.charAt(0));
                }
            }
        }
    }
    /********End********/
    /********Beign********/
    /*** 计算follow集*/
    static void follow(String noTer){
        for (int i = 0; i < noTerminal.size(); i++){
            for (int j = 0; j < 2;j++){
                if (grammar_rules[i][j] != null){
                    String str = grammar_rules[i][j];
                    //文法开始符号
                    if (noTer.equals(init)) {
                        followSet[noTerminal.indexOf(init)][terminal.indexOf("#")] = "#";
                    }
                    int index = str.indexOf(noTer);
                    //noTer不在最后位置
                    if (index != -1 && index != str.length() - 1){
                        String ch = String.valueOf(str.charAt(index + 1));
                        //ch是非终结符
                        if (noTerminal.contains(ch)){
                            for (int k = 0; k < terminal.size(); k++){
                                if (firstSet[noTerminal.indexOf(ch)][k] != null && !firstSet[noTerminal.indexOf(ch)][k].equals("-")){
                                    followSet[noTerminal.indexOf(noTer)][k] = firstSet[noTerminal.indexOf(ch)][k];
                                    for (int l = 0; l < terminal.size(); l++){
                                        if (followSet[i][l] != null){
                                            followSet[noTerminal.indexOf(noTer)][l] = followSet[i][l];
                                        }
                                    }
                                }
                            }
                        } else {
                            //ch不是非终结符
                            followSet[noTerminal.indexOf(noTer)][terminal.indexOf(ch)] = ch;
                        }
                    } else if (index > 0 && index == str.length() - 1){
                        //noTer在最后位置，防止死循环
                        if (!noTerminal.get(i).equals(noTer)) {
                            follow(noTerminal.get(i));
                            for (int k = 0; k < terminal.size(); k++){
                                if (followSet[i][k] != null){
                                    followSet[noTerminal.indexOf(noTer)][k] = followSet[i][k];
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    /********End********/
    /********Beign********/
    /*** 构建LL(1)分析表*/
    static void table(){
        int index = 0;
        for (int i = 0; i < noTerminal.size(); i++){
            int num = 0, temp = 0;
            int[] flag = new int[terminal.size()];
            for (int j = index; j < newGrammer.length; j++){
                if (newGrammer[index][1].equals(newGrammer[j][1])){
                    flag[temp] = Integer.valueOf(newGrammer[j][0]);
                    num++;
                    temp++;
                }
            }
            index += num;
            if (num == 1){
                for (int j = 0; j < firstSet[i].length; j++){
                    if (firstSet[i][j] != null){
                        analysis[i][j] = flag[0];
                    }
                }
            } else {
                temp = 0;
                for (int j = 0; j < firstSet[i].length; j++){
                    if (firstSet[i][j] != null) {
                        if (!firstSet[i][j].equals("-")){
                            analysis[i][j] = flag[temp];
                            temp++;
                        } else {
                            for (int f = 0; f < followSet[i].length; f++){
                                if (followSet[i][f] != null){
                                    analysis[i][f] = flag[temp];
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    /********End********/
    /*** 输出分析栈*/
    static void analysisStack(String test){
        List<String> stack = new ArrayList<>();
        stack.add("#");
        stack.add("E");
        String outStack = test + "#";
        boolean flag = true;
        while (flag){
            String inStack = "";
            for (int i = 0; i < stack.size(); i++){
                inStack = inStack + stack.get(i);
            }
            System.out.println(String.format("%-10s",inStack) + String.format("%-10s",outStack));
            String NT = stack.get(stack.size()-1);
            String T = String.valueOf(outStack.charAt(0));
            if (NT.equals(T) && NT.equals("#")){
                System.out.println("分析成功");
                break;
            } else if (NT.equals(T)){
                stack.remove(stack.size()-1);
                outStack = outStack.substring(1);
            } else {
                if (analysis[noTerminal.indexOf(NT)][terminal.indexOf(T)] > 0){
                    int num = analysis[noTerminal.indexOf(NT)][terminal.indexOf(T)];
                    String s = newGrammer[num-1][2];
                    stack.remove(stack.size()-1);
                    for (int i = s.length()-1; i >= 0; i--){
                        if (!s.equals("-")) {
                            stack.add(String.valueOf(s.charAt(i)));
                        }
                    }
                }else {
                    System.out.println("ERROR: 分析出错");
                }
            }
        }
    }
}