LR0 JAVA实现

更新时间：2023-09-17 02:53:01 阅读量：高中教育文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

lr03推荐度：
相关推荐

编译原理课程设计

LR0语法分析程序

姓名：班级：学号：指导老师

日期：2010年7月10日

一：设计目的............................................................................................................ 3 二：设计要求............................................................................................................ 3 三：设计思想............................................................................................................ 3 四：算法描述， ........................................................................................................ 4

4.1定义的构造I的闭包CLOSURE（I） ............................................................ 4 4.2文法项目集规范族步骤 ................................................................................. 4 4.3分析表的构造算法 ........................................................................................ 4 五：程序结构............................................................................................................ 5 5.1 mainFrame类 ....................................................................................................... 5

5.2AddPoint类 ................................................................................................... 5 5.3 LR0类 .......................................................................................................... 5 5.4 LR0Table类 .................................................................................................. 6 5.5 TerminalAndNon类 ....................................................................................... 6 5.6 Transform类 ................................................................................................. 6 六：运行结果............................................................................................................ 6

6.1主界面 .......................................................................................................... 6 6.2输入界面 ...................................................................................................... 7 6.3 显示自动机 .................................................................................................. 7 6.4 LR0分析表 ................................................................................................... 8 七：设计技巧:........................................................................................................... 8 八：心得体会............................................................................................................ 8 九：程序清单............................................................................................................ 9

9.1 mainFrame.java.............................................................................................. 9 9.2 addPoint.java ............................................................................................... 13 9.3 Transform.java ............................................................................................. 14 9.4 TerminalAndNon.java ................................................................................... 15 9.5 LR0.java ..................................................................................................... 19 9.6 LR0Table.java.............................................................................................. 23

一：设计目的

通过编写LR0语法分析程序，加深对LR0语法分析程序的理解，加深对编译原理的理解，培养动手能力。

二：设计要求

可根据自己实际情况，选择以下一项作为分析算法的输入：

（1）直接输入根据己知文法构造的LR(0)分析表。（2）输入已知文法的项目集规范族和转换函数，由程序自动生成LR(0)分析表；

（3）输入已知文法，由程序自动生成LR(0)分析表。

三：设计思想

LR0语法分析程序的核心部分是LR0分析表，和生成这个分析表的自动机，这张分析表分成两部分，一是动作ACTION，二是状态转换 GOTO，他们都是二维数组，ACTION(s,a)表示当前状态s面临符号a是应采取什么动作，GOTO（s,X）规定了状态s面临文法符号X时下一个状态时什么，显然，GOTO（s，X）定义了以文法符号为字母表的DFA。

四：算法描述

4.1定义的构造I的闭包CLOSURE（I）

若文法G以扩展为G‘，而S为文法G的开始符号拓广后增加S’S.如果I是文法G’的项目集，：（1） I的项目均在CLOSURE（I）中。

（2）若A->a.Bb属于CLOSURE(I)，则每一项如B->.R的项

目也属于CLOSURE(I).

（3）重复（2）直到不出现新的项目为止。即CLOSURE(I)

不再扩大。

4.2文法项目集规范族步骤

（1）置项目S’->S为初态集的核，然后对核求闭包，

CLOSURE{S’->S}得到初态的项目集。

（2）对初态集或其他所构造的项目集应用转换函数

GOTO(I.,X)=CLOSURE(J)求出新状态J的项目集。

（3）重复（2）直到不出现新的项目为止。

4.3分析表的构造算法

假设已构造LR0项目集规范族为： C={I0,I1,..........In}

其中Ik为项目集的名字,k为状态名，令包含S->.S项目的集合Ik的下标k的初始状态。那么分析表的ACTION表和GOTO表的构造步骤如下：

（1）若项目A->a.ab属于Ik且状态函数GO（Ik,a）=Ij,当a为

终极符时则置ACTION【k，a】为Sj，其动作含义为终结

符a移进符号栈，状态j进入状态栈，（相当于状态k遇a转向状态j）。

（2）若项目A->a.属于Ik，则对任何终结符a和‘#’置ACTION

【k，a】和ACTION【k,#】为“rj”,j为文法G‘中某产生式A->a的序号。rj动作的含义是当前文法符号栈顶的符号串a规约为A,,并将栈顶指针从栈顶向下移动|a|的长度，符号栈中弹出|a|个符号，非终结符A变为当前面临的符号。

（3）若GOTO(Ik，A)=Ij,则置GOTO(k，A)为“j”,其中A为非

终结符，表示当前状态为‘k‘时遇文法符号A是状态应转向j，因此A移入文法符号栈,j移入状态栈。

（4）若项目S’->S.属于Ik，则置ACTION【k，#】为“acc”，

表示接受。

（5）凡不用上述方法填入的分析表中的元素，均应填上“报错

信息”，为了表的清晰，我们仅在表中用空白表示错误标志。

五：程序结构

5.1 mainFrame类

这是主程序，也是主界面，把其他几个类的功能综合在一起，通过Java的事件机制吧点和箭头以标准的方式显示出来。

5.2AddPoint类

这个类的功能是把从输入界面中提取的字符串装换成“1S>AB”的形式，为后面的类调用提供方便。

5.3 LR0类

这个类的功能是生成自动机，并存在一个二维数组里。

5.4 LR0Table类

这个类就是生成LR0的分析表。

5.5 TerminalAndNon类

这个类是把转换成的字符串中的终结符和非终结符提取出来放到字符数组里，方便以后调用，也编写了判断是否为终结符的方法，是否为非终结符的方法。

5.6 Transform类

这个类是从字符串中把产生式分离出来，放到一个数组之中。

六：运行结果

6.1主界面

6.2输入界面

6.3 显示自动机

6.4 LR0分析表

七：设计技巧

首先设计了一个美观的界面，有一个文件帮助菜单，里面有按钮显示帮助信息，最左边的空白文本域可以输入文法，输入时以>号代替箭头，什么都不输入表示空串，当按下“compile”按钮时把输入的文法提取出来，放入一个字符串中，然后调用某些方法把

这个字符串中的文法提取出来，放入数组中，把他转化如”1SAB”的形式，其中第一位1是指点在第一位，是为了以后调用方便而设计，然后编写了方法把项目集规范族显示出来，程序中也是如上形式流动，界面上显示是运用事件处理显示的是箭头的点，最后经过仔细观察自动机的规律，运用课本上的算法，输出了LR0分析表。

八：心得体会

经过两周的课程设计，看似很长，时间却很紧张，本来以为很简单的课程设计，自己动手做之后才发现，有很多细节问题需要考虑的，不做是不可

能有体会的，这次课程设计不仅增加了我对编译的理解，更加深了对LR0语法分析程序的理解，也使得我能够更加熟练的运用Java语言进行编程，让我对编译原理更感兴趣，为我们以后的毕业设计及工作打下基础，总之，这两周的课程设计收益很多，感受很多，感谢老师们组织这次课程设计。

九：程序清单

9.1 mainFrame.java

import java.awt.*; import javax.swing.*; import java.awt.event.*; import javax.swing.event.*; import javax.swing.border.*;

public class mainFrame implements ActionListener{ JTextArea file=new JTextArea(20,40); JTextArea show=new JTextArea(20,40); JTextArea error=new JTextArea(12,90); JButton button=new JButton(\LR0 lr=new LR0();

AddPoint addPoint=new AddPoint(); public mainFrame(){ JFrame frame=new JFrame();

Container contentPane=frame.getContentPane(); JPanel mainPanel=new JPanel(); JPanel errorPanel=new JPanel(); JPanel p1=new JPanel(); JPanel p2=new JPanel();

mainPanel.setLayout(new FlowLayout());

p1.add(new JScrollPane(file)); p2.add(new JScrollPane(show));

p1.setBorder(BorderFactory.createTitledBorder(BorderFactory.createLineBorder(Color.gray,2),\请在此处输入文法\

TitledBorder.LEFT,TitledBorder.TOP));

p2.setBorder(BorderFactory.createTitledBorder(BorderFactory.createLineBorder(Color.gray,2),\自动机\

TitledBorder.LEFT,TitledBorder.TOP));

errorPanel.setBorder(BorderFactory.createTitledBorder(BorderFactory.createLineBorder(Color.gray,2),\分析表\

TitledBorder.LEFT,TitledBorder.TOP));

mainPanel.add(p1); mainPanel.add(button); mainPanel.add(p2);

button.addActionListener(this);

errorPanel.add(new JScrollPane(error)); contentPane.setLayout(new BorderLayout()); contentPane.add(mainPanel,BorderLayout.CENTER); contentPane.add(errorPanel,BorderLayout.SOUTH); JMenu fileMenu=new JMenu(\JMenu helpMenu=new JMenu(\帮助\JMenuItem newM =new JMenuItem(\JMenuItem open=new JMenuItem(\JMenuItem exit=new JMenuItem(\JMenuItem save=new JMenuItem(\JMenuItem help1=new JMenuItem(\帮助\JMenuItem about=new JMenuItem(\关于本系统\helpMenu.add(help1);

helpMenu.add(about);

JMenuBar MBar=new JMenuBar(); MBar.add(helpMenu); frame.setJMenuBar(MBar); frame.setTitle(\frame.pack();

frame.setVisible(true);

frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); }

public static void main(String[] args){ new mainFrame(); }

public void actionPerformed(ActionEvent e){

String s=file.getText();

StringBuffer output=new StringBuffer(); int m=0;

StringBuffer[][] I0=lr.Lr0(s);

for(int i=0;i

if(!I0[i][0].toString().equals(\ output.append(\m++;

for(int j=0;j

if(!I0[i][j].toString().equals(\

int point=(int)I0[i][j].charAt(0)-46; for(int n=1;n

if(I0[i][j].charAt(n)=='>')

output.append(\→\else {if(n==point){ }

output.append(\

output.append(I0[i][j].charAt(n)); } }

if(point==I0[i][j].length()){

output.append(\ }

output.append(\}

output.append(\} }

LR0Table lrt=new LR0Table();

StringBuffer stb=new StringBuffer(); String[][] lr0table=lrt.lr0Table(s); for(int

i=0;i

}

stb.append(\for(int

stb.append(lr0table[98][i]+\

i=0;i

stb.append(i+\for(int

j=0;j

}

stb.append(\

if(lr0table[i][j]==(null)) stb.append(\

else stb.append(lr0table[i][j]+\

}

error.setText(stb.toString()); show.setText(output.toString()); } }

9.2 addPoint.java

public class AddPoint{

Transform t=new Transform(); public String[] add(String str){ String[] strOut1=new String[100];

StringBuffer[] strOut=new StringBuffer[100]; for(int i=0;i

strOut[i]=new StringBuffer();

String[] strIn=new String[50]; strIn=t.transfer(str); int m=0;

for(int i=0;i

for(int k=0;k

if(!strIn.equals(\ }

for(int j=1;j

strOut[m].append(j); strOut[m].append(strIn[i]); m++;

}

strOut1[k]=strOut[k].toString();

return strOut1; }

public static void main(String[] args){

AddPoint addPoint=new AddPoint();

String[] test=new String[100];

String strTest=\test=addPoint.add(strTest);

for(int i=0;i

}

} }

System.out.println(test[i]);

9.3 Transform.java

public class Transform{

public String[] transfer(String s){ }

else if(s.charAt(i)=='\\n'||s.charAt(i)==' '){

String[] tt=new String[50];

StringBuffer[] strBuf=new StringBuffer[50]; for(int i=0;i

strBuf[i]=new StringBuffer();

int j=0;

for(int i = 0;i

if(s.charAt(i)=='>'){

strBuf[j].append(\

}

if(s.charAt(i-1)!=' ') j++;

else strBuf[j].append(s.charAt(i));

for(int i=0;i

return tt;

tt[i]=strBuf[i].toString();

public static void main(String[] args){

String s=\Transform t=new Transform(); String[] p=new String[50]; p=t.transfer(s);

for(int i=0;i

System.out.println();

}

9.4 TerminalAndNon.java

public class TerminalAndNon{

Transform t=new Transform();

public char[] getNonTerminal(String s){ String[] str=new String[50]; int length=str.length;

str=t.transfer(s); for(int i=0;i

}VN1[0]=VN[0]; int k=1;

VN[i]=str[i].charAt(0);

char[] VN=new char[length]; char[] VN1=new char[length];

for(int i=1;i

return VN1; }

public char[] getTerminal(String s){

TerminalAndNon tt=new TerminalAndNon(); int flag=0;

for(int j=0;j

if(flag==0){ }

VN1[k]=VN[i]; k++;

if(VN[i]==VN[j]){ flag=1;

char[] ch=new char[50]; char[] terminal=new char[50]; char[] terminal1=new char[50]; for(int i=0;i<50;i++) terminal1[i]=' '; ch=tt.getNonTerminal(s); String[] str=t.transfer(s);

int k=0;

if(!tt.isNonTerminal(str[i].charAt(j),ch)&&(str[i].charA

for(int i=0;i

if(!str[i].equals(\

for(int j=0;j

t(j)!='>')){

} }

terminal1[0]=terminal[0]; int ss=1;

} }

if(str[i].charAt(j)!=' '){ } k++;

terminal[k]=str[i].charAt(j);

for(int i=1;i

int flag=0;

for(int j=0;j

if(terminal[i]==terminal[j]){

} }

flag=1;

if(flag==0){ } }

return terminal1; }

public boolean isNonTerminal(char c,char[] vn){ }

public static void main(String[] args){

String s=\TerminalAndNon ter=new TerminalAndNon(); char[] vn=new char[50]; vn=ter.getNonTerminal(s);

for(int i=0;i

char[] terminal=new char[50]; terminal=ter.getTerminal(s); for(int i=0;i

System.out.print(terminal[i]); System.out.print(vn[i]);

for(int i=0;i

return false;

if(vn[i]==c) return true;

terminal1[ss]=terminal[i]; ss++;

}

System.out.println(ter.isNonTerminal('A',vn)); System.out.println(ter.isNonTerminal('T',vn)); System.out.println(ter.isNonTerminal('E',vn)); System.out.println(ter.isNonTerminal('D',vn)); System.out.println(ter.isNonTerminal('a',vn)); }

9.5 LR0.java

public class LR0{

int m=0;

TerminalAndNon ter=new TerminalAndNon(); AddPoint addPoint=new AddPoint();

StringBuffer[] strBuf=new StringBuffer[50]; public LR0(){

for(int i=0;i

arg){//arg:S>AB\\nA>a

strBuf[i]=new StringBuffer();

public void project(String str, String str:1S>AB

String[] string=addPoint.add(arg);

char[] c=ter.getNonTerminal(arg);

int i=(int)(str.charAt(0)-48);