资源描述：
《编译原理中项目集规范族的分析与研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第28卷第6期佳木斯大学学报(自然科学版)Vo.l28No.62010年11月JournalofJiamusiUniversity(NaturalScienceEdition)Nov.2010文章编号:1008-1402(2010)06-0888-03编译原理中项目集规范族的分析与研究岳小婷(东北财经大学管理科学与工程学院,辽宁大连116025)摘要:LR分析法是一种应用较广泛的语法分析方法,项目集规范族是构造LR分析表的基础.本文将词法分析方法与语法分析方法联系起来,以有限自动机知识为基础,给出了一种基于自动机的构造项目集
2、规范族的方法,然后,给出了一种更简洁的方法,并比较了两种方法的异同.关键词:编译程序;LR分析法;项目集规范族中图分类号:TP314文献标识码:A0引言1.1构造一个识别文法所有活前缀的NFA编译程序包括词法分析、语法分析、语义分析、例如文法G:中间代码生成、代码优化、代码生成等阶段.其中,SaAcB词法分析阶段以高级语言编写的源程序作为输入,Ab利用确定有限自动机DFA识别单词,输出由记号AAb[1]名和属性值构成的二元式序列;语法分析以二Bd元式序列中的记号名序列作为输入,将其视为句识别活前缀的NFA的每个状态由项目构成,[2]子,判断
3、它是否能由源语言的文法产生.语法分析项目记录了产生式右部识别的中间步骤.例如,的方法有自上而下和自下而上两种方法,LR分析项目A.b识别出活前缀A,意味已经看到A且A法是一种自下而上方法,因此在每一步规约时都需位于分析栈的顶部,可能从下一个输入记号中得到要找到当前右句型的句柄.句柄是符号串,因而可b;项目A.Ab识别出活前缀,意味着将要选择以按照词法分析的方法,构造一个有限自动机产生式AAb来识别A;项目AAb.识别出活前DFA,将句柄的识别划分为若干状态,每个状态识缀Ab,意味着Ab位于分析栈的顶部,如果下一步别一个字符,经过若干状态就可以识别出右句型的利
4、用产生式AAb规约,则Ab是句柄.活前缀,同时也识别出句柄的左部的部分字符.因1.1.1文法G的项目(NFA的状态)如下:而,对句柄的识别就转变成对活前缀的识别.识别(1)S.aAcB(2)Sa.AcB(3)SaA.Cb活前缀的DFA中的所有状态的集合就是项目集规(4)SaAc.B(5)SaAcB.(6)A.b范族.(7)Ab.(8)A.Ab(9)AA.b(10)AAb.(11)B.d(12)Bd.1利用DFA构造项目集规范族其中,项目为NFA的初态,而其它项目均是NFA词法分析中,在构造识别单词的确定有限自动的终态,且每个终态都可以识别出一个活前缀.机
5、DFA时,一般是先构造一个非确定有限自动机1.1.2NFA的状态转换NFA,再利用确定化算法,将NFA确定化为DFA.利用项目确定了NFA的状态之后,需要确定在此,利用这种思想,将识别活前缀的确定有限自状态之间的转换.假设状态i和状态j是源自同一动机DFA的构造方法设定为两步,首先,构造一个个产生式,且两个状态中的圆点相差一个文法符识别文法所有活前缀的NFA;其次,将NFA确定化号,则状态之间的转换包括两种情况,状态i和状为DFA.态j间相差一个记号,或者,状态i和状态j间相差收稿日期:2010-09-15作者简介:岳小婷(1973-),女,山东乳山人,东
6、北财经大学管理科学与工程学院讲师,博士.第6期岳小婷:编译原理中项目集规范族的分析与研究889[3]一个非终结符.DFA,如图5所示.状态i和状态j间相差一个记号,意味着在分2利用GOTO函数构造项目集规范族析中此记号从输入移进到分析栈的顶部,例如,项目(1)到项目(2)的转换,如图1所示,在NFA中构造项目集规范族的另一种方法是利用GO表示如下:TO函数,此方法利用到项目集闭包的概念.IIaIbIcIdIAIB{1}{2,6,8}图1项目(1)到项目(2)的转换{2,6,8}{7}{3,9}{3,9}{10}{4,11}{4,11}{12}{5}图4
7、状态转换矩阵形式的DFA图2项目(1)到项目(3)的转换2.1项目集闭包定义状态i和状态j间相差一个非终结符,该转换设I是文法G的一个项目集,则项目集闭包比较复杂.以项目(2)Sa.AcB到项目(3)SaA.CLOUSURE(I)定义如下:cB的转换为例,首先,因为非终结符A不会作为输(1)I中的任一项目属于LOUSURE(I);(2)入符号出现,所以此转换只能与非终结符A压入如果项目A.B属于CLOUSURE(I),非终结分析栈对应,即利用产生式Ab将b规约到A或符B的产生式为B!,则项目B.!也属于者利用产生式AAb将Ab规约到A.既然要利用CLOU
8、SURE(I),重复此操作,直到没有新
