icewing

编译原理语法分析器 - LL(1) 文法 (Java版)
LL(1)文法既不是二义性的,也不含左递归,对LL(1)文法的所有句子均可进行确定的自顶向下语法分析。
扫描右侧二维码阅读全文
31
2019/05

编译原理语法分析器 - LL(1) 文法 (Java版)

LL(1)文法既不是二义性的,也不含左递归,对LL(1)文法的所有句子均可进行确定的自顶向下语法分析。

原始文法

E→E+T|E/T|T
T→T-F|T*F|F
F→(E)|i

消除左递归

E→TM
M→+TM|/TM|ε
T→FN
N→-FN|*FN|ε
F→(E)|i

First集和Follow集

First(E)={(,i}    Follow(E)={),#}
First(T)={(,i}    Follow(T)={+,/,#}
First(F)={(,i}    Follow(F)={-,*,#}
First(M)={+,/,ε}  Follow(M)={),#}
First(N)={-,*,ε}  Follow(N)={+,/,#}

预测分析表

1

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Work1 {

    /*
     * 原始文法:
     *
     * E→E+T|E/T|T
     * T→T-F|T*F|F
     * F→(E)|i
     */

    /*
     * 消除左递归
     *
     * E→TM
     * M→+TM|/TM|ε
     * T→FN
     * N→-FN|*FN|ε
     * F→(E)|i
     */

    /*
     * 求First集和Follow集
     *
     * First(E)={(,i}    Follow(E)={),#}
     * First(T)={(,i}    Follow(T)={+,/,#}
     * First(F)={(,i}    Follow(F)={-,*,#}
     * First(M)={+,/,ε} Follow(M)={),#}
     * First(N)={-,*,ε} Follow(N)={+,/,#}
     */

    // 构造预测分析表
    private String[] Vt = {"+", "/", "-", "*", "(", ")", "i"}; // 终结符
    private String[] Vn = {"E", "T", "F", "M", "N"};    //非终结符
    private String[][] M = {
            //+=0      /=1       -=2        *=3      (=4       )=5    i=6    #=7
            { "",      "",       "",        "",      "TM",     "",    "TM",  ""},      //E=0
            { "",      "",       "",        "",      "FN",     "",    "FN",  ""},      //T=1
            { "",      "",       "",        "",      "(E)",    "",    "i",   ""},      //F=2
            { "+TM",   "/TM",    "",        "",      "",       "ε",  "",    "ε"},     //M=3
            { "ε",    "ε",     "-FN",     "*FN",   "",       "",    "",    "ε"}    //N=4
    };

    //开始分析
    private String[] stack = new String[256];
    private String stack_top;
    private int stack_ptr = -1;
    private int ptr = 0;    // 下标
    private char c_temp;
    private int Vt_code;
    private int Vn_code;

    //获取字符串,并确定分析仪表的列
    private void get_char(String sentence){
        c_temp = sentence.charAt(ptr);
        ptr++;
        if(c_temp == '+'){
            Vt_code = 0;
        }else if(c_temp == '/'){
            Vt_code = 1;
        }else if(c_temp == '-'){
            Vt_code = 2;
        }else if(c_temp == '*'){
            Vt_code = 3;
        }else if(c_temp == '('){
            Vt_code = 4;
        }else if(c_temp == ')'){
            Vt_code = 5;
        }else if(c_temp == 'i'){
            Vt_code = 6;
        }else if(c_temp == '#'){
            Vt_code = 7;
        }
    }
    //存入stack数组
    private void push(String str){
        stack_ptr++;
        stack[stack_ptr] = str;
    }
    //置空stack数组,并确定分析表的行
    private void pull(){
        stack_top = stack[stack_ptr];
        stack[stack_ptr] = null;
        stack_ptr--;

        if(stack_top.equals("E")){
            Vn_code = 0;
        }else if(stack_top.equals("T")){
            Vn_code = 1;
        }else if(stack_top.equals("F")){
            Vn_code = 2;
        }else if(stack_top.equals("M")){
            Vn_code = 3;
        }else if(stack_top.equals("N")){
            Vn_code = 4;
        }
    }

    //判断是不是终结符
    private boolean isVt(String str){
        for(int i = 0; i < Vt.length; i++){
            if(str.equals(Vt[i])){
                return true;
            }
        }
        return false;
    }

    //判断是不是非终结符
    private boolean isVn(String str){
        for(int i = 0; i < Vn.length; i++){
            if(str.equals(Vn[i])){
                return true;
            }
        }
        return false;
    }


    public boolean SyntaxAnalyse(String sentence){

        push("#");
        push("E");
        get_char(sentence);
        boolean flag = true;
        while(flag){
            pull();
            if(isVt(stack_top)){
                if(stack_top.equals(String.valueOf(c_temp))){
                    get_char(sentence);
                }else{
                    return false;
                }
            }else if(stack_top.equals("#")){
                if(stack_top.equals(String.valueOf(c_temp))){
                    flag = false;
                }else{
                    return false;
                }
            }else if(M[Vn_code][Vt_code] != null){
                if(!M[Vn_code][Vt_code].equals("ε")){
                    for(int i = M[Vn_code][Vt_code].length() - 1; i >= 0 ; i--){
                        push(String.valueOf(M[Vn_code][Vt_code].charAt(i)));
                    }
                }
            }else{
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        while(true){
            Work1 sa = new Work1();
            System.out.print("请输入语句:");
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            String str = in.readLine();
            String sentence = str + "#";
            boolean result = sa.SyntaxAnalyse(sentence);

            if(result == true){
                System.out.println(str + " 是正确表达式!");
            }else if(result == false){
                System.out.println(str + " 是错误表达式!");
            }else{
                System.out.println("分析程序出现错误!");
            }
        }
    }

}

运行结果

2

最后修改:2019 年 05 月 31 日 03 : 41 PM
生活需要一些仪式感,比如手冲一杯咖啡:)

发表评论