lro.java

LRO文法的Java版本

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

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


public class LR0
{

    public static int PRODUCT_SIZE;

    public static final List<Product> PRODUCTS = new ArrayList<Product>();

    public static final String START = "S";

    public static final List<String> TERMINATORS = new ArrayList<String>();

    public static final List<String> NTERMINATORS = new ArrayList<String>();

    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>();

    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("--------------");
    }

    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());
        }
    }

    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("匹配失败！！！！");
        }

    }

    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);
        }
    }

    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;
    }

    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);

            }
        }
    }

    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 + "}");
            }
        }
    }

    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;
    }

    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;
    }

    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;
    }

    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)
        {
            return false;
        }
        if (goStateNum > 0 && TERMINATORS.contains(currentSymbol))
        {
            stateStack.push(goStateNum);
            symbolStack.push(currentSymbol);
        }
        if (goStateNum < 0 && (TERMINATORS.contains(currentSymbol) || currentSymbol.equals("#")))
        {
            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("#"))
        {
            return true;
        }
        if (goStateNum > 0 && NTERMINATORS.contains(currentSymbol))
        {
            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;

public class AnalysisItem
{

    public int stateNum;

    List<SymbolAndActOrGoStateNum> symbolAndActOrGoStateNum = new ArrayList<SymbolAndActOrGoStateNum>();

    public void add(String grammaticalSymbol, int actOrGoStateNum)
    {
        symbolAndActOrGoStateNum.add(new SymbolAndActOrGoStateNum(grammaticalSymbol, actOrGoStateNum));
    }
}

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

public class Item extends Product
{
    public int 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;

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


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

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

    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;

public class Product
{
    public String leftPart;

    public String 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;

public class SymbolAndActOrGoStateNum
{
    public String grammaticalSymbol;

    public int ActOrGoStateNum;

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