ATLASC语法分析器中冲突消解问题的研究

《ATLASC语法分析器中冲突消解问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据ATLAS—C语法分析器中冲突消解问题的研究梁红玉李爱萍王家礼(西安电子科技大学机电工程学院，西安710071)E-mail：lruby_74@163．con摘要论文对在设计ATIAS—C语法分析器～中YACC工具所无法解决的冲突进行了具体的讨论与研究，并且对出现的冲突提出了相应的解决方案。实验结果证明论文提出的消解冲突的方法在设计语法分析器时具有可行性。关键词YACCLALR(1)文法移进／归约冲突归约／归约冲突文章编号1002—8331一(2005)23—0102—03文献标识码A中图分类号TP311AStudyontheMethodofDeletingConf

2、lictforATLAS—CSyntaxAnalyzerLiangHongyuLiAipingWangJiaU(SchoolofElectromechanicalEngineering，XidianUniversity，Xi"an710071)Abstract：ItisdifficulttogivethenoconflictssyntaxrulesforcomplexgrammarinYACC．Inthispaper，thecategoryofconflictsispresentedandthemethodofdeletingcorrespondingconflictsis

3、putforwardforATIAS—Csyntaxanalyzer．Intheend，thecorrectATLAS—Cparsingtreeissuccessfullyconstructedwiththeabovediscussedmethod．Keywords：YACC，LALR(1)grammar，shift／reduceconflict，reduce／reduceconflictATLAS(AbbreviatedTestLanguageforA11Systems)语言是一种军用和民航使用较早的测试语言，现已成为军用ATE(AutomateTestEquipment

4、)广泛使用的一种标准测试语言[11。构造A711LAS—C语法分析器是设计ATLAS—C翻译器整个过程的重要阶段。ATIAS是一种较为复杂的测试规范语言，其关键字数量之多。其语言结构之庞大，足以让其它语言相形见绌圜。运用基于LALR(1)算法的语法分析自动生成工具YACC来产生像AⅡAS这样的大型语法树是较为复杂的工程，因为按照ATLAS语言的语法规则所写的规则，会产生大量的冲突，使得YACC工具不能正确生成语法分析程序。而解决YACC报告的冲突问题是很具有挑战性的一项工程[31。本文利用YACC构造ATLAS语言到C语言语法树的实现过程，讨论了出现的各种具体冲突，并给出了

5、相应的消解方法。1L～LRfl)文法与YACC中的冲突本文利用基于Windows系统下的YACC工具来构建从ATLAS语言到C语言的语法分析树。YACC又称LALR(1)分析生成器(AnLALR(1)ParserGenerator)，是利用LAI瓜(1)文法构建的自动语法分析器生成工具，因此要很好地利用YACC．对LALR(1)文法的理解是完全必要的。1．1LALR(1)文法在编译原理中，语法分析方法可分为自底向上和自顶向下两大类，LALR(1)(kokAheadLeftRecursive)方法，又称向前查看一步左递归法．是LR方法的子类，而LR分析属于自底向上分析类。由于

6、LALR(1)在构建语法树的过程与其它几种(LR(0)、LR(1)、SLR(1))相比，具有SLR(1)状态少的优点和LR(1)的适用范围广的优点。因此很多YACC都是基于该文法的具体运用【4】。LALR(1)分析的方法是：从左至右和自底向上的分析，且在分析的每一步，只需根据分析栈当前已经移进和归约出的全部文法符号，并且再向前看1个符号，来确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前应采取的分析动作(是移进还是按某一产生式进行归约等)。1．2YACC中的冲突【3】由于YACC基于LALR(1)文法，故其创建语法分析程序时可能出现两类冲突：

7、“移进／归约”和“归约，归约”。1．2．1移进，归约冲突例如有下列文法规则：exp：Xlexp’+’exp：该文法又称二义性文法，容易产生移进，归约冲突。当输入字符串为“X+x+X”，YACC有两种可能的分析：(1)采用归约项，使得语法分析程序使用“(X+x)+x”；(2)采用移进项，使得语法分析程序使用“x+(X+x)”；此时出现的冲突为移进，归约冲突。1．2．2归约，归约冲突例如有下列文法规则：prog：pmalpmb；pma：X；pmb：XIY：该文法中，一个‘x’可能是proga，也可能是progb，这是造