lr1文法_lr1文法都是无二义性 - CSDN
精华内容
参与话题
  • 编译原理之LR(1)文法

    千次阅读 2019-11-30 17:01:26
    LR(0)分析方法是一种自底向上分析方法,自底向上分析方法是一种移进归约过程,当分析的栈顶符号串形成句柄或可归约串时就采取归约动作。若是限定采用规范规约,那么自底向上分析法的关键问题是在分析过程中如何确定...

    LR(0)分析方法是一种自底向上分析方法,自底向上分析方法是一种移进归约过程,当分析的栈顶符号串形成句柄或可归约串时就采取归约动作。若是限定采用规范规约,那么自底向上分析法的关键问题是在分析过程中如何确定句柄。LR 分析法正是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输人串的k(k≥0)个符号就可唯一地 确定分析器的动作是移进还是归约和用哪个产生式归约,因而也就能唯一地确定句柄。LR分析法的归约过程是规范推导的逆过程,所以LR分析过程是种规范归约过程。

    LR(k)分析方法是1965年Knuth提出的,括号中的k表示向右查看输入事符号的个数。这种方法比起自顶向下的LL(k)分析方法和自底向上的优先分析方法对文法的限制要少得多,也就是说,对于大多数用无二义性上下文无关文法描述的语有都可以用相定的LR分析器进行识别,而且这种方法还具有分析速度快,能准确即时地指出出错位置的特点。的构造工作量相当大,k愈大,构造愈复它的主要缺点是对于一个实用语言文法的分析器译程序,当采用LR分析器时都是借助于美国杂,实现比较困难。因此,目前许多实用的编能接受一个用BNF描述的满足 LR类中LALR(1)Bell实验室推出的yacc来实现的。

    对于LR文法,我们可以自动构造相应的LR分析表。为了构造LR分析表,我们需要定义一个重要概念——文法的规范句型“活前缀”。

    这种句柄之后不含任何符号的前缀称为活前缀。

    在LR分析工作过程中的任何时候,栈里的文法符号(自栈底而上)X1X2…Xm应该构成活前缀,把输入串的剩余部分配上之后即应成为规范句型(如果整个输入串确实构成一个句子)。因此,只要输入串的已扫描部分保持可归约成一个活前缀,那就意味着所扫描过的部分没有错误。

    对于一个文法G,我们可以构造一个有限自动机,它能识别G的所有活前缀,然后把这个自动机转变成LR分析表,按照该LR分析表进行LR分析,就能保证在分析的过程中,如果分析的句子是正确的,栈里的文法符号(自栈底而上)始终构成活前缀。

    假若一个文法G的拓广文法的活前缀识别自动机中的每个状态(项目集)不存在下述情况:(1)既含移进项目又含归约项目;(2)含有多个归约项目,则称G是一个LR(0)文法。该自动机的状态集合即为该文法的LR(0)项目集规范族。

    构造识别文法活前缀DFA有3种方法:

    (1)根据形式定义求出活前缀的正则表达式,然后由此正则表达式构造NFA再确定为DFA;

    (2)求出文法的所有项目,按一定规则构造识别活前缀的NFA再确定化为DFA;

    (3)使用闭包函数(CLOSURE)和转向函数(GO(I,X))构造文法G’的LR(0)的项目集规范族,再由转换函数建立状态之间的连接关系来得到识别活前缀的DFA。

    符号串的前缀是指该符号串的任意首部,包括空串ε。例如,对于符号串abc,其前缀有ε,a,ab,abc。如果输入串没有错误的话,一个规范句型的活前缀是该句型的一个前缀,但它不含句柄之后的任何符号。之所以称为活前缀,是因为在该前缀后联接尚未输入的符号串可以构成一个规范句型。

    活前缀与句柄的关系如下:

    (1)活前缀已含有句柄的全部符号,表明产生式A→β的右部β已出现在栈顶。

    (2)活前缀只含句柄的一部分符号,表明A→β1β2的右部子串β1已出现在栈顶,期待从输入串中看到β2推出的符号。

    (3)活前缀不含有句柄的任何符号,此时期望A→β的右部所推出的符号串。

    在文法G的每个产生式的右部(候选式)的任何位置上添加一个圆点,所构成的每个产生式称为LR(0)项目。如产生式A® xyz有如下项目:A®.xyz,A®x.yz,A®xy.z,A®xyz.。为刻划分析过程中的文法的每一个产生式的右部符号已有多大一部分被识别(出现在栈顶),可以用这种标有圆点的产生式来确定。

    (1)A→β.刻划产生式A→β的右部β已出现在栈顶。

    (2)A→β1.β2 刻划A→β1β2的右部子串β1已出现在栈顶,期待从输入串中看到β2推出的符号。

    (3)A→.β 刻划没有句柄的任何符号在栈顶,此时期望A→β的右部所推出的符号串。

    (4)对于A→ε的LR(0)项目只有A→.。

       设文法G=(VT,VN,S,P)是一个上下文无关文法,若存在一个规范推导SAw12w(其中A12P),则称项目A12对活前缀=1是有效的,即LR(0) 有效项目。
    

    从直观意义上讲,一个LR(0)项目指明了在分析过程中的某一步我们看到产生式的多大部分被识别,LR(0)项目中的圆点可看成是分析栈栈顶与输入串的分界线,圆点左边为已进入分析栈的部分,右边是当前输入或继续扫描的符号串。

    不同的LR(0)项目,反映了分析栈顶的不同情况。我们根据LR(0)项目的作用不同,将其分为四类:

    (1)归约项目:

    表现形式:A→a.

    这类LR(0)项目表示句柄a恰好包含在栈中,即当前栈顶的部分内容构成了所期望的句柄,应按A→a进行归约。

    (2)接受项目:

    表现形式:→a.

    其中是文法惟一的开始符号。这类LR(0)项目实际是特殊的归约项目,表示分析栈中内容恰好为a,用→a进行归约,则整个分析成功。

    (3)移进项目:

    表现形式:A→a.(bVT)

    这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀,为构成恰好有句柄的活前级,需将b移进分析栈。

    (4)待约项目:

    表现形式:A→α.Bβ (BVN)

    这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀,为构成恰好有句柄的活前缀,应把当前输入字符串中的相应内容先归约到B。

    在给出LR(0)项目的定义和分类之后,我们从这些LR(0)项目出发,来构造能识别文法所有前缀的有限自动机。其步骤是:首先构造能识别文法所有活前缀的非确定的有限自动机,再将其确定化和最小化,最终得到所需的确定的有限自动机。

    由文法G的LR(0)项目构造识别文法G的所有活前缀的非确定有限自动机的方法:

    (1)规定含有文法开始符号的产生式(设→A)的第一个LR(0)项目(即→.A)为NFA的惟一初态。

    (2)令所有LR(0)项目分别对应NFA的一个状态且LR(0)项目为归约项目的对应状态为终态。

    (3)若状态i和状态j出自同一文法G的产生式且两个状态LR(0)项目的圆点只相差一个位置,即:

    若i为X→X1X2·…Xi-1·Xi…Xn, j为 X→X1X2…Xi·Xi+1…Xn,则从状态i引一条标记为Xi的弧到状态j。

    (4)若状态i为待约项目(设X→α·Aβ),则从状态i引ε弧到所有A→·r的状态。

    为了使“接受”状态易于识别,我们通常将文法G进行拓广。

    假定文法G是一个以S为开始符号的文法,我们构造一个,它包含了整个G,但它引进了一个不出现在G中的非终结符,并加进一个新产生式→S,以→S为开始符号。那么,我们称是G的拓广文法。

    这样,便会有一个仅含项目→S的状态,这就是惟一的“接受”态。

    如果I是文法G'的一个项目集,定义和构造I的闭包CLOSURE(I)如下:

    (1)
    I的项目都在CLOSURE(I)中。

    (2)
    若A→a.Bb属于CLOSURE(I),则每一形如B→.g的项目也属于CLOSURE(I)。

    (3)
    重复(2)直到CLOSURE(I)不再扩大。

    定义转换函数如下:

    GO(I,X)= CLOSURE(J)

    其中:I为包含某一项目集的状态,X为一文法符号,J={ A→aX .b | A→a.X b∈I}。

    圆点不在产生式右部最左边的项目称为核,惟一的例外是S′→.S,因此用GOTO(I,X)状态转换函数得到的J为转向后状态闭包项目集的核。

    使用闭包函数(CLOSURE)和转换函数(GO(I,X))构造文法G’的LR(0)的项目集规范族,步骤如下:

    (1) 置项目S′→.S为初态集的核,然后对核求闭包CLOSURE({S′→.S})得到初态的闭包项目集。

    (2) 对初态集或其他所构造的项目集应用转换函数GO(I,X)=
    CLOSURE(J)求出新状态J的闭包项目集。

    (3)
    重复(2)直到不出现新的项目集为止。

    计算LR(0)项目集规范族C={I0,I1
    , … In }的算法伪代码如下:

    Procedure itemsets(G’);

    Begin C := {
    CLOSURE ({S’®.S})}

    Repeat

    For C 中每一项目集I和每一文法符号X

    Do if GO(I,X) 非空且不属于C

                 Then 把 GO(I,X) 放入C中
    

    Until C 不再增大

    End;

    一个项目集可能包含多种项目,若移进和归约项目同时存在,则称移进-归约冲突,若

    归约和归约项目同时存在,则称归约-归约冲突。下面看一个具体的例子:

    我们希望能根据识别文法的活前缀的DFA建立LR分析器,因此,需要研究这个DFA的每个项目集(状态)中的项目的不同作用。

    我们说项目A→β1.β2对活前缀αβ1是有效的,其条件是存在规范推导。一般而言,同一项目可能对几个活前缀都是有效的(当一个项目出现在几个不同的集合中时便是这种情形)。若归约项目A→β1.对活前缀是有效的,则它告诉我们应把符号串归约为A,即把活前缀变成αA。若移进项目A→β1.β2对活前缀是有效的,则它告诉我们,句柄尚未形成,因此,下一步动作应是移进。但是,可能存在这样的情形,对同一活前缀,存在若干项目对它都是有效的。而且它们告诉我们应做的事情各不相同,互相冲突。这种冲突通过向前多看几个输入符号,或许能够获得解决。

    对于每个活前缀,我们可以构造它的有效项目集。实际上,一个活前缀γ的有效项目集正是从上述的DFA的初态出发,经读出γ后而到达的那个项目集(状态)。换言之,在任何时候,分析栈中的活前缀X1X2…Xm的有效项目集正是栈顶状态Sm所代表的那个集合。这是LR分析理论的一条基本定理。实际上,栈顶的项目集(状态)体现了栈里的一切有用信息——历史。

    前面我们已经对LR(0)文法进行了定义,下面我们来看一下LR(0)分析表是如何构造的。
    

    对于LR(0)文法,我们可以直接从它的项目集规范族C和活前缀识别自动机的状态转换函数GO构造出LR分析表。下面是构造LR(0)分析表的算法。

    假定C={I0, I1,…,In},令每个项目集Ik的下标k为分析器的一个状态,因此,G’的LR(0)分析表含有状态0,1,…,n。令那个含有项目S’→.S的Ik的下标k为初态。ACTION子表和GOTO子表可按如下方法构造:

    (1)若项目A→α.aβ属于Ik且GO (Ik,
    a)= Ij, a为终结符,则置ACTION[k, a]为“把状态j和符号a移进栈”,简记为“sj”;

    (2)若项目A→α.属于Ik,那么,对任何终结符a,置ACTION[k,a]为“用产生式A→α进行规约”,简记为“rj”;其中,假定A→α为文法G’的第j个产生式;

    (3)若项目S’→S.属于Ik, 则置ACTION[k,
    #]为“接受”,简记为“acc”;

    (4)若GO (Ik, A)= Ij, A为非终结符,则置GOTO[k, A]=j;

    (5)分析表中凡不能用上述1至4填入信息的空白格均置上“出错标志”。

    按上述算法构造的含有ACTION和GOTO两部分的分析表,如果每个入口不含多重定义,则称它为文法G的一张LR(0)分析表。具有LR(0)表的文法G称为一个LR(0)文法,LR(0)文法是无二义的。

    例如,文法G(E)的拓广文法如下:

    (0)S’→E

    (1)E→aA

    (2)E→bB

    (3)A→cA

    (4)A→d

    (5)B→cB

    展开全文
  • LR1文法分析句子

    千次阅读 2019-06-09 16:29:32
    LR1.java import java.io.BufferedReader; import java.io.FileReader; import java.util.ArrayList; import java.util.List; public class LR1 { private List<String> nonTerminals=new ArrayList<...

    LR1.java

    import java.io.BufferedReader;
    import java.io.FileReader;
    import java.util.ArrayList;
    import java.util.List;
    
    public class LR1 {
    	private List<String> nonTerminals=new ArrayList<String>();//非终结符集合
    	private List<String> terminals=new ArrayList<String>();//终结符集合
    	private List<ArrayList<String>> productions=new ArrayList<ArrayList<String>>();//产生式集合
    	private List<ArrayList<String>> pros=new ArrayList<ArrayList<String>>();//产生式集合
    	List<String> conbine=new ArrayList<String>();//combine存储所有的文法符号(非终结符+终结符)
    	private String start=null;//开始符号
    	String[][] a=new String[60][60];//分析表
    	
    	public LR1() {
    		// TODO Auto-generated constructor stub
    	}
    	public void analyse(String str) {
    		initAnalysisTable();//先初始化分析表
    		//输出分析表
    		System.out.println("*******************分析表************************");
    		for(int i=0;i<60;i++) {
    			for(int j=0;j<60;j++) {
    				if(a[i][j]!=null) {
    					System.out.println(i+"+"+conbine.get(j)+"->"+a[i][j]);
    				}
    			}
    		}
    		
    		Stack state=new Stack();//状态栈
    		Stack analysis =new Stack();//符号栈
    		state.push("0");
    		analysis.push("#");
    		
    		int tt=0,i=0;//tt记录步骤次数,i记录句子指针位置
    		String firstChar=str.substring(i,i+1);
    		int m = Integer.parseInt(state.getTopObjcet());
    		int n = conbine.indexOf(firstChar);
    		//如果输入符号中含有非法符号,即不属于当前文法的文法符号集合,提示并终止程序
    		if(n==-1) {
    			System.out.println("出错了!!!输入符号中含有非法符号");
    			return;
    		}
    		//System.out.println(conbine);
    		while(a[m][n]!="acc") {
    			System.out.println("************步骤"+(++tt)+"*************");
    			System.out.print("状态栈:");
    			state.output();
    			System.out.print("符号栈:");
    			analysis.output();
    			System.out.print("输入串:");
    			System.out.println(str.substring(i));
    			System.out.print("执行动作:");
    			System.out.print("ACTION["+m+","+firstChar+"]="+a[m][n]+"    ");
    			if(a[m][n]==null) {
    				System.out.println("出错了!!!该句子语法错误");
    				break;
    			}else if(a[m][n].startsWith("S")) {
    				//System.out.println(a[m][n].substring(1, a[m][n].length()));
    				state.push(a[m][n].substring(1, a[m][n].length()));
    				analysis.push(firstChar);
    				System.out.println("\nACTION["+m+","+firstChar+"]="+a[m][n]+",移进"+firstChar+",状态"+a[m][n].substring(1, a[m][n].length())+"入栈");
    				firstChar=str.substring(++i,i+1);
    			}else if(a[m][n].startsWith("r")) {
    				int loc = Integer.parseInt(a[m][n].substring(1, a[m][n].length()));
    				ArrayList<String> pp = productions.get(loc);
    				String mm="";
    				String nn="";
    				for(int j=0;j<pp.size()-1;j++) {
    					mm+=state.pop();
    					nn+=analysis.pop();
    				}
    				analysis.push(pp.get(0));
    				int x = Integer.parseInt(state.getTopObjcet());
    				int y = conbine.indexOf(pp.get(0));
    				System.out.println("GOTO["+x+","+pp.get(0)+"]="+a[x][y]);
    				System.out.println("ACTION["+m+","+firstChar+"]="+a[m][n]+"按规则"+a[m][n].substring(1, a[m][n].length())+
    						"将"+mm+"归约到"+pp.get(0)+",弹出栈顶状态"+mm+"、符号"+nn+",且GOTO["+x+","+pp.get(0)+"]="+a[x][y]+
    						",状态"+a[x][y]+"入栈,符号"+pp.get(0)+"入栈");
    				state.push(a[x][y]);
    			}
    			m = Integer.parseInt(state.getTopObjcet());
    			n = conbine.indexOf(firstChar);
    			if(n==-1) {
    				System.out.println("出错了!!!输入符号中含有非法符号");
    				return;
    			}
    		}
    		if(a[m][n]=="acc") {
    			System.out.println("************步骤"+(++tt)+"*************");
    			System.out.print("状态栈:");
    			state.output();
    			System.out.print("符号栈:");
    			analysis.output();
    			System.out.print("输入串:");
    			System.out.println(str.substring(i));
    			System.out.print("执行动作:");
    			System.out.println("ACTION["+m+","+firstChar+"]="+a[m][n]+",分析成功");
    		}
    	}
    	//得到分析表
    	public void initAnalysisTable(){
    		List<List<String>> originalCollect=new ArrayList<List<String>>();//初态项目集
    		List<List<List<String>>> collect=new ArrayList<List<List<String>>>();//LR项目集规范族collect
    		terminals.add("#");
    		ArrayList<String> pro=new ArrayList<String>();
    		pro.addAll(productions.get(0));//获取第一个产生式S'→S
    		pro.add(1,".");//转换为项目
    		pro.add(",");
    		pro.add("#");
    		originalCollect.add(pro);
    		closure(pro,originalCollect);//求 Closure{S'→·S,#},得初态项目集 originalCollect
    		//System.out.println(originalCollect);
    		collect.add(originalCollect);//将初态项目集加入到LR项目集规范族collect
    		
    		System.out.println("*************GO函数***************");
    		conbine.addAll(nonTerminals);
    		conbine.addAll(terminals);
    		//System.out.println("conbine="+conbine);
    		int length=-1,t=0;
    		while(length<collect.size()) {//当项目集规范族collect的大小不再变化时终止
    			length=collect.size();//记录项目集规范族collect的变化前的大小
    			for(;t<collect.size();t++) {//遍历collect中的项目集即状态
    				List<List<String>> mo=collect.get(t);
    				for(int i=0;i<conbine.size();i++) {
    					List<List<String>> p=go(t,mo,conbine.get(i));//当状态遇到文法符号conbine.get(i)时采取的动作或者说项目集遇到文法符号得到的项目集
    					if(p.size()>0) {
    						System.out.println("+++++++++++++");
    						System.out.println("GO(I"+t+","+conbine.get(i)+")="+p);
    
    						if(!collect.contains(p)) {
    							collect.add(p);//将go函数得到的项目集加入到collect中
    						}
    						
    						if(nonTerminals.contains(conbine.get(i))) {
    							a[t][i]=""+collect.indexOf(p);//如果当前文法符号是非终结符标记为:应移入的下一状态。GOTO
    						}else {
    							a[t][i]="S"+collect.indexOf(p);//如果当前文法符号是终结符标记为:把当前输入符号及下一个状态移入分析栈中。ACTION	
    						}
    					}
    				}	
    			}
    		}
    	}
    	//文法文本解析与存储
    	public void initialize(String filePath) {
    		try {
    			BufferedReader br = new BufferedReader(new FileReader(filePath));
    			String s;
    			String[] sss=null;
    			for(s=br.readLine();s!=null;s=br.readLine()) {
    				if(s.indexOf("{")!=-1) {
    					int begin=s.indexOf("{");
    					int end=s.indexOf("}");
    					sss=s.substring(begin+1, end).split(",");
    				}
    				//判断每一行是非终结符、终结符、产生式还是开始符号
    				if(s.charAt(0)=='V'&&s.charAt(1)=='n') {
    					//存储非终结符
    					for(int i=0;i<sss.length;i++) {
    						nonTerminals.add(sss[i]);
    					}
    				}else if(s.charAt(0)=='V'&&s.charAt(1)=='t') {
    					//存储终结符
    					for(int i=0;i<sss.length;i++) {
    						terminals.add(sss[i]);
    					}
    				}else if(s.charAt(0)=='P') {
    					//存储产生式
    					for(int i=0;i<sss.length;i++) {
    						
    						String left=sss[i].substring(0, 1);//产生式左部:一个非终结符
    						String[] right=sss[i].substring(sss[i].indexOf(">")+1).split("\\|");//某个产生式左部对应的产生式右部集合
    						for(int j=0;j<right.length;j++) {
    							ArrayList<String> p=new ArrayList<String>();
    							ArrayList<String> pro=new ArrayList<String>();
    							p.add(left);
    							pro.add(left);
    							p.add(right[j]);
    							for(int t=0;t<right[j].length();t++) {
    								pro.add(right[j].substring(t,t+1));
    							}
    							productions.add(pro);
    							pros.add(p);
    						}
    						
    					}
    				}else if(s.charAt(0)=='S') {
    					//存储开始符号
    					start=s.substring(2);
    					ArrayList<String> pro=new ArrayList<String>();
    					pro.add("S'");
    					pro.add(start);
    					productions.add(0, pro);
    				}
    				
    				sss=null;
    			}
    			br.close();
    		}catch(Exception e) {
    			e.printStackTrace();
    		}
    	}
    	//文法输出
    	public void output() {
    		System.out.println("非终结符有");
    		for(int i=0;i<nonTerminals.size();i++) {
    			System.out.println(nonTerminals.get(i));
    		}
    		System.out.println("终结符有");
    		for(int i=0;i<terminals.size();i++) {
    			System.out.println(terminals.get(i));
    		}
    		System.out.println("产生式有");
    		for(int i=0;i<productions.size();i++) {
    			System.out.println(productions.get(i));
    					
    		}
    		System.out.println("开始符号有");
    		System.out.println(start);
    	}
    	//定义单个项目item的闭包函数
    	public void closure(List<String> item,List<List<String>> result) {
    		//System.out.println("result***"+result);
    		int loc=item.indexOf(".");
    		//如果当前项目是A→α·Bβ,a的形式
    		int dot = item.indexOf(",");
    		if(loc<dot-1 && nonTerminals.contains(item.get(loc+1))) {
    			String m=item.get(loc+1);
    			//如果期待的下一个符号是非终结符,循环遍历productions中的每一条规则
    			for(int i=0;i<productions.size();i++) {
    				ArrayList<String> pro=new ArrayList<String>();
    				pro.addAll(productions.get(i));
    				//如果产生式是B→γ的形式
    				if(m.equals(pro.get(0))) {
    					pro.add(1, ".");
    					List<String> tem = item.subList(loc+2,item.size());
    					List<String> right = new ArrayList<String>();
    					right.addAll(tem);
    					right.remove(",");//得到βa
    					List<String> firstSet = new ArrayList<String>();
    					findFirstSet(right, firstSet);//得到FIRST(βa)
    					pro.add(",");
    					pro.addAll(firstSet);//将first集加入到B→.γ对应的项目中用,分隔,
    					
    					//System.out.print(pro.subList(0, pro.indexOf(",")).toString().equals(item.subList(0, dot).toString()));
    					//System.out.println(item+"->"+pro);
    					
    					if(result.contains(pro) || pro.subList(0, pro.indexOf(",")).toString().equals(item.subList(0, dot).toString())) {continue;}
    					result.add(pro);//将B→.γ,FIRST(βa)对应的项目加入到闭包集合中
    					if(nonTerminals.contains(pro.get(2))){
    						closure(pro,result);//如果γ的第一个符号是非终结符,递归查找pro的闭包函数
    					}
    					
    				}
    			}
    		}
    	}
    	//First集
    	public void findFirstSet(List<String> right,List<String> first){
    		//System.out.println(right);
    		String single=right.get(0);
    		if(terminals.contains(single) && !first.contains(single)) {
    			first.add(single);
    		}else if(single.equals("ε")) {
    			right=right.subList(1, right.size());
    			findFirstSet(right, first);
    		}else {
    			//说明此产生式右部首字符是一个不同于左部的非终结符
    			for(int i=0;i<productions.size();i++) {
    				ArrayList<String> pro =new ArrayList<String>();
    				pro.addAll(productions.get(i));
    				if(single.equals(pro.get(0)) && !single.equals(pro.get(1))) {
    					findFirstSet(pro.subList(1, pro.size()), first);
    				}
    			}
    		}
    	}
    	//定义当输入文法符号时项目集的GO函数
    	public List<List<String>> go(int t,List<List<String>> items,String m) {
    		List<List<String>> resultList = new ArrayList<List<String>>();//存储当输入符号m时items对应的项目集
    		//循环遍历项目集中的每个项目
    		for(int i=0;i<items.size();i++) {
    			List<String> list=new ArrayList<String>();
    			list.addAll(items.get(i));
    			int loc=list.indexOf(".");
    			int dot = list.indexOf(",");
    			
    			if(loc<dot-1) {
    				String n=list.get(loc+1);//期待的下一个符号
    				if(n.equals(m)) {//如果期待的下一个符号与当前文法符号一样
    					//System.out.println(items+":"+loc);
    					list.set(loc, n);
    					list.set(loc+1, ".");
    					if(!resultList.contains(list))
    						resultList.add(list);
    					closure(list,resultList);//求当前项目的闭包集合并加入到re中
    				}
    			}else if(loc==(dot-1) ) {//如果当前项目是可归约的
    				//System.out.println(loc+"*************"+dot);
    				int o = terminals.indexOf(m);
    				List<String> searchWord = list.subList(dot+1, list.size());//得到可归约项目的搜索符号
    				list = list.subList(0, loc);
    				//如果当前项目是S'->S,# 时,表示此时为可接受状态,记录到分析表中,标记为:可接受
    				if(list.equals(productions.get(0))) {
    					//System.out.println(list+","+m);
    					if(o==terminals.size()-1) {
    						a[t][o+nonTerminals.size()]="acc";
    					}
    				}else {
    					//查找可归约项目对应的规则
    					for(int j=1;j<productions.size();j++) {//查找可归约项目对应的规则
    						if(list.equals(productions.get(j))) {		
    							if(o>=0 && searchWord.contains(m)) {
    								a[t][o+nonTerminals.size()]="r"+j;//记录到分析表中,标记为:可按第j条规则归约
    							}
    							break;
    						}
    					}
    				}
    			}
    		}
    		return resultList;
    	}
    	
    }
    

    辅助类Stack.java

    import java.util.ArrayList;
    import java.util.List;
    import java.util.EmptyStackException;
    
    public class Stack {
        private List<String> pool = new ArrayList<String>();
        public Stack() {
        }
        public boolean isEmpty() {
            return pool.isEmpty();
        }
    
        // 获取栈顶元素
        public String getTopObjcet() {
            if (isEmpty()) {return null;}
            return pool.get(pool.size()-1);
        }
        //弹出栈操作
        public String pop() {
            String e=pool.get(pool.size()-1);
            pool.remove(pool.size()-1);
            return e;
        }
        //压入栈
        public void push(String e) { 
        	pool.add(e);
    
        }
        // 获取当前栈大小
        public int getStatckSize() {
            return pool.size();
        }
        //输出当前栈
        public void output() {
        	System.out.println(pool);
        }
    
    }

    测试类Test.java

    
    public class Test {
    
    	public Test() {
    		// TODO Auto-generated constructor stub
    	}
    	public static void main(String[] args) {
    		String str = "i*i+i#";//测试数据_1对应的句子
    		//String str = "abbcde#";//测试数据_2对应的句子
    		//String str = "aacbb#";//测试数据_3对应的句子
    		LR1 lr=new LR1();
    		lr.initialize("D:\\Project\\Java\\LR0\\src\\测试数据_4.txt");
    		lr.output();
    		lr.analyse(str);
    		
    	}
    }
    

    测试数据_1.txt

    G=(Vn,Vt,S,P)
    Vn={E,T,F}
    Vt={+,*,(,),i}
    P={E->E+T,E->T,T->T*F,T->F,F->(E),F->i}
    S=E
    //"i*i+i#"测试句子

    测试数据_2.txt

    G=(Vn,Vt,S,P)
    Vn={S,A,B}
    Vt={a,c,e,b,d}
    P={S->aAcBe,A->b,A->Ab,B->d}
    S=S
    //"abbcde#"测试句子

    测试数据_3.txt

    G=(Vn,Vt,S,P)
    Vn={S,A,B}
    Vt={a,b,c,d}
    P={S->A,S->B,A->aAb,A->c,B->aBb,B->d}
    S=S
    //"aacbb#"测试句子

     

    展开全文
  • LR(1)文法智能分析

    千次阅读 2015-07-31 09:27:44
    LR1文法全智能分析 // by hfut yzk#include "stdafx.h" #include #include #include #include #include #include #include #include using namespace std; #pragma region vars struct xiangmu //一...

    LR1文法全智能分析


    // by  hfut yzk
    #include "stdafx.h"
    #include<fstream>
    #include<string>
    #include<map>
    #include<vector>
    #include<stack>
    #include<set>
    #include<cstring>
    #include<queue>
    using namespace std;
    
    #pragma region vars
    struct xiangmu										  //一个项目
    {
        int nump;										   //产生式编号
        int id;											 //.的位置
        string fst;										 //集合
    };
    
    map<char,int>getnum;	
    char getchars[100];									//获得对应字符
    vector<string>proce;								  //产生式
    int table[30][30];									 //预测分析表 -1
    int tb_s_r[30][30];								   //是移进项还是规约项,-1,-2.
    int num=0;int numvt=0;							 //numvt是终结符集合,0是‘#’,numvt表空字
    string first[100];									//每个符号的first集
    bool gotfirst[100];									//是否已经完成FIRST集合
    string getp[100];								//获得某终结符在左边的产生式集合
    vector<vector<xiangmu> >v;						//项目集族
    int e[100][3];
    int head[100];
    int nume=0;		                             //链式前向星项目集族图
    
    
    fstream cin ("H:/课程设计/编译原理2015/lr(1)/in.txt");
    fstream cout ("H:/课程设计/编译原理2015/lr(1)/out.txt");
    fstream cout2 ("H:/课程设计/编译原理2015/lr(1)/out2.txt");
    #pragma endregion
    
    #pragma region functions
    void readin();
    void getpp();
    void dfsgetfirst(int nv,int nump);
    void get_first();
    void clear() ;
    void addegde(int from,int to,int w)    ;
    inline bool xmeq(xiangmu a,xiangmu b);
    bool isin(xiangmu a,vector<xiangmu> b) ;								  //xm a is in xmji b
    bool xmjieq(vector<xiangmu> a,vector<xiangmu> b) ;						 //两个项目集是否相等
    vector<xiangmu>  hebing(vector<xiangmu>a ,vector<xiangmu>b) ;			//合并项目集 a,b 复给 a
    int xmji_isin_xmjizu(vector<xiangmu>a,vector<vector<xiangmu> >b) ;     //查找项目集,若有,则返回编号,一举俩得
    vector<xiangmu> get_close(xiangmu t)    ;                              //对项目 T作闭包
    void get_xiangmujizu()        ;									     //获得项目集族
    void print_xmjizu()           ;                                     //打印项目集族
    bool get_table();
    void print_table();
    void  print_now_state(int count,stack<int>state,stack<int>wd,int i);
    bool analyze(); 
    
    
    #pragma endregion
    
    /*******************************************读入vt,vn,编号1-num,读入所有产生式*********************************************/
    void readin()                                  
    {
        memset(table,-1,sizeof(table));
        getnum['#']=0;
        getchars[0]='#';
        //cout<<"请输入所有终结符:"<<endl;
        char x;
        do
        {
          cin>>x;
          getnum[x]=++num;
          getchars[num]=x;
        }while(cin.peek()!='\n');
         numvt=++num;
         getnum['@']=numvt;        //kong zi
         getchars[num]=('@');
       // cout<<"请输入非终结符集:"<<endl;
        do
        {
          cin>>x;
          getnum[x]=++num;
          getchars[num]=x;
        }while(cin.peek()!='\n');
     //   cout<<"输入所有产生式(空字用‘@’表示),以‘end’结束:"<<endl;
        string pro;
         while(cin>>pro&&pro!="end")
         {
             string ss;
             ss+=pro[0];
             for(int i=3;i<pro.size();i++)
             {
                 if(pro[i]=='|')
                 {
                      proce.push_back(ss);
                      ss.clear();ss+=pro[0];
                 }
                 else
                 {
                     ss+=pro[i];
                 }
             }
              proce.push_back(ss);
        }
    }
    
    void getpp()
    {
        for(int i=0;i<proce.size();i++)
        {
            int temp=getnum[proce[i][0]];
            getp[temp]+=char('0'+i);
        }
    }
    
    /****************************************************获得first集************************************************************/
    void dfsgetfirst(int nv,int nump)							 //当前的符号,和对应产生式编号
    {
       int temp=getnum[proce[nump][1]];							 //产生式推出来的首符
        gotfirst[nump]=1;										  //标记
        if(temp<=numvt)first[nv]+=char('0'+temp);				//是终结符
        else
        {
            for(int i=0;i<getp[temp].size();i++)				 //所有temp可以推出来的符号对应的产生式
              {
                  if(proce[nump][0]==proce[nump][1])continue;	//左递归的产生式不用不影响求fisrt集
                  dfsgetfirst(temp,getp[temp][i]-'0');
              }
    
            first[nv]+=first[temp];								//回溯时候沿途保存
        }
    }
    void get_first()
    {
        for(int i=1;i<=numvt;i++)										  //    终结符first集合是它自己.
        {
            first[i]=char('0'+i);
        }
         for(int i=0;i<proce.size();i++)
        {
            if(proce[i][0]==proce[i][1])continue; //左递归的产生式不用不影响求fisrt集
            if(gotfirst[i])continue;              //已经生成。
            int temp=getnum[proce[i][0]];
              dfsgetfirst(temp,i);
        }
    }
    /***************************************************添加边*****************************************************************/
    void addegde(int from,int to,int w)           
    {
        e[nume][0]=to;e[nume][1]=head[from];head[from]=nume;
        e[nume++][2]=w;
    }
    /******************************************************初始化函数*********************************************************/
    void clear()                
    {
        for(int i=0;i<100;i++)
           head[i]=-1;
         for(int i=0;i<30;i++)
           for(int j=0;j<30;j++)
             tb_s_r[i][j]=table[i][j]=-1;
        nume=0;
    }
    
    
    /******************************************************获得项目集族*******************************************************/
    inline bool xmeq(xiangmu a,xiangmu b)
    {
        if(a.fst==b.fst&&a.id==b.id&&a.nump==b.nump)return 1;
        return 0;
    }
    
    bool isin(xiangmu a,vector<xiangmu> b)      //xm a is in xmji b
    {
        for(int i=0;i<b.size();i++)
        {
            if(xmeq(a,b[i]))return 1;
        }
        return 0;
    }
    
    vector<xiangmu>  hebing(vector<xiangmu>a ,vector<xiangmu>b)  //合并项目集 a,b 复给 a
    {
        for(int i=0;i<b.size();i++)
        {
            if(isin(b[i],a))continue;
            else
             a.push_back(b[i]);
        }
        return a;
    }
    
    bool xmjieq(vector<xiangmu> a,vector<xiangmu> b)  //两个项目集是否相等
    {
        if(a.size()!=b.size())return 0;
         for(int i=0;i<a.size();i++)
         {
            if(!isin(a[i],b))return 0;
         }
         return 1;
    }
    
    int xmji_isin_xmjizu(vector<xiangmu>a,vector<vector<xiangmu> >b)  //查找项目集,若有,则返回编号,一举俩得
    {
        for(int i=0;i<b.size();i++)
        {
            if(xmjieq(a,b[i]))return i;
        }
        return -1;
    }
    
    
    vector<xiangmu> get_close(xiangmu t)									     //对项目 T作闭包
    {
       vector<xiangmu> temp;
       temp.push_back(t);
        queue<xiangmu> q;												  //bfs完成闭包
        q.push(t);
        while(!q.empty())
        {
          xiangmu cur=q.front();
          q.pop();
          if(cur.id==proce[cur.nump].size())							  //归约项舍去
              continue;
         int tt=getnum[proce[cur.nump][cur.id]];							   //tt is thm num of '.'zhihoudefuhao
          if(tt<=numvt)   continue ;									  //若是终结符,则不必找了
          for(int i=0;i<getp[tt].size();i++)							 //对应产生式的编号
           {
              xiangmu c;
             c.id=1;                               //
             c.nump=getp[tt][i]-'0';             //
            if(proce[cur.nump].size()-cur.id==1)						 // the last : A->BC.D,a/b
              c.fst+=cur.fst;
             else													 //not the last  :A->B.CFb,a/b
            {
              int tttnum=getnum[proce[cur.nump][cur.id+1]];
              c.fst+=first[tttnum];
            }
             if(!isin(c,temp))									    //排重,新的项目就加入。
             {
                 q.push(c);
                 temp.push_back(c);
             }
            }
          }
          return temp;
    }
    
    
    void get_xiangmujizu()             //获得项目集族
    {
        vector<xiangmu>temp;
        xiangmu t;
        t.nump=0;t.id=1;t.fst+='0';    //初始的项目集:0
        temp=get_close(t);
        queue<vector<xiangmu> >q;        //bfs法获得
        q.push(temp);
        v.push_back(temp);             //第一个入
        while(!q.empty())
        {
             vector<xiangmu> cur=q.front();
             q.pop();
             for(int i=1;i<=num;i++)     //所有符号
             {
                 if(i==numvt)continue;      //'#'
                 vector<xiangmu> temp;
                  for(int j=0;j<cur.size();j++)     //该项目集中的所有项目
                  {
                     if(cur[j].id==proce[cur[j].nump].size())continue;  //是规约项目,无法再读入了
                     int tt=getnum[proce[cur[j].nump][cur[j].id]];
                    if(tt==i)                                          //can read in 符号i
                    {
                        xiangmu tempt;
                        tempt.fst=cur[j].fst;
                        tempt.id=cur[j].id+1;
                        tempt.nump=cur[j].nump;
                        temp=hebing(temp,get_close(tempt));
                    }
                  }
                  if(temp.size()==0)continue;             //该符号无法读入。
                    int numcur=xmji_isin_xmjizu(cur,v);   //当前节点标号
                    int tttnum=xmji_isin_xmjizu(temp,v);  //新目标标号
                       if(tttnum==-1)                    //新的项目集
                       {
                        v.push_back(temp);
                        q.push(temp);
                        addegde(numcur,v.size()-1,i) ;   //添加边,权为读入的符号
                      }
                       else                             //老的项目集
                       {
                        addegde(numcur,tttnum,i);
                       }
             }
        }
    }
    
    
    /************************************************项目集族打印*********************************************************/
    void print_xmjizu()              //打印项目集族
    {
        for(int i=0;i<v.size();i++)
        {
            cout<<"项目集"<<i<<":"<<endl;
          for(int j=0;j<v[i].size();j++)
            {
              cout<<proce[v[i][j].nump]<<" "<<v[i][j].id<<" "<<v[i][j].fst<<endl;
            }
          cout<<endl;
        }
        for(int i=0;i<v.size();i++)
        {
            for(int j=head[i];j!=-1;j=e[j][1])
            {
                cout<<"  "<<getchars[e[j][2]]<<endl;
                cout<<i<<"--->"<<e[j][0]<<endl;
            }
        }
    }
    
    
    
    /*********************************获得LR1分析表*************************************************************************/
    bool get_table()											  //获得分析表table[i][j]=w:状态i-->j,读入符号W。
    {
        for(int i=0;i<v.size();i++)								  //遍历图
        {
            for(int j=head[i];j!=-1;j=e[j][1])
            {
                if(table[i][e[j][2]]!=-1)return 0;				     //多重入口,报错.
                 table[i][e[j][2]]=e[j][0];
                tb_s_r[i][e[j][2]]=-1;							  //移近项-1。
            }
        }
        for(int i=0;i<v.size();i++)								 //遍历所有项目
        {
          for(int j=0;j<v[i].size();j++)
            {
                if(v[i][j].id==proce[v[i][j].nump].size())					 //归约项
                {
                    for(int k=0;k<v[i][j].fst.size();k++)
                       {
                          if(table[i][(v[i][j].fst)[k]-'0']!=-1)return 0;           //多重入口,报错.
                         if(  (v[i][j].fst)[k]=='0'&&v[i][j].nump==0)
                            table[i][(v[i][j].fst)[k]-'0']=-3 ;           //接受态。
                         else
                         {
                            table[i][(v[i][j].fst)[k]-'0']=v[i][j].nump;
                            tb_s_r[i][(v[i][j].fst)[k]-'0']=-2;            //归约态
                         }
                       }
                }
             }
         }
         return 1;
    }
    
    
    void print_table()
    {
       // cout<<"LR(1)分析表:"<<endl;
      //  cout<<"状态   "<<"         actoin     "<<endl;
    	cout<<num<<" "<<v.size()<<endl;
         for(int j=0;j<=num;j++)
            {
                if(j==numvt)continue;
                cout<<"    "<<getchars[j];
            }
    	  cout<<endl;
         
        for(int i=0;i<v.size();i++)
        {
            cout<<i<<"   ";
            for(int j=0;j<=num;j++)
            {
                if(j==numvt)continue;
    			if(j<numvt)
                {
    				if(table[i][j]==-3)     cout<<"acc"<<"  ";               //接受
                    else if(table[i][j]==-1)cout<<"X  ";                       //空
    				else if(tb_s_r[i][j]==-1)cout<<"s"<<table[i][j]<<"   ";  //移近
    				else if(tb_s_r[i][j]==-2)cout<<"r"<<table[i][j]<<"   ";  //归约
    			}
    			else 
    			{
    				if(table[i][j]==-3)     cout<<"acc"<<"  ";               //接受
                    else if(table[i][j]==-1)cout<<"X  ";                       //空
    				else if(tb_s_r[i][j]==-1)cout<<""<<table[i][j]<<"   ";  //移近
    				else if(tb_s_r[i][j]==-2)cout<<""<<table[i][j]<<"   ";  //归约
    			}
    
            }
            cout<<endl;
        }
    
    }
    
    
    string word;
    void  print_now_state(int count,stack<int>state,stack<int>wd,int i)
    {
        cout2<<count<<'\t'<<'\t';
        stack<int>temp;
        while(!state.empty())
        {
            temp.push(state.top());
            state.pop();
        }
        while(!temp.empty())
        {
            cout2<<temp.top();
            temp.pop();
        }
        cout2<<'\t'<<'\t';
         while(!wd.empty())
        {
            temp.push(wd.top());
            wd.pop();
        }
        while(!temp.empty())
        {
            cout2<<getchars[temp.top()];
            temp.pop();
        }
        cout2<<'\t'<<'\t';
        for(int j=i;j<word.size();j++)
            cout2<<word[j];
        cout2<<'\t'<<'\t';
    }
    
    
    /*********************************************分析程序**************************************************************/
    bool analyze()
    {
        cout2<<"       "<<word<<"的分析过程"<<endl;
        cout2<<"步骤\t\t"<<"状态栈\t\t"<<"符号栈\t\t"<<"输入串\t\t"<<"动作说明"<<endl;
          stack<int>state;   //俩个栈:状态栈和符号栈
          stack<int>wd;
          int count=0;
          state.push(0);     //初始化
          wd.push(0);        //'#'
        for(int i=0;;)       //i,读入文本的
        {
            int cur=state.top();
            if(table[cur][getnum[word[i]]]==-1)    // 空白,报错误
                 return 0;
            if(table[cur][getnum[word[i]]]==-3)  //接受态
                {
                    print_now_state(count++,state,wd,i);
                    cout2<<"      恭喜!acc!"<<endl;
                    return 1;
                }
            if(tb_s_r[cur][getnum[word[i]]]==-1)       //移进项
            {
                print_now_state(count++,state,wd,i);
               int newstate=table[cur][getnum[word[i]]];
                cout2<<"action["<<cur<<","<<getnum[word[i]]<<"]="<<newstate;
                cout2<<",状态"<<newstate<<"入栈"<<endl;
                wd.push(getnum[word[i]]);
                state.push(newstate);
                i++;
            }
            else if(tb_s_r[cur][getnum[word[i]]]==-2)         //归约
            {
                print_now_state(count++,state,wd,i);
    
                 int numpro=table[cur][getnum[word[i]]];   //用该产生式归约
                int len=proce[numpro].size()-1;
                for(int ii=0;ii<len;ii++)                 //弹栈
                 {
                     wd.pop();
                     state.pop();
                 }
                 wd.push(getnum[proce[numpro][0]]);    //新入
                 int cur=state.top();
                cout2<<"用"<<proce[numpro][0]<<"->";
                 for(int ii=1;ii<=len;ii++)
                     cout2<<proce[numpro][ii];
                cout2<<"进行归约,"<<"goto["<<cur<<","<<getnum[word[i]]<<"]="<<table[cur][getnum[proce[numpro][0]]];
                cout2<<"入栈"<<endl;
                 state.push(table[cur][getnum[proce[numpro][0]]]);
            }
        }
        return 1;
    }
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
        clear();
        readin();
        getpp();
        get_first();
        get_xiangmujizu();
        if(!get_table())
        {
           // cout<<"此文法在生成分析表时候有多重入口,非LR(1)文法!"<<endl;
    		cout<<-1<<endl;
            return 0;
        }
      // print_xmjizu();
       print_table();
       //cout<<"请输入字:"<<endl;
       cin>>word;
       word+='#';
       if(!analyze())
           cout2<<"error!"<<endl;
       else;
    
        return 0;
    }
    



    import java.util.*;
    
    import javax.swing.*;
    
    import java.awt.*;
    import java.awt.event.ActionEvent;
    import java.awt.event.ActionListener;
    import java.awt.geom.GeneralPath;
    import java.lang.Thread;
    import java.lang.Runnable;
    
    public class LR1  extends JFrame 
    {
    	
    	JButton go_table;
    	JButton go_ana;
    	 public LR1()  throws Exception                                                       //初始化构造函数
    	 {
    		 setBounds(0, 0, 1380, 800);                                                      //设定大小   
             this.setBackground(Color.WHITE);										   //背景色	
             this.setTitle("LR(1)文法分析");
             this.setLayout(null);
             readin();
             
               JLabel title= new JLabel("LR1   文   法   分   析",JLabel.CENTER);     
    	 		title.setFont(new Font("长城行楷体", Font.BOLD, 80));               //标签相关设置
    	 		title.setForeground(new Color(0,0,0));
    	 		title. setBounds(0,0,1380,100); 
    	 	    add(title); 
             
             
             
             
             go_table=new JButton("LR1分析表=>");
             go_ana=new JButton("LR1分析器=>");
             go_table.setBounds(700, 150, 400, 100);
             go_ana.setBounds(700, 400, 400, 100);
             Font f=new Font("长城行楷体",Font.BOLD,40);
            
             go_table.setFont(f);
             go_ana.setFont(f);
             go_table.addActionListener(new presslistener1());
             go_ana.addActionListener(new presslistener2());
             
             add(go_table);
             add(go_ana);
             
             this.setVisible(true);
    	 }
    		void readin()throws Exception 
    		{
    			java.io.File file= new java.io.File("H:/课程设计/编译原理2015/lr(1)/in.txt");                      //读入数据
    			Scanner input =new Scanner(file);	
    	
    		  
     		    JLabel vt= new JLabel("终结符:");     
    	 		vt.setFont(new Font("长城行楷体", Font.BOLD, 20));               //标签相关设置
    	 		vt.setOpaque(true);
    	 		vt.setForeground(new Color(0,0,0));
    	 		vt. setBounds(0,100,200,50); 
    	 	    add(vt); 
    	 	    
    	 	    String ss=input.nextLine();
    	 	    JTextField temp0=new JTextField(ss);
    		   temp0. setBounds(0,150,500,50);
    			temp0.setFont(new Font("长城行楷体", Font.BOLD, 15));
    		     this.add(temp0);
    	 	    
    		       JLabel vn= new JLabel("非终结符:");     
    		 		vn.setFont(new Font("长城行楷体", Font.BOLD, 20));               //标签相关设置
    		 		vn.setOpaque(true);
    		 		vn.setForeground(new Color(0,0,0));
    		 		vn. setBounds(0,200,200,50); 
    		 	    add(vn); 
    	 		 
    		 	    ss=input.nextLine();
    			 	 JTextField temp1=new JTextField(ss);
    				temp1. setBounds(0,250,500,50);
    				temp1.setFont(new Font("长城行楷体", Font.BOLD, 15));
    				 this.add(temp1);
    				
    				     JLabel pro= new JLabel("产生式:   ");     
    				     pro.setFont(new Font("长城行楷体", Font.BOLD, 20));               //标签相关设置
    				     pro.setOpaque(true);
    				     pro.setForeground(new Color(0,0,0));
    				     pro. setBounds(0,300,200,50); 
    				 	   add(pro); 
    				 	   
    				 	   int cnt=0;
    				 	   do
    				 	   {
    				 		    ss=input.next();
    				 		    if(ss.equals("end"))break;
    				 		    
    						 	  JTextField temp=new JTextField(ss);
    							temp. setBounds(0,350+cnt*50,500,50);
    								temp.setFont(new Font("长城行楷体", Font.BOLD, 15));
    							     this.add(temp);	   
    							     cnt++;
    				 	   }while(true);    
    		}
    
    		 class  presslistener1 implements ActionListener  
    		    {  
    		        public void actionPerformed(ActionEvent e)  
    		        {  
    		        	//LR1.this .setVisible(false);  
    		        	try {
    						show_table mytable =new show_table();
    					} catch (Exception e1) {
    						e1.printStackTrace();
    					}
    		     
    		        }     
    		    }  
    		 
    		 class  presslistener2 implements ActionListener  
    		    {  
    		        public void actionPerformed(ActionEvent e)  
    		        {  
    		        	//LR1.this .setVisible(false);  
    		        	try {
    						show_ana mytable =new show_ana();
    					} catch (Exception e1) {
    						e1.printStackTrace();
    					}
    		     
    		        }     
    		    }  
    		
         
    }

    import java.util.*;
    import javax.swing.*;
    
    import java.awt.*;
    import java.awt.event.ActionEvent;
    import java.awt.event.ActionListener;
    import java.awt.geom.GeneralPath;
    import java.lang.Thread;
    import java.lang.Runnable;
    
    public class show_ana extends JFrame  {
    	
    	int col;
    	int row;
    	
    	public show_ana()  throws Exception
    	{
    		 setBounds(0, 0, 1380, 800);                                                        //设定大小   
             this.setBackground(Color.WHITE);										   //背景色	
             this.setTitle("LR(1)文法分析过程");
             this.setLayout(null);
             
             readin();
             this.setVisible(true); 
    	}
    	
    	public void readin ()throws Exception                                       //读入图函数
     	{    
    		java.io.File file= new java.io.File("H:/课程设计/编译原理2015/lr(1)/out2.txt");                      //读入数据
    			Scanner input =new Scanner(file);	
    		  String ss=input.next();
    		
     		 /*  JLabel table= new JLabel(ss,JLabel.CENTER);     
    	 		table.setFont(new Font("长城行楷体", Font.BOLD, 20));               //标签相关设置
    	 		table.setOpaque(true);
    	 		table.setForeground(new Color(0,0,0));
    	 		table. setBounds(0,0,1380,50); 
    	 		 add(table); */
     	
     				col=5;
     				row=100;
     				
     				int curcol=1380/col;
     				int currow=25;
    
     				for(int i=0;i<col;i++)
     				{
     					JTextField temp=new JTextField(input.next());
    		 				temp. setBounds(1380/col*i,50,curcol,currow);
    		 				temp.setFont(new Font("长城行楷体", Font.BOLD, 15));
    		 			     this.add(temp);
     				}
     				
     				for(int i=0;i<row;i++)
     		 			for(int j=0;j<col;j++)
     		 			{
     		 			   if(!input.hasNext()){i=1000;break;} 
     		 				String s= input.next();
    	 					JTextField temp=new JTextField(s);
     		 				temp. setBounds(1380/col*j,50+(i+1)*currow,curcol,currow);	
     		 				temp.setFont(new Font("长城行楷体", Font.BOLD, 15));
     		 			     this.add(temp);
     		 			}
     				
     				
     				input.close(); 
           	}
    }
    

    import java.util.*;
    import javax.swing.*;
    
    import java.awt.*;
    import java.awt.event.ActionEvent;
    import java.awt.event.ActionListener;
    import java.awt.geom.GeneralPath;
    import java.lang.Thread;
    import java.lang.Runnable;
    
    public class show_table  extends JFrame  {
    	
    	int col;
    	int row;
    	
    	public show_table()  throws Exception
    	{
    		 setBounds(0, 0, 1380, 800);                                                      //设定大小   
             this.setBackground(Color.WHITE);										   //背景色	
             this.setTitle("LR(1)文法分析");
             this.setLayout(null);
           
             readin();
             this.setVisible(true); 
    	}
    	public void readin ()throws Exception                                       //读入图函数
     	{    
     		   JLabel table= new JLabel(" 状态                                                                                          ACTION                                                            GO                            ");     
    	 		table.setFont(new Font("长城行楷体", Font.BOLD, 20));               //标签相关设置
    	 		table.setOpaque(true);
    	 		table.setForeground(new Color(0,0,0));
    	 		table. setBounds(0,0,1380,50); 
    	 		 add(table); 
     			java.io.File file= new java.io.File("H:/课程设计/编译原理2015/lr(1)/out.txt");                      //读入数据
     				Scanner input =new Scanner(file);	
     				col=input.nextInt();
     				col++;
     				row=input.nextInt();
     				
     				int curcol=1380/col;
     				int currow=600/row;
     				
     				if(col==-1)             //多重入口
     				{
     					JOptionPane.showMessageDialog(null, "此文法在生成分析表时候有多重入口,非LR(1)文法!");
     					System.out.println("此文法在生成分析表时候有多重入口,非LR(1)文法!\n");
                        return ;					                
     				}
     				JTextField temp0=new JTextField();
    	 				temp0. setBounds(0,50,curcol,currow);
    	 		        this.add(temp0);
     				for(int i=0;i<col-1;i++)
     				{
     					JTextField temp=new JTextField(input.next());
    		 				temp. setBounds(1380/col*(i+1),50,curcol,currow);
    		 				temp.setFont(new Font("长城行楷体", Font.BOLD, 15));
    		 			     this.add(temp);
     				}
     				
     				for(int i=0;i<row;i++)
     		 			for(int j=0;j<col;j++)
     		 			{
     		 				String s= input.next();
    	 					if(s.equals("X"))s="";
    	 					JTextField temp=new JTextField(s);
     		 				temp. setBounds(1380/col*j,50+(i+1)*currow,curcol,currow);	
     		 				temp.setFont(new Font("长城行楷体", Font.BOLD, 15));
     		 			     this.add(temp);
     		 			}
     				
     				
     				input.close(); 
     			
           			}
    }
    

    import java.util.*;
    import javax.swing.*;
    import java.awt.*;
    import java.awt.event.ActionEvent;
    import java.awt.event.ActionListener;
    import java.awt.geom.GeneralPath;
    import java.lang.Thread;
    import java.lang.Runnable;
    public class start {
    	
    	
    	public static void main(String[] args) throws Exception
    	 {
    		 LR1 lr1= new LR1();
    		//show_table mytable =new show_table();
    	   //	show_ana myana= new show_ana();
    		
    	 }
    
    }
    


    展开全文
  • LL(1)定义:一个文法G是LL(1)的,当且仅当对于G的每一个非终结符A的任何两个不同产生式 A→α|β,下面的条件成立:SELECT( A→α)∩SELECT( A→β)=,其中, α|β不能同时ε。 解释:LL(1)的意思是,第一个L,...

    LL(1)定义:一个文法G是LL(1)的,当且仅当对于G的每一个非终结符A的任何两个不同产生式 A→α|β,下面的条件成立:SELECT( A→α)SELECT( A→β)=,其中,

    α|β不能同时ε。

    解释:LL(1)的意思是,第一个L,指的是从左往右处理输入,第二个L,指的是它为输入生成一个最左推导。1指的是向前展望1个符号。LL(1)文法是上下文无关文法的一个子集。它用的方法是自顶向下的(递归式的处理)。它要求生成的预测分析表的每一个项目至多只能有一个生成式。上面的定义说的是,任何两个不同的产生式 A→α和 A→β,选择A→α或者 A→β是不能有冲突的,即SELECT( A→α)∩SELECT( A→β)=,具体来说,就是,第一:First( A→α∩ First( A→β)=,首符集不能有交集,否则当交集中的元素出现时,选择哪个产生式进行推导是不确定的,(这其中也包含了α|β不能同时ε,否则交集就是{ε}不为空),第二:若任何一个产生式β,有ε属于First(β),应有First(A)∩Follow( A)为空(当ε属于First(β),则A有可能被空串代替,那么就要看A的下一个字符,即Follow集,即要求Follow集和First集不能相交,否则可能发生冲突)。

    LR文法:定义:如果某一文法能够构造一张分析表,使得表中每一个元素至多只有一种明确动作,则该文法称为LR文法。

    拓展:由上面的定义可以看到,LL(1)和LR文法都是无二义性的:LL(1)要求生成的预测分析表的每一个项目至多只能有一个生成式,即对于读头下的每一个字符,都可以明确地选择哪个产生式来推导,LR文法要求每一步都有明确的动作,移进和归约都是可确定的,没有二义性。

    比较两大类型(自顶向下 vs 自底向上)的文法的特点:

    1.首先LL(1)分析法是自上而下的分析法。LR(0),LR(1),SLR(1),LALR(1)是自下而上的分析法。
       2.自上而下:从开始符号出发,根据产生式规则推导给定的句子。用的是推导
       3.自下而上:从给定的句子规约到文法的开始符号。用的是归约
       4.自上而下就是一种试探过程,怎么试探?需要你写出它的FIRST()集与FOLLOW()集。写出这两个集合后根据LL(1)分析表构造规则画出LL(1)分析表。现在基本完成了大半,当计算机输入句子时,分析程序便会根据输入去和分析表进行匹配,如果每步都能够匹配成功则说明符合该语法规则,分析成功。
       FIRST()集:其实是终结符的集合,看该非终结符A能不能产生以它里面的某个符号开头的句子。(这也是自上而下分析法的思想)
       5.自下而上就是把句子变成非终结符,在把非终结符变成非终结符,这样不断的进行如果能到根节点则成功。

     LL(1)就是向前只搜索1个符号,即与FIRST()匹配,如果FIRST为空则还要考虑Follow。
      LR需要构造一张LR分析表,此表用于当面临输入字符时,将它移进,规约(即自下而上分析思想),接受还是出错。
       LR(0)找出句柄前缀,构造分析表,然后根据输入符号进行规约。不考虑先行,只要出现终结符就移进,只要出现归约状态,就无条件归约,这样子可能出现归约-移进,归约-归约冲突。
       SLR(1)使用LR(0)时若有归约-归约冲突,归约-移进冲突,所以需要看先行,则只把有问题的地方向前搜索一次。

    SLR(1)定义:满足下面两个条件的文法是SLR(1)文法

    a.对于在s中的任何项目 A→α.Xβ,当X是一个终结符,且X在Follow(B)中时,s中没有完整的项目B→r.

    b.对于在s中的任何两个完整项目A→α.和 B→β.,Follow(A)Follow(B)为空。

    解释:a.当X是一个终结符且X出现在读头上,对于项目 A→α.Xβ应该采用移进,若有完整的项目B→r.Follow(B)中有X,当X出现在读头上时,此时应该归约,于是,就产生了移进和归约冲突

    b.假设Follow(A)∩Follow(B)为{ X },对于A→α.,若Follow(A)[A后面的元素]出现时,应该归约,同理B也一样,于是,会产生归约-归约冲突,SLR(1)是为了消除LR(0)的两个冲突。
       LR(1)1.在每个项目中增加搜索符。2.举个列子如有A->α.Bβ,则还需将B的规则也加入。
       LALR(1)就是假如两个产生式集相同则将它们合并为一个,几合并同心集

    总结:

    见到First集就移进,见到Follow集就归约。

    LR(0):见到First集就移进,见到终态就归约

    SLR(1)见到First集就移进,见到终态先看Follow集,与Follow集对应的项目归约,其它报错。

    SLR分析法包含的展望信息是体现在利用了Follow(A)信息,可以解决“归约-归约”冲突

    SLR分析法没有包含足够的展望信息,不能完成解决“移进-归约”冲突,需要改进。

    下面是LR(0),SLR(1),LALR(1),LR(1)文法处理能力的比较,圆圈越大说明能力越强。


    展开全文
  • 编译原理之LL(1) 、LR(0)、SLR、LR(1)、LALR文法的对比

    万次阅读 多人点赞 2019-08-31 19:45:23
    考完编译原理有一段时间了,记得当时都被以上这五种文法搞懵了,所以希望写篇文章帮助那些正在学习的人。以下内容是依据龙书中文版讲解的,由于...首先来看张图,上图是四种文法的包含关系,即 LR(1)文法范围最大...
  • 第四章 语法分析(下)——LR文法

    千次阅读 2018-11-13 14:53:41
    LR(k)文法中,L指对输入进行从左到右的扫描,R表示反向构造一个最右推导序列。k表示在做出语法分析决定时向前看k个输入符号。 常用的LR(k)文法包括: - SLR:简单LR - LR(1):规范LR - LALR:向前看LR(Look ...
  • 编译原理语法分析LR1

    千次阅读 2008-11-10 18:29:00
    // LR1.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include "CharStack.h"#include "IntStack.h"#include #include #include #include struct BNFNODE // 产生式节点{char ...
  • 一个能用的LR1文法: S' -> <程序> <程序> -> <声明列表>|<程序> <函数> <声明列表> -> <声明>|<声明列表> <声明> <声明> -> include...
  • c++实现lr1分析器

    2020-07-21 09:59:33
    c++实现的LR1文法分析,简洁的方式实现了编译原理中的LR1分析器。
  • 该程序能够根据给定的文法判断它是否为LR0,SLR1LR1,LALR1文法; 打印项目集,分析表,Go函数; 若文法属于LR1,将进行LALR1文法的判断,若属于LALR1文法,将继续打印LALR1文法的项目集,分析表和Go函数。
  • 编译原理与编译构造 LR文法

    千次阅读 2017-10-31 09:36:08
    LR文法——通用语法分析法,基于规约、FA对于文法B→αAβ,A→γB \to \alpha A \beta, A \to \gamma ,我们有自动机,确切地说,是分层的有限自动机(NFA),如下图。 对于每个状态(就是每个圈)的命名,我们不会...
  • SLR(1),LALR(1),LR(1)文法的区别

    千次阅读 2019-07-01 14:37:28
    三个文法的简单介绍SLR(1)SLR(1)的使用条件SLR(1)带来的问题LR(1)向前搜索符的构造LR(1)的问题LALR(1)LALR(1)的问题 SLR(1) SLR(1):简单的LR(1)文法。不带向前搜索符,为了解决LR(0)中移进-规约冲突和规约-规约...
  • LR(1)文法中向前搜索符的确定 生成搜索符的两种方式: 1.项目[S’-> . S,],自动生成搜索符],自动生成搜索符],自动生成搜索符 2.从项目[A->α.Bβ,?]生成项目[B->…,first(β)], 自动生成搜索符first(β...
  • LL(1)文法判断

    千次阅读 2014-12-01 20:23:41
    LL(1)文法判断 题型: 1.判断该文法是否是LL(1文法? 2.若是,给出它的LL(1)分析表,否则说明理由。 概念: 对于产生式 A -> α | β 1.如果α、β均不能推导出ε(空语句),则 FIRST(α) ∩ ...
  • 语法分析之LR0文法

    2019-12-17 16:28:03
    打造简单的编译器(二)——语法分析(LR0文法) #include<iostream> #include<vector> #include<map> using namespace std; typedef char grammarType; grammarType start, S; //开始符号,S用来...
  • LR0文法分析器

    2020-07-25 23:32:52
    LR(0)文法分析器(LR (0) grammar parser)对于实现整个编译器而言,语法分析器是整个过程的核心部分,同时对构造整个编译器起到了关键作用,对程序的进一步扩展,以后有机会涉及对编译器的编写而言,将会是很容易便...
  • 类型 流程 ...Created with Raphaël 2.1.2开始cluster中添加初始项目集{{{{0,0,{'#'}}}}}未遍历完cluster中的元素?展开当前项目集set按项目符号生成新项目集合生成移进表生成归约表(包括接受表)处理冲突...
  • 大三上学期的编译原理实验,自己用C#写的代码。有词法分析、LL1分析、LR1分析这三次实验。
  • 以这个文法为例: A → A + B A → a B → b 这个文法可以推导出 a,a + b,a + b + b 之类的字符串。不过,它也是左递归的(LL 分析中,A → A + B 会使得语法生成树向左下无限生长)。这使得这个语法不适用于 LL ...
  • 编译原理课程设计,实现lr(1)项目集、分析表以及对具体句子的语法分析 作者邮箱:wangrui_kd@hotmail.com
1 2 3 4 5 ... 20
收藏数 1,802
精华内容 720
关键字:

lr1文法