《编译器的自动生成工具LEX和YACC的使用方法.doc》由会员分享，可在线阅读，更多相关《编译器的自动生成工具LEX和YACC的使用方法.doc（29页珍藏版）》请在三一文库上搜索。
1、编译器的自动生成工具LEX和YACC的使用方法一、 词法分析程序产生器LEX的用法11 Lex概述Lex是一个词法分析器（扫描器）的自动产生系统，它的示意图如图1.1。Lex源程序是用一种面向问题的语言写成的。这个语言的核心是正规表达式，用它描述输入串的词法结构。在这个语言中用户还可以描述当某一个词形被识别出来时要完成的动作，例如在高级语言的词法分析器中，当识别出一个关键字时，它应该向语法分析器返回该关键字的内部编码。Lex并不是一个完整的语言，它只是某种高级语言（称为lex的宿主语言）的扩充，因此lex没有为描述动作设计新的语言，而是借助其宿主语言来描述动作。我们只介绍C作为lex的宿主语言
2、时的使用方法，在Unix系统中， FORTRAN语言的一种改进形式Ratfor也可以做lex的宿主语言。图1.1 Lex示意图Lex自动地表示把输入串词法结构的正规式及相应的动作转换成一个宿主语言的程序，即词法分析程序，它有一个固定的名字yylex，在这里yylex是一个C语言的程序。yylex将识别出输入串中的词形，并且在识别出某词形时完成指定的动作。看一个简单的例子：写一个lex源程序，将输入串中的小写字母转换成相应的大写字母。程序如下：%a-z printf(“%c”,yytext0+A-a)；上述程序中的第一行%是一个分界符，表示识别规则的开始。第二行就是识别规则。左边是识别小写字母的
3、正规式。右边就是识别出小写字母时采取的动作:将小写字母转换成相应的大写字母。Lex的工作原理是将源程序中的正规式转换成相应的确定有限自动机，而相应的动作则插入到yylex中适当的地方，控制流由该确定有限自动机的解释器掌握，对于不同的源程序，这个解释器是相同的。12 lex源程序的格式lex源程序的一般格式是：辅助定义的部分 % 识别规则部分% 用户子程序部分其中用花括号起来的各部分都不是必须有的。当没有“用户子程序部分”时，第二个%也可以省去。第一个%是必须的，因为它标志着识别规则部分的开始，最短的合法的lex源程序是：%它的作用是将输入串照原样抄到输出文件中。识别规则部分是Lex源程序的核心
4、。它是一张表，左边一列是正规式，右边一列是相应的动作。下面是一条典型的识别规则：integer printf（found keywcrd INT）;这条规则的意思是在输入串中寻找词形“integer”，每当与之匹配成功时，就打印出 “found keyword INT”这句话。注意在识别规则中，正规式与动作之间必须用空格分隔开。动作部分如果只是一个简单的C表达式，则可以写在正规式右边同一行中，如果动作需要占两行以上，则须用花括号括起来，否则会出错。上例也可以写成：integer printf（found keyword INT）;下面先介绍识别规则部分的写法，再介绍其余部分。1.3 Lex用的
5、正规式一个正规式表示一个字符串的集合。正规式由正文字符与正规式运算符组成。正文字符组成基本的正规式，表示某一个符号串；正规式运算符则将基本的正规式组合成为复杂的正规式，表示字符串的集合。例如：ab仅表示字符串ab，而(a b)+表示字符串的集合：ab，abab，ababab，。Lex中的正规式运算符有下列十六种： “ - ？ * + | （） / $ % 上述运算符需要作为正文字符出现在正规式中时，必须借助于双引号”或反斜线，具体用法是；xyz“+”或xyz+表示字符串xyz+为避免死记上述十多个运算符，建议在使用非数字或字母字符时都用双引号或反斜线。要表示双引号本身可用”，要表示反外线用”或
6、前面说过，在识别规则中空格表示正规式的结束，因此要在正规式中引进空格必须借助双引号或反斜线，但出现在方括号之内的空格是例外。几个特殊符号：n是回车换行（newline）t是tabb是退格（back space）下面按照运算符的功能分别介绍上述正规式运算符。1 字符的集合用方括号对可以表示字符的集合。正规式a b c与单个字符a或b或c匹配在方括号中大多数的运算符都不起作用，只有、- 和 例外。运算符 - 表示字符的范围，例如a-z 0-9 _ 表示由所有小写字母，所有数字、尖括号及下划线组成的字符集合。如果某字符集合中包括-在内，则必须把它写在第一个或最后一个位置上，如-+0-9与所有数字和正
7、负号匹配。在字符集合中，运算符必须写在第一个位置即紧接在左方括号之后，它的作用是求方括号中除之外的字符组成的字符集合相对于计算机的字符集的补集，例如abc与除去a、b和c以外的任何符号匹配。运算符在方括号中同样发挥解除运算符作用的功能。2 与任意字符匹配的正规式运算符形成的正规式与除回车换行符以外的任意字符匹配。在lex的正规式中，也可以用八进制数字与一起表示字符，如40-176与ASCII字符集中所有在八进制 40（空格）到八进制176（）之间的可打印字符匹配。3 可有可无的表达式运算得？指出正规式中可有可无的子式，例如ab?c与ac或abc匹配，即b是可有可无的。4 闭包运算运算符*和十是
8、 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, a
9、bcd或abcdef匹配。6、上下文相关性lex可以识别一定范围的上下文，因此可在一定程度上表示上下文相关性。若某正规式的第一个字符是，则仅当该正规式出现在一行的开始处时才被匹配，一行的开始处是指整个输入串的开始或者紧接在一个回车换行之后，注意还有另一个作用即求补，的这两种用法不可能发生矛盾。若某正规式的最后一个字符是$，则仅当该表达式出现在一行的结尾处时才被匹配，一行的结尾处是指该表达式之后紧接一个回车换行。运算符/指出某正规式是否被匹配取决于它的后文，例如ab/cd仅在ab之后紧接cd的情况下才与ab匹配。$其实是/的一个特殊情形，例如下面两个正规式等价：ab$,ab/ n某正规式是否被匹
10、配，或者匹配后执行什么样的动作也可能取决于该表达式的前文，前文相关性的处理方法在后面专门讨论，将用到运算符 7、重复和辅助定义当被 括起来的是数字对时， 表示重复；当它括起来的是一个名字时，则表示辅助定义的展开。例如:a1，5表示集合a.aa.aaa.aaaa.aaaaa。digit则与预先定义的名叫dight的串匹配，并将有定义插入到它在正规式中出现的位置上，辅助定义在后面专门讨论。最后，符号%的作用是作为lex源程序的段间分隔符。14 Lex源程序中的动作前面说过当Lex识别出一个词形时，要完成相应的动作。这一节叙述Lex为描述动作提供的帮助。首先应指出，输入串中那些不与任何识别规则中的正
11、规式匹配的字符串将被原样照抄到输出文件中去。因此如果用户不仅仅是希望照抄输出，就必须为每一个可能的词形提供识别规则，并在其中提供相应的动作。用lex为工具写程序语言的词法分析器时尤其要注意。最简单的一种动作是滤掉输入中的某些字符串，这种动作用C的空语句“；”来实现。例：滤掉输入串中所有空格、tab和回车换行符，相应的识别规则如下：tn；如果相邻的几条规则的动作都相同，则可以用|表示动作部分，它指出该规则的动作与下一条规则的动作相同。例如上倒也可以写成：“ ”| “t”|“n”；注意t和n中的双引号可以去掉。外部字符数组yytext的内容是当前被某规则匹配的字符串，例如正规式a-z+与所有由小写
12、字母组成的字符串匹配，要想知道与它匹配的具体字符串是什么，可用下述规则：az printf（“ s”， yytext）;动作printf（“s”，yytext）就是将字符数组yytext的内容打印出来，这个动作用得很频繁，Lex提供了一个宏ECHO来表示它，因此上述识别规则可以写成：az+ECHO；请注意，上面说过缺省的动作就是将输入串原样抄到输出文件中，那么上述规则起什么作用呢？这一点将在“规则的二义性”一节中解释。有时有必要知道被匹配的字符串中的字符个数，外部变量yyleng就表示当前yytext中字符的个数。例如要对输入串中单词的个数和字符的个数进行计数（单词假定是由大写或小写字母组成的
13、字符串），可用下述规则：a-zAZ+ words+；Chars+=yyleng；注意被匹配的字符串的第一个字符和最后一个字符分别是yytext0和yytextyyleng-1下面介绍三个Lex提供的在写动作时可能用到的C函数lyymore（）当需下一次被匹配的字符串被添加在当前识别出的字符串后面，即不使下一次的输入替换yytext中已有的内容而是接在它的内容之后，必须在当前的动作中调用yymore( )。例：假设一个语言规定它的字符串括在两个双引号之间，如果某字符串中含有双引号，则在它前面加上反斜线。用一个正规式来表达该字符串的定义很不容易，不如用下面较简明的正规式与yymore（）配合来识别
14、： * if（yytextyyleng1= =yymore( );elsenormal user processing;当输入串为”abcdef”时，上述规则首先与前五个字符”abc匹配，然后调用yymore（ ）使余下部分”def被添加在前一部分之后，注意作为字符串结尾标志的那个双引号由”normal user proessing”部分负责处理。2yyless（n）如果当前匹配的字符串的末尾部分需要重新处理，那么可以调用 yyless（n）将这部分子串“退回”给输入串，下次再匹配处理。yyless(n)中的n是不退回的字符个数，即退回的字符个数是yyleng-n。例；在C语言中串“=-a”具
15、有二义性，假定要把它解释为“=-a”同时给出信息，可用下面的识别规则：=-a-zA-Zprintf（“Operator（=-）ambiguousn”）；yyless（yyleng-1）;action for-上面的规则先打印出一条说明出现二义性的信息，将运算符后面的字母返回给输入串，最后将运算符按“=”处理另外，如果希望把“=- a”解释为”- a”，这只需要把负号与字母一起退回给输入串等候下次处理，用下面的规则即可：=-a-zA-Z printf（“Operator（=-） ambiguousn”）； yyless (yyleng-1);action for = 3. yywrap ( )当
16、Lex处理到输入串的文件尾时，自动地调用yywrap（），如果 yywrap（）返回值是1，那么Lex就认为对输入的处理完全结束，如果yywrap（）返回的值是0,Lex就认为有新的输入串等待处理。Lex自动提供一个yywrap（），它总是返回1，如果用户希望有一个返回0的yywrap（ ），那么就可以在”用户子程序部分”自己写一个 yywrap（），它将取代Lex自动提供的那个yywrap（），在用户自己写的yywrap（）中，用户还可以作其他的一些希望在输入文件结束处要作的动作，如打印表格、输出统计结果等，使用yywrap（）的例子在后面举出。1. 5识别规则的二义性有时Lex的程序中可能
17、有多于一条规则与同一个字符串匹配，这就是规则的二义性，在这种情况下，Lex有两个处理原则：1） 能匹配最多字符的规则优先;2） 在能匹配相同数目的字符的规则中，先给出的规则优先。例：设有两规则按下面次序给出：integer kegword actiona-z+ identifier action如果输入是integers，则它将被当成标识符处理，因为规则integer只能匹配7个字符，而a-z+能匹配8个字符；如果输入串是integer，那么它将被当作关键字处理，因为两条规则都能与之匹配，但规则integer先给出。 1.6 lex源程序中的辅助定义部分Lex源程序的第一部分是辅助定义，到目前
18、为止我们只涉及到怎样写第二部分，即识别规则部分的写法，现在来看第一部分的写法。在Lex源程序中，用户为方便起见，需要一些辅助定义，如用一个名字代表一个复杂的正规式。辅助定义必须在第一个之前给出，并且必须从第一列开始写，辅助定义的语法是：name translation例如用名字IDENT来代表标识符的正规式的辅助定义为IDENT a-zA-Za-zA-Z0-9*辅助定义在识别规则中的使用方式是用运算符 将 name括起来，Lex自动地用 translation去替换它，例如上述标识符的辅助定义的使用为：IDENTaction for identifer下面我们用辅助定义的手段来写一段识别FOR
19、TRAN语言中整数和实数的Lex源程序：D 0一9E DEde-+？ D+D+ printf（“integer”）；D+.D*(E)? |D*.D+(E)? |D+E printf( real );请注意在辅助定义部分中可以使用前面的辅助定义。例如：定义E时使用了D，但所用的辅助定义必须是事先已定义过的，不能出现循环定义。上面的规则只是说明辅助定义的用法，并不是识别FORTRAN中数的全部规则，因为它不能处理类似35.EQI这样的问题，即会把35.EQI中的35.E当作实数，怎么解决这种问题请读者思考。除了上面介绍的辅助定义之外，用户还需要在Lex源程序中使用变量，还需要有一些自己写的子程序。
20、前面已经见过两个常用的变量即yytext和yylong，也介绍过几个Lex提供的子程序yymore,yyless和yywrap,现在介绍用户如何自己定义变量和写子程序。Lex是把用户写的Lex源程序转换成一个C语言的程序yylex，在转换过程中，Lex是把用户自己的变量定义和子程序照抄到yylex中去,lex规定属于下面三种情况之一的内容就照抄过去；1） 以一个空格或tab起头的行，若不是 Lex的识别规则的一部分，则被照抄到 Lex产生的程序中去。如果这样的行出现在第一个之前，它所含的定义就是全局的，即Lex产生的程序中的所有函数都可使用它。如果这样的行紧接在第一个之后但在所有识别规则之前，
21、它们就是局部的，将被抄到涉及它的动作相应的代码中去。注意这些行必须符合C语言的语法，并且必须出现在所有识别规则之前。这一规定的一个附带的作用是使用户可以为Lex源程序或Lex产生的词法分析器提供住解，当然注解必须符合C语言文法。2） 所有被界于两行和之间的行，无论出现在哪里也无论是什么内容都被照抄过去，要注意 和必须分别单独占据一行例如:#define ENDOFFILE 0#include int flag提供上面的措施主要因为在C语言中有一些行如上例中的宏定义或文件蕴含行必须从第一列开始写。3） 出现在第二个之后的任何内容，不论其格式如何，均被照抄过去。1.7 怎样在Unix系统中使用Le
22、x假定已经写好了一个Lex源程序。怎样在Unix系统中从它得到一个词法分析器呢？Lex自动地把Lex源程序转换成一个C语言的可运行的程序，这个可运行的程序放在叫Lex.yy.c的文件中，这个C语言程序再经过C编译，即可运行。例，有一名叫source的Lex源程序，第一步用下面的命令将它转换成lex.yy.c：$lex source（$是 Unix的提示符）。Lex.yy.c再用下面的命令编译即得到可运行的目标代码 a.out：$cc lex.yy.c -ll上面的命令行中的-11是调用Lex的库，是必须使用的。Lex可以很方便地与Yacc配合使用，这将在下一章中介绍。1.8例子这一节举两个例子
23、看看Lex源程序的写法。1将输入串中所有能被7整除的整数加3，其余部分照原样输出，先看下面的Lex源程序：int k；0-9+scanf（-1， yytext，“d”，k）;if（k 7 = =0）printf（“d”，k+3）；elseprintf（“ d”, k）;上面的程序还有不足的地方，如对负整数，只是将其绝对值加上3，而且象X7,49.63这样的项也做了修改，下面对上面的源程序稍作修改就避免了这些问题。int k;-?0-9+scanf（1，yytext，“d”，&k）；printf（“d”，k7= =0？k+3;k）;-?0-9+ ECHO;A-Za-zA-Za-z0-9+ ECH
24、O;2下一个例子统计输人串中各种不同长度的单词的个数，统计结果在数组lengs中,单词定义为由字母组成的串，源程序如下；int lengs 100;a-z+ lengsyyleng+;|n ;yywrap ( )int i ；printf（“Length No.words n”） ;for（i0；i100；i+)if（lengsi0） ptintf（“5d 10dn”，i， lengsi）;return (1);在上面的流程序中，当Lex读入输入串时，它只统计而不输出，到输入串读入完毕后，才在调用 yywrap（）时输出统计结果，为此用户自己提供了yywrap（），注意yywrap（）的最后一
25、个语句是返回值1。1.9 再谈上下文相关性的处理在3中介绍Lex用的正规式时提到了上下文相关性的表示，这里再详细介绍Lex提供的处理上下文相关的措施。要处理的问题是某些规则在不同的上下文中要采取不同的动作，或者说同样的字符串在不同的上下文中有不同的解释。例如在程序设计语言中，同一个等号“=”，在说明部 分表示为变量赋初值，这时的动作应是修改符号表内容；而在语句部分等号就是赋值语句的赋值号，这时又应该产生相应于赋值语句的代码。因此要依据等号所处的上下文来判断它的含义。Lex提供了两种主要的方法:1）使用标志来区分不同的上下文标志是用户定义的变量，用户在不同的上下文中为它置不同的值，以区分它在哪个
26、上下文中，这样识别规则就可以根据标志当前值决定在哪个上下文中并采取相应的动作。例：将输入串照原样输出，但对magic这个词，当它出现在以字母a开头的行中，将其改为first，出现在以b开头的行中将其改为second，出现在以c开头的行中则改为third。使用标志flag的Lex源程序如下；int flag ;a flag=a;ECHO;b flag=b; ECHO;c flag=c; ECHO;n flag=o; ECHO;magicswitch (flag) case a : printf (“first”); break; case b: printf (“second”); break;
27、 case c : printf (“third”); break; default; ECHO; break; 2）使用开始条件来区分不同上下文在Lex源程序中用户可以用名字定义不同的开始条件。当把某个开始条件立置于某条识别规则之前时，只有在Lex处于这个开始条件下这条规则才起使用，否则等于没有这条规则。Lex当前所处的开始条件可以随时由用户程序（即Lex动作）改变。开始条件由用户在Lex源程序的“辅助定义部分”定义，语法是Start name1 name2 name3其中Start可以缩写成S或s。开始条件名字的顺序可以任意给出，有很多开始条件时也可以由多个Start行来定义它们。开始条件
28、在识别规则中的使用方法是把它用尖括号括起来放在识别规则的正规式左边:name1expression要进入开始条件如Name1，在动作中用语句BEGIN name1它将Lex所处的当前开始条件改成 name1。要恢复正常状态，用语句BEGIN 0它将 Lex恢复到 Lex解释器的初始条件。一条规则也可以在几个开始条件下都起作用，如 rule使rule在三个不同的开始条件下都起作用。要使一条规则在所有开始条件下都起作用，就不在它前面附加任何开始条件。例：解决1）中的问题，这次用开始条件，Lex源程序如下：start AA BB CCa ECHO； BEGIN AA；b ECHO； BEGIN BB
29、；c ECHO； BEGIN CC；n ECHO； BEGIN 0；AAmagic printf （“first”） ;BBmagic Printf（“second”）；CCmagic Printf（“third”）；1.10 Lex源程序格式总结为使用方便起见，将Lex源程序的格式，Lex的正规式的格式等总录于此。Lex源程序的一般格式为：definitionsrulesuser subroutines辅助定义部分包括以下项目；1）辅助定义，格式为：name translation2）直接按照抄的代码，格式为：空格 代码3）直接照抄的代码，格式为：代码4）开始条件，格式为：S namel n
30、ame2还有几个其他项目，不常使用故略去。识别规则部分的格式是expression action其中expression必须与action用空格分开，动作如果多于一行，要用花括号括起来。Lex用的正规式用的运算符有以下一些：x 字符x“x”字符x，若为运算符，则不起运算符作用x 同上xy 字符x或yx-z 字符x，或y，或zx 除x以外的所有字符. 除回车换行外的所有字符x 出现在一行开始处的xyx 当 Lex处于开始条件 y时， xX 出现在一行末尾处的xx？ 可有可无的 Xx* 0个或多个xx+ 1个或多个xx|y X或y（x）字符xx/y 字符x但仅当其后紧随yxx 辅助定义XX的展开x
31、（m,n）m到n个x二、语法分析程序自动产生器yacc的使用方法2.l yacc概述形式语言都有严格定义的语法结构，我们对它们进行处理时首先要分析其语法结构。yacc是一个语法分析程序的自动产生器，严格地说Lex也是一个形式语言的语法分析程序的自动产生器。不过Lex所能处理的语言仅限于正规语言，而高级语言的词法结构恰好可用正规式表示，因此Lex只是一个词法分析程序的产生器。yacc可以处理能用LALR（1）文法表示的上下文无关语言。而且我们将会看到yacc具有一定的解决语法的二义性的功能。yacc的用途很广，但主要用于程序设计语言的编译程序的自动构造上。例如可移植的C语言的编译程序就是用yac
32、c来写的。还有许多数据库查询语言是用yacc实现的。因此，yacc又叫做“编译程序的编译程序（A Compiler ComPiler）。yacc的工作示意图如下； 图2.1 yacc示意图在图2.1中，“yacc源程序”是用户用yacc提供的一种类似BNF的语言写的要处理的语言的语法描述。yacc会自动地将这个源程序转换成用LR方法进行语法分析的语法分析程序yyparse，同Lex一样，yacc的宿主语言也是C，因此yyparse是一个C语言的程序，用户在主程序中通过调用yyparse进行语法分析。语法分析必须建立在词法分析的基础之上，所以生成的语法分析程序还需要有一个词法分析程序与它配合工作
33、。yyparse要求这个词法分析程序的名字为yylex。用户写yylex时可以借助于Lex。因为Lex产生的词法分析程序的名字正好是yylex，所以 Lex与yacc配合使用是很方便的，这将在2.5的2.5.3中详细介绍，请注意词法分析程序也是可以包含在yacc源程序中的。在yacc源程序中除了语法规则外，还要包括当这些语法规则被识别出来时，即用它们进行归约时要完成的语义动作，语义动作是用C语言写的程序段。语法分析的输出可能是一棵语法树，或生成的目标代码，或者就是关于输入串是否符合语法的信息。需要什么样的输出都是由语义动作和程序部分的程序段来实现的。下面分节介绍yacc源程序的写法以及在Uni
34、x系统中使用yacc的有关命令。2.2 yacc源程序的一般格式一个yacc源程序一般包括三部分：说明部分；语法规则部分；程序段部分，这三部分内容依次按下面的格式组织在一起：说明部分语法规则部分程序段部分上述三部分中说明部分和程序段部分不必要时可省去，当没有程序段部分时，第二个也可以省去。但是第一个是必须有的。下面详细介绍各部分的组成及写法。2.3 yacc源程序说明部分的写法yacc源程序的说明部分定义语法规则中要用的终结符号，语义动作中使用的数据类型、变量、语义值的联合类型以及语法规则中运算符的优先级等。这些内容的组织方式如下：头文件表宏定义数据类型定义全局变量定义语法开始符定义语义值类型
35、定义终结符定义运算符优先级及结合性定义2.3.1 头文件表yacc直接把这部分定义抄到所生成的C语言程序y.tab.c中去的，所以要按C语言的语法规定来写。头文件表是一系列C语言的include语句，要从每行的第一列开始写，例如：includestdio.hinclude math.hincludectype.h#include “header.h”.2.3.2 宏定义这部分用C语言的 define语句定义程序中要用的宏。例如. define EOF Odefine max（x,y）（xy）？x:y）. 2.3.3 数据类型定义这部分定义语义动作中或程序段部分中要用到的数据类型，例如：. ty
36、pedef struct interval double lo， hi；INTERVAL；.2.3.4 全局变量定义外部变量（external variable）和yacc源程序中要用到的全局变量都在这部分定义，例如：.extern int nfg;douhle dreg 26；INTERVAL Vreg26；.另外非整型函数的类型声明也包含在这部分中，请参看2.6例2。重申一遍，上述四部分括在 和之间的内容是由yacc原样照抄到y.tab.c中去，所以必须完全符合C语言文法，另外，界符和最好各自独占一行，即最好不写成% int x; %2.3.5 语法开始符定义上下文无关文法的开始符号是一个
37、特殊的非终结符，所有的推导都从这个非终结符开始，在yacc中，语法开始符定义语句是：% start 非终结符如果没有上面的说明，yacc自动将语法规则部分中第一条语法规则左部的非终结符作为语法开始符。2.3.6语义值类型定义yycc生成的语法分析程序yyparse用的是LR分析方法，它在作语法分析时除了有一个状态栈外，还有一个语义值栈，存放它所分析到的非经结符和终结符的语义值，这些语义值有的是从词法分析程序传回的，有的是在语义动作中赋与的，这些在介绍语义动作时再详细说明。如果没有对语义值的类型做定义，那么yacc认为它是整型（int）的，即所有语法符号如果赋与了语义值，则必须是整型的，否则会出
38、类型错，但是用户经常会希望语义值的类型比较复杂，如双精度浮点数，字符串或树结点的指针。这时就可以用语义值类型定义进行说明。因为不同的语法符号的语义值类型可能不同，所以语义值类型说明就是将语义值的类型定义为一个联合（Union），这个联合包括所有可能用到的类型（各自对应一个成员名），为了使用户不必在存取语义值时每次都指出成员名，在语义值类型定义部分还要求用户说明每一个语法符号（终结符和非终结符）的语义值是哪一个联合成员类型。下面举例说明并请参看2.6例2。 unionint ivaldouble dvalINTERVAL VVal;token ival DREG VREGtoken dval C
39、ONSTtype dyaldexptype vvalvexP在上述定义中，以union开始的行定义了语义值的联合类型，共有三个成员类型分别取名为ival, dval, vval。以token开始的行定义的是终结符（见2.3.7）所以DREG,VREG和CONST都是终结符，尖括号中的名字就是这些终结符的语义值的具体类型。如DREG和VREG这两个终结符的语义值将是整型（int）的，成员名是ival。以tyPe开始的行是说明非终结符语义值的类型。如非终结符dexP的语义值将是双精度浮点类型，请注意，在yacc中非终结符不必特别声明，但是当说明部分有对语义值类型的定义，而且某非终结符的语义值将被存
40、取，就必须用上面的方法定义它的类型。2.3.7 终结符定义在yacc源程序语法规则部分出现的所有终结符（文字字符literal除外）必须在这部分定义，定义方法如下例： token DIGIT LETTER每个终结符定义行以token开头，注意与token之间没有空格，一行中可以定义多个终结符，它们之间用空格分开，终结符名可以由字母，数字，下划线组成，但必须用字母开头。非终结符名的组成规则与此相同。终结符定义行可多于一个。yacc规定每个终结符都有一个唯一的编号（token number）。当我们用上面的方式定义终结符时，终结符的编号由yacc内部决定，其编号规则是从257开始依次递增，每次加1
41、.但这个规则不适用于文字字符（literal）的终结符。例如在下面的语法规则中，；就是文字字符终结符:stats： stats； stat；expr: expr+ expr;文字字符终结符在规则中出现时用单引号括起来。它们不需要用token语句定义，yacc对它们的编号就采用该字符在其字符集（如ASCII）中的值。注意上面两条语法规则末尾的分号是yacc元语言的标点符号，不是文字字符终结符。yacc也允许用户自己定义终结符的编号。如果这样，那么终结符定义的格式就是：token终结符名 整数其中“终结符名”就是要定义的终结符，“整数”就是该终结符的编号，每一个这样的行定义一个终结符。特别注意不同
42、终结符的编号不能相同。例如%token BEGIN 100token END 101%token IF 105token THEN 200.在3.6中我们说过如果用户定义了语义值的类型，那么那些具有有意义的语义值的终结符其语义值的类型要用Union中的成员名来说明，除了在3.6段中介绍的定义方法外，还可以把对终结符的定义和其语义值的类型说明分开，例如%token DREG VREG CONSTtype ival DREG VREGtype dval CONST2.3.8运算符优先级及结合性定义请看下面的关于表达式的文法：%token NAMEexpr: expr+ expr|expr expr
43、|expr*expr|NAME;这个文法有二义性，例如句子abc可以解释成（a b）一 c也可以解译成 a（b c），虽然这两种解释都合理但造成了二义性，如果将句子ab*C解释为（ab）*c就在语义上错了。yacc允许用户规定运算符的优先级和结合性，这样就可以消除上述文法的二义性。例如规定”具有相同的优先级，而且都是左结合的，这样。abc就唯一地解释为( a b)一 c。再规定*的优先级大于”，则 a b* c就正确地解释为 a（b*c） 了，因此上述文法的正确形式应是token NAMEleft +-left * expr：expr+ expr|expr- exPr|expr* expr|NAME;在说明部分中以left开头的行就是定义算符的结合性的行。left表示其后的算符是遵循左结合的；right表示右结合性，而nonas