2018-06-10发表2018-06-10更新编译原理26 分钟读完 (大约3929个字)0次访问

编译原理——SLR语法分析

SLR分析实验的难点在于构造SLR的分析表，构造分析表首先要求出拓广文法对应的项目集规范族，再根据项目集规范族构造分析表。虽然看上去并不是很复杂，但在实现的过程中遇到了很多问题，由于考虑问题不够全面，刚开始写的代码中有很多的bug，在调试分析的过程中花费了我很多的时间。

程序功能

输入

通过读取文件方式获取拓广文法G’，通过键盘输入获取以#结尾的待分析串。

输出

输出当前文法，以及该文法的项目集规范族、文法中所有非终结符的FOLLOW集，对当前分析串的分析过程。

LR分析

LR分析法是一种自底向上的语法分析技术，它适用于上下文无关文法的语法分析。L指的是从左向右扫描输入字符串，R指的是构造最右推导的逆过程，k指的是在决定语法分析动作时需要向前看的符号个数。

LR分析的优点

LR语法分析器几乎能够识别所有能用上下文无关文法描述的程序设计语言结构。
LR分析法是已知的最一般的无回溯移动归约语法分析法，而且可以和其他移动归约分析法一样被有效地实现。
LR分析法分析的文法类是预测分析法能分析的文法类的真超集。
在自左向右扫描输入符号串时，LR语法分析器能及时发现语法错误。

LR分析算法

LR语法分析器由输入、输出、栈、驱动程序以及包含动作和转移两部分的语法分析表组成。对于所有的LR语法分析器，驱动程序都是相同的，分析程序每次从输入缓冲区读入一个符号，并使用栈来保存形如S0X1S1X2S2…XmSm的串，其中Sm在栈顶，Xi是文法符号，Si是状态符号，在SLR分析表中，就是第一列的stateNum。栈顶的状态符号和当前的输入符号用来检索语法分析表，以决定移动归约分析的动作。

语法分析表由动作函数action和转移函数goto两部分组成。

LR分析算法可以用下面的过程表示：

输入：文法G的LR语法分析表和输入串w

输出：如果w属于L(G)，则输出w的自底向上分析，否则报错。

方法：首先把初始状态0放在语法分析器栈顶，把w#放在输入缓冲区，然后执行如下程序：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
令ip指向w#的第一个符号：
repeat forever begin
令s是栈顶状态，a是ip所指向的符号；
if action[s, a] = “移动状态s进栈” then begin
把a和S对应的stateNum依次压入栈顶；
ip++；
end
else if action[s, a] = “按文法产生式A->ß归约” then begin
从栈顶弹出2*|ß长度|个符号；
令s对应的stateNum为现在的栈顶状态；
把A和goto[stateNum, A]依次压入栈；
输出产生式A->ß;
end
end if action[s, a] = “接收” then
return；
else error()
end
接下来我们结合具体的代码以及注释看一下分析过程的实现：

static void analyze () {
//   init()主要工作是从键盘获取输入串，初始化分析栈以及输入串栈
    init();
    while ( true ) {
        String s = stAnalysis.peek();
        String a = stInputStr.peek();
//       获取分析表中[s, a]项内容
        String content = AnalysisTable.getContent(Integer.valueOf(s), a);
        /*如果content内容是接收，则说明分析成功
        如果content为空，则说明分析过程出错*/
        if (content.equals(Config.accept)) {
                outputStack(content);
                System.out.println("success");
                return;
            } else if (!content.equals("")) {
//                获取S或者r的stateNum
                int stateNum = Integer.parseInt
                    (content.substring(1, content.length()));
//           移动进栈状态时，根据算法中的步骤执行
            if (content.charAt(0) == 'S') {
                outputStack(content);
                stAnalysis.push(a);
                stAnalysis.push(String.valueOf(stateNum));
                stInputStr.pop();
            }     
//           按文法产生式归约的情况
            else if (content.charAt(0) == 'r') {
                outputStack(content);
                for (int i = 0; i < 2 * Config.productions.get(stateNum).body.length(); i++) {
                    stAnalysis.pop();
                }
                int tmp = Integer.valueOf(stAnalysis.peek());
                stAnalysis.push(Config.productions.get(stateNum).head);
                stAnalysis.push(AnalysisTable.getContent(tmp, Config.productions.get(stateNum).head));
            }
        } else {
            System.out.println("error");
            return;
        }
    }
}

构造分析表

LR文法

如果我们能够为G构造出LR语法分析表，则称G为LR文法。直观得讲，为了使一个文法是LR文法，只要保证在句柄出现在栈顶时，自左向右扫描的移动归约分析器能够及时识别它。

文法G的LR(0)项目

文法G的LR(0)项目是在G的产生式右部某处加点的产生式。

例如：产生式A->XYZ可以生产如下四个项目：

A->·XYZ

A->X·YZ

A->XY·Z

A->XYZ·

产生式A->ε只生成一个项目A->·。项目表示在语法分析过程中的某一时刻，我们已经看见了一个产生式所能推出的字符串的多大部分。例如，上面的第一个项目表示我们希望下一步从输入中看见由XYZ推出的字符串，第二个项目表示我们刚从输入中看见了由X推出的字符串，下面希望看见由YZ推出的字符串。

下面结合具体代码来看一下项目类的结构：

public class Item extends Production {
    int dotPos;
    
    Item(String head, String body, int pos) {
        super(head, body);
        this.dotPos = pos;
    }
    
    @Override
    public String toString () {
        String front = body.substring(0, dotPos);
        String behind = body.substring(dotPos, body.length());
        return head + "->" + front + "·" + behind;
    }
}

Item类继承自Production类，Production是产生式类，主要属性有产生式的左部head以及右部body，Item类中增加了一个dotPos属性，表示点在产生式右部的位置，并且重写了toString方法，调用toString方法时返回带·的产生式。

再来看一下项目集类的结构：

class ItemSet {
    ArrayList<Item> items = new ArrayList<>();

    Item get(int i) {
        return items.get(i);
    }

    void add(Item item) {
        items.add(item);
    }

    void add(Production production) {
        Item item = new Item(production.head, production.body, 0);
        if (contains(item)) {
            return;
        }
        items.add(item);
    }

    private boolean contains(Item item) {
        for (Item tmpItem : items) {
            if (tmpItem.head.equals(item.head)
                    && tmpItem.body.equals(item.body) &&
                    tmpItem.dotPos == item.dotPos)
                return true;
        }

        return false;
    }
}

项目集是类型为Item的动态数组。

SLR方法的思想

SLR方法的主要思想：首先从文法构造出识别活前缀的确定有穷自动机。我们把项目划分成一组集合，这些集合对应DFA的状态，而项目可以看成是识别活前缀的NFA的状态。我已经提到过，项目集规范族是构造语法分析表的基础，而为了构造项目集规范族，我们需要定义拓广文法，并且引入闭包运算（closure）和转移函数（go）。

拓广文法

如果文法G的开始符号是S，那么G的拓广文法G’是在G的基础上增加一个新的开始符号s和产生式s->S。新产生式的目的是来指示语法分析器什么时候应该停止分析并接受输入，即当语法分析器执行归约s->S时，分析成功。

闭包运算与转移函数

如果I是文法G的项目集，那么closure(I)是从I出发由下面两条规则构造的项目集：

初始时，把I的每个项目都加入到closure(I)中；
如果A->α·Bβ在closure(I)中，且存在产生式B->γ，若B->·γ不在closure(I)中，则将其加入closure(I)。反复运用该规则，知道没有更多的项目可加入closure(I)为止。

Go(I, X)函数定义为所有项目集[A->αX·β]的闭包。如果I是对某个活前缀γ的有效项目集，那么Go(I, X)是对活前缀γX有效的项目集。

项目集的构造

先求第一条产生式(s->S)的闭包，再从这个闭包产生的项目集开始，对每个项目集I和每个文法符号X都执行Go(I, X)运算，将结果加入到项目集中，直到没有更多的项目可以加入到项目集为止。

构造项目集规范族的过程写在ItemSets类中：

import java.util.ArrayList;

class ItemSets {

//    获取所有形如Vn->...的产生式
    private static ArrayList<Production> getProductionByVn(String Vn) {
        ArrayList<Production> productions = new ArrayList<>();
        for (Production production : Config.productions) {
            if (production.head.equals(Vn))
                productions.add(production);
        }

        return productions;
    }

    //    构造I0
    static void generateItemSets () {
        ItemSet itemSet = new ItemSet();
        itemSet.add(Config.productions.get(0));

//        *后跟非终结符
        if (Config.VN.contains(itemSet.get(0).body.substring(0, 1))) {
            ArrayList<Production> productions = 
                getProductionByVn(itemSet.get(0).body);
            for (Production production : productions) {
                itemSet.add(production);
                generateItemSetsByProduction(itemSet, production);
            }
        }

        Config.itemSets.add(itemSet);
    }

    /*若当前产生式右部的首字符为非终结符，即对应·VN的情况，
    则将通过当前产生式右部作为head获取到的产生式添加到该项目集中。*/
    private static void generateItemSetsByProduction
        (ItemSet itemSet, Production production) {
        String ch = String.valueOf(production.body.charAt(0));
        if (Config.VN.contains(ch)) {
            ArrayList<Production> productions = getProductionByVn(ch);
            for (Production tmpProduction : productions) {
                itemSet.add(tmpProduction);
            }
        }
    }

    static ItemSet Go (ItemSet itemSet, String X) {
//        保存Go(I, X)的结果
        ItemSet result = new ItemSet();
//        tmpVN用来记录当前VN是否已经在这次运算中添加
        ArrayList<String> tmpVN = new ArrayList<>();

        for (Item item : itemSet.items) {
            Item tmp;
//            当前项目符合A->α·Bβ形式
            if (item.dotPos != item.body.length() &&         String.valueOf(item.body.charAt(item.dotPos)).equals(X)) {
//                先将A->αB·β添加到项目集中
                tmp = new Item(item.head, item.body, item.dotPos + 1);
                result.add(tmp);
                if (tmp.dotPos != tmp.body.length()) {
                    if (Config.VN.contains( 
                        String.valueOf(                        tmp.body.charAt(tmp.dotPos))) && 
                        !tmpVN.contains(String.valueOf(                            tmp.body.charAt(tmp.dotPos)))) {
                        ArrayList<Production> productions = 
                            getProductionByVn(                            String.valueOf(tmp.body.charAt(tmp.dotPos)));
                        for (Production production : productions) {
                            result.add(production);
                            generateItemSetsByProduction(result, production);
                            tmpVN.add(production.head);
                        }
                    }
                }
            }
        }
        ItemSet moreVn = new ItemSet();
        for (Item item : result.items) {
            if (item.dotPos != item.body.length()                    && 
                Config.VN.contains(String.valueOf(item.body.charAt(item.dotPos)))) {
                ArrayList<Production> productions = 
                    getProductionByVn(String.valueOf(item.body.charAt(item.dotPos)));
                for (Production production : productions) {
                    moreVn.add(production);
                    generateItemSetsByProduction(moreVn, production);
                    tmpVN.add(production.head);

                }
            }
        }
        for (Item item : moreVn.items) {
            if (!isContainItem(item, result))
                result.add(item);
        }

        return result;
    }

    //    index为项目集下标
    static void buildItemSet (int index) {
        ItemSet beginItemSet = Config.itemSets.get(index);

        buildItemSetElement(beginItemSet);

//        对每个项目集进行遍历
        if (index < Config.itemSets.size() - 1) {
            buildItemSet(index + 1);
        }

    }

//    对当前项目集进行Go运算
    private static void buildItemSetElement (ItemSet itemSet) {
        for (String vn : Config.VN) {
            ItemSet result = Go(itemSet, vn);
            if (result.items.size() > 0 && contains(result))
                Config.itemSets.add(result);
        }

        for (String vt : Config.VT) {
            ItemSet result = Go(itemSet, vt);
            if (result.items.size() > 0 && contains(result))
                Config.itemSets.add(result);
        }
    }

//    当前项目集规范族中是否存在该项目集
    private static boolean contains (ItemSet itemSet) {
        boolean flag = true;
        for (ItemSet itemSet1 : Config.itemSets) {
            if (itemSet.items.size() != itemSet1.items.size()) {
                flag = false;
            } else {
                boolean tmp = true;
                for (int i = 0; i < Math.min(itemSet1.items.size(), itemSet.items.size()); i++) {
                    if (!(itemSet.items.get(i).head.equals(
                        itemSet1.items.get(i).head)                            && itemSet.items.get(i).body.equals(
                                itemSet1.items.get(i).body)                            && itemSet.items.get(i).dotPos == 
                          itemSet1.items.get(i).dotPos)) {
                        tmp = false;
                    }
                }
                if (tmp) {
                    flag = true;
                    break;
                } else {
                    flag = false;
                }
            }
        }
        return !flag;
    }

    static void outputItemSets () {
        System.out.println("项目集规范族：");
        int num = 0;
        for (ItemSet itemSet : Config.itemSets) {
            System.out.println("I" + num + ": ");
            num++;
            for (Item item : itemSet.items) {
                System.out.println(item.toString());
            }
        }
    }

//    当前项目集中是否存在该项目
    private static boolean isContainItem(Item item, ItemSet itemSet) {
        for (Item tmp : itemSet.items) {
            if (item.head.equals(tmp.head)
                    && item.body.equals(tmp.body)
                    && item.dotPos == tmp.dotPos)
                return true;
        }
        return false;
    }
}

构造SLR语法分析表

SLR是LR分析表中功能最弱但最易实现的，构造分析表的先决条件包括：拓广文法G’的项目集规范族C，每个非终结符A的Follow集。

SLR语法分析表的构造：

输入：拓广文法G’

输出：G’的SLR语法分析表函数action和goto

方法：

构造C

从Ii构造状态i，分析动作如下：

如果[A->α·aβ]在Ii中，并且Go(Ii, a) = Ij，则置action[i, a]为“移动j进栈”（Sj），这里的a必须是终结符。

如果[A->α·]在Ii中，则对FOLLOW(A)中的所有a，置action[i, a]为“归约A->α”。这里的A不能是s（起始符号）。

如果[s->S·]在Ii中，则置action[i, #]为“接收”。

如果上述规则产生的动作有冲突，那么G就不是SLR(1)文法。在这种情况下是构造不出G的语法分析器的。

对所有的非终结符A，使用下面的规则构造状态i的goto函数：

如果Go(Ii, A) = Ij，则goto[i, A] = j。

语法分析器的初始状态是从包含[s->·S]的项目集构造出的状态。

我定义了一个AnalysisItem类来存放每一个分析项目：

class AnalysisItem {
    int stateNum;
    String actionOrGoto;
    String content;

    AnalysisItem(int stateNum, String actionOrGoto, String content) {
        this.stateNum = stateNum;
        this.actionOrGoto = actionOrGoto;
        this.content = content;
    }
}

stateNum保存当前项目的状态，actionOrGoto是当前项目对应的文法符号，content是当前项目的内容。

构造分析表的具体代码，其他功能函数具体实现可以查阅项目中AnalysisTable文件：

static void generateTable () {
//    遍历项目集规范族中的每个项目
    for (ItemSet itemSet : Config.itemSets) {
        for (Item item : itemSet.items) {
//            获取该项目集在项目集规范族中的位置，即Ii的下标i
            int indexOfI = Config.itemSets.indexOf(itemSet);
            AnalysisItem analysisItem;
//            该项目是否为A->α·形式
            if (item.dotPos != item.body.length()) {
//                获取Ij = Go(I, X)
                ItemSet tmpItemSet = ItemSets.Go(itemSet, String.valueOf(item.body.charAt(item.dotPos)));
//                获取下标j
                int indexOfJ = indexOf(tmpItemSet);
//                若满足A->α·aß，且a为终结符，则置action[i, a]为Sj
                if (Config.VT.contains(String.valueOf(item.body.charAt(item.dotPos)))) {
                    analysisItem = new AnalysisItem(indexOfI, String.valueOf(item.body.charAt(item.dotPos)), "S" + Integer.toString(indexOfJ));
                    if (isContainAnalysisItem(analysisItem)) {
                        Config.analysisTable.add(analysisItem);
                    }
                }
            } else {
//                满足A->α·，且α不为起始符号，则对FOLLOW(A)中所有的a，
//                置action[i, a]为rj，j为A->α在文法中的位置
                if (!item.head.equals(Config.productions.get(0).head)
                        && Config.VN.contains(item.head)) {
                    Set set = FollowSet.getFollow(item.head);
                    int indexJ = indexOfProduction(item);
                    for (String follow : set.body) {
                        analysisItem = new AnalysisItem(indexOfI, follow, "r" + Integer.toString(indexJ));
                        if (isContainAnalysisItem(analysisItem)) {
                            Config.analysisTable.add(analysisItem);
                        }
                    }
                }
//                对s->S·，置action[i, #]为接受
                if (item.head.equals(Config.productions.get(0).head)
                        && item.body.equals(Config.productions.get(0).body)
                        && item.dotPos == 1) {
                    analysisItem = new AnalysisItem(indexOfI, Config.endSyntax, Config.accept);
                    if (isContainAnalysisItem(analysisItem)) {
                        Config.analysisTable.add(analysisItem);
                    }
                }
            }
//            对所有的非终结符，使用下面的规则构造状态i的goto函数：
//            如果Go(Ii, A) = Ij，则goto[i, A] = j。
            for (String vn : Config.VN) {
                ItemSet tmpItemSet = ItemSets.Go(itemSet, vn);
                if (tmpItemSet.items.size() > 0) {
                    int indexJ = indexOf(tmpItemSet);
                    analysisItem = new AnalysisItem(indexOfI, vn, Integer.toString(indexJ));
                    if (isContainAnalysisItem(analysisItem)) {
                        Config.analysisTable.add(analysisItem);
                    }
                }
            }
        }
    }
}

以上就是构造分析表的所有算法，我结合部分代码以及注释进行了解释，完整的项目文件请点击。

程序测试

测试用例：

文法

a,A,V,E,T,F
=,+,-,*,/,(,),i
a->A
A->V=E
E->E+T
E->E-T
E->T
T->T*F
T->T/F
T->F
F->(E)
F->i
V->i

输入串

i=i+i*(i-i)

运行结果

运行结果以文件形式保存，分别为项目集规范族itemSets.txt，分析表analyzeTable.txt以及运行结果result.txt。