java编写简单的语法分析预测程序

参考链接： 预测以下Java程序的输出

编译原理课程中，编了一个简单的语法分析预测程序，这个程序时根据固定的文法得到预测分析表，然后编写程序来判断表达式是否会正确推到出来。 

 前提是程序没有左递归符合LL(1)文法： 

 文法如下： 

 E→TE' 

 E’ →+TE'|ε 

 T→FT' 

 T’ →*FT'|ε 

  F→(E)|i 

 为了程序便于编写将E'替换为e,T'替换为t 

 (2)FIRST集 

 FIRST(E)={(,i};  

 FIRST(E’)={+, ε}; 

 FIRST(T)={(,i}; 

 FIRST(T’)={ *, ε}; 

 FIRST(F)={(,i}; 

 (3)FALLOW集 

 FOLLOW(E)={),#}; 

 FOLLOW(E’)={),#}; 

 FOLLOW(T)={+,),#}; 

 FOLLOW(T’)={+,),#}; 

 FOLLOW(F)={*,+,),#}; 

 (4)预测分析表 

     i  +  *  (  )  #  E  E->TE’        E->TE’        E’     E’->+TE’        E’->ε  E’->ε  T  T->FT’        T->FT’        T’     T’->ε  T’->*FT’     T’->ε  T’->ε  F  F->i        F->(E)       

  一、Stack.java 

  public class Stack {

    private char s[];

    private int top;

    private int base;

    private final int MAX = 200;

    /**

     * 

    * <p>Title: </p>

    * <p>Description: 初始化栈</p>

     */

    public Stack() {

        initStack();

    }

    private void initStack() {

        s = new char[MAX];

        base = 0;

        top = 0;        

    }

    public boolean isEmpty() {

        if(top == base) {

            return true;

        }else {

            return false;

        }

    }

    /**

     * 

    * <p>Title: getTop</p>

    * <p>Description: 获取栈顶元素</p>

    * @return 返回栈顶元素

     */

    public char getTop() {

        return s[top-1];

    }

    /**

     * 

    * <p>Title: push</p>

    * <p>Description: 进栈方法</p>

    * @param str 进栈的字符

     */

    public void push(String str) {

        for (int i = str.length() - 1; i >= 0; i--) {

            s[top++] = str.charAt(i);

        }

    }

    /**

     * 

    * <p>Title: clear</p>

    * <p>Description: 清空栈</p>

     */

    public void clear() {

        top = base;

    }

    /**

     * 

    * <p>Title: pop</p>

    * <p>Description: 出栈</p>

    * @return 栈顶元素出栈并返回出栈的元素

     */

    public char pop() {

        return s[--top];

    }

    /**

     * 

    * <p>Title: size</p>

    * <p>Description: 返回栈中元素个数</p>

    * @return 栈中元素个数

     */

    public int size() {

        return top;

    }

    /**

     * 打印栈里面的元素

     */

    public String toString() {

        StringBuffer tempStack = new StringBuffer();

        for (int i = 0; i < top; i++) {

            tempStack.append(s[i]);

        }

        return tempStack.toString();

    }

} 

 二、GrammarAnalyze.java 

  package grammarAnalyze;

public class GrapparAnalyze {

    //分析表将E'替换为e,T'替换t

    private String tab[][] = { 

        { "$", "i",  "+",   "*",  "(",   ")", "#" },

        { "E", "Te", "$",   "$",  "Te", "$",  "$" },

        { "e", "$", "+Te", "$",   "$",  "ε",  "ε" },

        { "T", "Ft", "$",   "$",  "Ft","$",  "$" },

        { "t", "$",  "ε",   "*Ft", "$", "ε",  "ε" },

        { "F",  "i",  "$",   "$",  "(E)","$", "$" } };

    private String input;  //input中存放输入的表达式

    private StringBuffer tempBuffer;    //存放要输出的字符串

    private int ptr, row, col, step; //指针，预测表中的行，列，当前步骤

    private boolean symbol;

    private Stack stack;

    public GrapparAnalyze(){

        stack = new Stack();

        tempBuffer = new StringBuffer();

        symbol=true;

        input="";

        stack.clear();

        stack.push("#");

        row=1;

        ptr=0;

        step=1;

    }

    public int column(char c) {  //判断预测表中的列

        switch (c) {

        case 'i':

            return 1;

        case '+':

            return 2;

        case '*':

            return 3;

        case '(':

            return 4;

        case ')':

            return 5;

        case '#':

            return 6;

        default:

            return -1;

        }

    }

    public int line(char c) { //判定预测表中的行

        switch (c) {

        case 'E':

            return 1;

        case 'e':

            return 2;

        case 'T':

            return 3;

        case 't':

            return 4;

        case 'F':

            return 5;

        default:

            return -1;

        }

    }

    public void show(String str) {

        tempBuffer.append(String.format("%-7d%-14s%-20s%-20s\r\n", 

                step, filter(stack.toString()), filter(input.substring(ptr)), filter(str)));

         step++;

    }

    public void analyse() {

        stack.push(tab[row][0]);   //预测表中的第一个元素‘E’

        show("初始化");

        String tmp;

        char ctmp;   //栈顶元素

        while (!(input.charAt(ptr) == '#' && stack.getTop() == '#')) {

            ctmp = stack.getTop();//获取栈顶的元素

            if (input.charAt(ptr) == ctmp) { //与栈顶元素比较

                stack.pop();

                ptr++;

                show("" + ctmp + "匹配");

                continue;

            }

            //判断ptr位置的终结符所在预测表的列位置

            col = column(input.charAt(ptr));

            if (col == -1) {

                symbol = false;

                show("未定义的字符");

                ptr++;

                break;

            }

            //判断栈顶位置所在预测表的行位置

            row = line(ctmp);

            if (row == -1) {

                symbol = false;

                show("出错");

                stack.pop();

                if (input.charAt(ptr) != '#') {

                    ptr++;

                }

                continue;

            }

            tmp = tab[row][col];

            if (tmp.charAt(0) == '$') {

                symbol = false;

                show("出错");

                stack.pop();

                if (input.charAt(ptr) != '#') {

                    ptr++;

                }

            } else if (tmp.charAt(0) == 'ε') {

                stack.pop();

                show("" + ctmp + "->" + 'ε');

            } else {

                stack.pop();

                stack.push(tmp);

                show("" + ctmp + "->" + tmp);

            }

        }

    }　　　　　　//过滤方法将打印的字符串中e和t替换为E'和T'

    public String filter(String src) {

        if(src.contains("e") || src.contains("t")) {

            StringBuffer result = new StringBuffer();

            char item;

            for(int i = 0;i < src.length(); i++) {

                item = src.charAt(i);

                if(item == 'e') {

                    result.append("E'");

                    continue;

                }else if(item == 't') {

                    result.append("T'");

                    continue;

                }

                result.append(item);

            }

            return result.toString();

        }else {

            return src;

        }

    }

    public String work(String inputExpression) { 

        input = inputExpression + '#';

        symbol = true;

        tempBuffer.append(String.format("%-8s%-20s%-20s%-20s\r\n",

                "步骤","分析栈","剩余输入栈","所用产生式"));

        analyse();

        if (symbol) {

            tempBuffer.append("\r是正确的符号串\r");

            return tempBuffer.toString();

        } else {

            tempBuffer.append("\r不是正确的符号串\r");

            return tempBuffer.toString();

        }

    }

    public StringBuffer getTempBuffer() {

        return tempBuffer;

    }

    public void setTempBuffer(StringBuffer tempBuffer) {

        this.tempBuffer = tempBuffer;

    }

    public Stack getStack() {

        return stack;

    }

    public void setStack(Stack stack) {

        this.stack = stack;

    }

    public String[][] getTab() {

        return tab;

    }

    public void setTab(String[][] tab) {

        this.tab = tab;

    }

    public String getInput() {

        return input;

    }

    public void setInput(String ns) {

        this.input = ns;

    }

    public int getPtr() {

        return ptr;

    }

    public void setPtr(int ptr) {

        this.ptr = ptr;

    }

    public int getRow() {

        return row;

    }

    public void setRow(int row) {

        this.row = row;

    }

    public int getCol() {

        return col;

    }

    public void setCol(int col) {

        this.col = col;

    }

    public int getStep() {

        return step;

    }

    public void setStep(int step) {

        this.step = step;

    }

    public boolean isBoo() {

        return symbol;

    }

    public void setBoo(boolean boo) {

        this.symbol = boo;

    }

}

 　　三、主程序GrammarMain.java 

  package grammarAnalyze;

import java.util.Scanner;

public class GrammarMain {

    public static void main(String[] args){

        boolean isContinue = true;

        while(isContinue) {

            GrapparAnalyze analyze = new GrapparAnalyze();

            Scanner scan = new Scanner(System.in);

            System.out.println("请输入你要翻译的表达式：");

            String inputExpression = scan.nextLine();

            String srcdata = inputExpression.trim();

            if("".equals(srcdata) || srcdata == null) {

                System.out.println("输入表达式为空，请重新输入");

            }else {

                String result = analyze.work(srcdata);

                System.out.println(result);

                System.out.println("是否继续？y/n");

                String yn = scan.nextLine();

                if("no".equals(yn) || "n".equals(yn)) {

                    isContinue = false;

                }

            }

        }

    }

}

 　　四、测试运行 

转载于:https://www.cnblogs.com/ya-qiang/p/9101883.html