利用基本文法改写模式解决语法分析冲突

《利用基本文法改写模式解决语法分析冲突》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2006年6月北京邮电大学学报Jun.2006第29卷第3期JournaIofBeiingUniversityofPostsandTeIecommunicationsVoI.29No.3!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!文章编号：1007-5321（2006）03-0086-05利用基本文法改写模式解决语法分析冲突李虎，金茂忠，刘超，许福（北京航空航天大学软件工程研究所，北京100083）摘要：分析了LALR（1）分析器生成系统中语

2、法分析冲突问题的起因和解决冲突的时机及策略，提出改写文法应遵循的4条规则，将常用的文法改写技巧总结为7个基本的文法改写模式.应用案例表明，提出的文法改写规则和基本文法改写模式可有效解决语法分析冲突.关键词：LALR（1）；语法分析器生成器；YACC；语法分析；冲突；文法改写；消歧中图分类号：TP301.2文献标识码：AResolvingParsingConflictsbyBasicRulesandPatternsofGrammarRewritingLIHu，JINMao-zhong，LIUChao，XUFu（Instituteof

3、SoftwareEngineering，BeihangUniversity，Beiing100083，China）Abstract：TheoriginoftheparsingconfIictsofgrammarbyusingLALR（1）parsergeneratorsisana-Iyzed.ThemomentandmethodstoeIiminateconfIictsincompiIingphasesisstudied.FourbasicruIesofgrammarrewritingasweIIassevenbasicgramm

4、arrewritingpatternstoresoIveconfIictsarepro-posed.CasestudiesshowthattheproposedtechniguesarehighIyeffectiveindeveIopingconfIict-freeparsers.Keywords：LALR（1）；parsergenerator；yetanothercompiIer’scompiIer；parsingconfIict；grammarrewriting；disambiguation［1］Yetanothercompi

5、Ier’scompiIe（rYACC）是美考虑它的分析程序如何构造，而是为了理解和维护国贝尔实验室著名的编译程序生成系统.凡是以字语言的语义而设计.如此设计出的文法称为语义文符流为输入的语法制导的软件都可以利用YACC法.“标准”语言的文法可以从语言参考手册中获开发.正确消除语法分析冲突是利用YACC产生语得，但它一般是高度歧义的.此种文法需要被改写法分析程序时最难解决的一个问题.本文剖析语法为无语法分析冲突的分析文法，方可用于开发分析分析冲突的成因和可能的消除策略，从变换文法遵程序.循的规则出发提出消除语法分析冲突的基本文法变语

6、法分析冲突的消除可以在编译过程的几个阶换模式，并说明这些模式的应用.段进行.图1示意了消除冲突的典型时机和策略.第1个时机是文法描述阶段，它通过改写文法1消除语法分析冲突的时机和策略或指定上下文无关的消歧规则来消除冲突.优先级语言的设计者在设计一个语言的文法时一般不规则是常用的上下文无关消歧规则，结合性规则是收稿日期：2005-04-27基金项目：国家自然科学基金项目（60573084）作者简介：李虎（1974—），男，博士生，E-maiI：tiger.Ii@cse.buaa.edu.cn.第3期李虎等：利用基本文法改写模式解决语

7、法分析冲突87法分为词法和语法2个层次.必要时可以调整词法分析程序和语法分析程序的分工，重新定义词法和语法.例如，l个词法单位既可以定义为l个ASCII字符，也可以定义为具有特定含义的字符串，如标识符.规则#为保持文法的可读性和可维护性，应尽可能地利用上下文无关的消歧规则而少改写文法产生式.规则$一些情况下，可以将被分析语言L的文法改写为G，使得L!L（G）.有时文法的等价变换难以消除语法分析冲突，可以尝试扩充待分析的语言，在语义处理阶段进一步执行合法性检查，缩小分析程序接受的语言范围，图l消除语法分析冲突的时机和策略保持语言的原

8、始定义.如果分析程序的输入事先经优先级规则的特例.消歧规则的上下文无关性是指过错误处理，则分析程序接受的语言范围可以扩大.这种规则不依赖于发生冲突时被分析程序的上软件再（逆向）工程工具一般要求被分析的程序必须下文.事先正确通过编译，待分析程序的语法