用于消除语法分析冲突的YACC文法变换模式.doc

用于消除语法分析冲突的YACC文法变换模式 摘要：YACC是Unix/Linux上一个用来生成编译器的编译器（编译器代码生成器）生成的编译器主要是用C语言写成的语法解析器（Parser），需要与词法解析器Lex一起使用，再把两部份产生出来的C程序一并编译。本来只在Unix系统上才有，但现时已普遍移植往Windows及其他平台(Yet Another Compiler Compiler)是美国贝尔实验室著名的编译程序生成系统，用于开发以字符流输入的，语法制导的软件，如计算机语言的编(翻)译程序、解释程序、程序理解和白盒测试工具、语法制导的编辑器等近年来许多利用YACC的开发工作均指出了消除语法分析冲突的困难性，如开发C／C++程序理解工具的前端_2 J、Fortran95至C++的翻译程序、测试及测试控制标记语言TTCN-3的语法分析程序L4 J、硬件描述语言VHDL的分析程序等．本文借鉴软件设计模式的研究方法，总结出7个用于消除语法分析冲突的文法变换模式．下面介绍文中用到的几个基本概念和有关约定． 一、概念和约定 在本文中，术语“YACC”代表采用u也R(1)分析方法的一大类语法分析程序生成系统，包括贝尔实验室的YACC[“、自由软件基金会(GNU)的BiSo一6 J及它们的所有变体，乙虬R(1)分析方法属于移进归约分析方法．所谓移进，是指分析栈中移人新的终结符号归约是指用一条产生式的左部符号替换若干个栈顶符号，出栈符号的数目取决于产生式右部的长度．文法的LALR(1)分析表记录了当分析器的状态为s，当前面临的输入符号为t时应该执行的分析动作如果分析表的一个人口中记录了两个不同的分析动作，则称该文法包含一个语法分析突．分析冲突有两种：移进一归约冲突和归约一归约冲突，一个文法是LALR(1)文法，当且仅当它的LAI R(1)分析表中不含语法分析冲突．“UR(1)文法属于无歧义的上下文无关文法子类．若一个文法是歧义的。那么它的LALR(1)分析表一定含有语法分析冲突．有关上下文无美文法、LR分析方法和YACC的知识，可参考《编译原理教材》，如[1]或[7]．在下文列举的文法范例中，约定首字母大写的英文字符串表示文法的非终结符号，全小写的英文字符串代表文法的终结符号． 二、 YACC的冲突消除规则 现今的程序设计语言的语法主要是采用上下文无关文法描述的，但是上下文无关文法并非能够描述计算机语言的全部语法结构，例如，C++、VHDL等语言的语法明显带有上下文相关性．用YACC开发这些语言的分析器不可避免地会存在语法分析冲突．另一方面，语言的设计者在设计一个语言的文法时一般不考虑它的分析程序如何构造，而是为了理解和维护语言的语义而设计．如此设计出的文法称为语义文法(semantic grammar)．“标准”语言的文法可以从该语言的语言参考手册中获得，这样得到的文法往往是歧义文法．带有歧义的语义文法需要被改写为无语法分析冲突的分析文法(parsing grammar)，才能用来开发语言的分析程序．对于开发者自定义的语言，特别是许多领域专用语言(domain—specificlanguage)，需要由开发者自行设计它们的文法，消除语法分析冲突．YAcc支持用户自定义上下文无关的消歧规则，用于消除语法分析冲突，所谓上下文无关的消歧规则，是指这种规则不依赖于被分析程序的上下文环境．果没有在YACC的输入文法规范中指定文法符号的优先级和结合性，YACC将采用默认规则消除所有的冲突…： (1)遇到移进一归约冲突对选择移进； (2)遇到归约一归约冲突时按照在文法规范中先声明的产生式归约． 上述默认规则认为移进动作的优先级总是高于归约动作，先声明的产生式的优先级总是高于后声明的产生式，优先级的高低与发生冲突时被分析程序的上下文无关所以默认规则也是上下文无关的消歧规则．理论上已经证明，能用上下文无关的消歧规则解决的语法分析冲突，利用文法的等价变换也能解决，例如，图1左侧所示的简单表达式文法是一个歧义文法．对输入句子identify+identify‘identify，该文法的I，AI．R(1)分析器读入串identify+identify后，有两种可能的分析动作：按产生式Expr—Expr+Expr归约，或移进一个新的符号“*”．如果在文法规范中指定“*”号的优先级高于“十”号，便可消除该文法的歧义．即使不规定优先级，这个文法也可以被等价变换为图1右侧所示的无歧义文法． 总而言之，使用YACC等常用的确定性分析程序生成系统，文法变换是主要的并且是最强的语法分析冲突消除手段． 三、文法变换模式 形式语言理论告诉我们，上下文无关文法的等价性、文法的歧义性都是不可判定问题．也就是说，任给一个文法G，不存在一个算法能够判断G是否为一个无歧