基于语法分析的数学公式分析器的设计

基于语法分析的数学公式分析器的设计摘要本论文研究编译原理，使用LEX&YACC工具，编写数学公式分析器。编译原理是计算机专业的一门重要专业课，通过编写数学公式分析器，加深对专业知识的理解。本论文编写的数学公式分析器，可以进行算数运算分析，变量运算，变量名可以是字母，也可以是单词。关键词： 词法分析； 语法分析； 产生式； AbstractabstractThis paper studies the compiler principle, using LEX&YACC tools to write mathematical formula analyzer.The compiler principle is an important professional course for computer majors. It helps to deepen the understanding of professional knowledge by writing mathematical formulas and analyzers.The mathematical formula analyzer written in this paper can do arithmetic analysis, variable operations, variable names can be letters, or they can be words.Key words: LEXical analysis; grammatical analysis; production type;II摘要IAbstractI第1章 研究背景与国内外现状1第2章 设计思路12.1 设计依据12.1.1 编译过程12.1.2 词法分析12.1.3 语法分析22.1.4 语义分析22.1.5 代码优化32.1.6 项目设计方案3第3章 LEX&YACC简介与其语法结构43.1 LEX简介43.2 LEX格式43.3 LEX识别规则53.3.1 LEX用的正规式53.4 YACC简介63.5 YACC源程序说明部分的写法73.4 实现词法分析的思路分析93.4.1 无意义字符的识别93.4.2 标识符、数字、字符和字符串的识别9第4章 语法分析中的产生式114.1 产生式简介114.2 左递归的消除114.3 算数运算产生式1114第5章 基于语法分析的数学公式分析器的设计155.1 实现简单算数运算155.2 保存运算符与变量155.3 支持多字符变量155.4 编译运行程序：155.5 总结16参考文献18第1章 研究背景与国内外现状LEX&YACC是20世纪70年代由贝尔实验室开发，已经成为标准的UNIX实用程序。LEX&YACC既适合编译程序，解释程序的专业编译程序编写用户。也适合非编译程序编写许多应用程序。LEX&YACC使用范围包括，应用在输入中茶盅模式的应用程序，也可以应用在输入或命令语言的应用程序LEX&YACC的源程序经过LEX处理后生成的词法分析程序与YACC处理后生成的语法分析程序，可以用C语言描述，可以使用C编译器编译，与其他目标文件或命令文件连接。目前国内外应用LEX&YACC最多的方向是编写软PLC的编译器。使用LEX&YACC编写的程序与用户的手动编写的词法分析语法分析程序相比较，可以大大的降低编码量提升速度和提高质量。第2章 设计思路2.1 设计依据2.1.1 编译过程编译实现的是由源程序到可执行程序之间的转换。首先源程序经编译后以机器码的形式存储在代码区中，随着程序的逐条执行，不断进行着执行指令、压栈、出栈、清栈（管理栈空间）的操作，不断在代码区、静态数据区和动态数据区跳转，完成程序的执行。2.1.2 词法分析计算机存储的源代码，与我们直接写出的程序是不相同的。计算机中所有的数据均已0和1的形式存储在存储单元中，源代码也一样。我们输入源程序，对构成源程序的字符串从左到右一个字符一个字符地进行扫描和分解，依据词法规则(或构词规则)识别出一个个的单词(单词符号或符号)，转换成机器容易识别的内码形式。内码用二元式(种别码，属性值)表示。我们的输入是字符串。我们的输出序对是(种别码，属性值)。属性值是单词的机内表示是最初级的语法分析 单词种类我们可以分为两类。一类是特殊的单词，如保留字、运算符、分界符等，这些都是源语言所提供的；另一类是普通单词，如用户在源程序中定义的标识符、常数等。 图2-1：计算机中某段程序的16进制表示例如：程序段int x,a,b;x=a+b*50;词法分析后的结果为保留字 “int”、标识符 “x”、界限符“,”、标识符 “a”、界限符 “,”、标识符 “b”、界限符“；” 、标识符 “x”、运算符 “=”、标识符 “a”、运算符 “+”、标识符“b” 、运算符“*”、整常数 “50” 、界限符“；”。 通过编写的词法程序，历遍存储在内存中的十六进制源代码，将十六进制源代码全部转换为关键字、数字、字符串、分隔符等。不难发现词法分析只能够识别出一些可直接确定含义的字符。识别关键字后，并不能确定关键字的具体含义。例如分析结果中，“int”、“（”和“=”可以确定其分别表示整形、括号和相等或赋值。但是对于“m”，在目前词法分析的阶段，只能确定“m”是一个标识符，无法确定“m”是函数还是变量，要确定“m”的具体表示，只能将“m”放在其所在句型做分析，这就需要进行编译的第二步 语法分析。2.1.3 语法分析词法分析的作用是从连续的字符中扫描出标识符、关键字、数字运算符并存储为符号流。语法分析就是从符号流中识别出符合语法规定的语句。计算机不具有向人一样直接识别一条语句的功能。所以他只有逐个识别所有符号，识别出符合语言语法的语句。语法的概念是语句中的规则，在计算机中这一规则表示为产生式。通过产生式产生的语法被语法分析器编写入其中输出为模板。语法分析器的作用是将词法分析器识别出的符号与模板匹配，匹配出语法后按语法识别整句，明确语句语法。2.1.4 语义分析语义就是程序的“意思”，语义分析要分析语法成分的含义和用途，根据语义规则进行的运算和操作，同时进行相应的语义检查。根据语义规则产生一种介于源语言与目标代码之间的一种中间代码。中间代码是不依赖于机器但是又便于生成依赖于机器的目标代码的一种结构简单、含义明确的记号系统。中间代码常用四元式来表示（算符，左操作数，右操作数，结果），中间代码简单规范、机器无关、易于优化与转换 。2.1.5 代码优化对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生更为高效(省时间和空间)的目标代码。主要依据是等价变换规则，优化主要包括：删除公共子表达式、合并已知量、删除无用赋值、循环优化、算符规约等等。2.1.6 项目设计方案要实现数学公式分析器，需要完成两部分程序设计。首先是词法分析器程序设计，根据词法分析原理，需要从输入符号流中提取标识符号、10进制数、“+”“-”“*”“/”“(”“)”“，”“；”“n”“=”。然后使用语法分析识别出算数运算，数学函数，变量运算，用户自定义公式。最终输出正确结果。 第3章 LEX&YACC简介与其语法结构3.1 LEX简介LEX本质是词法分析器，我们编写的.l文件经过配置后，按照正则表达式逐个字符历遍文件解析文件。解析过程中不断更新内存数据解析状态。但是因LEX没有堆栈故而LEX绝不可以用于剖析外壳结构。但是YACC增加了一个堆栈，并且能够轻易处理像括号这样的结构。LEX适用于模式匹配，如果对算数运算有更多要求，我们就需要使用YACC了。LEX是LEXical compiler的缩写，是Unix环境下非常著名的工具,主要功能是生成一个词法分析器(scanner)的C源码,描述规则采用正则表达式(regular expression)。描述词法分析器的文件*.l，经过LEX编译后，生成一个LEX.yy.c 的文件，然后由C编译器编译生成一个词法分析器。词法分析器，简单来说，其任务就是将输入的各种符号，转化成相应的标识符(token)，转化后的标识符 很容易被后续阶段处理。它被设计用来对输入字符流进行词法处理。它接受一种高级的、面向问题的说明书，并用它匹配字符串中的字符、生成能够识别正则表达式的程序。正则表达式通过用户输入的代码说明书给入。LEX识别这些表达式，并且将输入流分成一些匹配这些表达式的字符串。在这些字符串的分界处，用户提供的程序片段被执行。LEX代码文件将正则表达式和程序片断关联。对每一条输入到由LEX生成程序的表达式，相应的代码片段被执行。为了完成任务，除了需要提供匹配的表达式以外，用户还需要提供其它代码，甚至是由其他生成器产生的代码。用户提供一般程序设计语言的代码片断完成程序识别表达式。因此，用户自由编写动作时，并不影响其编写高层的表达式语言来匹配字符串表达式。这就避免迫使用户使用字符串语言来进行输入分析时，也必须使用同样的方法来编写字符处理程序，而这样做有时是不合适的。LEX不是完整的语言，但是是一个新语言的生成器，它可以插入到各种不同的被叫做“宿主语言”的程序设计语言中。就像大多数目的语言可以生成在不同计算机硬件上运行的代码，LEX可以生成不同的宿主语言。宿主语言用于LEX生成输出代码，也用于用户插入程序片断。这使得LEX适用于不同的环境和不同的使用者。每一个应用程序可以是硬件、适用于该任务的宿主语言、用户背景和局部接口属性的直接结合。现在，LEX唯一支持的宿主语言是C，尽管Fortran（形式为Ratfor2）在过去也被支持。LEX自身存在于UNIX、GCOS和OS/370上；但是LEX生成的代码可以在任何适当的编译器上使用。LEX将用户输入的表达式和动作actions（在这篇文章中被称作源代码）转换为宿主语言；生成的程序叫做yyLEX。yyLEX识别字符流中的表达式（本文称作输入流），并且当每一个表达式被检测出来后，输出相应的动作。3.2 LEX格式LEX源程序的一般格式是：辅助定义的部分%识别规则部分%用户子程序部分其中用花括号起来的各部分都不是必须有的。当没有“用户子程序部分”时，第二个%也可以省去。第一个%是必须的，因为它标志着识别规则部分的开始，最短的合法的LEX源程序是：%它的作用是将输入串照原样抄到输出文件中。3.3 LEX识别规则识别规则都分是LEX源程序的核心。它是一张表，左边一列是正规式，右边一列是相应的动作。下面是一条典型的识别规则：integer printf（found keywcrd INT）;这条规则的意思是在输入串中寻找词形“integer”，每当与之匹配成功时，就打印出“foundkeyword INT”这句话。注意在识别规则中，正规式与动作之间必须用空格分隔开。动作部分如果只是一个简单的C表达式，则可以写在正规式右边同一行中，如果动作需要占两行以上，则须用花括号括起来，否则会出错。上倒也可以写成：integer printf（found keyword INT）;下面先介绍识别规则部分的写法，再介绍其余部分。3.3.1 LEX用的正规式一个正规式表示一个字符串的集合。正规式由正文字符与正规式运算符组成正文字符组成基本的正规式，表示某一个符号串；正规式运算符则将基本的正规式组合成为复杂的正规式，表示字符串的集合。例如：ab仅表示字符串ab，而（a b）+表示字符串的集合：ab，abab，ababab，）。LEX中的正规式运算符有下列十六种：“ -？*+| （）/$ %”。上述运算符需要作为正文字符出现在正规式中时，必须借助于双引号”或反斜线，具体用法是；xyz“+”或xyz+，表示字符串xyz+，要表示双引号本身可用”，要表示反外线用”或，在识别规则中空格表示正规式的结束，因此要在正规式中引进空格必须借助双引号或反斜线，但出现在方括号之内的空格是例外。几个特殊符号：n是回车换行，t是tab，b是退格。下面按照运算符的功能分别介绍上述正规式运算符。（1）字符的集合用方括号对可以表示字符的集合。如a b c表示与单个字符a或b或c匹配。在方括号中大多数的运算符都不起作用，只有-和例外。运算符-表示字符的范围，例如a-z 0-9 -，表示由所有小写字母，所有数字、尖括号及下划线组成的字符集合。如果某字符集合中包括-在内，则必须把它写在第一个或最后一个位置上，如；-+0-9，表示与所有数字和正负号匹配。在字符集合中，运算符必须写在第一个位置即紧接在左方括号之后，它的作用是求方括号中除之外的字符组成的字符集合相对于计算机的字符集的补集，如 abc与除去a、b和c以外的任何符号匹配。运算符在方括号中同样发挥解除运算符作用的功能。（2）与任意字符匹配的正规式运算符。形成的正规式与除回车换行符以外的任意字符匹配。LEX的正规式中，也可以用八进制数字与一起表示字符，如40-176。与ASCII字符集中所有在八进制 40（空格）到八进制176（）之间的可打印字符匹配。（3）可有可无的表达式运算得？指出正规式中可有可无的子式，如ab?c，与ac或abc匹配，即b是可有可无的。（4）闭包运算运算符*和十是 LEX正规式中的闭包运算符，它们表示正规式中某子式的重复，例如a*表示由0个或多个a组成的字符串的集合，而a+表示由1个或多个a组成的字符串的集合，下面两个正规式是常用的：a-z+和A-Za-zA-Za-z 0-9*。第一个是所有由小写字母组成的字符串的集合，第二个是由字母开头的字母数字串组成的集合。（5） 选择和字符组运算符|表示选择：如（ab|cd）表示与ab或cd匹配。运算符（）表示一组字符（ab）表示字符串ab，而ab则表示单个字符a或b。圆括号（）用于表示复杂的正规式，如：（ab|cd+）？（ef）*，表示与abefef, efef, cdef, cddd匹配，但不与abc, abcd或abcdef匹配。（6）上下文相关性LEX可以识别一定范围的上下文，因此可在一定程度上表示上下文相关性。若某正规式的第一个字符是，则仅当该正规出现在一行的开始处时才被匹配，一行的开始处是指整个输入串的开始或者紧接在一个回车换行之后，注意还有另一个作作即求补，的这两种用法不可能发生矛盾。若某正规式的最后一个字符是$，则仅当该表达式出现在一行的结尾处时才被匹配，一行的结尾处是指该表达式之后紧接一个回车换行。某（7）重复和辅助定义当被括起来的是数字对时，表示重复；当它括起来的是一个名字时，则表示辅助定义的展开。例如：a1，5 ，表示集合a.aa.aaa.aaaa.aaaaa.digit则与预先定义的名叫dight的串匹配，并将有定义插入到它在正规式中出现的位置上。3.4 YACC简介图3-1：LEX与YACC编译过程YACC本质是语法分析器，YACC运行后会生成语法编译器，YACC需要以LEX一起使用将YACC与LEX编译器生成的C程序一并编译。分析程序生成器(parser generator)是一个指定某个格式中的一种语言的语法作为它的输入，并为该种语言产生分析过程以作为它的输出的程序。在历史上，分析程序生成器被称作编译-编译程序( compiler- compiler )，这是由于按照规律可将所有的编译步骤作为包含在分析程序中的动作来执行。现在的观点是将分析程序仅考虑为编译处理的一个部分，所以这个术语也就有些过时了。合并 LALR(1) 分析算法是一种常用的分析生成器，它被称作 YACC( yet another compiler- compiler )。给出 YACC 的概貌来，将使用YACC为 TINY 语言开发一个分析程序。作为 YACC 对说明文件中的 %token NUMBER 声明的对应。YACC 坚持定义所有的符号记号本身，而不是从别的地方引入一个定义。但是却有可能通过在记号声明中的记号名之后书写一个值来指定将赋给记号的数字值。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的功能和需求。3.5 YACC源程序说明部分的写法YACC源程序的说明部分定义语法规则中要用的终结符号，语义动作中使用的数据类型、变量、语义值的联合类型以及语法规则中运算符的优先级等。这些内容的组织方式如下：头文件表宏定义数据类型定义全局变量定义语法开始符定义语值类型定义终结符定义运算符优先级及结合性定义（1）头文件表YACC直接把这部分定义抄到所生成的C语言程序y.tab.c中去的，所以要按C语言的语法规定来写。头文件表是一系列C语言的include语句，要从每行的第一列开始写。（2）宏定义这部分用C语言的 define语句定义程序中要用的宏。（3）数据类型定义这部分定义语义动作中或程序段部分中要用到的数据类型。（4）语法开始符定义上下文无关文法的开始符号是一个特殊的非终结符，所有的推导都从这个非终结符开始，在YACC中，语法开始符定义语句是：% start 非终结符如果没有上面的说明，YACC自动将语法规则部分中第一条语法规则左部的非终结符作为语法开始符。（5）语义值类型定义yycc生成的语法分析程序yyparse用的是LR分析方法，它在作语法分析时除了有一个状态钱外，还有一个语义值钱，存放它所分析到的非经结符和终结符的语义值，这些语义值有的是从词法分析程序传回的，有的是在语义动作中赋与的，这些在介绍语义动作时再详细说明。如果没有对语义值的类型做定义，那么YACC认为它是整型（int）的，即所有语法符号如果赋与了语义值，则必须是整型的，否则会出类型错，但是用户经常会希望语义值的类型比较复杂，如双精度浮点数，字符串或树结点的指针这时就可以用语义值类型定义进行说明。因为不同的语法符号的语义值类型可能不同，所以语义值类型说明就是将语义值的类型定义为一个联合，这个联合包括所有可能用到的类型（各自对应一个成员名），为了使用户不必在存取语义值时每次都指出成员名，在语义值类型定义部分还要求用户说明每一个语法符号（终结符和非终结符）的语义值是哪一个联合成员类型。（6）终结符定义在YACC源程序语法规则部分出现的所有终结符（文字字符literal除外）必须在这部分定义，定义方法如下例： token DIGIT LETTER每个终结符定义行以token开头，注意与token之间没有空格，一行中可以定义多个终结符，它们之间用空格分开，终结符名可以由字母，数字，下划线组成，但必须用字母于头。非终结符名的组成规则与此相同。终结符定义行可多于一个。YACC规定每个终结符都有一个唯一的编号（token number）。当我们用上面的方式定义经结符时，终结符的编号由YACC内部决定，其编号规则是从257开始依次递增，每次加1。但这个规则不适用于文字字符（literal）的终结符。例如在下面的语法规则中，；就是文字字符终结符:stats： stats； stat；expr: expr+ expr;文字字符终结符在规则中出现时用单引号括起来。它们不需要用token语句定义，YACC对它们的编号就采用该字符在其字符集（如ASCII）中的值。注意上面两条语法规则末尾的分号是YACC元语言的标点符号，不是文字字符终结符。YACC也允许用户自己定义终结符的编号。如果这样，那么终结符定义的格式就是：token终结符名 整数其中“终结符名”就是要定义的终结符，“整数”就是该终结符的编号，每一个这样的行定义一个终结符。特别注意不同终结符的编号不能相同3.4 实现词法分析的思路分析3.4.1 无意义字符的识别对于空白分隔符处理思路是，遇到后，将其视为空白字符直接略过，然后一直向后遍历一直到下一个字符非空白分隔符。对于换行符处理思路与空白分隔符相同是，遇到后，也是将其视为空白字符直接略过，然后一直向后遍历一直到下一个字符非换行符。3.4.2 标识符、数字、字符和字符串的识别（1）标识符识别标识符的识别，当识别到字母时，一直向下遍历，直到下一个字符不是字母且不是数字且不是下划线，就跳出循环，标记此为标识符。标识符的具体含义需要通过语法分析器分析。（2）数字的识别数字的识别分为两步，第一步为识别数字，识别出数字后将后续内容存为字符串。识别数字的过程，首先判断是否符合数字规则，c语言中我们可以这样表述：while (ISIDNUM (*cur) | *cur = . | VALID_SIGN (*cur, cur-1)当我们碰到空格就可以跳出循环，同时根据计算的数字长度开辟空间，记录数字内容。根据字符串里面的具体内容分析属性。数字的属性包括三种，分别是类型属性、进制属性和后缀信息。属性分类类型属性整型、浮点型等进制属性十进制、八进制、十六进制等后缀信息短类型、宽类型等辅助类型表3-1：数字属性分类（3）字符或字符串识别当识别到第一个字符时，我们首先需要判断字符或字符串前面有没有修饰符（“L”“U”“u”“8”）。然后就碍事识别字符或字符串了，首先分局是否识别到“”，判断是否是字符串。若是字符串则根据是否有修饰符或者修饰符的种类来设置字符的类型。（4）运算符和分隔符的识别“/”的识别由“/”开头组成的字符（除“/”外）具体类型注释符号“/*”和“*/”注释掉它们之间的内容“/”注释掉当前行的内容运算符“/=”对运算符左边和右边的操作数做除法并且将结果赋给左边的操作数表3-2：除号识别“/”有许多不同的组合，我们要根据不同的类型的区别来识别。识别到“/”后，当其后字符为“*”，则符号为注释符（直到一系列字符后识别到“*”后紧跟“/”注释内容识别完毕）；当其后字符为“/”，则符号也为注释符（直到我们识别到“n”后紧跟“”，行注释内容识别完毕）；当其后字符为“=”则我们识别到的一定是除号；当不属于上面的情况是我们识别到的就是符号“/”。“”识别相同）由“”开头组成的字符（除“”外）含义=小于等于=左移且赋值左移表3-3：由“”开头组成的字符识别到“”后，当其后是“=”则标记为小于等于；当其后是“”紧跟“=”则是左移赋值；当其后是“”紧跟其他符号（不是等号），则是左移符号。其他情况为符号“”。“%”的识别“%”的识别较为简单，识别到“%”后，若其后面紧跟“=”则表示的是求余赋值符号“%=”，若不是，则是符号“%”其他运算符的识别大致相同。第4章 语法分析中的产生式4.1 产生式简介产生式的实质是一种解决方案，设计一种让计算机能够应对某语法的任意变换的语法模板。产生式“”左边为“左部”，右边为“右部”。左部是右部内容组织形式的一种集约化（即要求右部工作效益和效率高）体现。“|”与列表就是集约化的体现。列表就是将相同的各项进行合并，使其形成一套能够让计算机理解的组织形式（形式）。使用或我们可以更高效的写出表达式。综上所述，我们要写出集约化的表达式，一定要灵活使用或与列表。4.2 左递归的消除对于任意一个非终结符，经过一次或多次展开后形成的产生式，如果其右部第一个因子与产生式左部相同，则称为“左递归”。左递归有直接左递归与简介左递归。图4-1：直接左递归与间接左递归与产生式匹配时是由上到下由左到右的串行匹配表达式，只有匹配到终结符号时才能结束匹配。直至全部匹配完，退出循环。在匹配时我们要避免左递归形成死循环。种类解除方案直接左递归首先，把所有产生式写成候选形式，即写出全部可能的产生式。然后进行合并推导。间接左递归首先，将非终结符以某种顺序排列（Ai），然后用Ai代替非终结符号，最后化简。表4-1：直接左递归与间接左递归的解除方案4.3 算数运算产生式（1）算数运算产生式最简单的算数表达式是：“数字+运算符(加减乘除)+数字”，公式中的“数字”也可以是“数字+运算符(加减乘除)+数字”，即使用递归规则简化语法模板。算数运算产生式NUMBER| 算数运算产生式+NUMBER| 算数运算产生式-NUMBER| 算数运算产生式*NUMBER| 算数运算产生式/NUMBER表4-2：算数运算固定模板不过，这种固定的语法模板即使结合了递归使得计算机能够应对一些简单的变换，不过仍会对同一公式产生歧义性。（2） 算数表达歧义性编写语法分析程序要避免语法分析会产生歧义性，仅简单按照3.1的算数运算产生式，会产生歧义性。例如我们输入4+6*8，如下表有两种可能的分析。图2.5中，语法分析将4+6认为是一个表达式，输出结果为（4+6）*8。图2.6中，语法分析将6*8认为是一个表达式，输出结果为4+（6*8）。表达式4+6*8语法分析+468*图4-2：4+6*8的可能性14+6*8语法分析8*6+4表达式图4-3：4+6*8的可能性2可以隐式地和显式地在语法中规定优先级和结合规则。选择的是使用通常的优先级和左结合的隐式地编写语法。图4-4：优先级和左结合的代码段截图按照图中的优先级4+6*8将按照4+(6*8)的方式运算。写YACC源程序时会经常碰到。二义性会带来冲突。YACC可以用为算符确定优先级和结合规则解决由二义性造成的冲突，但是有一些由二义性造成的冲突不易通过优先级方法解决，对于这样的二义性造成的冲突和一些不是由二义性造成的冲突，YACC提供了下面两条消除二义性的规则：出现移进归约冲突时，进行移进；出现归约归约冲突时，按照产生式在YACC源程序中出现的次序，用先出现的产生式归约。我们可以看出用这两条规则解决上面的IF语句二义性问题是合乎我们需要的。所以用户不必将上述文法改造成无二义性的。当YACC用上述两条规则消除了二义性，它将给出相应信息。YACC源程序中的产生式也有一个优先级和结合性这个优先级和结合性就是该产生式右部最后一个终结符或文字字符的优先级和结合性，当使用了Prec子句时，该产生式的优先级和结合性由Prec子句决定。当然如果产生式右部最后一个终结符或文字字符没有优先级或结合性，则该产生式也没有优先级或结合性。根据终结符（或文字字符）和产生式的优先级和结合性，YACC又有两个解决冲突的规则： 当出现移进/归约冲突或归约归约冲突，而当时输入符号和语法规则（产生式）均没有优先级和结合性，就用 AI和A2来解决这些冲突。当出现移进归约冲突时，如果输入符号和语法规则（产生式）都有优先级和结合性，那么如果输入符号的优先级大于产生式的优先级就移进如果输入符号的优先级小于产生式的优先级就归约。如果二者优先级相等，则由结合性决定动作，左结合则归约，右结合则移进，无结合性则出错。 用优先级和结合性能解决的冲突，YACC不报告给用户。写YACC源程序时会经常碰到。二义性会带来冲突。YACC可以用为算符确定优先级和结合规则解决由二义性造成的冲突，但是有一些由二义性造成的冲突不易通过优先级方法解决，例如IF语句二义性问题，YACC提供了下面两条消除二义性的规则：出现移进归约冲突时，进行移进；出现归约归约冲突时，按照产生式在YACC源程序中出现的次序，用先出现的产生式归约。这两条规则可以解决IF语句二义性问题。所以用户不必将上述文法改造成无二义性的。当YACC用上述两条规则消除了二义性，它将给出相应信息。YACC源程序中的产生式也有一个优先级和结合性这个优先级和结合性就是该产生式右部最后一个终结符或文字字符的优先级和结合性，当使用了Prec子句时，该产生式的优先级和结合性由Prec子句决定。当然如果产生式右部最后一个终结符或文字字符没有优先级或结合性，则该产生式也没有优先级或结合性。根据终结符（或文字字符）和产生式的优先级和结合性，YACC又有两个解决冲突的规则：当出现移进/归约冲突或归约归约冲突，而当时输入符号和语法规则（产生式）均没有优先级和结合性。当出现移进归约冲突时，如果输入符号和语法规则（产生式）都有优先级和结合性，那么如果输入符号的优先级大于产生式的优先级就移进如果输入符号的优先级小于产生式的优先级就归约。如果二者优先级相等，则由结合性决定动作，左结合则归约，右结合则移进，无结合性则出错。第5章 基于语法分析的数学公式分析器的设计5.1 实现简单算数运算由上一章得出我们在进行数学运算表达式的设计时，要集约化。需要设定优先级已经左结合的隐式编写语法。词法分析以及语法分析程序如下。词法分析程序最重要的是对，数字以及运算符号的识别。并将识别到数字以及运算符标记。0-9+ yylval = atoi(yytext); return INTEGER; -+*/n return *yytext;这两行代码表示，识别数字，运算符换行符，另我们还需要一行，舍弃空格以及无效字符。我们要在语法分析规则段程序规定了运算符的优先级。我们要使用递归高效的写出了算数运算的表达式。expr INTEGER |expr + expr |expr - expr |expr * expr |expr / expr5.2 保存运算符与变量公式分析器要是别单字符的字母变量，因为AZ一共只有26个，数量有限，所以我们能在26个大小的数组中存储，使得公式分析器的范围更广。因此如果要在程序中保存运算符与变量，需要做以下扩充变化：增加全局数组来存放变量，不过变量名有限制，只支持单字符；增加全局数组存放分析过的语句；增加函数打印堆栈信息；增加函数打印目前的分析语句。5.3 支持多字符变量如果想支持多字符，我们只需要再定义一个全局变量。5.4 编译运行程序：在ubuntu系统下LEX&YACC被FLEX&BISON代替，故而我们使用FLEX&BISON编译运行程序。（1）首先，编译LEX文件，生成LEX.yy.c文件图5-1：编译LEX文件（2）其次，编译YACC文件，生成ch3-01.tab.h 与ch3-01.tab.c文件图5-2：编译YACC文件（3）链接生成的.c 文件，并生成相应的可执行文件图5-3：链接生成的.c 文件（4）运行可执行文件，计算图5-4：运行可执行文件5.5 总结本项目将大学阶段的计算机理论应用于设计。在项目完成阶段的主要任务是对编译原理进行深入了解，并在使用lax&YACC和fLEX&bison工具的时候对LINUX（Ubuntu）系统的进一步进行了熟悉。限制于大学阶段的能力范围，本论文所完成的公式分析器可以完成单字节，多字节变量、简单数学公式分析。 参考文献1张晶,杨冬,郭德贵,金英,刘磊. 编译原理实践课程教学方法研究J. 吉林大学学报(信息科学版),2005,(S2):142-144.2郑君民,王振龙,赵万生. 基于LEX&YACC的电火花加工译码系统J. 电加工与模具,2005,(06):27-29.3罗海丽. 基于LEX语言的词法分析程序自动构造过程J. 包头钢铁学院学报,2005,(04):314-317.4臧秀娟,刘维亭. 基于LEX和YACC的C_Minus编译器J. 信息技术,2011,(05):122-124+128.5喻赛花,游有鹏,魏明江. 基于LEX&YACC的PLC结构化文本编译器的设计与开发J. 可编程控制器与工厂自动化,2011,(09):31-33+73.6李欣,谭晓青. 抵抗滑动攻击的LEX算法改进J. 计算机工程与应用,2012,(26):101-103+117.7丁英嘉,王能斌. 语言开发工具LEX和YACC的分析