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

1、用于消除语法分析冲突的YACC文法变换模式摘要：YACC是Unix/Linux上一个用来生成编译器的编译器（编译器代码生成器）。YACC生成的编译器主要是用C语言写成的语法解析器（Parser），需要与词法解析器Lex一起使用，再把两部份产生出来的C程序一并编译。YACC本来只在Unix系统上才有，但现时已普遍移植往Windows及其他平台。 本文分析了使用LAI R(1)分析程序生成系统YACC时经常遇到的语法分析冲突问题及消除语法。分析冲突的策略，总结了一组文法变换模式，利用这些模式可以有效地解决语法分析冲突阉题。关键词： YACC 语法分析 冲突文法变换 模式引言YACC(Yet Ano

2、ther Compiler Compiler)是美国贝尔实验室著名的编译程序生成系统，用于开发以字符流输入的，语法制导的软件，如计算机语言的编(翻)译程序、解释程序、程序理解和白盒测试工具、语法制导的编辑器等近年来许多利用YACC的开发工作均指出了消除语法分析冲突的困难性，如开发CC+程序理解工具的前端_2 J、Fortran95至C+的翻译程序、测试及测试控制标记语言TTCN-3的语法分析程序L4 J、硬件描述语言VHDL的分析程序等本文借鉴软件设计模式的研究方法，总结出7个用于消除语法分析冲突的文法变换模式下面介绍文中用到的几个基本概念和有关约定一、概念和约定在本文中，术语“YACC”代表

3、采用u也R(1)分析方法的一大类语法分析程序生成系统，包括贝尔实验室的YACC“、自由软件基金会(GNU)的BiSo一6 J及它们的所有变体，乙虬R(1)分析方法属于移进归约分析方法所谓移进，是指分析栈中移人新的终结符号归约是指用一条产生式的左部符号替换若干个栈顶符号，出栈符号的数目取决于产生式右部的长度文法的LALR(1)分析表记录了当分析器的状态为s，当前面临的输入符号为t时应该执行的分析动作如果分析表的一个人口中记录了两个不同的分析动作，则称该文法包含一个语法分析突分析冲突有两种：移进一归约冲突和归约一归约冲突，一个文法是LALR(1)文法，当且仅当它的LAI R(1)分析表中不含语法分

4、析冲突“UR(1)文法属于无歧义的上下文无关文法子类若一个文法是歧义的。那么它的LALR(1)分析表一定含有语法分析冲突有关上下文无美文法、LR分析方法和YACC的知识，可参考编译原理教材，如1或7在下文列举的文法范例中，约定首字母大写的英文字符串表示文法的非终结符号，全小写的英文字符串代表文法的终结符号二、 YACC的冲突消除规则现今的程序设计语言的语法主要是采用上下文无关文法描述的，但是上下文无关文法并非能够描述计算机语言的全部语法结构，例如，C+、VHDL等语言的语法明显带有上下文相关性用YACC开发这些语言的分析器不可避免地会存在语法分析冲突另一方面，语言的设计者在设计一个语言的文法时

5、一般不考虑它的分析程序如何构造，而是为了理解和维护语言的语义而设计如此设计出的文法称为语义文法(semantic grammar)“标准”语言的文法可以从该语言的语言参考手册中获得，这样得到的文法往往是歧义文法带有歧义的语义文法需要被改写为无语法分析冲突的分析文法(parsing grammar)，才能用来开发语言的分析程序对于开发者自定义的语言，特别是许多领域专用语言(domainspecificlanguage)，需要由开发者自行设计它们的文法，消除语法分析冲突YAcc支持用户自定义上下文无关的消歧规则，用于消除语法分析冲突，所谓上下文无关的消歧规则，是指这种规则不依赖于被分析程序的上下文

6、环境果没有在YACC的输入文法规范中指定文法符号的优先级和结合性，YACC将采用默认规则消除所有的冲突：(1)遇到移进一归约冲突对选择移进；(2)遇到归约一归约冲突时按照在文法规范中先声明的产生式归约上述默认规则认为移进动作的优先级总是高于归约动作，先声明的产生式的优先级总是高于后声明的产生式，优先级的高低与发生冲突时被分析程序的上下文无关所以默认规则也是上下文无关的消歧规则理论上已经证明，能用上下文无关的消歧规则解决的语法分析冲突，利用文法的等价变换也能解决，例如，图1左侧所示的简单表达式文法是一个歧义文法对输入句子identify+identifyidentify，该文法的I，AIR(1)

7、分析器读入串identify+identify后，有两种可能的分析动作：按产生式ExprExpr+Expr归约，或移进一个新的符号“*”如果在文法规范中指定“*”号的优先级高于“十”号，便可消除该文法的歧义即使不规定优先级，这个文法也可以被等价变换为图1右侧所示的无歧义文法总而言之，使用YACC等常用的确定性分析程序生成系统，文法变换是主要的并且是最强的语法分析冲突消除手段三、文法变换模式形式语言理论告诉我们，上下文无关文法的等价性、文法的歧义性都是不可判定问题也就是说，任给一个文法G，不存在一个算法能够判断G是否为一个无歧义的上下文无关文法，也不存在这样的算法：该算法能够将G自动变换为G，使

8、得G为一个无歧义的文法且L(G)=L(G)实践中，人们只能运用那些经过验证的文法变换经验和技巧消除语法分析冲突设计模式是软件工程领域的研究热点，它记录、提炼存在于软件开发人员头脑中反复出现的特定上下文中的共性问题及其经过多次验证的成功解将3个文法变换技巧命名为3个I AIR(1)等价变换模式，但是没有给出进一步的定义和说明结合长期以来的实践经验，我们将常用语法冲突消除技巧进一步总结为7个文法变换模式模式的描述问题一直是模式研究的重点使用形式化的记号表示模式的名称和解决方案，以便能够被计算机自动识别和抽取；用面向人的自然语言描述模式要解决的问题、问题出现的上下文和应用实铡，以便于交流和理解首先来

9、看最常用的关键字模式关键字(keyword)模式消除语法分析冲突的通用方法是在语言中增加终结符作为保留的关键字记为：introduce(keyword，X)，其含义是为文法符号x定义的语言增加一个保留的关键字keyword作为文法的终结符号，语法分析程序生成系统的一个重要应用是支持软件项目和组织中的普通开发人员设计和实现领域专用语言。也称小语言(microlanguage或little language)关键字模式改变了语言的定义。用于在语言设计中避免语法分析冲突，图2中的条件语句文法是歧义的，该文法关于句子ii exprl then if expr2 then stintl else stm

10、t2有两棵不同的分析树增加一个保留的关键宇endit"，不仅可以消除文法的歧义，还可以使文法变得清晰直观加宽(widen)模式用语言范围更“宽”的文法符号替换语言范围较“窄”的文法符号，常常可以消除语法分析冲突widen模式记为：widen(r，X。珥玎"，Xb。叫)该式的含义是产生式r右部 被另一个符号Xb，“替换，L(xb)兰L(Xnarrow)图3给出了用widen模式消除Java文法的一个归约一归约冲突的实例widen模式扩充了文法定义的语言有时文法的等价变换难以消除语法分析冲突。可以尝试扩充待分析的语言，在语义处理阶段进一步执行合法性检查，缩小分析程序接受的语言范

11、围，保持语言的原始定义如果分析程序的输人事先经过错误处理，则分析程序接受的语言范围可以扩大软件再(逆向)工程工具一般要求被分析的程序必须事先正确通过编译，待分析程序的语法错误已经在编译阶段被发现和纠正因此，即使工具前端接受的语言范围被适当扩大，一般也不会对后端应用造成显著影响。优先级(precedence)模式为产生式和文法符号设置优先级和结合性，消除文法歧义优先级和结合性是语言的设计者给出的，通常只在语言参考手册或语言设计者规定了符号优先级时才能应用优先级模式记为：precedence(z(a_e-SOC。)>y(asso)其含义是规定文法符号(产生式)的相对优先级和符号的结合性词法反

12、馈(1exical feedback)模式让词法分析程序区分歧义的语法成分，将消除语法分析冲突的任务从语法分析阶段前移至词法分析阶段词法反馈模式记为：lexicalfeedbaek(X，。1，5C2，zH)上式的含义是将一个引起歧义的终结符号或非终结符号x区分为n种可能的终结符号z1，5c2，z。，由词法分析程序决定X的词法解释，词法反馈模式的应用范围很广举一个例子，一些早期的计算机语言中关键字不是保留字，标识符可以与关键字取相同的名字例如在PL1语言中，下列语旬是合法的条件语句s】：ifif=thenthenthen=if如果不区分if的词法解释，将会产生语法分析冲突可将if和then区分为

13、“关键字(keyword)”和“标识符(identify)”；每遇到个if或then，让词法分析程序根据上下文返给语法分析程序关键字或标识符内嵌(inline)模式。inline模式用于减少分析方法展望的符号个数，使LALR(m)文法(m>1)等价变换为LALR(n)文法(n<m)，记为：inline(r，x，l，72，rn)上式中，非终结符号x出现在产生式r的右部，r1'r2，靠是定义x的其它产生式。用rl，r2，h右部的非终结符号替换r右部的X，往往可以消除语法分析冲突inline模式不应改变语言的定义，图4给出用inline模式消除移迸一归约冲突的例子消除产生式是in

14、line模式的一个重要应用e产生式的存在经常引起移进一归约冲突利用inline模式可以消除由e产生式引起的语法分析冲突，图5给出一个例子提因子(factor)模式factor模式将多条产生式的相同右部或右部相同的部分作为公因子提取出来，用另一个文法符号表示，并用这个符号替换上层产生式的右部符号，记为：factor(rl，72，R)其中，rl和r2是左部符号不同的两条产生式，且它们的右部完全相同或部分相同R是被替换了右部符号的某一上层产生式归约一归约冲突在大多数情况下预示着文法的设计存在严重缺陷【1“factor模式用于消除归约一归约冲突，并且常与inline模式结合使用Factor模式不应改变

15、文法定义的语言，图6给出了factor模式的应用实例：消除了由Boyschris和Girlschris引超的归约一归约冲突在文法被重构之前，ch“s即可以是男孩，也可以是女孩文法的设计显然存在缺陷，默认(default)模式不改变文法，让分析程序生成系统根据默认的消歧规则解决冲突在某些情形下默认规则恰好符合语言规约例如，ISOIEC C+标准规定：“else总是与它前面最近的if匹配成一个条件语句”这相当于规定遇到“悬挂else7，'冲突时一律选择移进动作开发者应将有关的消歧规则注释在文法规范中，否则文法规范将难以理解和维护Default模式可记为：default(r，s，ref)或default(r1，2，ref)该式的含义是：由产生式r和符号s(或由产生式r1和72)引起的移进一归约(或归约一归约)冲突由语法分析程序生成系统默认的消歧规则解决，ref指出消歧规则的依据，如语言参考手册中有关的消歧规则所在的章节号四、结束语YACC,Bison的应用非常广泛，是语法分析程序生成系统事实上的工业标准，被绝大多数编译原理教材列为必修内容在长期使用娶渡m开发程序分析、理解、度量和泌