LR分析器
自己写的，真的很烂…不过正是因为全部自己写的，验收非常顺利，最后期末总分87，很满意惹
LR分析器部分
package LR;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Stack;
public class LR {
static char vn[];//非终结符数组
static char vt[];//终结符数组
static String verbs[];//文法数组
static boolean first[][] = new boolean[3][8];//first集
static ArrayList<String[]> lrmap = new ArrayList<String[]>();//LR项目集族
static String acttable[][];//LR分析表
static String rowdata[][] = new String[50][6];//添加到窗口表格里的数组
static windows win;//窗口
static final String path ="D://Eclipse/e1903.txt";//文法保存路径
static int isflag = 0;
public static void main(String args[]) throws Exception{
int i ,j ,k=0,flag=0;char c;char temp2[] = {'0','0','0','0','0','0','0','0','0','0'};ArrayList<String> list = new ArrayList<String>();
File file = new File(path);BufferedReader br = new BufferedReader(new FileReader(file));
String temp;
while((temp = br.readLine())!= null){
list.add(temp);
}
br.close();//关闭文件
verbs = new String[list.size()];
for( i =0;i < list.size();i++){
verbs[i] = list.get(i);
}
for(i = 0 ;i<verbs.length;i++){
c = verbs[i].charAt(3);
for(j=0;j<10;j++){
if(c == temp2[j]){
flag = 1;break;
}
}
if(flag == 0){
temp2[k] = c;k++;
}
flag = 0;
}
k=0;for(i=0;i<10;i++){
if(temp2[i] != '0'){
k++;
}
}
vn = new char[k];
for(i= 0;i<k;i++){
vn[i] = temp2[i];
}
k=0;flag = 0;char temp3[] = {'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0'};
for(i=0;i<verbs.length;i++){
for(j=6;j<verbs[i].length();j++){
if( verbs[i].charAt(j) != '|' && (verbs[i].charAt(j)<'A' || verbs[i].charAt(j)>'Z') && verbs[i].charAt(j) != '@' ){
temp3[k] = verbs[i].charAt(j);k++;
}
}
}
int len = 0;char temp4[] = {'0','0','0','0','0','0','0','0','0','0'};
for(i=0;i<k;i++){
c = temp3[i];flag = 0;
for(j=0;j<10;j++){
if( c == temp4[j]){
flag = 1;break;
}
}
if(flag == 0){
temp4[len]=c;len++;
}
}
k=0;
for(i=0;i<10;i++){
if(temp4[i] != '0'){
k++;
}
}
vt = new char[k+2];
for(i= 0;i<k;i++){
vt[i] = temp4[i];
}
vt[k] = '#';vt[k+1] = '@';
first_final(vn,vt,verbs);
LR lr = new LR(acttable,verbs,vn,vt);
acttable = actiongoto(lrmap,verbs,vn,vt);
windows wins = new windows(rowdata,vn,vt,verbs,acttable);//创建窗口
String temp5[];
String str;
for(i = 0 ; i < lrmap.size() ; i++){
temp5 = lrmap.get(i);
str = "项目集I"+i+":";
wins.textshow.append(str);
for(j = 1 ; j < temp5 .length-1 ; j++){
str= temp5[j];
wins.textshow.append(str);
}
str = "\n";
wins.textshow.append(str);
}
str = "ACTION表：\n";
wins.textshow.append(str);
str = " ";
for(i = 0 ; i < vt.length -1; i++){
str = str +vt[i] + " ";
}
for(i = 0 ; i < vn.length ;i++){
str = str + vn[i] + " ";
}
str = str + "\n";
wins.textshow.append(str);//输出ACTIONGOTO表头
str = "";
for(i = 0 ; i < acttable.length ;i++){
str = ""+i;
for(j = 0 ; j < acttable[i].length ; j++){
if(acttable[i][j] != null){
str = str + " "+acttable[i][j];
}
else{
str = str + " "+"null";
}
}
str = str +"\n";
wins.textshow.append(str);
}
}
LR(String acttable[][],String verbs[],char vn[],char vt[]){
acttable = new String[22][vn.length+vt.length-1];
getclosure(verbs,vn,vt);
}
static int indexofx(char c, String s){
int i = 0;
if(s == null){
return -2;
}
for(i = 3;i<s.length(); i++){
if(s.charAt(i) == c){
return i;//返回C的位置
}
}
return -1;//没有c返回-1
}
//对于String类的求字符位置
static int indexofx(char c, char s[]){
int i;
for(i = 3;i<s.length;i++){
if(s[i] == c){
return i;
}
}
return -1;//没有c返回-1
}
//对于char[]类的求字符位置
static int indexofor (int i,String s){
for(i=i+1;i<s.length();i++){
if(s.charAt(i) == '|'){
return i;
}
}
return -1;//-1表示没有‘|’
}
//indexofor函数返回产生式右边‘|’的位置
static int vn(char a,char c[]){
int i ;
for(i=0;i<c.length;i++){
if(c[i] == a){
return i;
}
}
return -1;//-1表示a不是非终结符
}
// vn 函数返回a在非终结符数组中的位置
static int vt(char a, char c[] ){
int i ;
for(i=0;i<c.length;i++){
if(c[i] == a){
return i;
}
}
return -1;//-1表示a不是终结符
}
// vt 函数返回a在终结符数组中的位置
static void fir(String s,int i , char vn[],char vt[],String verbs[]){
int c = vn(s.charAt(3),vn);
//c是这一条产生式左侧的非终结符,c为非终结符数组中的位置，同时也是first[][]中行数
int k;
if(vt(s.charAt(i),vt) != -1){
first[c][vt(s.charAt(i),vt)] = true;//写入first集
}//右侧第一个字符是终结符，直接写入first集
else{
//当前判断的字符式是非终结符
if(first[vn(s.charAt(i),vn)][vt.length] == false){
first(s.charAt(i),vn,vt,verbs);//i是非终结符，并且还未求first集，先求出first集
}
for(k=0;k<vt.length;k++){
if(first[vn(s.charAt(i),vn)][k] == true && vt[k] != '@'){
first[c][k] = true;//把i的first集中除了空串的终结符给c的first集
}
}
if(first[vn(s.charAt(i),vn)][vt('@',vt)] == true){
//此时i的first集中有空串
if(i == s.length() - 1){
//i是产生式最后一位
first[c][vt('@',vt)] = true;
return;//这条产生式结束。准备扫描下一条
//规则四：A->BCD......,BCD...的first集中都含有空，则把空写入c的first集中
}
if( s.charAt(i+1) != '|'){
//规则四：A->BCD......,将BCD...的first集-@写入c的first集中
i++;//指向后一个字符
fir(s,i,vn,vt,verbs);//迭代将产生式中所有连续非终结符的first集都求出来
}
else{
//i+1是 | ,这条产生式暂时结束，同上一个if，每个first集都有@,写入@
first[c][vt('@',vt)] = true;
}
}
}
}
//求某一条产生式的first集，此时并不是某一个非终结符的first集，因为有的非终结符有多条产生式
static void first(char c,char vn[],char vt[],String verbs[]){
int i,j;
String s;
for(i=0;i< verbs.length;i++){
s = verbs[i];
if( c == s.charAt(3)){
//找到c的产生式
j=6;
if(s.charAt(3) != s.charAt(j)){
fir(s,j,vn,vt,verbs);//求关于这条产生式的first集
}
while( indexofor(j,s) != -1 && j < s.length()){
//判断这条产生式有没有‘|’
j = indexofor(j,s);//定位到下一条‘|’
j++;
if(s.charAt(3) != s.charAt(j)){
fir(s,j,vn,vt,verbs);//求关于这条产生式的first集
}
}
}
}
first[vn(c,vn)][vt.length] = true;//标记已经求过这个非终结符的first集
}
//求某一个非终结符的first集
static void first_final(char vn[],char vt[],String verbs[]){
int i;
for(i=0;i<vn.length;i++){
if(!first[i][7] ){
//当这个非终结符的first集还没求，求first集
first(vn[i],vn,vt,verbs);
}
}
}
//求所有非终结符的first集
void getclosure(String verbs[],char vn[],char vt[]){
String temp[],t2[];
int i = 1 ;
String state[];
String test[] = {"0-","S->.E,#"};
temp = closure(test,verbs,vn,vt);
ArrayList<String> t3 = new ArrayList<String>();
for(i = 0 ; i < temp.length ; i++){
t3.add(temp[i]);
}
t3.add("0");
String t4[] = new String[t3.size()];
for(i = 0;i<t4.length;i++){
t4[i] = t3.get(i);
}
lrmap.add(t4);
int n=0;
while(true){
n= lrmap.size();
for(i = 0;i < lrmap.size();i++){
state = lrmap.get(i);
clo(acttable,state,verbs,vn,vt);
}
if(n == lrmap.size()){
break;
}
}
for(i = 0 ; i < lrmap.size() ; i++){
t2 = lrmap.get(i);
for(int j = 0 ; j < t2.length ; j++){
System.out.println(""+t2[j]);
}
System.out.println("\n");
}
}
//生成项目集规范族
void clo(String act[][],String str[],String verbs[],char vn[],char vt[]){
int i , j , k ,m ,n , lastnum ;
char u ,v ,p;
ArrayList<String> next =new ArrayList<String>();
String last;
String temp,left,right;
char fir[];
String newsta[];
boolean flag[] = new boolean[str.length];
for(i = 1; i < str.length -1; i++){
next.clear();//每一次建立新状态清空list
last = str[str.length-1];
k = indexofx('.',str[i]);//定位'.'
u = str[i].charAt(k+1);//定位'.'后面的字符
if(flag[i] == true){
continue;
}
if(u == ','){
//此状态是规约项目
continue;
}
else{
//不是规约项目
temp = ""+last+u;
next.add(temp);
for(j = 1 ; j < str.length -1; j++){
k = indexofx('.',str[j]);//定位'.'
v = str[j].charAt(k+1);//定位'.'后面的字符
p = str[j].charAt(k+2);
if(u == v){
flag[j] = true;
left = str[j].substring(0,k);//‘.’左边部分字符串
m = indexofx(',',str[j]);
right = str[j].substring(k+2);
temp = left+v+'.'+right;
if(!isexit(next,temp)){
next.add(temp);
}
}
}
String nextsta[] = new String[next.size()];
for(j = 0;j < next.size() ; j++){
nextsta[j] = next.get(j);
}
newsta = closure(nextsta,verbs,vn,vt);
for(j = next.size();j < newsta.length; j++){//把产生的等价产生式写入项目集
next.add(newsta[j]);
}
temp = ""+lrmap.size();//写入项目集编号
next.add(temp);
String newst[] = new String[next.size()];
for(j = 0;j < next.size(); j++){
newst[j] = next.get(j);
}
if(compare(newst,lrmap,verbs,vn,vt) == -1){
lrmap.add(newst);
}
else{
k = compare(newst,lrmap,verbs,vn,vt);
lrmap.get(k)[0]= lrmap.get(k)[0] + "|" + newst[0];
}
}
}
}
//由某一个项目集得到新的项目集
String[] closure(String[] next,String verbs[],char vn[],char vt[]){
String[] fin;
ArrayList<String> temp = new ArrayList<String>();
int i ,j , k , n , len;
char u ,v;
String add,use,str;
char fu[];
for(i = 0 ; i < next.length ; i++){
temp.add(next[i]);
}
while(true){
len = temp.size();
for(i = 1 ; i < temp.size();i++){
use = temp.get(i);
k = indexofx('.',use);//标记‘.’的位置
u = use.charAt(k+1);//'.'后的字符
v = use.charAt(k+2);//u后的字符
n = indexofx(',',use);//','的位置
if(vn(u,vn) != -1){//u为非终结符，需要把等价产生式写进去
for(j=0;j<verbs.length;j++){//开始查找U的产生式
if(u == verbs[j].charAt(3)){
str = verbs[j];
if(vn(v,vn) != -1){//求first集
fu = getfir(use.substring(k+2),verbs,vn,vt);
for(n = 0 ; n < fu.length;n++){
add = str.substring(3,6)+'.'+str.substring(6)+','+fu[n];
if(!isexit(temp,add)){
temp.add(add);
}
}
}
else if(vt(v,vt) != -1){//v是终结符，新展望就是v
add = str.substring(3,6)+'.'+str.substring(6)+','+v;
if(!isexit(temp,add)){
temp.add(add);
}
}
else{//v是',',新展望继承
add = str.substring(3,6)+'.'+str.substring(6)+use.substring(n);//use.substring(n)是继承的展望
if(!isexit(temp,add)){
temp.add(add);
}
}
}
}
}
}
if(len == temp.size()){//项目集大小不再变化，说明闭包已经求完
break;
}
}
fin = new String[temp.size()];
for(i = 0 ; i < temp.size() ; i++){
fin[i] = temp.get(i);
}
return fin;
}
//得到某一项目集的闭包
static String[][] actiongoto(ArrayList<String[]> lrmap,String verbs[],char vn[],char vt[]){
String act[][] = new String[lrmap.size()][vn.length + vt.length-1];//初始化actiongoto表,去除@
String temp[] ;
String str;
int i , j , next , last ,k , n ,key=0,or;
char bri, u , v , newc;
act[1][5] = "acc";//acc单独求得
for(i = 1 ; i < lrmap.size() ; i++){//从1 开始因为I0没有来源项目集，单独填表
temp = lrmap.get(i);//i是当前项目集编号
or = indexofor(0,temp[0]);
if(or == -1){//记录‘|’
or = temp[0].length();
}
int g=0;
while(g < temp[0].length()){
last = Integer.parseInt(temp[0].substring(g,or-1));//last为当前项目集的来源项目集编号
g =or+1;
bri = temp[0].charAt(temp[0].length()-1);//last移进bri到i
if(vn(bri,vn) != -1){//bri是非终结符，填入goto
act[last][vn(bri,vn)+vt.length-1] = ""+i;
for(j = 1 ; j < temp.length -1; j++){//第一行是last和bri，不用扫描
str = temp[j];
k = indexofx('.',str);//定位'.'
u = str.charAt(k-1);//定位'.'之前的字符
v = str.charAt(k+1);//定位'.'之后的字符，判断移进或规约
if(u != '>' ){//不是等价产生式
if( v != ','){//移进项目
continue;
}
else{//v是','，意味着'.'在最后，是规约项目
newc = str.charAt(str.length()-1);
for( n = 0 ; n < verbs.length ; n++){
if(verbs[n].substring(3).equals(str.substring(0,str.length()-3))){//找到规约使用的文法
key = n;//记下文法序号
break;
}
}
if(newc == '#' && i == 1){
continue;
}
act[i][vt(newc,vt)] = "r"+key;
}
}}
}
else{//bri是终结符，开始遍历temp判断移进项目或规约项目
act[last][vt(bri,vt)] = "s"+i;
for(j = 1 ; j < temp.length -1; j++){//第一行是last和bri
str = temp[j];
k = indexofx('.',str);//定位'.'
u = str.charAt(k-1);//定位'.'之前的字符
v = str.charAt(k+1);//定位'.'之后的字符，判断移进或规约
if(u != '>' ){//不是等价产生式，等价产生式不用判断
if( v != ','){//移进项目
continue;
}
else{//v是','，意味着'.'在最后，是规约项目
newc = str.charAt(str.length()-1);
for( n = 0 ; n < verbs.length ; n++){
if(verbs[n].substring(3).equals(str.substring(0,str.length()-3))){//找到规约使用的文法
key = n;//记下文法序号
break;
}
else{
key = -1;
}
}
act[i][vt(newc,vt)] = "r"+key;
}
}
}
}
or = indexofor(or,temp[0]);
if(or == -1 ){
or = temp[0].length();
}
}
}
return act;
}
//建actiongoto表
void words(Object rowdata[][],String msg,char vn[],char vt[],String acttable[][]){
String rule = new String();//所用产生式
String action = new String();//动作
String m = new String();
Stack<Character> temp = new Stack<Character>();//分析栈
Stack<Integer> state = new Stack<Integer>();//状态栈
temp.setSize(20);//初始化分析栈大小
state.setSize(20);//初始化状态栈大小
temp.push(new Character('#'));//#入栈
state.push(new Integer(0));//入栈
rule = " ";
action = "初始化";
char u;
int v;
int str[];
char str2 [];
String test ,test2;
int i=0,j,k=-1,n;
while(i < msg.length()){
n=0;
k++;
str= new int[10];
for(j=0;j<10;j++){
str[j]=' ';
}
rowdata[k][0]=""+k;//步骤
for(j=0;j<state.size();j++){
if(state.get(j)!= null){
str[n] = state.get(j);
n++;
}
}
ArrayList<Integer> r = new ArrayList<Integer>();
for(j = 0 ; j < n ; j++){
r.add(str[j]);
}
test = r.toString();
rowdata[k][1]=""+test;//输出状态栈
str2= new char[10];
for(j=0;j<10;j++){
str2[j]=' ';
}
for(j=0;j<temp.size();j++){
if(temp.get(j)!= null){
str2[n] = temp.get(j);
n++;
}
}
test2 = new String(str2);
rowdata[k][2]=""+test2;//输出分析栈
rowdata[k][3]=msg.substring(i);//输出字符串
rowdata[k][4]=rule;//输出所用产生式
rowdata[k][5]=action;//输出动作
u = msg.charAt(i);//字符串第一个字符
v = state.peek();
String mov,mov2;
int next,next2,len;
char non,v2;
if(acttable[v][vt(u,vt)] != null){//不为空
if(acttable[v][vt(u,vt)].charAt(0) == 's'){//移进
temp.push(u);//入栈
mov = acttable[v][vt(u,vt)].substring(1);//要入栈的状态符号(字符串状态)
next = Integer.parseInt(mov);//要入栈的状态符号(int)
state.push(next);
i++;
rule = " ";
action = "移进,s"+mov;
continue;
}
else if(acttable[v][vt(u,vt)].charAt(0) == 'r'){//规约
mov = acttable[v][vt(u,vt)].substring(1);//用来规约的产生式序号(字符串状态)
next = Integer.parseInt(mov);//用来规约的产生式序号(int)
len = verbs[next].substring(6).length();
non = verbs[next].charAt(3);
while(len>0){
state.pop();
temp.pop();
len--;
}
temp.push(non);//入栈
v2 = temp.peek();//分析栈的栈顶
v = state.peek();//此刻状态栈的栈顶
if(acttable[v][vn(v2,vn)+vt.length-1] != null){
mov2 = acttable[v][vn(v2,vn)+vt.length-1];
next2 = Integer.parseInt(mov2);
state.push(next2);//入栈新的状态符号
}
else{//为空，出错
action = "Error1!";
rowdata[k+1][0]=" ";rowdata[k+1][1]=" ";rowdata[k+1][2]=" ";rowdata[k+1][3]=" ";rowdata[k+1][4]=" ";
rowdata[k+1][5]=action;
return ;//出错返回
}
rule = verbs[next].substring(3);//所用产生式
action = "归约，r"+mov+"，进入状态"+next2;
continue;
}
else{//为acc
rule = " ";
action = "accept!";
rowdata[k+1][0]=" ";rowdata[k+1][1]=" ";rowdata[k+1][2]=" ";rowdata[k+1][3]=" ";rowdata[k+1][4]=" ";
rowdata[k+1][5]=action;
return ;//出错返回
}
}
else{//为空，ERROR
action = "ERROR2!";
rowdata[k+1][0]=" ";rowdata[k+1][1]=" ";rowdata[k+1][2]=" ";rowdata[k+1][3]=" ";rowdata[k+1][4]=" ";
rowdata[k+1][5]=action;
return ;//出错返回
}
}
}
int compare(String fin[],ArrayList<String[]> lrmap,String verbs[],char vn[],char vt[]){
int i ;
for(i = 0 ; i < lrmap.size() ; i++){
if(ecompare(fin,lrmap.get(i)) == true){
return i;
}
}
return -1;
}
//判断某一新项目集是否已存在
boolean ecompare(String fin[],String temp[]){
int i , j ;
boolean flag[] = new boolean [fin.length-2];
String str1;
if(fin.length != temp.length){
return false;
}
else{
for(i = 1 ; i < fin.length -1; i++){
str1 = fin[i];
for( j = 1 ; j < temp.length -1; j++){
if(str1.equals(temp[j])){
flag[i-1] = true;
break;
}
flag[i-1] = false;
}
}
for( i = 0 ; i < fin.length -2; i++){
if(flag[i] == false){
return false;
}
}
return true;
}
}
//compare函数调用此函数进行判断
char[] getfir(String temp,String verbs[],char vn[],char vt[]){
ArrayList<Character> str = new ArrayList<Character>();
int i,j;
j = vn(temp.charAt(0),vn);
for(i = 0 ; i < vt.length-1; i++){
if(first[j][i] == true){
str.add(vt[i]);
}
}
if(first[j][vt.length-1] == true && temp.charAt(1) != ','){
str.add(temp.charAt(1));
}
char fir[] = new char[str.size()];
for(i = 0 ; i < fir.length; i++){
fir[i] = str.get(i);
}
return fir;
}
//求字符串的first集
boolean isexit(ArrayList<String> s,String temp){
int i;
for(i = 0; i < s.size() ; i++){
if(temp.equals(s.get(i))){
return true;//字符串数组中已经存在此行,重复
}
}
return false;
}
//判断状态集里是否已经存在这个状态
}
窗口部分
package LR;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.*;
import javax.swing.table.DefaultTableModel;
public class windows extends JFrame {
private static final long serialVersionUID = 1L;
static String msg;
Container contain;
JTextField text;
JLabel myLabel;
DefaultTableModel model;
JTable table;
JTextArea textshow;
public windows(Object rowdata[][],char vn[],char vt[],String verbs[],String acttable[][]){
setTitle("LR1");
contain = getContentPane();
contain.setLayout(new BorderLayout());//布局器
text = new JTextField(30);//创建输入文本框
myLabel=new JLabel("Words:",SwingConstants.LEFT);
JButton button = new JButton ("ok");//创建确定按钮
Object[] columnNames = {"步骤","状态栈","分析栈","剩余输入串","所用产生式","动作"};
model = new DefaultTableModel(rowdata,columnNames); // 新建一个默认数据模型
table = new JTable(model); // 用数据模型创建JTable，JTable会自动监听到数据模型中的数据改变并显示出来
JScrollPane jsp = new JScrollPane(table); // 用列表创建可滚动的Panel，把这个Panel添加到窗口中
textshow = new JTextArea(30,65);
JScrollPane jsp2 = new JScrollPane(textshow); // 用TextArea创建可滚动的Panel，把这个Panel添加到窗口中
JPanel panel = new JPanel();
JPanel myPanel=new JPanel();
myPanel.add(myLabel);
myPanel.add(text);
myPanel.add(button);
panel.setLayout(new BorderLayout());
contain.add(myPanel, BorderLayout.NORTH);
contain.add(jsp, BorderLayout.CENTER);
contain.add(jsp2, BorderLayout.EAST);
contain.add(panel, BorderLayout.SOUTH);
setSize(1000, 300);
setVisible(true);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
pack();
//操作界面
button.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent ae) {
msg = text.getText();
if(msg!=null){
try{
LR one = new LR(acttable,verbs,vn,vt);
one.words(rowdata,msg,vn,vt,acttable);
reset(one.win,rowdata);
}
catch(Exception exp){}
}
}
});//监听消息。
}
void reset(windows win,Object rowdata[][]){
int i;
for(i=0;i<rowdata.length;i++){
model.removeRow(0);
model.addRow(rowdata[i]);
}
win.table = new JTable(model);
}//更新分析过程
}//窗口布局