C类关系分析毕业论文.doc

目录C+类关系分析毕业论文目 录第1章引言11.1课题背景11.2课题的价值和意义11.3国内外的研究现状11.4难点、核心问题2第2章需求分析32.1主要任务32.2功能需求32.3性能需求42.4需要的技术4第3章相关知识53.1程序设计语言63.1.1 C、C+语言63.1.2 Lex & Yacc63.1.3Dot图形编程语言73.2C+的类之间关系9第4章系统设计94.1环境和工具114.1.1Flex114.1.2Bison114.1.3Graphviz & Dot124.1.4GNU套件134.2流程图144.3模块和设计144.3.1C+解析器模块154.3.2 图像生成模块16第5章C+的解析165.1C+语法的特点175.1.1命名(names)175.1.2声明符、声明、和类型185.2歧义文法的解析195.2.1逆歧义解析（parsing against an ambiguity）195.2.2无歧义解析（多遍遍历）205.3回溯搜索205.3.1 Yacc中的线性搜索215.3.2 Yacc中的二叉树搜索23第6章抽象语法树（AST）的生成276.1抽象语法树（AST）的结构276.2AST的生成算法描述28第7章AST转换成Dot337.1算法337.2实现的功能35第8章系统测试368.1测试工具378.2测试用例388.3功能性438.4可靠性43第9章结论449.1已经完成的工作449.2需要改进的工作44参考文献44致谢46附录47外文资料原文50外文资料译文60第1章 引言第1章 引言1.1 课题背景C+是一种在软件工业中广泛应用的支持面向对象的优秀程序设计语言。C+的成功和C的成功是分不开的。因为C+中支持C898的语法，所以在最早的时候，C+被人们看作是C的一种扩展。因为C的简单和高效，所以它非常适合于系统底层编程。但是随着近年来软件工程的规模不断扩大，许多新的编程思想和模型涌现了出来。C+结合这些新特性，在一直不断的发展之中。尤其是面向对象思想在C+的使用中深入人心，以面向对象的思想看待事物，他们有着共同的属性，但是却在不同程度上有所延伸，所以C+中支持了继承的类的用法。然而在大型的工程中，各种类的声明相当之多，导致他们之间的继承关系不容易分析出来，这时就需要一种工具来形象的现实这其中的关系。1.2 课题的价值和意义该课题的价值在于通过实现class2pic程序，为以C+解析器为基础的工具提供一个模式：解析器解析，生成AST，处理AST为工具所用。其中涉及到的C+解析过程中的问题，AST的生成和处理，并且生成其他语言过程给类似的工具制作提供一定的参考价值。1.3 研究现状C+在软件工业上的非常成功，但是C+语法的复杂使与之相关的解析工具研究工作进展比较缓慢，但是它在工业领域广泛的应用使很多公司花费很大财力去支持与之相关的工具的发展，但是他们的研究成果大多数是不公开的。下面介绍几个公开的项目：Elsa /smcpeak/elkhound/sources/elsa/ 是一个在elkhound基础上开发的C+解析器，它解析C和C+的输入，并把它们转换成抽象语法树。并且做一些类型检测，但是现在还不能拒绝所有不正确的语法。作者是Scott McPeak。GCC-xml /HTML/Index.html，是在GCC的C+ 前端的基础上开发的工具，它把C+源代码转换成GCC内部表示形式的XML语言，因为XML语言容易解析，所以再对XML进行解析就容易的多了，这样就实现了C+ 的解析并且容易构造更复杂的C+ 解析器。它是开源的，作者是Brad King。这两个工具在解析工具方面有相当的代表性，前者是直接用解析器生成器在解析阶段生成抽象语法树，而后者是用解析器生成器产生XML语言，然后再通过解析XML文件达到解析前面语言的目的。1.4 难点、核心问题 C+的ISO标准文法9并不是LALR(1)语法，对于如何用yacc之类的解析器生成器语言编写BNF表达式是一个挑战（也就是如何构造C+解析器）。 对于实际问题构建一个合适的抽象语法树节点结构。 如何从抽象语法树生成直观的图像文件。65第2章 需求分析第2章 需求分析2.1 主要任务该项目的主要任务是通过分析C+类声明文件，生成类的关系的图形。先要把C+声明文件转换成抽象语法树(AST)，然后通过一定的方法把AST转换成图像文件。2.2 功能需求图形中使用箭头表示出继承的方向，还有继承类型，以及虚继承。class a ;class b : public a int c;class c:private a ;class d: protected c;class e: public d,public b ;则通过分析得到图2-1，其中箭头指向基类。虚线表示继承是虚继承，箭头的颜色表示继承中的访问权限，绿色表示public,黄色表示protected，红色表示private继承。由于本项目中只是要显示出类之间的关系，所以经过考察决定使用专用的流程图生成软件来解决这个问题。图2-12.3 性能需求由于本项目的性质和C+解析器的制作难度以及工作量，所以在性能上省略了很多需求，在人感受能够允许的范围内即可。2.4 需要的技术结合以上需求分析和难点核心问题，这个课题的难点基本可以分为两个部分，C+的解析语法分析和图形的生成。程序语言的前端（文法解析）已经经历了很多年的发展，已经趋于成熟。在实践中，主要采用两种做法，手写语法分析和语法分析生成工具编写。两者都各有利弊，对于手写的语法分析工具，它的优点是方便调试，方便修改。但是缺点是工作量大，而且这些工作很多都是重复的。对于语法分析生成工具，它有书写修改方便，易懂的优点，但是也存在调试困难等缺点。在class2pic的项目中，因为必须对C+源文件进行完全的解析，这意味着要对17页之巨的C+文法编写规则，用语法生成工具来做的话，工作量相对较小，所以选择语法生成工具制作C+解析器。图像的生成方面，有两种方案：1. 对抽象语法树进行渲染，并对点阵图进行填充，然后再转换成其他类型。2. 把抽象语法树转换成图形生成语言，然后对该语言进行编译从而生成图像。对于这两种方案，class2pic中选择第二种方案，因为第一种方案存在扩展性差，并且相对比较繁琐的缺点。由于生成图像主要是要求表示出类(class)之间的继承关系的关系图，没有必要用像素来画图像以及使用openGL之类的3D图像库，那样做会增加不必要的复杂性，得不偿失。所以选择以一种图形语言作为中间代码，然后对它进行编译生成图像。这样做的好处是可以获得更好的通用性和兼容性，并且也可以生成许多格式的图像文件。经过考察Graphviz的工具包中的dot正是用来画流程图和关系图的。所以选择dot为图形生成语言，它的语法简单，很适合用AST来生成，一次遍历就可以生成对应的语言，而且可以编译成多种图形格式，有jpg, png, svg, fig, mif, hpgl, pcl, imap, cmap等9种图形格式，还可以生成PDF和PS文件。本项目也可以生成这些格式的图像。第3章 相关知识第3章 相关知识本章介绍了项目涉及到编程语言和C+中类之间关系的简单介绍，他们是本项目的基础。3.1 程序设计语言class2pic中混合了许多程序设计语言，下面将大概介绍这几种语言的特性和特点，尤其是yacc和dot图像编程语言的简单语法。3.1.1 C、C+语言class2pic混合使用了C和C+语言，C+中包含C89的语法，所以可以视为本程序是用C+编写。不过，确切的说是用C+编译器来编译这两种语言。3.1.2 Lex & YaccLex 和Yacc都是在70年代由贝尔实验室开发的。他们都是特意为编写编译程序和解释程序的人设计的工具，同时也对非编译程序编写人员所感兴趣的很多应用程序也非常有用。Lex和yacc程序由三部分组成：定义段、规则段、和用户程序段。定义段%规则段%用户程序段这些部分都是由两个百分号的行分开的。尽管一部分可以为空，但是前两个部分是必须的。第三部分和前面的%行可以忽略（这个结构和yacc使用的结构是相同的，其实它是从yacc的结构复制过来的。定义段包括文字块(literal block)、定义(definition)、内部表声明(internal table declaration)、起始条件(start condition)和转换(translation)。以空白开始的行被拷贝到C文件中。规则段包含模式行和C代码。以空白开始的行或包围在 ”%“ 和 ”%” 中的内容是C代码。C代码被拷贝到生成的C文件中。规则段开始的行靠近生成的yylex()函数的开头，并且应该是与模式相关的代码所使用的变量或声明或者扫描程序的初始化代码。当lex扫描程序运行时，它把输入与规则段的模式进行匹配，每次发现一个匹配的时候，就执行与之相关的C代码。如果模式后面跟着的是“|”而不是C代码，那些这个模式将使用下一个模式相同的C代码。用户程序段的内容被lex全部拷贝到C文件中。Yacc的定义段包括文字块、逐字拷贝到生成的C文件开头部分的C代码，通常包括声明和#include行。可能有%union、%start、%token、%type、%left、%right和%nonassoc声明。也可以包含C和C+风格的注释。所有这些都是可选的。Yacc的规则段有语法规则和包含C代码的动作组成。语法规则是下列的格式：Non-terminal: statement 1 可选的C代码 | statement 2 + statement3 $ = $1 + $3; | statement4|statement n;动作后面可以是空白的，或者包含一个C代码（被”“ “”包围着）。Yacc的用户程序段中的文本被逐字拷贝到C文件中。通常这部分包括从动作调用的程序。在动作中可以对规则中的状态进行引用，$1引用规则中的第一个状态，在上面就是引用statement2背后隐藏的数据结构。$2引用规则中的第二个状态。$这个非终结符被规约时的树的引用。3.1.3 Dot图形编程语言Dot Dot是Graphviz套件的一个分支。是一个用来画流程图的语言和工具，他通过读取那些有属性的节点和节点之间的关系来画出图形，它可以生成很多格式的图形，比如gif，png，svg或者是PostScript。一个简单的例子 这个例子是从Dot的教程中获得的。如下：1: digraph G 2: main - parse - execute; 3: main - init; 4: main - cleanup; 5: execute - make_string; 6: execute - printf 7: init - make_string; 8: main - printf; 9: execute - compare; 10: 图3-1上面的代码产生的图形如图3-1：当然还可以在节点或者关系后边增加属性，属性包含在 ”“和”内，本项目中用到的属性有：style=dotted；shape=box；color=red等。有关语言的详细细节请参考dot语言的手册。3.2 C+的类之间关系C+3的类之间可以继承，可以是public, private, protected 加上virtual属性的一个组合。是强有力的抽象表达工具。对于public继承，子类型可以访问父类型中属性为public和protected的成员，当然外界的函数 不包括被声明为友元的函数也可以通过child_class: father_class:member的形式访问父类型中的public成员。通过public继承的两个类之间描述了一种“接口关系”，这意味着积累的接口会与派生类的接口合并。当派生类和基类之间是“is-a”关系时，适合采用public继承。相比之下protected或private派生比较不常见，他们是一种实现关系，而不是“is-a”关系。基类的接口（共用部分）与派生类的实现（private或protected，取决于派生的类型）相结合。事实上，private派生类类似于给类添加一个而外的部分充当private数据成员。子类型和外界函数都不能访问任何成员，即使该成员被声明为public也不行。对于protected继承，子类型可以访问父类型中的public和protected权限的成员，但是外界的函数却不可以访问父类型的成员。protected派生像是给派生类添加了一个对象作为protected数据对象，只不过派生类可以访问该对象的this指针。虚继承，就是把基类声明为virtual，对于虚继承的最好的例子3莫过于iostream库的构造了，对用户可见的两个最主要的istream类和istream类（输入的流）和ostream类（输出的流）.这两个类有很多共同的属性：格式状态信息、条件状态信息、本地化信息、用来放置数据的实际缓冲区等。这些共用的属性被抽象成ios类，istream和ostream都从它派生。iostream它支持对文件的读和写的操作，从ostram和istream类派生。但是在缺省的情况下，它继承了ios基类的两份单独的实例。虚拟继承就是为了解决这类问题，它继承了多个基类的实例，但只共享一份单独的共享实例。所以ostream和istream都只共享一份ios类的实例，就不会产生冗余的问题。由一个“虚继承”而来的类的每一个实例都含有一个vptr指向它的虚基类子对象。这个指针在程序员的范围内是不可见的，是编译器在语义部分生成的，通常来说我们可以把它看成透明的。通过多重继承，每个虚基类指针（vptr）都指向同一个对象，这允许积累对象在所有派生类中被有效的共享。对于任何一个基类表中存在虚基类的类来说，其成员函数的初始化过程都要经历对其虚基类指针和虚表的初始化。确切的说，所有含有多态，也就是有虚函数或者虚基类的类都要对虚表(vtbl)和指向虚表的指针(vptr)进行初始化。第4章 系统设计第4章 系统设计在本章，介绍了class2pic的运行环境和其中涉及的工具，包括Flex、Bison、Dot和GNU工具链。在本章的第3节，介绍了本项目的主要模块构造和之间的API设计。4.1 环境和工具Class2pic的运行环境是在Linux/GNU操作系统下，同时安装了Graphviz套件的环境下。下面是构造过程中使用过的工具的介绍：4.1.1 FlexLex是LEXical compiler的缩写，是Unix环境下非常著名的工具,主要功能是生成一个词法分析器(scanner)的C源码,描述规则采用正则表达式 (regular expression)。描述词法分析器的文件 *.l ，经过lex编译后，生成一个lex.yy.c 的文件，然后由C编译器编译生成一个词法分析器。词法分析器，简单来说，其任务就是将输入的各种符号，转化成相应的标识符(token)，转化后的标识符 很容易被后续阶段处理。Flex是GNU版本的Lex，全称是FastLex，它的词法分析速度比其他的lex程序要快些。4.1.2 Bisonyacc(Yet Another Compiler Compiler)，是Unix/Linux上一个用来生成编译器的编译器（编译器代码生成器）。yacc生成的编译器主要是用C语言写成的语法解析器 （Parser），需要与词法解析器Lex一起使用，再把两部份产生出来的C程序一并编译。yacc本来只在Unix系统上才有，但现时已普遍移植往 Windows及其他平台。分析程序生成器(parser generator)是一个指定某个格式中的一种语言的语法作为它的输入，并为该种语言产生分析过程以作为它的输出的程序。在历史上，分析程序生成器被称 作编译-编译程序( compiler- compiler )，这是由于按照规律可将所有的编译步骤作为包含在分析程序中的动作来执行。现在的观点是将分析程序仅考虑为编译处理的一个部分，所以这个术语也就有些过 时了。合并 LALR(1) 分析算法是一种常用的分析生成器，它被称作 yacc( yet another compiler- compiler )。给出 yacc 的概貌来，将使用Yacc为 TINY 语言开发一个分析程序。yacc的输入是巴科斯范式（BNF）表达的语法规则以及语法规约的处理代码，yacc输出的是基于表驱动的编译器，包含输入的语法规约的处理代码部分。yacc是开发编译器的一个有用的工具,采用LALR(1)语法分析方法。yacc最初由AT&T的Steven C. Johnson为Unix操作系统开发，后来一些兼容的程序如Berkeley yacc，GNU bison，MKS yacc和Abraxas yacc陆续出现。它们都在原先基础上做了少许改进或者增加，但是基本概念是相同的。由于所产生的解析器需要词法分析器配合，因此Yacc经常和词法分析器的产生器，一般就是和lex联合使用。IEEE POSIX P1003.2 标准定义了Lex和Yacc的功能和需求。Bison是yacc的GNU实现。4.1.3 Graphviz & DotGraphviz是一个图形抽象化的软件，由AT&T所开发。您可以透过编辑dot 图形编程语言，表达节点的特性与节点之间的关系，就可以轻松的画出一张关系图出来，可以应用在网页设计（SiteMap）、软件工程、网络、数据库.等。它是个画程序流程图、ER 图、关系图不可多得的好帮手，在本项目中，用它来实现图像生成部分，通过编译dot语言来产生图像。现已支持中文UTF-8。它包括以下部分： Dot Graphviz中用来编写层次图形和流程图的工具，它的层次算法尽量使所有的边都同一个方向，并且避免箭头的重合和减少箭头的长度。它的简单语法参考3.1.3节。 neato和fdp 用来生成结构图，在graphviz中叫做“spring model layout”。neato使用Kamada-Kawai算法，它相当于一个静态的多维设计图。fdp实现Fruchterman-Reingold算法来解决大型的图形和没有箭头的设计图。 twopi 辐射图设计工具，节点被放在一个同心圆并且他们他们之间的距离取决于他们和根节点距离。 circo 圆形设计图生成工具，适合于生成多个图形结构的结构，比如通信网络图。4.1.4 GNU套件在编程过程中，使用了GCC作为编译器，GDB作为调试器，但是yacc编译的程序比较难于调试，调试主要依靠输出文字和断言。GCC是优秀的C/C+编译器，gcc（GNU C Compiler）是GNU推出的功能强大、性能优越的多平台编译器，是GNU的代表作品之一。gcc是可以在多种硬体平台上编译出可执行程序的超级编译器，其执行效率与一般的编译器相比平均效率要高20%30%。 gcc 编译器能将C、C+语言源程序、汇程式化序和目标程序编译、连接成可执行文件，如果没有给出可执行文件的名字，gcc将生成一个名为a.out的文件。 在Linux系统中，可执行文件没有统一的后缀，系统从文件的属性来区分可执行文件和不可执行文件。而gcc则通过后缀来区别输入文件的类别，下面我们来介绍gcc所遵循的部分约定规则。 .c为后缀的文件: C语言源代码文件； .a为后缀的文件: 是由目标文件构成的档案库文件； .C，.cc或.cxx 为后缀的文件: 是C+源代码文件； .h为后缀的文件: 是程序所包含的头文件； .i 为后缀的文件: 是已经预处理过的C源代码文件； .ii为后缀的文件: 是已经预处理过的C+源代码文件； .m为后缀的文件: 是Objective-C源代码文件； .o为后缀的文件: 是编译后的目标文件； .s为后缀的文件: 是汇编语言源代码文件； .S为后缀的文件: 是经过预编译的汇编语言源代码文件。gdb是GNU的调试程序。gdb是一个用来调试C和C+程序的强力调试器。它使你能在程序运行时观察程序的内部结构和内存的使用情况。以下是 gdb 所提供的一些功能： 它使你能监视你程序中变量的值。 它使你能设置断点以使程序在指定的代码行上停止执行。 它使你能一行行的执行你的代码。4.2 流程图Class2pic流程图如图4-1，上半部分一个用虚线包围的模块是解析器模块，它产生AST抽象语法树给后边的模块使用，相当于一个编译器的前端。C+语言解析器模块符号表抽象树（AST）dot语言Dot语言的编译歧义搜索Bison解析器得到ID返回类型或者是ID图形文件C+源文件图4-1 class2pic的流程图下面一个被虚线包围的模块是图像生成模块，它把AST转换成DOT文件然后再编译成图像。4.3 模块和设计本节主要介绍一下流程图中两个主要模块的设计。4.3.1 C+解析器模块C+解析器模块一共包含CxxLexing.cxx CxxLexing.hxx CxxToken.hxx CxxLexer.cxx CxxParser.hxx CxxParsing.cxx CxxParsing.hxx CxxParser.cxx CxxParser.hxx CxxLexer.l CxxParser.y 等11个文件。其中文件名中包含Lex的都是和词法分析器有关的文件。除CxxLexer.l是Lex文件外，其他的文件都是辅助性的。其中带有lexing的文件都是在词法解析过程中要用到辅助程序和宏定义。文件名中包含Parser的文件都是和语法分析器有关的文件。除CxxParser.y是bison文件外，其他的文件都是辅助解析器工作的文件。以Parsing结尾的文件都是有关在文法解析过程中用到的宏定义和程序。其中CxxParsing.hxx包含了几个重要的AST生成的宏，如TREE_INIT_A_CLASS_NODE，TREE_INIT_A_BASE_NODE，TREE_ADD_SIBLING等。其中TREE_INIT_A_CLASS_NODE是在抽象语法树中一个类的声明做初始化工作的宏。TREE_INIT_A_BASE_NODE是在抽象语法树中一个基类的声明做初始化工作的宏。TREE_ADD_SIBLING是在抽象语法树中增加一个兄弟的宏，其中用到了TREE_INIT_A_CLASS_NODE等宏。包含Token是Lex和Parser共用的文件。其中包含了符号（Token）的定义和一些宏定义。Token是Lex产生的Token的定义，在这里被实现为以struct CxxToken为基类的多层结构。这样做的原因是为了得到更好的可扩展性。关于AST的节点的信息存放在global.h中，是所有文件都包含的一个文件。其中有很多共用的信息如共用数据结构的定义等。该模块的接口为yyparse()。并且这个模块为下面的模块提供抽象语法树，并把这个树结构保存在total_tree里面。total_tree是一个全局变量，后面的图像生成模块就通过它来生成图像。4.3.2 图像生成模块该模块由dot.c dot.h tree.c tree.h四个C语言文件构成。dot.c提供一个API ：void tree2dot(dotattr *attr,char *title, tree t, FILE *out);它接受一个抽象语法树，然后把抽象语法树转换成对应的dot语言输出，通过AST转换成dot语言的算法介绍在第一章。在tree.h中提供了一个API：tree new_expr_node(expr_kind);这个API返回一个新的节点，参数是节点的类型。expr_kind是一个enum，声明在globals.h中，其实这个API的设计可以简单成一个new_class_declaration()的，但是出于扩展性的考虑使用了这样的形式，在以后的工作中如果要把类中声明的函数加在AST中的话，就只需要增加一个expr_kind的类型就可以了。为抽象语法树增加节点的宏都在解析器模块中，具体的算法将在下面的章节介绍。其中，增加节点的宏节点可见附录。第5章 解析C+第5章 解析C+C+是一种语法非常复杂的编程语言，C+解析器设计的复杂度相当高，在引言部分已经做了介绍。这一章主要介绍了C+语法一些特点和用yacc类工具构造解析器的一些困难，和解决方法。还有用回溯搜索来解决模板和符号产生的大量语法歧义的介绍。5.1 C+语法的特点这一节主要分析一下C+语法的命名和声明等的特点。5.1.1 命名(names)在我们实现新文法之前，我们首先来分析一下ISO的C+文法中名字的特点。当我们要声明一个变量的时候，都要规约到这条文法。decl-specifier-seq declarator = initializer ;decl-specifier-seq代表一个变量声明前的修饰符序列像staic或者extern之类的，它可以生成像static unsigned int这样的声明修饰符。Declarator从declarator-id得到一个声明ID，它包括了像指针，函数，数组后缀，和纯ID这样的形式。当一个变量出现在表达式中，它被规约成id-express表达式。id-express和declarator看似相同却有着重大的区别。一个类型的名字(type-name)出现在表达式中是合法的。函数调用被收纳在postfix-expression中，其中支持把type-name和function-name而且还包括了构造函数和类型转换文法。在id-expression中的（没有：的构析函数语法）unscoped destructor name带反操作（）的和一个与操作的表达式有歧义。比如，no_class_name & 7和classname()有歧义。id-expression中的全局构析函数(global destructor)看似正确，但却是语法上的冗余，只是增加了语法的复杂性。同样的问题出现在全局(global) template-name中，不过这更像一个错误。有以下声明：template void sort(T *arr , size_t arr_size);但是下面的的赋值却不能被接受。p = &:sort;（可能是C+编译器不想让用户知道泛型实例化过程中的函数放在什么地方而这样设置的。）5.1.2 声明符、声明、和类型C+语法定义：declarator:direct-declaratorptr-operator declaratordirect-declarator-iddeclarator-iddirect-declarator ( parameter-declaration-clause ) cv-qualifier-seqoptexception-sepcificationoptdirect-declarator constant-expressionopt ( declarator )因为有一个交互的递归，delcarator 和 direct-declarator使得这个文法很难理解。同时，也使上下文无关文法无法无歧义的解析同时具有前缀和后缀的表达式。考虑affixed-productionterminalprefix affixed-productionaffixed-production postfix当解析下面的这行的时候，无论先解析prefix还是postfix都无法清楚的解析。prefix terminal postfix5.2 歧义文法的解析5.2.1 逆歧义解析（parsing against an ambiguity）通过改写文法，或者在超前（lookahead）解析器中通过一个解决歧义的标记(token)在文法中解决歧义。这种超前解析器的方法很直接，但是绕开问题的方法可能带来其他的问题，更坏的是如果对程序作了不正确的假设，导致了另外的一种复杂的递归的歧义。ABAandBonlyBonlyAAandBonlyBonlyAAandBonlyBA图5-1 新文法生成图而且对文法的改写也非常复杂。假设我们有两个互相歧义的文法A和B，明显的，我们只要去在所有语句里寻找还有A和一部分和B的部分的文法AandB然后把它们都去除掉就可以去除歧义。这个文法可以替换原来的文法A，B为onlyA和onlyB，所以A和B的文法就可以变成由onlyA和onlyB加上AandB组成的新文法，如图5-1所示。但是，实际上，在实际应用中，这样的文法分析是非常复杂的，要得到一个正确的文法非常的困难。转换AandB到BNF文法相对容易些， 但是onlyA和onlyB会使文法变成一个非常复杂的表达式。进一步，在一个非递归环境来实现他们就更加的复杂了。比如，一个递归文法是“这个是一个声明而不是一个表达式”会增加很多工作量。在C+的声明/表达式的情况中，“这个是一个声明而不是一个表达式”可以不被识别，因为C+的除去歧义的规则可以把歧义文法规约成一个声明。所以文法可以保持A不动，然后把“这是一个表达式而不是声明”写成onlyB。一旦去除歧义的文法被识别，它必须在不超前看超过一个字符的情况下把文法转换成BNF表达式。但是不能让某个表达式单独的转换，必须把相关的表达式都转换成那样的形式，这样才可以避免规约/规约冲突和移进/规约冲突的发生。在一个正规的C+解析器中，他们的类型识别系统几乎可以解决大多数的歧义，对于这个问题都是有相似的方法。gcc，CPPP,和Roskind文法都提出了解决上述的问题主要是靠经验，因为这个问题已经复杂到非经验主义不能解决的地步。gcc和CPPP的文法都不能正确的识别过分复杂的声明/表达式歧义。最后，parsing agaist an ambiguity需要一个非常精确详细的文法实现。去除其中的递归歧义是非常困难的。Roskind的工作16详细说明了有什么样的工作量来实现这样的解析。而且gcc的文法实现也是经过很长时间才达到的。5.2.2 无歧义解析（多遍遍历）声明和表达式的歧义可以通过把表达式看成声明来去掉歧义。一个多遍解析可以首先解析声明，如果解析失败了再来解析表达式的方法来去除歧义。这样实现大大简化了文法的实现因为文法不需要因为歧义而重写了。我们只需要把注意放在实现一个多遍遍历上面就可以了。回溯就是在上下文的标记流(token stream)中查询现在的文法是否满足某个语法，如果不是就查看是否满足另外的语法（或者多个）。手写解析器通常这样实现，它们通常使用自顶向下和LL文法的解析方法。查看最左边的标记并且做出一个可以恢复的不成熟的判断。但是因为一个LR解析器可以避免不成熟的判断，所以回溯是不必要的步骤，并且回溯会使性能下降很多，一个正规的文法中一般都不支持回溯搜索。在class2pic中使用的解析器中，回溯使性能下降了20%左右，这对于一个产品级的编译器是绝对不可接受的。但是在一个以研究为主的工具中是可以接受的。5.3 回溯搜索在LALR文法中加入回溯是为了可以很容易的重新解析其他的可选的文法，因为像yacc这样广泛使用的工具给了编程人员一个可以想象的空间，可以很容易的增加自己想要的东西到其中。首先来解释一下yacc中的线性搜索技术，然后我们来看一下二叉搜索和解析器中文法使用了搜索的地方的总结。5.3.1 Yacc中的线性搜索在最初的class2pic C+解析器中，在statement中做标记，当发生声明/表达式歧义的时候会执行一个线性搜索来消除歧义。statement:mark declaration_stamement unmark|mark remark expression_statement unmark| mark remark error ; unmarkmark: /* empty */ push_input_context_marker();remark:error rewind_input_context_to_marker();unmark: /*empty*/ pop_input_context_marker();其中： /*empty*/ 是为了表示这是一个空规则，相当于终结符。 被被包围的内容会在动作规约的时候执行。 error是解析器遇到语法错误或者不能识别的符号时返回的符号mark是把一个标记符加入到符号序列中。remark是回溯并且尝试另外一种情况来解析同样的符号序列。在实践中，状态子句(statements)是嵌套的，所以用栈来实现mark和unmark是非常有必要的。在解析器中，所有的非终结符都是通过其他的规则移进而被解析的，mark的规约保证语句具有相同的前缀，而对应的栈会一直存在。首先，解析器会尝试declaration_stamement，如果成功解析就会执行unmark。如果解析过程中存在错误，解析器会返回error同时被规约到remark，所以就会执行mark remark expression_statement unmark如果成功解析了expression_statement，则会unmark，否则就会规约到最后的一个规则，即mark remark error ; unmark这时会报告一个错误，并且“吃掉”一个“；”，然后接着执行后面的解析。抽象语法树（AST）的节点会在这些规则的最后，也就是在这些规则完全被识别之后建立。这样的方法相对比较容易实现，但是它需要输入流支持“做标记”和回溯到某个特定的位置。在实践中，这样的文法会有一些潜在的错误。在解析很复杂的语句时， mark和unmark的匹配失败会导致栈溢出，同样会造成解析失败。当解析控制动作被转换成解析表的时候，会导致没有被成功匹配的mark规则被忽略。statement:selection_statement|mark declaration_stamement unmark|mark remark expression_statement unmark| mark remark error ; unmark selection_statement:if ( condition ) statementif ( condition ) statement else statementswitch ( condition ) statement一个以if开始的statement只能匹配selection_statement,因为if在文法中只在这里出现过。所以selection_statement就会在没有标记(marking)和回溯栈的情况下被解析。这是可能的，因为解析器会向前查看一个标记来决定动作。selection_statement前面没有mark可以减少回溯带来的额外代价，同样的副作用还有输入的标记序列(input token sequence)必须调整从而实现回溯。最重要的是，mark的省略上升为一个错误了。例如，解析器进入了selection_statement中，但却没有正确解析这个子句，但是解析器又没有为其他的规则做回溯标记，这样解析器就不能正确解析了，更麻烦的是：文法看起来是正确的。回溯的适合解决类型名(type-name)和标识符(identifier)的歧义。因为他们都有相同的特点，他们都是名字。 回溯在模板中的应用回溯不是很适合解决模板名字(template-name)引起的歧义，因为在一种情况下它可以是被剪括号（）括起来的模板名字。template_name - 5 /template_name - 5而在另