import java.util.*;
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>();
/**
* 开始文法符号<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>();
/**
* 初始化推导式,即使用文法规定的产生式P初始化推导式集合
*/
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()
{
int j=0;
String Start="S";
NTERMINATORS.add(Start);
while(true)
{
Scanner in = new Scanner(System.in);
String scan;
String L=new String();
String R=new String();
scan=in.nextLine();
if(scan.equals("@"))
{
break;
}
else
{
String[] sc=scan.trim().split("[ ]+");
L=sc[0];
NTERMINATORS.add(L);
for(int i=1;i<sc.length;i++)
{
R+=sc[i];
if(!sc[i].equals("|"))
{
TERMINATORS.add(sc[i]);
}
}
if(j==0)
{
PRODUCTS.add(new Product(Start, L));
}
// System.out.println(L);
// System.out.println(R);
int temp1=0;
int temp2=0;
for(int i=0;i<R.length();i++)
{
String str;
if(R.charAt(i)=='|')
{
temp2=i;
str=R.substring(temp1, temp2);
PRODUCTS.add(new Product(L, str));
temp1=temp2+1;
}
}
if(temp2!=0)
{
String str=R.substring(temp2+1, R.length());
PRODUCTS.add(new Product(L ,str));
}
if(temp1==0&&temp2==0)
{
PRODUCTS.add(new Product(L, R));
}
}
j++;
}
TERMINATORS.removeAll(NTERMINATORS);
for(int i=0;i<TERMINATORS.size();i++)
{
for(int k=0;k<i;k++)
{
if(TERMINATORS.get(i).equals(TERMINATORS.get(k)))
{
TERMINATORS.remove(i);
}
}
}
for(String S : TERMINATORS)
{
System.out.println("-----"+S+"========");
}
for(String S : NTERMINATORS)
{
System.out.println("++++++++"+S+"---------");
}
PRODUCT_SIZE = PRODUCTS.size();
}
/**
* 显示文法的产生式
*/
public static void displayG()
{
System.out.println("开始符号:" + START);
System.out.println("文法的产生式如下:");
for (Product p : PRODUCTS)
{
System.out.println(p.toString());
}
}
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);
LR(0).rar_LR_LR java_LR(0)_parser code java_parser java
版权申诉
131 浏览量
2022-09-21
06:55:25
上传
评论
收藏 12KB RAR 举报
![avatar](https://profile-avatar.csdnimg.cn/2416af5c19524431b870352d943af459_weixin_42659196.jpg!1)
周楷雯
- 粉丝: 80
- 资源: 1万+