《编译原理中项目集规范族的分析与研究.pdf》由会员分享，可在线阅读，更多相关《编译原理中项目集规范族的分析与研究.pdf（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、?第 28卷 第 6期?佳 木 斯 大 学 学 报(自 然 科 学 版)?Vo.l 28No.6?2010?年 11 月?Journal of JiamusiUniversity(Natural Science Edition)?Nov.?2010文章编号:1008-1402(2010)06-0888-03编译原理中项目集规范族的分析与研究?岳小婷(东北财经大学管理科学与工程学院,辽宁 大连 116025)摘?要:?LR分析法是一种应用较广泛的语法分析方法,项目集规范族是构造 LR分析表的基础.本文将词法分析方法与语法分析方法联系起来,以有限自动机知识为基础,给出了一种基于自动机的构造项目集规
2、范族的方法,然后,给出了一种更简洁的方法,并比较了两种方法的异同.关键词:?编译程序;LR分析法;项目集规范族中图分类号:?TP314?文献标识码:?A0?引?言编译程序包括词法分析、语法分析、语义分析、中间代码生成、代码优化、代码生成等阶段.其中,词法分析阶段以高级语言编写的源程序作为输入,利用确定有限自动机 DFA识别单词,输出由记号名和属性值构成的二元式序列 1;语法分析以二元式序列中的记号名序列作为输入,将其视为句子,判断它是否能由源语言的文法产生.语法分析的方法有自上而下和自下而上两种方法,LR分析法是一种自下而上方法,因此在每一步规约时都需要找到当前右句型的句柄.句柄是符号串,因而
3、可以按照词法分析的方法,构造一个有限自动机DFA,将句柄的识别划分为若干状态,每个状态识别一个字符,经过若干状态就可以识别出右句型的活前缀,同时也识别出句柄的左部的部分字符.因而,对句柄的识别就转变成对活前缀的识别.识别活前缀的 DFA中的所有状态的集合就是项目集规范族.1?利用 DFA构造项目集规范族词法分析中,在构造识别单词的确定有限自动机 DFA时,一般是先构造一个非确定有限自动机NFA,再利用确定化算法,将 NFA 确定化为 DFA.在此,利用这种思想,将识别活前缀的确定有限自动机 DFA的构造方法设定为两步,首先,构造一个识别文法所有活前缀的 NFA;其次,将 NFA确定化为 DFA
4、.1.1?构造一个识别文法所有活前缀的 NFA例如文法 G:S aAcBA bA AbB d识别活前缀的 NFA的每个状态由项目构成,项目记录了产生式右部识别的中间步骤 2.例如,项目 A.b识别出活前缀 A,意味已经看到 A且 A位于分析栈的顶部,可能从下一个输入记号中得到b;项目 A.Ab识别出活前缀?,意味着将要选择产生式 A Ab来识别 A;项目 A Ab.识别出活前缀 Ab,意味着 Ab位于分析栈的顶部,如果下一步利用产生式 A Ab规约,则 Ab是句柄.1.1.1?文法 G的项目(NFA的状态)如下:(1)S.aAcB(2)S a.AcB(3)S aA.Cb(4)S aAc.B(5
5、)S aAcB.(6)A.b(7)A b.(8)A.Ab(9)A A.b(10)A Ab.(11)B.d(12)B d.其中,项目?为 NFA的初态,而其它项目均是 NFA的终态,且每个终态都可以识别出一个活前缀.1.1.2?NFA的状态转换利用项目确定了 NFA的状态之后,需要确定状态之间的转换.假设状态 i和状态 j是源自同一个产生式,且两个状态中的圆点相差一个文法符号,则状态之间的转换包括两种情况,状态 i和状态 j间相差一个记号,或者,状态 i和状态 j间相差?收稿日期:2010-09-15作者简介:岳小婷(1973-),女,山东乳山人,东北财经大学管理科学与工程学院讲师,博士.第 6
6、期岳小婷:编译原理中项目集规范族的分析与研究一个非终结符 3.状态 i和状态 j间相差一个记号,意味着在分析中此记号从输入移进到分析栈的顶部,例如,项目(1)到项目(2)的转换,如图 1所示,在 NFA中表示如下:图 1?项目(1)到项目(2)的转换图 2?项目(1)到项目(3)的转换状态 i和状态 j间相差一个非终结符,该转换比较复杂.以项目(2)S a.AcB到项目(3)S aA.cB的转换为例,首先,因为非终结符 A不会作为输入符号出现,所以此转换只能与非终结符 A压入分析栈对应,即利用产生式 A b将 b规约到 A或者利用产生式 A Ab将 Ab规约到 A.既然要利用产生式规约,在规约
7、前必须先识别 b或 Ab,项目(6)A.b识别出活前缀?,意味着将要选择产生式 A b来识别 A,项目(8)A.Ab识别出活前缀?,意味着将要选择产生式 A Ab来识别 A,因此,需要给项目(2)S a.AcB添加两条?弧(表示识别出活前缀?),分别指向项目(6)A.b和项目(8)A.Ab,在识别 A的基础上,从项目(2)S a.AcB发出一条 A弧到项目(3)S aA.cB,表示将非终结符 A压入分析栈,如图 2所示.按照上述两种方法,逐步构造出一个识别文法G所有活前缀的 NFA,如图 3所示.图 3?识别文法 G所有活前缀的 NFA1.2?NFA确定化为 DFA对图 3所示的 NFA,采用
8、确定化算法,消除图中的?弧,得到的状态转换矩阵形式的 DFA如图 4所示,集合中的数字是项目的标号.对项目集重新编号,得到项目集规范族 c=I0,I1,I2,I3,I4,I5,I6,I7,以及状态转换图形式的DFA,如图 5所示.2?利用 GOTO函数构造项目集规范族构造项目集规范族的另一种方法是利用 GO?TO函数,此方法利用到项目集闭包的概念.IIaIbIcIdIAIB12,6,82,6,873,93,910 4,114,11 125图 4?状态转换矩阵形式的 DFA2.1?项目集闭包定义设 I是文法 G的一个项目集,则项目集闭包CLOUSURE(I)定义如下:(1)I中的任一项目属于 L
9、OUSURE(I);(2)如果项目 A?.B 属于 CLOUSURE(I),非终结符 B 的产生式为 B!,则项目 B .!也属于CLOUSURE(I),重复此操作,直到没有新项目加入CLOUSURE(I).2.2?GOTO函数定义及应用GOTO(I,X)函数是一个状态转换函数,其中 I是一个项目集,而 X是一个文法符号,GOTO(I,X)是 I中所有形如 A?.X 的项所对应的项 A?X.的集合的项目集闭包.如果记 Jx=A?X.|A?.X!I,则GOTO(I,X)=CLOUSURE(Jx)图 5?状态转换图形式的 DFA对应文法 G,相应的项目集如下:I0=CLOUSURE(S.aAcB)
10、=S.a AcBI1=GOTO(I0,a)=S a.AcB,A.b,A.AbI2=GOTO(I1,b)=A b.I3=GOTO(I1,A)=S aA.cB,A A.bI4=GOTO(I3,b)=A Ab.I5=GOTO(I3,c)=S a Ac.B,B.d889佳 木 斯 大 学 学 报(自 然 科 学 版)2010年I6=GOTO(I5,d)=B d.I7=GOTO(I5,B)=S aAcB.相应地,得到项目集规范族 C及状态转换图形式的 DFA如图 5所示.3?两种方法比较利用 DFA方法构造项目集规范族,需要根据文法构造 NFA,然后将 NFA 利用确定化算法转为DFA,虽然有助于原理的
11、理解,但步骤繁琐,而利用GOTO函数构造项目集规范族,更侧重于应用,运算步骤简单,简洁实用.两种方法虽然侧重点不同,但实际上在原理上是一致的,Jx相当于在做 NFA,而 GOTO(I,X),即 CLOUSURE(Jx)相当于在做NFA的确定化运算.选择 DFA方法,有助于原理的理解,并且将词法分析和语法分析联系起来,巩固了 NFA和 DFA 以及确定化算法等知识点,选择GOTO函数方法,有助于在应用上快速有效地得到项目集规范族.参考文献:1?陈意云,张昱.编译原理 M.北京:高等教育出版社,2008:14-15.2?赵建华,郑滔.编译原理 M.北京:机械工业出版社,2009:142-143.3
12、?冯博琴,冯岚.编译原理与实践 M.北京:机械工业出版社,2000:150-15.The Analysis of Collection in Compiler PrinciplesYUE X iao-T ing(School ofM anagem ent Science,DongbeiUniversity of Finance and Econom ics,Dalian 116025,China)Abstract:?LR analysis is an i mportant syntax analysisw ith broader application,while the collection
13、 is thebase of constructing LR analysis table.Based on Finite automata,this article made a relation between lexical a?nalysis and syntax analysis,gave twom ethods in constructing collection,and then compared their si m ilarities anddifferences.Key words:?compiler;LR analysis;collection(上接 875页)A M e
14、thod of on Speaker Recognition BasedonW avelet PacketAnalysis and SVMWANG Zhi-lan(Beijing Eart h Station ofABRS,Beijing 102206,China)Abstract:In the speaker recognition system,the key proble m is giving the personality feature of the speak?er.Thispaper studiedwavelet packet transform and analyzed th
15、e extraction ofMFCC parameters.A new parame?terwas extracted using wavelet packet transfor m in place of Fourier transform.The Fisher criterion was used tomeasure the recognition of various parameters.A new hybrid parameterwas constructed through a combination ofthe F isher criterion.Finally,a support vectormachine(SVM)wasused to achieve the classification of SpeakerRecognition.Experi m ental data show that the m ethod is effective in raising the recognition rate of the speakerrecognition system.Key words:speaker recognition;MFCC;wavelet packet analysis;F isher criterion;SVM890