D 的个人博客

但行好事莫问前程

  menu
417 文章
3446695 浏览
4 当前访客
ღゝ◡╹)ノ❤️
/  

LR(0)文法分析程序[00原创]

编译原理的实验。。。。

package cn.edu.ynu.sei.lr.lr0;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/
 * LR(0)主分析程序
 * 参看《编译原理》清华大学出版社 1998 版
 * @author 88250
 */
public class LR0
{
    /
     * 产生式大小
     */
    public static int PRODUCT_SIZE;

    /
     * 产生式集
     */
    public static final List<Product> PRODUCTS = new ArrayList<Product>();

    /
     * 开始文法符号<br>
     * <b>这里的 S 已经是拓广文法的开始符号<b>
     */
    public static final String START = "S";

    /
     * 终结符集合，即 Vt
     */
    public static final List<String> TERMINATORS = new ArrayList<String>();

    /
     * 非终结符集合，即 Vn
     */
    public static final List<String> NTERMINATORS = new ArrayList<String>();

    /
     * 项目集规范族<br>
     * <b>注意：</b>每个项目集所在的下标即状态编号
     */
    public static List<ItemSet> itemSetFamilies = new ArrayList<ItemSet>();

    /
     * 分析表
     */
    public static List<AnalysisItem> analysisTable = new ArrayList<AnalysisItem>();

    /
     * 分析过程中使用的状态栈
     */
    public static Stack<Integer> stateStack = new Stack<Integer>();

    /
     * 分析过程中使用的符号栈
     */
    public static Stack<String> symbolStack = new Stack<String>();

    /
     * 根据给定右部返回产生式集中左部与之相同的产生式
     * @param rightPart 给定右部
     * @return 产生式集合
     */
    public static List<Product> getProductByRightPart(String rightPart)
    {
        List<Product> ret = new ArrayList<Product>();

        for (Product p : PRODUCTS)
        {
            if (p.leftPart.equals(rightPart))
            {
                ret.add(p);
            }
        }
        return ret;
    }

    /
     * 初始化项目集规范族
     */
    public static void initItemSetFamilies()
    {
        ItemSet is = new ItemSet();
        is.add(PRODUCTS.get(0));

        if (NTERMINATORS.contains(is.get(0).rightPart.substring(0, 1)))
        {// 圆点后是非终结符
            List<Product> ps = getProductByRightPart(is.get(0).rightPart);
            for (Product p : ps)
            {
                is.add(p);
            }
        }
        itemSetFamilies.add(is);
    }

    /
     * 显示项目集规范族
     */
    public static void displayItemSetFamilies()
    {
        System.out.println("项目集规范族如下：");
        int i = 0;
        for (ItemSet is : itemSetFamilies)
        {
            System.out.println("--------------");
            System.out.println("I" + i + ": ");
            i++;
            for (Item item : is.items)
            {
                System.out.println(item.toString());
            }
        }
        System.out.println("--------------");
    }

    /
     * 初始化推导式，即使用文法规定的产生式 P 初始化推导式集合
     */
    public static void initG()
    {
        // 初始化产生式
        PRODUCTS.add(new Product(START, "E"));
        PRODUCTS.add(new Product("E", "aA"));
        PRODUCTS.add(new Product("E", "bB"));
        PRODUCTS.add(new Product("A", "cA"));
        PRODUCTS.add(new Product("A", "d"));
        PRODUCTS.add(new Product("B", "cB"));
        PRODUCTS.add(new Product("B", "d"));
        PRODUCT_SIZE = PRODUCTS.size();

        // 初始化终结符
        TERMINATORS.add("a");
        TERMINATORS.add("b");
        TERMINATORS.add("c");
        TERMINATORS.add("d");

        // 初始化非终结符
        NTERMINATORS.add("S");
        NTERMINATORS.add("E");
        NTERMINATORS.add("A");
        NTERMINATORS.add("B");
    }

    /
     * 显示文法的产生式
     */
    public static void displayG()
    {
        System.out.println("开始符号：" + START);
        System.out.println("文法的产生式如下：");
        for (Product p : PRODUCTS)
        {
            System.out.println(p.toString());
        }
    }

    /
     * @param args the command line arguments
     */
    public static void main(String[] args)
    {
        initG();
        displayG();
        initItemSetFamilies();
        buildItemSetCore(0);
        displayItemSetFamilies();
        buildAnalysisTable();
        displayAnalysisTable();
        initStack();
        if (match("bccd#"))
        {
            System.out.println("匹配成功！");
        }
        else
        {
            System.out.println("匹配失败！！！！");
        }

    }

    /
     * 构造核项目
     * <p>核项目的定义参看课本 P128</p>
     * @param itemSetIndex 项目集索引，即项目集的下标
     */
    public static void buildItemSetCore(int itemSetIndex)
    {
        ItemSet startItemSet = itemSetFamilies.get(itemSetIndex);

        List<Item> cores = getCopyOfItems((startItemSet.items));
        for (Item item : cores)
        {
            if (item.rightPart.length() == item.dotPos)
            {// 规约项目
                continue;
            }
            ItemSet is = new ItemSet();
            item.dotPos++;
            is.add(item);

            if (contains(item))
            {// 如果这个核项目已经存在，说明在规范族中已经存在包含该核项目的项目集
                // 此时，应该跳过它，避免了自己迭代自己而造成的无限循环
                continue;
            }
            // 新建一个核项目
            itemSetFamilies.add(is);
            // 构建这个核项目所在的项目集
            buildItemSetElements(is);
        }

        if (itemSetIndex < itemSetFamilies.size() - 1)
        {// 直到不再增大为止
            buildItemSetCore(itemSetIndex + 1);
        }
    }

    /
     * 返回给定项目集合的副本
     * @param list
     * @return 给定项目集的副本
     */
    public static List<Item> getCopyOfItems(List<Item> list)
    {
        List<Item> ret = new ArrayList<Item>();
        for (Item i : list)
        {
            Item item = new Item(i.leftPart, i.rightPart, i.dotPos);
            ret.add(item);
        }
        return ret;
    }

    /
     * 构造一个项目集
     * @param is
     */
    public static void buildItemSetElements(ItemSet is)
    {
        Item item = is.get(0);
        int dotPos = item.dotPos;
        if (item.rightPart.length() == dotPos)
        {
            return;
        }
        if (NTERMINATORS.contains(item.rightPart.substring(dotPos, dotPos + 1)))
        {// 圆点后是非终结符
            String sysm = item.rightPart.substring(dotPos, dotPos + 1);
            List<Product> ps = getProductByRightPart(sysm);
            for (Product p : ps)
            {
                is.add(p);

            }
        }
    }

    /
     * 判断当前项目集规范族中是否已经包含给定项目为核项目的项目集
     * @param coreItem 给定的核项目
     * @return 如果包含返回<code>true</code>，否则返回<code>false</code>
     */
    public static boolean contains(Item coreItem)
    {
        for (ItemSet is : itemSetFamilies)
        {
            if (is.get(0).leftPart.equals(coreItem.leftPart) && is.get(0).rightPart.equals(coreItem.rightPart) && is.get(0).dotPos == coreItem.dotPos)
            {
                return true;
            }
        }
        return false;
    }

    /**
     * 构造文法的分析表
     */
    public static void buildAnalysisTable()
    {
        for (int i = 0; i < itemSetFamilies.size(); i++)
        {
            ItemSet is = itemSetFamilies.get(i);
            AnalysisItem ai = new AnalysisItem();
            ai.stateNum = i;
            for (int j = 0; j < is.items.size(); j++)
            {
                Item item = is.get(j);
                int dotPos = item.dotPos;
                if (dotPos == item.rightPart.length())
                {// 规约项目
                    if (item.rightPart.equals(PRODUCTS.get(0).rightPart))
                    {// 如果该项目右部与拓广文法中第一个产生式右部相同，说明是接受项目
                        ai.add("#", Integer.MAX_VALUE);
                        continue;
                    }
                    int numOfProduct = 0 - getNumOfProduct(item.leftPart, item.rightPart); // 规约的时候用负数表示
                    for (int k = 0; k < NTERMINATORS.size(); k++)
                    {
                        String nterminator = NTERMINATORS.get(k);
                        ai.add(nterminator, numOfProduct);
                    }
                    ai.add("#", numOfProduct);

                    continue;
                }
                else
                {// 移进项目
                    String afterDotPos = item.rightPart.substring(dotPos, dotPos + 1);
                    int numOfItemSet = getNumOfItemSet(item, afterDotPos);
                    ai.add(afterDotPos, numOfItemSet);
                    continue;

                }
            }
            analysisTable.add(ai);
        }
    }

    /**
     * 显示文法的分析表
     */
    public static void displayAnalysisTable()
    {
        System.out.println("分析表如下：");
        for (int k = 0; k < analysisTable.size(); k++)
        {
            AnalysisItem ai = analysisTable.get(k);
            System.out.println("-------------");
            System.out.println("状态" + k);
            for (int i = 0; i < ai.symbolAndActOrGoStateNum.size(); i++)
            {
                System.out.println("{" + ai.symbolAndActOrGoStateNum.get(i).grammaticalSymbol + " " + ai.symbolAndActOrGoStateNum.get(i).ActOrGoStateNum + "}");
            }
        }
    }

    /**
     * 返回符合给定圆点位置以及给定圆点位置之前一个文法符号的项目集编号
     * @param itm
     * @param afterDotPos  给定圆点位置之前的一个文法符号
     * @return 项目集编号，如果不存在符合给定的项目集则返回<code>Integer.MIN_VALUE</code>
     * @see java.lang.Integer.MIN_VALUE
     */
    public static int getNumOfItemSet(Item itm, String afterDotPos)
    {
        for (int i = 0; i < itemSetFamilies.size(); i++)
        {
            ItemSet is = itemSetFamilies.get(i);
            for (int j = 0; j < is.items.size(); j++)
            {
                Item item = is.get(j);
                if (item.dotPos >= 1 && (item.dotPos <= item.rightPart.length()) && (itm.leftPart.equals(item.leftPart)))
                {// 至少移进过一次
                    String beforeDotPos = item.rightPart.substring(item.dotPos - 1, item.dotPos);
                    if (beforeDotPos.equals(afterDotPos))
                    {
                        return i;   // 返回项目编号
                    }
                }
            }
        }
        return Integer.MIN_VALUE;
    }

    /**
     * 返回给定产生式的编号
     * @param leftPart 产生式左部
     * @param rightPart 产生式右部
     * @return 产生式编号，如果出错则返回<code>Integer.MIN_VALUE</code>
     * @see java.lang.Integer.MIN_VALUE
     */
    public static int getNumOfProduct(String leftPart, String rightPart)
    {
        for (int i = 0; i < PRODUCT_SIZE; i++)
        {
            Product p = PRODUCTS.get(i);
            if (p.leftPart.equals(leftPart) && p.rightPart.equals(rightPart))
            {
                return i;
            }
        }
        return -1;
    }

    /**
     * 根据当前需要处理的文法符号查找分析表，给出下一个要转换的状态编号
     * @param curSymbol 当前的文法符号
     * @param curStateNum 当前的状态
     * @return 找到的话返回 GO 状态编号，否则返回<code>java.lang.Integer.MIN_VALUE</code>
     */
    public static int findGoState(String curSymbol, int curStateNum)
    {
        for (AnalysisItem ai : analysisTable)
        {
            if (ai.stateNum == curStateNum)
            {
                for (SymbolAndActOrGoStateNum goFunction : ai.symbolAndActOrGoStateNum)
                {
                    if (goFunction.grammaticalSymbol.equals(curSymbol))
                    {
                        return goFunction.ActOrGoStateNum;
                    }
                }
            }
        }
        return Integer.MIN_VALUE;
    }

    /**
     * 对于输入串进行分析处理<br>
     * 参看课本 P131(5)
     * 这里的分析串是以'#'结束的
     * @param is Input String，输入串
     * @return 如果输入串通过了语法分析则返回<code>true</code>，否则返回<code>false</code>
     */
    public static boolean match(String is)
    {
        if (is.isEmpty())
        {
            is = "#";
        }
        String currentSymbol = is.substring(0, 1);  // 获取当前要处理的文法符号
        int goStateNum = findGoState(currentSymbol, stateStack.peek());
        displayStateStack();
        System.out.print(" | ");
        displaySymbolStack();
        System.out.println(" | " + is);
        if (goStateNum == Integer.MIN_VALUE)
        {// 5)
            return false;
        }
        if (goStateNum > 0 && TERMINATORS.contains(currentSymbol))
        {// 1)
            stateStack.push(goStateNum);
            symbolStack.push(currentSymbol);
        }
        if (goStateNum < 0 && (TERMINATORS.contains(currentSymbol) || currentSymbol.equals("#")))
        {// 2)
            int k = PRODUCTS.get(0 - goStateNum).rightPart.length();

            for (int i = 0; i < k; i++)
            {
                stateStack.pop();
                symbolStack.pop();
            }
            // 进行规约
            symbolStack.push(PRODUCTS.get(0 - goStateNum).leftPart);
            stateStack.push(findGoState(PRODUCTS.get(0 - goStateNum).leftPart,
                                        stateStack.peek()));
        }
        if (goStateNum == Integer.MAX_VALUE && currentSymbol.equals("#"))
        {// 3)
            return true;
        }
        if (goStateNum > 0 && NTERMINATORS.contains(currentSymbol))
        {// 4)
            symbolStack.push(currentSymbol);
            stateStack.push(goStateNum);
        }

        return match(is.substring(1, is.length()));
    }

    /**
     * 显示符号栈
     */
    public static void displaySymbolStack()
    {
        for (int i = 0; i < symbolStack.size(); i++)
        {
            System.out.print(symbolStack.get(i));
        }
    }

    /**
     * 显示状态栈
     */
    public static void displayStateStack()
    {
        for (int i = 0; i < stateStack.size(); i++)
        {
            System.out.print(stateStack.get(i));
        }
    }

    /**
     * 初始化符号栈和状态栈
     */
    public static void initStack()
    {
        symbolStack.push("#");
        stateStack.push(0);
        System.out.println("分析过程如下：");
        System.out.println("状态栈  ｜  符号栈 ｜ 输入串");
    }
}

package cn.edu.ynu.sei.lr.lr0;

import java.util.ArrayList;
import java.util.List;

/**
 * 预测分析表里的分析项
 * <p>根据课本 P131，预测分析表分为三个部分，表头如下：<br>
 * <table border="1">
 *  <tr>
 *      <td>状态</td><td>ACTION</td><td>GOTO</td>
 *  </tr>
 * </table>
 * 这个类描述了分析表中的一个项。例如表示当前状态为 0，输入字符移进／规约编号为(a, S2)，(b, r1)的项：<br>
 * (0, {(a, 2), (b, -1)})  其中，'{}'内部的是一个列表，在 ACTION 或 GOTO 中出现的移进（Sn）都用正数表示，<br>
 * 而规约(rn)用负数表示，接受状态用<code>java.lang.Integer.MAX_VALUE<code>表示
 * </p>
 * @see #java.lang.Integer.MAX_VALUE
 * @author 88250
 * @version 1.0.1.1, Nov 12, 2007
 */
public class AnalysisItem
{
    /**
     * 状态编号，即项目集规范族里的项目集编号（下标）
     * @see cn.edu.ynu.sei.lrparser.lr0.Main#itemSetFamilies
     */
    public int stateNum;

    /**
     * 语法符号和移进下标或规约产生式编号集，即 ACTION 表或是 GOTO 表的列值
     */
    List<SymbolAndActOrGoStateNum> symbolAndActOrGoStateNum = new ArrayList<SymbolAndActOrGoStateNum>();

    /**
     * 添加一个文法符号跳转状态编号项
     * @param grammaticalSymbol
     * @param actOrGoStateNum
     */
    public void add(String grammaticalSymbol, int actOrGoStateNum)
    {
        symbolAndActOrGoStateNum.add(new SymbolAndActOrGoStateNum(grammaticalSymbol, actOrGoStateNum));
    }
}

package cn.edu.ynu.sei.lr.lr0;

/**
 * 项目集中的一个项目
 * <p>在文法 G 中每个产生式的右部适当位置添加一个圆点构成项目</p>
 * @author 88250
 * @version 1.0.0.0, Nov 11, 2007
 */
public class Item extends Product
{
    public int dotPos;

    /**
     * 带参数的构造器
     * @param leftPart 项目左部
     * @param rightPart 项目右部
     * @param dotPos 项目右部的圆点位置
     */
    public Item(String leftPart, String rightPart, int dotPos)
    {
        super(leftPart, rightPart);
        this.dotPos = dotPos;
    }

    @Override
    public String toString()
    {
        String beforeDotPos = rightPart.substring(0, dotPos);
        String afterDotPos = rightPart.substring(dotPos, rightPart.length());
        return leftPart + "->" + beforeDotPos + "." + afterDotPos;
    }
}

package cn.edu.ynu.sei.lr.lr0;

import java.util.ArrayList;
import java.util.List;

/**
 * 项目集
 * @author 88250
 * @version 1.0.0.0, Nov 11, 2007
 */
public class ItemSet
{
    public List<Item> items = new ArrayList<Item>();
   
    /**
     * 返回项目集中的一个项目
     * @param i
     * @return 指定索引的一个项目
     */
    public Item get(int i)
    {
        return items.get(i);
    }

    /**
     * 添加一个项目
     * @param item
     */
    public void add(Item item)
    {
        items.add(item);
    }

    /**
     * 根据给定的产生式添加一个项目，圆点位置为 0
     * @param product
     */
    public void add(Product product)
    {
        Item item = new Item(product.leftPart, product.rightPart, 0);
        for (Item i: items)
        {
            if (i.leftPart.equals(item.leftPart)
                    && i.rightPart.equals(item.rightPart)
                    && i.dotPos == item.dotPos)
            {
                return;
            }
        }
        items.add(item);
    }
}

package cn.edu.ynu.sei.lr.lr0;

/**
 * 产生式
 * @author 88250
 * @version 1.0.0.1, Nov 11, 2007
 */
public class Product
{
    public String leftPart;

    public String rightPart;

    /**
     * 产生式
     * @param leftPart 产生式左部
     * @param rightPart 产生式右部
     */
    public Product(String leftPart, String rightPart)
    {
        this.leftPart = leftPart;
        this.rightPart = rightPart;
    }
   
    @Override
    public String toString()
    {
        return leftPart + "->" + rightPart;
    }
}

package cn.edu.ynu.sei.lr.lr0;

/**
 * 文法符号跳转状态编号项
 * @author 88250
 * @version 1.0.1.1, Nov 12, 2007
 */
public class SymbolAndActOrGoStateNum
{
    public String grammaticalSymbol;

    public int ActOrGoStateNum;

    public SymbolAndActOrGoStateNum(String grammaticalSymbol,
                                     int ActOrGoStateNum)
    {
        this.grammaticalSymbol = grammaticalSymbol;
        this.ActOrGoStateNum = ActOrGoStateNum;
    }
}


关于实验的一点点心得：

我认为对LR(0)的分析过程最重要要解决两个问题：1. 求解文法的项目集规范族；2. 分析表中每个分析项的数据结构与分析表的构造。下面分别阐述一下我的心得：

  1. 对于项目集规范族的构造

    从课本给出的算法描述可以看出这是一个迭代的过程。课本的算法核心思想是求解出一个项目集（）即状态机中一个方形的所有项目）再根据吃进的文法符号跳转出下一个项目集（该跳转的项目集开始只包含核），然后在计算这个项目集。按照算法设计（搜索算法）的观点，这是一个广度优先的过程。而我设计的求解算法是构建完一个项目集后就吃进该项目集内项目可以吃进的文法符号，构建出一系列核，然后从第一个核开始构建它的项目集。很明显，这是一个深度优先的过程。所以后面用于测试的文法虽然定义与课本上一样，但是项目集的编号不同了。

    另外，在构建一个项目集的时候最重要的是要解决在吃进一个文法符号的时候跳转的项目集是本身项目集的情况，这种情况会引起死递归。经过分析，在一个项目吃进文法符号形成的核如果与这个项目自身所在的项目集的核相同，则因该跳过，因为项目集规范族中的所有核是不会相同的。

    而所有的这些，都是建立在核的定义上的，所以我觉得核的定义很重要，对于求解项目集规范族是很有帮助的。

  2. 对于分析表的构造

    在项目集规范族求解出来的基础上不难得出分析表的。但是，由于分析表本身结构比较复杂，所以构造分析表也显得比较麻烦了。分析原因，我觉得是由于分析表的数据结构定义引起的问题。书上画出的分析表是很直观，可以简述为：

    行：表示状态x下可以采取的动作

    列：表示文法定义的每个文法符号可以采取的动作

    (行，列）：表示在状态x下吃进一个a文法符号应该采取的动作

    这个表乍一看，以为是个二维表，其实不然。按照课本的图，我的分析如下：

    在(行，列）这个值中存在移进、归约、接受和不接受。这样一来，本来的二维表至少变成楼三维表：在横纵坐标上还有竖坐标（表示移进或者归约）。所以在设计这个分析表的时候应该慎重，避免给算法带来过大的复杂度。

    分析至此，分析表的数学模型已经出来了。下面再接合课本的分析表，给出我的分析表结构定义，如下：

    课本上将一个分析表文为三个部分：状态编号；

    ACTION表；GOTO表。分析了他们的特点，我发现可以将ACTION表中下一状态的表示

    与GOTO表中跳转状态的表示合二为一，他们都可以只用状态编号来表示。这里，有一

    个问题就是在ACTION表中可能存在归约，而归约的时候必须用产生式下标。再次经过

    分析，这个下标可以用负数表示。这样，就可以区分出Sx与rx了；接受或者非接受可

    以用最大正整数和最大负整数分别表示。如此一来。在数据结构上分析表得到了统一，

    都可以用整数（int）类型来表示了，极大的简化了算法设计，所以数据结构的设计是

    相当的重要的。

以上两个大点的问题解决了，剩下的对输入串的匹配过程就比较简单了，这里不在赘述，我是按照课本的方法和步骤来的，源代码里很清晰了 :-)