编译原理生成LL1预测分析表

package com.leon;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/**
 * @author : Leon
 * @since : 2013-8-11
 * @see :
 */

public class LL1 {
    
    public String[] grammar_str;
    
    private int     token_i;
    
    private String  lambda = "lambda";
    
    public boolean[] mark_lambda(Grammar g) {
        boolean[] derives_lambda = new boolean[g.vocabulary.length];
        boolean changes;
        do {
            changes = false;
            for (int i = 0; i < g.productions.length; i++) {
                Production p = g.productions[i];
                if (!derives_lambda[index(p.lhs, g.vocabulary)]) {
                    if (p.rhs.length == 0) {
                        derives_lambda[index(p.lhs, g.vocabulary)] = true;
                        changes = true;
                        continue;
                    }
                    boolean rhs_derives_lambda = derives_lambda[index(p.rhs[0], g.vocabulary)];
                    for (int j = 1; j < p.rhs.length; j++) {
                        rhs_derives_lambda = rhs_derives_lambda && derives_lambda[index(p.rhs[j], g.vocabulary)];
                    }
                    if (rhs_derives_lambda) {
                        derives_lambda[index(p.lhs, g.vocabulary)] = true;
                        changes = true;
                    }
                }
            }
        }
        while (changes);
        return derives_lambda;
    }
    
    public Set<String> compute_first(String[] alpha, Set<String>[] first_set, Grammar g) {
        Set<String> result = new HashSet<String>();
        int k = alpha.length;
        if (k == 0) {
            result.add(lambda);
        }
        else {
            result.addAll(first_set[index(alpha[0], g.vocabulary)]);
            int i;
            for (i = 1; i < alpha.length && first_set[index(alpha[i - 1], g.vocabulary)].contains(lambda); i++) {
                result.addAll(first_set[index(alpha[i], g.vocabulary)]);
                if (result.contains(lambda)) {
                    result.remove(lambda);
                }
            }
            
            if (i == alpha.length && first_set[index(alpha[alpha.length - 1], g.vocabulary)].contains(lambda)) {
                result.add(lambda);
            }
        }
        return result;
    }
    
    @SuppressWarnings("unchecked")
    public Set<String>[] fill_first_set(Grammar g) {
        Set<String>[] first_set = new Set[g.vocabulary.length];
        for (int i = 0; i < first_set.length; i++) {
            if (first_set[i] == null) {
                first_set[i] = new HashSet<String>();
            }
        }
        boolean[] derives_lambda = mark_lambda(g);
        for (int i = 0; i < g.nonterminals.length; i++) {
            String nonterminal = g.nonterminals[i];
            if (derives_lambda[index(nonterminal, g.vocabulary)]) {
                first_set[index(nonterminal, g.vocabulary)].add(lambda);
            }
        }
        for (int i = 0; i < g.terminals.length; i++) {
            String terminal = g.terminals[i];
            first_set[index(terminal, g.vocabulary)].add(terminal);
            for (int j = 0; j < g.nonterminals.length; j++) {
                String nonterminal = g.nonterminals[j];
                if (have_derives(nonterminal, terminal, g)) {
                    first_set[index(nonterminal, g.vocabulary)].add(terminal);
                }
            }
        }
        boolean changes;
        do {
            changes = false;
            for (int i = 0; i < g.productions.length; i++) {
                Production p = g.productions[i];
                int before_size = first_set[index(p.lhs, g.vocabulary)].size();
                first_set[index(p.lhs, g.vocabulary)].addAll(compute_first(p.rhs, first_set, g));
                int after_size = first_set[index(p.lhs, g.vocabulary)].size();
                if (before_size != after_size) {
                    changes = true;
                }
            }
        }
        while (changes);
        return first_set;
    }
    
    @SuppressWarnings("unchecked")
    public Set<String>[] fill_follow_set(Grammar g, Set<String>[] first_set) {
        
        Set<String>[] follow_set = new Set[g.nonterminals.length];
        for (int i = 0; i < follow_set.length; i++) {
            if (follow_set[i] == null) {
                follow_set[i] = new HashSet<String>();
            }
        }
        follow_set[index(g.start_symbol, g.nonterminals)].add(lambda);
        boolean changes;
        do {
            changes = false;
            for (int i = 0; i < g.productions.length; i++) {
                Production p = g.productions[i];
                for (int j = 0; j < p.rhs.length; j++) {
                    String symbol = p.rhs[j];
                    if (index(symbol, g.nonterminals) != -1) {
                        String[] beta = build_beta(j, p.rhs);
                        Set<String> compute_first = compute_first(beta, first_set, g);
                        Set<String> set = new HashSet<String>(compute_first);
                        set.remove(lambda);
                        int before_size = follow_set[index(symbol, g.nonterminals)].size();
                        follow_set[index(symbol, g.nonterminals)].addAll(set);
                        if (compute_first.contains(lambda)) {
                            follow_set[index(symbol, g.nonterminals)].addAll(follow_set[index(p.lhs, g.nonterminals)]);
                        }
                        int after_size = follow_set[index(symbol, g.nonterminals)].size();
                        if (before_size != after_size) {
                            changes = true;
                        }
                    }
                }
            }
        }
        while (changes);
        return follow_set;
    }
    
    public void predict(Production p, Set<String>[] first_set, Set<String>[] follow_set, Grammar g, int p_index,
                        int[][] m) {
        Set<String> set = new HashSet<String>();
        for (int i = 0; i < p.rhs.length; i++) {
            if (first_set[index(p.rhs[i], g.vocabulary)].contains(lambda)) {
                continue;
            }
            else {
                set.addAll(first_set[index(p.rhs[i], g.vocabulary)]);
                break;
            }
        }
        if (set.size() == 0) {
            set.addAll(follow_set[index(p.lhs, g.nonterminals)]);
        }
        for (Iterator<String> iterator = set.iterator(); iterator.hasNext();) {
            String symbol = iterator.next();
            m[index(symbol, g.terminals)][index(p.lhs, g.nonterminals)] = p_index;
        }
    }
    
    public void gen_action(String[] symbol, Grammar g) {
        if (symbol.length == 0) {
            System.out.println("\t\t\t/* null */");
        }
        else {
            for (int i = 0; i < symbol.length; i++) {
                if (is_terminal(symbol[i], g)) {
                    System.out.println("\t\t\tmatch(\"" + symbol[i] + "\");");
                }
                else {
                    System.out.println("\t\t\t" + symbol[i] + "();");
                }
            }
        }
    }
    
    public void make_parsing_proc(String nonterminal, int[][] m, Grammar g) {
        System.out.println("public void " + nonterminal + "(){");
        System.out.println("\tString tok = current_token();");
        System.out.println("\tswitch(tok){");
        for (int j = 0; j < g.terminals.length; j++) {
            for (int i = 0; i < g.nonterminals.length; i++) {
                if (g.nonterminals[i].equals(nonterminal)) {
                    if (m[j][i] > 0) {
                        System.out.println("\t\tcase \"" + g.terminals[j]+"\":");
                        Production selected_p = g.productions[m[j][i] - 1];
                        gen_action(selected_p.rhs, g);
                        System.out.println("\t\t\tbreak;");
                    }
                    break;
                }
            }
        }
        System.out.println("\t\tdefault:");
        System.out.println("\t\t\tsyntax_error(tok);");
        System.out.println("\t\t\tbreak;");
        System.out.println("\t}");
        System.out.println("}");
    }
    
    public void ll1_driver(Grammar g, int[][] m) {
        Stack<String> stack = new Stack<String>();
        stack.push(g.start_symbol);
        String a = next_token();
        while (!stack.is_empty()) {
            System.out.println(stack);
            String symbol = stack.pop();
            if (is_nonterminal(symbol, g) && m[index(a, g.terminals)][index(symbol, g.nonterminals)] > 0) {
                Production p = g.productions[m[index(a, g.terminals)][index(symbol, g.nonterminals)] - 1];
                String[] rhs = p.rhs;
                for (int i = rhs.length-1; i >= 0; i--) {
                    stack.push(rhs[i]);
                }
            }
            else if (symbol.equals(a)) {
                a = next_token();
            }
            else {
                System.out.println("syntax error");
            }
        }
    }
    
    public String next_token() {
        if(token_i<grammar_str.length){
            return grammar_str[token_i++];
        }
        return null;
    }
    
    private boolean is_nonterminal(String symbol, Grammar g) {
        for (int i = 0; i < g.nonterminals.length; i++) {
            if (g.nonterminals[i].equals(symbol)) {
                return true;
            }
        }
        return false;
    }
    
    private boolean is_terminal(String symbol, Grammar g) {
        for (int i = 0; i < g.terminals.length; i++) {
            if (g.terminals[i].equals(symbol)) {
                return true;
            }
        }
        return false;
    }
    
    private boolean have_derives(String nonterminal, String terminal, Grammar g) {
        for (int i = 0; i < g.productions.length; i++) {
            Production production = g.productions[i];
            if (production.lhs.equals(nonterminal) && production.rhs.length > 0 && production.rhs[0].equals(terminal)) {
                return true;
            }
        }
        return false;
    }
    
    private int index(String symbol, String[] vocabulary) {
        for (int i = 0; i < vocabulary.length; i++) {
            if (symbol.equals(vocabulary[i])) {
                return i;
            }
        }
        return -1;
    }
    
    private String[] build_beta(int j, String[] rhs) {
        String[] result = new String[rhs.length - (j + 1)];
        int k = 0;
        for (int i = j + 1; i < rhs.length; i++) {
            result[k++] = rhs[i];
        }
        return result;
    }
    
}

package com.leon;

import java.util.Set;


/** @author : Leon
 * @since   : 2013-8-11
 * @see    : 
 */

public class Main {
    public static void main(String[] args) {
        new Main().do_third_gammar();
    }
    
    public void do_first_gammar(){
        LL1 c= new LL1();
        Grammar g = new Grammar();
        g.nonterminals = new String[]{"S","B","C"};
        g.terminals = new String[]{"a","b","c","d","e"};
        g.start_symbol = "S";
        g.vocabulary = new String[]{"S","B","C","a","b","c","d","e"};
        Production p1 = new Production("S",new String[]{"a","S","e"});
        Production p2 = new Production("S",new String[]{"B"});
        Production p3 = new Production("B",new String[]{"b","B","e"});
        Production p4 = new Production("B",new String[]{"C"});
        Production p5 = new Production("C",new String[]{"c","C","e"});
        Production p6 = new Production("C",new String[]{"d"});
        g.productions = new Production[]{p1,p2,p3,p4,p5,p6};
        Set<String>[] first_set = c.fill_first_set(g);
        for (int i = 0; i < first_set.length; i++) {
            Set<String> set = first_set[i];
            System.out.println(set);
        }
        Set<String>[] follow_set = c.fill_follow_set(g, first_set);
        for (int i = 0; i < follow_set.length; i++) {
            Set<String> set = follow_set[i];
            System.out.println(set);
        }
    }
    
    public void do_second_gammar(){
        LL1 c= new LL1();
        Grammar g = new Grammar();
        g.nonterminals = new String[]{"S","A","B"};
        g.terminals = new String[]{"a","b","c"};
        g.start_symbol = "S";
        g.vocabulary = new String[]{"S","A","B","a","b","c"};
        Production p1 = new Production("S",new String[]{"A","B","c"});
        Production p2 = new Production("A",new String[]{"a"});
        Production p3 = new Production("A",new String[]{});
        Production p4 = new Production("B",new String[]{"b"});
        Production p5 = new Production("B",new String[]{});
        g.productions = new Production[]{p1,p2,p3,p4,p5};
        Set<String>[] first_set = c.fill_first_set(g);
        for (int i = 0; i < first_set.length; i++) {
            Set<String> set = first_set[i];
            System.out.println(set);
        }
        Set<String>[] follow_set = c.fill_follow_set(g, first_set);
        for (int i = 0; i < follow_set.length; i++) {
            Set<String> set = follow_set[i];
            System.out.println(set);
        }
    }
    
    public void do_third_gammar(){
        LL1 c= new LL1();
        Grammar g = new Grammar();
        g.nonterminals = new String[]{"program","statement_list","statement","statement_tail","expression","id_list","expr_list","id_tail","expr_tail","primary","primary_tail","add_op","system_goal"};
        g.terminals = new String[]{"ID","INTLIT",":=",",",";","+","*","(",")","begin","end","read","write","$"};
        g.start_symbol = "system_goal";
        g.vocabulary = new String[]{"program","statement_list","statement","statement_tail","expression","id_list","expr_list","id_tail","expr_tail","primary","primary_tail","add_op","system_goal","ID","INTLIT",":=",",",";","+","*","(",")","begin","end","read","write","$"};
        Production p1 = new Production("program",new String[]{"begin","statement_list","end"});
        Production p2 = new Production("statement_list",new String[]{"statement","statement_tail"});
        Production p3 = new Production("statement_tail",new String[]{"statement","statement_tail"});
        Production p4 = new Production("statement_tail",new String[]{});
        Production p5 = new Production("statement",new String[]{"ID",":=","expression",";"});
        Production p6 = new Production("statement",new String[]{"read","(","id_list",")",";"});
        Production p7 = new Production("statement",new String[]{"write","(","expr_list",")",";"});
        Production p8 = new Production("id_list",new String[]{"ID","id_tail"});
        Production p9 = new Production("id_tail",new String[]{",","ID","id_tail"});
        Production p10 = new Production("id_tail",new String[]{});
        Production p11 = new Production("expr_list",new String[]{"expression","expr_tail"});
        Production p12 = new Production("expr_tail",new String[]{",","expression","expr_tail"});
        Production p13 = new Production("expr_tail",new String[]{});
        Production p14 = new Production("expression",new String[]{"primary","primary_tail"});
        Production p15 = new Production("primary_tail",new String[]{"add_op","primary","primary_tail"});
        Production p16 = new Production("primary_tail",new String[]{});
        Production p17 = new Production("primary",new String[]{"(","expression",")"});
        Production p18 = new Production("primary",new String[]{"ID"});
        Production p19 = new Production("primary",new String[]{"INTLIT"});
        Production p20 = new Production("add_op",new String[]{"+"});
        Production p21 = new Production("add_op",new String[]{"*"});
        Production p22 = new Production("system_goal",new String[]{"program","$"});
        g.productions = new Production[]{p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15,p16,p17,p18,p19,p20,p21,p22};
        Set<String>[] first_set = c.fill_first_set(g);
        for (int i = 0; i < first_set.length; i++) {
            Set<String> set = first_set[i];
            System.out.println(set);
        }
        System.out.println("===============================");
        Set<String>[] follow_set = c.fill_follow_set(g, first_set);
        for (int i = 0; i < follow_set.length; i++) {
            Set<String> set = follow_set[i];
            System.out.println(set);
        }
        System.out.println("===============================");
        System.out.println(g.terminals.length);
        System.out.println(g.nonterminals.length);
        System.out.println("===============================");
        int[][] m = new int[g.terminals.length][g.nonterminals.length];
        for (int i = 0; i < g.productions.length; i++) {
            c.predict(g.productions[i], first_set, follow_set, g, i+1, m);
        }
        for (int i = 0; i < m.length; i++) {
            for (int j = 0; j < m[i].length; j++) {
                System.out.print(m[i][j]+",");
            }
            System.out.println();
        }
        
        for (int i = 0; i < g.nonterminals.length; i++) {
            c.make_parsing_proc(g.nonterminals[i], m, g);
        }
        c.grammar_str = "begin ID := ID * INTLIT + ID ; end $".split(" ");
        for (int i = 0; i < c.grammar_str.length; i++) {
            System.out.println(c.grammar_str[i]);
        }
        c.ll1_driver(g, m);
    }
}