编译器实践(二)

本语言的文法如下:

programme -> statement blank | expr ; blank | repeat blank | function blank
statement -> if ( expr ) blank block blank magic
magic -> else blank block | yimixilu
block -> { blank programme_multi }
expr -> factor right | true | false | exec right | array right | c_shuzu
right -> double_operator expr | yimixilu
factor -> - primary | primary
primary -> ( expr ) | number | id | string
blank -> EOL blank | yimixilu
repeat -> while ( expr ) blank block
programme_multi -> programme programme_multi | yimixilu
param -> id
params -> param more_para | yimixilu
param_list -> ( params )
function -> func $ id param_list function_block blank
exec -> $ id epl
more_para -> , params | yimixilu
back -> return expr ; | yimixilu
function_block -> { blank programme_multi back blank }
epl -> ( eps )
eps -> ep emp | yimixilu
emp -> , eps | yimixilu
ep -> id | number | string | exec
shuzu -> [ number ] shuzu | yimixilu
array -> & id shuzu
c_shuzu -> 开辟数组 shuzu

然后用的语法分析算法是LL算法,会有一些冲突,构建预测分析表的代码如下:

public class PredictAnalyzeTable {
    private List<String> terminalWords;
    private List<String> nonTerminalWords;
    private List<String> grammers;
    private String[][] table;
    public PredictAnalyzeTable(Reader reader){
        grammers = new ArrayList<>();
        terminalWords = new ArrayList<>();
        nonTerminalWords = new ArrayList<>();
        LineNumberReader r = new LineNumberReader(reader);
        String line;
        try {
            while ((line = r.readLine()) != null) {
                grammers.add(line);
            }
            classify();
            initTable();
            constructTable();
        }catch (IOException io){
            io.printStackTrace();
        }
    }
    private void initTable(){
        table = new String[nonTerminalWords.size()][terminalWords.size()];
    }
    private void constructTable(){
        for (String nonTerminalWord : nonTerminalWords) {
            first(nonTerminalWord);
        }
        bug();
        for (int i = 0;i<nonTerminalWords.size();i++){
            System.out.println(Arrays.toString(table[i]));
        }
    }
    private void classify(){
        for(String s : grammers){
            String[] strings = s.split(" ");
            nonTerminalWords.add(strings[0]);
        }
        for(String s : grammers){
            String[] strings = s.split(" ");
            for (String unit : strings){
                if(nonTerminalWords.contains(unit) || terminalWords.contains(unit) || unit.equals("|") || unit.equals("->") || unit.equals("yimixilu"))
                    continue;
                terminalWords.add(unit);
            }
        }
        System.out.println(nonTerminalWords);
        System.out.println(terminalWords);
    }

    private List<String> first(String nonTerminalWord){
        List<String> list = new ArrayList<>();
        int index = nonTerminalWords.indexOf(nonTerminalWord);
        String body = grammers.get(index).split("-> ")[1];
        String [] multiRoad = body.split(" \\| ");
        for(String road : multiRoad){
            String res = road.split(" ")[0];

            if(nonTerminalWords.contains(res)){
                List<String> firsts = first(res);
                list.addAll(firsts);
                for (String f : firsts){
                    String pi = table[nonTerminalWords.indexOf(nonTerminalWord)][terminalWords.indexOf(f)];
                    if(pi != null && !pi.equals(road))
                        System.out.println("conflict!");
                    table[nonTerminalWords.indexOf(nonTerminalWord)][terminalWords.indexOf(f)] = road;
                }
            }else {
                if(!list.contains(res)){        //如果第一个字符是终结符,则在表中放入对应的生产式
                    list.add(res);
                    if(res.equals("yimixilu")){
                        continue;
                    }
                    String pi = table[nonTerminalWords.indexOf(nonTerminalWord)][terminalWords.indexOf(res)];
                    if(pi != null && !pi.equals(road))
                        System.out.println("conflict!");
                    table[nonTerminalWords.indexOf(nonTerminalWord)][terminalWords.indexOf(res)] = road;
                }
            }

        }
        return list;
    }


    private void bug(){
        table[5][0] = table[5][3] = table[5][11] = table[5][14] = "yimixilu";
        table[8][1] = table[8][2] = table[8][4] = table[8][5] = table[8][6] = table[8][10] = table[8][11] = table[8][12] = table[8][13] = table[8][15] = table[8][19] = table[8][16] = table[8][22] = "yimixilu";
        table[8][0] = "EOL blank";
        table[8][14] = "EOL blank";
        table[10][6] = table[10][19] = "yimixilu";
        table[2][14] = "yimixilu";
        table[12][3] = "yimixilu";
        table[16][3] = table[16][0] = "yimixilu";
        table[17][6] = "yimixilu";
        table[8][17] = "yimixilu";
        table[20][3] = "yimixilu";
        table[21][3] = "yimixilu";
        table[23][0] = table[23][3] = table[23][9] = "yimixilu";
        table[2][12] = "yimixilu";
        table[2][1] = "yimixilu";
        table[2][15] = "yimixilu";
        table[2][16] = "yimixilu";
        table[2][19] = "yimixilu";
    }

    public List<String> getTerminalWords() {
        return terminalWords;
    }

    public List<String> getNonTerminalWords() {
        return nonTerminalWords;
    }

    public String[][] getTable() {
        return table;
    }

}

first函数

就是教程中的First()方法

Bug函数

这里本来是计算教材中的Follow的,但是想了很久都不会,于是直接自己算文法的follow,算完在相应的位置填上,其中yimixilu代表空,在后面碰到这个会直接跳过。

运行效果:

[programme, statement, magic, block, expr, right, factor, primary, blank, repeat, programme_multi, param, params, param_list, function, exec, more_para, back, function_block, epl, eps, emp, ep, shuzu, array, c_shuzu]
[;, if, (, ), else, {, }, true, false, double_operator, -, number, id, string, EOL, while, func, $, ,, return, [, ], &, 开辟数组]

这里的第一个中括号是指代非终结符号,第二个是终结符号,终结符号甚至可以是中文。

[null, statement blank, expr ; blank, null, null, null, null, expr ; blank, expr ; blank, null, expr ; blank, expr ; blank, expr ; blank, expr ; blank, null, repeat blank, function blank, expr ; blank, null, null, null, null, expr ; blank, expr ; blank]
[null, if ( expr ) blank block blank magic, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null]
[null, yimixilu, null, null, else blank block, null, null, null, null, null, null, null, yimixilu, null, yimixilu, yimixilu, yimixilu, null, null, yimixilu, null, null, null, null]
[null, null, null, null, null, { blank programme_multi }, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null]
[null, null, factor right, null, null, null, null, true, false, null, factor right, factor right, factor right, factor right, null, null, null, exec right, null, null, null, null, array right, c_shuzu]
[yimixilu, null, null, yimixilu, null, null, null, null, null, double_operator expr, null, yimixilu, null, null, yimixilu, null, null, null, null, null, null, null, null, null]
[null, null, primary, null, null, null, null, null, null, null, - primary, primary, primary, primary, null, null, null, null, null, null, null, null, null, null]
[null, null, ( expr ), null, null, null, null, null, null, null, null, number, id, string, null, null, null, null, null, null, null, null, null, null]
[EOL blank, yimixilu, yimixilu, null, yimixilu, yimixilu, yimixilu, null, null, null, yimixilu, yimixilu, yimixilu, yimixilu, EOL blank, yimixilu, yimixilu, yimixilu, null, yimixilu, null, null, yimixilu, null]
[null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, while ( expr ) blank block, null, null, null, null, null, null, null, null]
[null, programme programme_multi, programme programme_multi, null, null, null, yimixilu, programme programme_multi, programme programme_multi, null, programme programme_multi, programme programme_multi, programme programme_multi, programme programme_multi, null, programme programme_multi, programme programme_multi, programme programme_multi, null, yimixilu, null, null, programme programme_multi, programme programme_multi]
[null, null, null, null, null, null, null, null, null, null, null, null, id, null, null, null, null, null, null, null, null, null, null, null]
[null, null, null, yimixilu, null, null, null, null, null, null, null, null, param more_para, null, null, null, null, null, null, null, null, null, null, null]
[null, null, ( params ), null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null]
[null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, func $ id param_list function_block blank, null, null, null, null, null, null, null]
[null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, $ id epl, null, null, null, null, null, null]
[yimixilu, null, null, yimixilu, null, null, null, null, null, null, null, null, null, null, null, null, null, null, , params, null, null, null, null, null]
[null, null, null, null, null, null, yimixilu, null, null, null, null, null, null, null, null, null, null, null, null, return expr ;, null, null, null, null]
[null, null, null, null, null, { blank programme_multi back blank }, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null]
[null, null, ( eps ), null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null]
[null, null, null, yimixilu, null, null, null, null, null, null, null, ep emp, ep emp, ep emp, null, null, null, ep emp, null, null, null, null, null, null]
[null, null, null, yimixilu, null, null, null, null, null, null, null, null, null, null, null, null, null, null, , eps, null, null, null, null, null]
[null, null, null, null, null, null, null, null, null, null, null, number, id, string, null, null, null, exec, null, null, null, null, null, null]
[yimixilu, null, null, yimixilu, null, null, null, null, null, yimixilu, null, null, null, null, null, null, null, null, null, null, [ number ] shuzu, null, null, null]
[null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, & id shuzu, null]
[null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, 开辟数组 shuzu]

这就是预测分析表了,相应的位置给出了当这一步是某个文法时,且碰到的符号是某个时,下一步究竟要做什么。

发布者

我乃堂堂SCUT的一条咸鱼!

发表评论

电子邮件地址不会被公开。 必填项已用*标注