flex资料.doc

LEX介绍 LEX（Lexical Analyzer Generator）即词法分析器生成工具是1972年贝尔实验室的M.E.Lesk和E.Schmidt在UNIX操作系统上首次开发的。GNU同时推出了和LEX完全兼容的FLEX（Fast Lexical Analyzer Genrator）。下面用到的例子都是基于flex的。LEX工作原理： LEX通过对源文件的扫描，经过宏替换将规则部分的正则表达式转换成与之等价的DFA，并产生DFA的状态转换矩阵（稀疏矩阵）；利用该矩阵和源文件的C代码产生一个名为int yylex()的词法分析函数，将yylex()函数拷贝到输出文件lex.yy.c中。函数yylex()以在缺省条件下的标准输入（stdin）作为词法分析的输入文件。 输入文件（扩展名为.l）LEX输出文件 lex.yy.cLex源文件格式为：定义部分%规则部分%用户附加的C语言代码 例1：int num_chars=0,num_lines=0; /*定义两个全局变量，一个及字符数，一个记行数.注意：该语句不能顶行*/%n +num_chars+; +num_lines;. +num_chars;%int main() yylex(); printf(“%d,%d”, num_chars,num_lines);int yywrap()/*文件结束处理函数，当yylex()读到文件结束标记EOF时，调用该函数时会，用户必须提供该函数，否则会提示编译出错 */ return 1;/返回1表示文件扫描结束，不必再扫描别的文件lex 的输入文件分成三个段，段间用% 来分隔。由于必须存在一个规则段，第一个% 总是要求存在模式 LEX的模式是机器可读的正则表达式。表意字符 匹配字符. 除换行外的所有字符n 换行* 0 次或无限次重复前面的表达式+ 1 次或更多次重复前面的表达式? 0 次或1 次出现前面的表达式 行的开始$ 行的结尾a|b a 或者 b(ab)+ 1 次或玩多次重复 aba+b 字符串a+b 本身（ C 中的特殊字符仍然有效） 字符类ab 除a,b 外的任意字符ab a, , b 中的一个az 从a 到z 中的任意字符a-z a,-,z 中的一个a-z a, z 中的一个 匹配文件结束标记表 1 ：简单模式匹配在方括号（） 中，通常的操作失去了本来含意。方括号中只保留两个操作，连字号（“ ”）和抑扬号（“ ” ） 。当把连字号用于两个字符中间时，表示字符的范围。当把抑扬号用在开始位置时，表示对后面的表达式取反。如果两个范式匹配相同的字符串，就会使用匹配长度最长的范式。如果两者匹配的长度相同，就会选用第一个列出的范式。定义部分定义部分由c语言的代码、模式的宏定义和条件模式的开始条件说明等部分组成。其中C代码由顶行的“%”和“%”引入，LEX扫描源文件时该部分将首先被拷贝到输出文件之中（去掉）“%”和“%”，在此可以定义必要的全局变量和包含模式处理时用到的外部函数的头文件，如：%#includeint num_chars=0,num_lines=0;%此外，在定义中出现的任何非顶行文字也将直接拷贝到输出文件中，可以利用这一规定了来定义C的全局变量。还有定义部分开可以加上C语言的注释/*/,该部分也将直接拷贝到输出文件中。规则部分规则部分是LEX源文件的核心，它包括一组模式和生成分析器识别相应模式进行处理的C语言动作。格式如下： C语言代码 模式1 动作1 模式2 动作2 模式3 动作3 。 模式n 动作n同定义部分一样，C语言代码也不能顶行书写，或则是用顶行的“%”和“%”所引用。这里可以定义输出的词法分析函数yylex()的局部变量。该部分一定出现在第一个模式之前。而每一个模式必须顶行书写，而模式对应的C语句必须和模式在一行。它们之间用白字符分割，若对应模式的C语句有多行，则可以用“”将这些C语句括起来。用户代码部分 LEX对用户代码部分不做任何处理，仅仅将该部分拷贝到输出文件lex.yy.c的尾部。在此部分可定义对模式进行处理的C语言函数、主函数和yylex()要调用的yywrap()等。若用户在其它用户模块中提供了这些函数的定义，此部分可省略，则后两部分的%可省略了。 yylex()函数的匹配原则 yylex()的函数原型为 int yylex(void)。它被调用后，首先它检查全局文件指针变量yyin是否有定义，如果是则设置将要扫描的文件为用户所定义的文件，否则设为标准输入文件stdin。接着利用yylex（）所定义的DFA分析被扫描的文件，如果有唯一的模式与被扫描的字符串匹配，则执行该模式的动作；如果有多个模式可以匹配相同的输入串，则yylex()选择匹配最长输入串的模式；若多个模式串匹配相等的输入串，则选择最前的模式进行匹配。例如：%program printf(“%sn”,yytext);/*模式1*/procedure printf(“%sn”,yytext);/*模式2*/a-za-z,0-9* printf(“%sn”,yytext);/*模式3*/当输入串为“programming”时，模式1（匹配“program”）和模式3（“programming”）都匹配，但会选择匹配串长的模式3。当输入串为“program”时，因为模式1和模式3匹配的串长度相等故会选择模式1.试验：在Linux操作系统（ubantu7.10版本）下装有flex和GCC编译器后：1. 把例1的内容保存到lextest.l中；2. 运行 flex lextest.l; 这时生成了一个lex.yy.c文件；3. 编译这个lex.yy.c ,用 gcc lex.yy.c o lexyy4. lexyytest.txt ，test.txt是一个待测试文件；结果：会显示出来test.txt中的行数和字符数。FLEX什么是FLEX？它是一个自动化工具，可以按照定义好的规则自动生成一个C函数yylex()，也成为扫描器（Scanner）。这个C函数把文本串作为输入，按照定义好的规则分析文本串中的字符，找到符合规则的一些字符序列后，就执行在规则中定义好的动作（Action）。例如在规则中可以这样定义：如果遇到一个换行字符n，那么就把行计数器的值加一。Flex文件就是一个文本文件，内容包括定义好的一系列词法规则。文件的命名习惯上以小写字母l(L)来作为文件后缀。如果为了清晰，也可以用.flx或者.flex作为文件的后缀名。Flex文件完成后，就执行下列命令：$ flex example.flex这个命令执行后将生成一个C文件，默认文件名为lex.yy.c。这个C文件主要内容就是函数yylex()的定义。如果要直接将这个文件编译成为一个可执行程序，还有一些要注意的地方。如果在Flex文件中没有提供main()函数的定义，那么这个C文件中不会有main()函数。此时单独编译这个C文件的时候，一定要加上-lfl的连接库参数；若提供了main()函数，就不必要提供这个连接库参数了。连接库libfl提供了一个缺省的main函数。缺省的main()函数中只是简单地调用yyflex()函数，而自己提供的main()函数则可以根据需要加入许多其他的处理代码。Flex文件词法规范定义文件给出了单词构成规则。词法文件在习惯上用字母l(即L的小写)来作为后缀。Flex文件由三个部分组成。或者说三个段。三个段之间用两个%分隔。定义段(definitions)%规则段(rules)%用户代码段(user code)定义段(definitions section)定义段包含着一些简单名字的定义(name definitions)，旨在简化扫描器的规范。定义名字的方法如下:name definition名字可以由字母或下划线开头，后跟零个或多个字母、数字、下划线、或短横线。名字的定义则从其后的第一个非空白字符(non-white-space)开始直到行尾。下面是一个例子，定义了一个名字DIGIT，其定义就是指一个数字，如下所示：DIGIT 0-9当在后面引用这个名字时，用一对花括号()括住该名字即可。它会被展开成一对圆括号括住的该名字的定义,即:name 展开成 (definition)例如：DIGIT+.DIGIT*就等价于：(0-9)+.(0-9)*定义段中还可以加入启动条件(start conditions)的声明。顾名思义，启动条件就如同C语言中的条件编译一样，根据指定的启动条件去激活一条规则，并用这条规则去匹配读入的字符。关于启动条件，后面还有更详细的介绍。规则段(rules section)规则由模式(pattern)和动作(action)两个部分组成。模式就是一个正则表达式，FLEX加入了一些自己的扩展。而动作一般就是一些C语句。模式指出了一个单词是如何构成的，当分析出一个符合该规则的单词时，就执行相应的动作。模式一定要位于一行的开头处，不能有缩进。而动作的开头一定要与模式在同一行。当动作是用一对花括号括起来时，可以将左花括号放在与规则相同的行，而其余部分则可以从下一行开始。用户代码段(user code)所有用户代码都被原样拷贝到文件lex.yy.c中。在这里可以定义一些辅助函数或代码，供扫描器yylex()调用，或者调用扫描器（一般来说就是main()了）。这一部分是可有可无的。如果没有的话，Flex文件中第二个%是可以省略的。在定义段或者规则段中，任何一行有缩进的文本或者包含在一对%和%之间的文本，都被原样拷贝到最后生成的C代码文件中（当然%和%会被移走）。在书写时%和%都必须在一行的开始处，不能缩进。在规则段中，第一条规则之前的任何未缩进的文本或者在%和%之间的文本，可以用来为扫描器声明一些本地变量和代码。一旦进入扫描器的代码，这些代码就会被执行。规则段内其他的缩进的文本或者%和%之间的文本还是被原样拷贝输出，但是他们的含义是尚未有明确定义，很可能引起编译时（compile-time）错误（这一特性是为了与POSIX兼容而提供的）。在定义段中，没有缩进的注释也会被原样拷贝到最后生成的C代码文件中，例如以/*开始的一行注释，直到遇到*/，这中间的文本会被原样拷贝输出。模式及其分类模式采用正则表达式来书写。正则表达式大致可以分为如下几类（从上到下，优先级依次递减）：（1）单字符匹配* x 匹配字符x。* . 匹配任意一个字符（字节），除了换行符。* xyz 匹配单个字符，这个字符是方括号中给出的字符类（character class）中的一个。* abj-oZ 匹配单个字符，这个字符是方括号中给出的字符类中的一个。与上一方式的区别是指定字符类时用到了一个范围表示法：j-o，这表示按照26个英文字母的顺序，从字母j开始一直到字母o共6个字母。这里减号（-）表示范围。如果减号本身也要作为一个匹配字符时，最好用转义字符（）去除其特殊含义。由于花括号（）在模式中用来引用名字，以及作为模式定义之后的动作（Action）定义块的首尾界定符，因此如果要在字符类中匹配花括号，必须用转义字符（）去除其特殊含义。下面这个例子定义了一个所有可打印字符的字符类：:alnum:blank:t+-*/&!_?$()%|.;:,#=* A-Z 匹配单个字符，这个字符必须是方括号中给定字符类以外的字符。在方括号内开始处的特殊符号（）表示否定。当字符不在字符类的开始处时，并不具有特殊含义，而是一个普通字符。* A-Zn 匹配单个字符，这个字符不可以是方括号中给出的字符类中的字符。与上一方式的不同在于，这里多了一个换行符，也就是说所匹配的字符不能是26个大写字母，也不能是换行符。根据上面的描述，在表达字符分类时，除了直接用字符以及字符范围来表达外，还有一种叫做字符类表达式的，也有同样的作用，常见的一些表达式如下：:alnum: :alpha: :blank: :cntrl: :digit: :graph:lower: :print: :punct: :space: :upper: :xdigit:每一个表达式都指示了一个字符分类，而且其名称与标准C函数isXXXX的名字对应。例如，:alnum:就指示了那些经由函数isalnum()检查后返回true的字符，也就是任何的字母或者数字。注意，有些系统上没有给出C函数isblank()的定义，所以flex自己定义了:blank:为一个空格或者一个tab。下面所举的几个例子，都是等价的：:alnum:alpha:digit:alpha:0-9a-zA-Z0-9应该注意字符类表达式的写法。一个字符类表达式是由一对:和:包住的，作为一个整体，在书写时不可与外层的混淆。（2）重复模式的匹配* r* r是一个正则表达式，特殊字符*表示0个或多个。因此这个模式表示匹配0个或多个r。* r+ r是一个正则表达式，特殊字符+表示1个或多个。因此这个模式表示匹配1个或多个r。* r? r是一个正则表达式，特殊字符?表示0个或1个。因此这个模式表示匹配0个或1个r。（从另一个角度看，就是说模式r是可选的）* r2,5 r是一个正则表达式，2,5表示2个到5个。因此这个模式表示匹配2个到5个r。也就是说可以匹配rr，rrr，rrrr，rrrrr四种重复的模式。* r2, r是一个正则表达式，2,省略了第二个数字，表示至少2个，不设上限。因此这个模式表示匹配2个及以上个r。也就是说至少可以匹配rr，还可以匹配rrr，rrrr等无限多种重复的模式。* r4 r是一个正则表达式，4只有一个数字，表示4个。因此这个模式确切地匹配4个r，即rrrr。（3）名字替换* name 这里name就是在前面的定义段给出的名字。这个模式将用这个名字的定义来匹配。（4）平凡（plain）文本串的匹配* “xyzfoo” 这个模式用来确切地匹配文本串：xyzfoo。注意最外层的单引号所包含的是整个模式表达式，也就是说，当希望匹配字串xyzfoo时，在书写规则时该字串必须用双引号括住。（5）特殊单字符的匹配* x 当x是一个a，b，f，n，r，t或v时，它就解释为ANSI-C中的x。否则就仍然作为一个普通字符x（一般用于诸如*字符的转义字符）。* 0 匹配一个NUL字符（ASCII码值为0）。* 123 匹配一个字符，其值用八进制表示为123。* x2a 匹配一个字符，其值用十六进制表示为2a。（6）组合模式的匹配* (r) 匹配规则表达式r，圆括号可以提高其优先级。* rs 匹配规则表达式r，其后紧跟着表达式s。这称为联接(concatenation)。* r|s 或者匹配规则表达式r，或者匹配表达式s。* r/s 匹配模式r，但是要求其后紧跟着模式s。当需要判断本次匹配是否为“最长匹配（longest match）时，模式s匹配的文本也会被包括进来，但完成判断后开始执行对应的动作（action）之前，这些与模式s相配的文本会被返还给输入。所以动作（action）只能看到模式r匹配到的文本。这种模式类型叫做尾部上下文（trailing context）。（有些r/s组合是flex不能识别的；请参看后面deficiencies/bugs一节中的dangerous trailing context的内容。）* r 匹配模式r，但是这个模式只出现在一行的开始处。也就是说，刚开始扫描时遇到的，或者说在刚扫描完一个换行字符后紧接着遇到的。* r$ 匹配模式r，但是这个模式只在一行的尾部。也就是说，该模式就出现在换行之前。这个模式等价于r/n。注意，flex中的换行（newline）的概念，就是C编译器中所使用的n，flex也采用同样的符号和解释。在DOS系统中，可能必须由你自己滤除输入中的r，或者明确地在模式中写成r/rn来代替r$。（在unix系统中换行是用一个字节 n 表示的，而DOS/Windows则采用两个字节 rn来表示换行。）（7）有启动条件（Start Condition）的模式匹配* r 匹配模式r，但需要启动条件s（后面后关于启动条件的讨论）。模式r是类似的，匹配模式r，只要有三个启动条件s1，s2，s3中的任一个即可。（启动条件简单来说，类似于C语言中的条件编译，满足了某个条件才启动这个模式参与匹配，否则不会启动该模式参与匹配。）* r 匹配模式r，在任何启动条件下都参与匹配，即使是排斥性的条件。上述还需要从实践中体会其含义（8）文件尾匹配* 匹配文件尾，即遇到了文件尾部。一般说来，都应该在模式中加入文件尾模式。这样可以有机会在文件扫描完成时增加一些额外的处理。* 在有启动条件s1或者s2的情况下，匹配文件尾部。一些常见规则的编写（待续）（1）双引号字符串。(SAFECHAR|RESTCHAR|_)*这里需要注意的地方是中间的重复模式的写法：(r)*。r可以是一个组合模式。中间的两个名称SAFECHAR和RESTCHAR是在定义段给出的两个字符类。此处应在实用中不断添加=创建一个简单的扫描器下列例子来自于Flex的手册。并在Windows+Cygwin+bison+flex+gcc的环境下编译运行。(1) 编辑Flex语法文件。/* name: example.flex */int num_lines = 0, num_chars = 0;%n +num_lines; +num_chars;. +num_chars;%int main()yylex();printf(# of lines = %d, # of chars = %dn, num_lines, num_chars);return 0;(2) 生成扫描器的C文件。$ flex example.flexThe output is lex.yy.c(3) 编译生成的C文件。编译时失败，出现了如下的问题：# gcc -g -Wall -lfl -o scan lex.yy.clex.yy.c:959: warning: yyunput defined but not used/cygdrive/c/DOCUME1/ADMINI1.78B/LOCALS1/Temp/ccHwCWNb.o: In function main:/cygdrive/c/home/sandbox/flex_exam_1/example.l:9: multiple definition of _main/usr/lib/gcc/i686-pc-cygwin/3.4.4/./././libfl.a(libmain.o):(.text+0x0): first defined here/cygdrive/c/DOCUME1/ADMINI1.78B/LOCALS1/Temp/ccHwCWNb.o: In function yylex:/cygdrive/c/home/sandbox/flex_exam_1/lex.yy.c:692: undefined reference to _yywrap/cygdrive/c/DOCUME1/ADMINI1.78B/LOCALS1/Temp/ccHwCWNb.o: In function input:/cygdrive/c/home/sandbox/flex_exam_1/lex.yy.c:1041: undefined reference to _yywrapcollect2: ld returned 1 exit status上述消息指出两个问题：（1）函数yywrap没有定义。（2）自定义函数main与连接库fl中的定义冲突了。第一个问题的解决办法是在第一段（定义段）中加上一个选项指令：%option noyywrap第二个问题的解决办法就是用gcc编译时不连接fl库，如下所示：# flex example.flex# lsexample.flex lex.yy.c# gcc -g -Wall -o scan lex.yy.clex.yy.c:977: warning: yyunput defined but not used# lsexample.flex lex.yy.c scan.exe# ./scan.exe789234345# of lines = 2, # of chars = 11修改过的代码如下：%option noyywrap 规约到DLDL = 读入下一个字符DL . = 规约到？但是这次的归约尝试失败了，因为没有任何符号的定义可以产生这种形式的字符串。也就是说，这种形式不能规约到任何符号。所以接着我们读入下一个字符1。这次可以将数字1归约到D符号。接着再读入一个字符4。4可以归约到D，继续归约到DL。这两次的读入和规约形成了D Dl这个序列，而这个序列可以归约到DL。DL . = 读入下一个字符1DL . 1 = 1归约到DDL . D = 读入下一个字符4DL . D 4 = 4归约到DDL . D D = 4继续归约到DLDL . D DL = D DL 归约到DL察看文法我们可以很快地注意到，FN能产生DL . Dl这种形式的序列，所以可以做一个归约。然后注意到FN可以从S符号产生，所以可以归约到S，然后停止，整个分析结束。DL . DL = 归约到FNFN = 规约到SS = 分析结束可能你已经注意到，我们经常可以选择是否现在就做归约，还是等到读入更多的符号后再作不同的归约。移进-归约分析算法有很多不同的变种，按照复杂度和能力递增的顺序是：LR(0)， SLR， LALR和LR(1)。LR(1)通常需要一个巨大的分析表，在实践上不具有实用性，因此LALR是最常使用的算法。SLR和LR(0)对于大部分的程序语言来说还不够强大。Bison分析器的算法1 Bison适合上下文无关文法（Context-free grammar），并采用LALR(1)算法Donnelly 06的文法。当bison读入一个终结符（token），它会将该终结符及其语意值一起压入堆栈。这个堆栈叫做分析器堆栈（parser stack）。把一个token压入堆栈通常叫做移进（shifting）。例如，假设一个中缀计算器已经读入1 + 5 * ，下一个准备读入的是3，那么这个栈里就有四个元素，每个元素都是移进的一个终结符。但堆栈并不是每读入一个终结符就分配一个栈元素给它。当已经移进的后n个终结符和组（groupings）与一个文法规则相匹配时，它们会被根据那个规则结合起来。这叫做归约（reduction）。栈中的那些终结符和组会被单个的组（grouping）替换。那个组的符号就是那个规则的结果。执行该规则的相应的动作（Action）也是归约处理的一部分，这个动作会计算这个组的语意值。例如，如果中缀计算器的分析器堆栈包含：1 + 5 * 3，并且下一个输入字符是换行符，那么上述后3个元素可以按照下面规则归约到15：expr: expr * expr;于是堆栈中就只包含下面三个元素了：1 + 15。此刻，另一个规约也可以执行，其结果是一个单值16。然后这个新行终结符就可以被移进了。分析器通过移进和归约尝试着缩减整个输入到单个的组。这个组的符号就是文法中的起始符号（start-symbol）。终结符预读Bison分析器并不总是在后n个终结符与组匹配某一规则时立即就进行归约。这种策略对于大部分语言来说并不合适。相反，当可以进行归约时，分析器有时会“预读”（looks ahead）下一个终结符来决定做什么。当一个终结符被读进来后，并不会立即移进堆栈，而是首先作为一个预读终结符（look-ahead token）。此后，分析器开始对栈上的终结符和组执行一个或多个归约，而预读终结符仍然放在一边。当没有归约可做时，这个预读终结符才会被移进堆栈。这并不表示所有可能的归约都已经做了，这要取决于预读终结符的类型，一些规则可能选择推迟它们的使用。下面研究一个需要做预读的案例。这里的三条规则定义了一个表达式，可以包含二元的加法运算符和一元的后缀阶乘运算符(!)，并且允许用括号进行分组。expr: term + expr| term;term: ( expr )| term !| NUMBER;假定终结符1 + 2已经读入并移进堆栈，那么接下来应该做什么呢？如果接下来的终结符是)，那么前三个终结符必须归约成一个expr。这是唯一的合法情况，因为移进)将会产生一个序列term )，而没有任何规则允许出现这种情况。不做归约移进)，堆栈上的元素序列是1 + 2 )，2可以归约成NUMBER，进而归约成term，与其后的 )形成term )的序列，检查所有规则发现没有任何规则定义了这种序列。如果下一个终结符是!记住此刻它还是预读终结符，那么该终结符必须立即移进堆栈以便2 !可以归约成一个term。如果相反地分析器在移进这个阶乘符号之前进行归约，那么1 + 2就会归约成expr。这将导致不可能移进!终结符，因为这样的话将会产生一个expr !序列。同样没有任何规则定义了这种序列。预读终结符存储在变量yychar中。它的语意值和位置，如果有的话，存储在变量yylval和yylloc中。移进-归约冲突假定我们正在分析一个语言，其中有if-then和if-then-else语句，对应的规则如下：if_stmt: IF expr THEN stmt| IF expr THEN stmt ELSE stmt;这里我们假设IF，THEN和ELSE是特别的关键字终结符。当ELSE终结符读入后作为一个预读终结符时，堆栈中的内容（假设输入是合法的）正好可以归约到第一条规则上。但是把它移进堆栈也是合理的，因为那样根据第二条规则就会导致最后的归约。在这种情况下，移进或者归约都是合法的，称为移进-归约冲突（shift-reduce conflict）。Bison的设计是，用移进来解决冲突，除非有操作符优先级声明的指令。为了解释如此选择的理由，让我们与其它可选办法进行一个比较。既然分析器更倾向移进ELSE，那么其结果是把else子句连接到最内层的if语句，从而使得下面两种输入是等价的：if x then if y then win (); else lose;if x then do; if y then win (); else lose; end;如果分析器选择归约而不是移进，那么其结果将是把else子句连接到最外层的if语句，从而导致下面两个输入是等价的：if x then if y then win (); else lose;if x then do; if y then win (); end; else lose;冲突的存在是因为文法有二义性：简单的嵌套的if语句的任一种解析都是合理的。已有的惯例是这种二义性的解决是通过把else子句连接到最内层的if语句而获得的；Bison是选择移进而不是归约来实现的。（一种更清晰的做法是写出无二义性的文法，但对于这种情况来说是非常困难的。）这种特殊的二义性首次出现在Algol 60的规范中，被称作dangling else ambiguity。对于可预见的合法的移进-归约冲突，为避免bison发出的警告，可以使用%expect n声明。那么只要移进-规约冲突的数量为n，就不会有警告产生。操作符优先级可能出现移进-归约冲突的其它地方还有算术表达式。此时移进就不总是更好的解决办法了。Bison通过声明操作符的优先级来指定何时移进何时归约。何时需要优先级考虑下面的二义文法片断（其二义性体现在1 2 * 3可以用两种不同的方式进行分析）：expr: expr - expr| expr * expr| expr expr| ( expr ).;假定分析器已经看到了终结符1，-和2；那么应该对它们归约到减法运算规则吗？这取决于下一个终结符。当然，若下一个终结符是)，就必须归约；此时移进是非法的，因为没有任何规则可以对序列- 2 )进行归约，也没有以这个序列开始的什么东西。但是如果下一个终结符是*或者，那么就需要做一个选择：移进或者归约，都可以让分析得以完成，但是却有不同的结果。为了决定Bison应该怎么做，必须考虑这两个结果。若下一个终结符即操作符op被移进，那么必然是op首先做归约，然后才有机会让前面的减法操作符做归约。其结果就是（有效的）1 (2 op 3)。另一方面，若在移进op之前先对减法做归约，那结果就是(1 2) op 3。很显然，这里移进或者规约的选择取决于减法操作符-与下一个操作符op之间的优先级：若op是乘法操作符*，那么就选择移进；若是关系运算符则应该选择规约。那么诸如1 2 5这样的输入又如何呢？是应该作为(1 2) 5 还是应该作为1 (2 5) ？对于大多数的操作符，我们倾向于前一种形式，称作左关联（left association）。后一种形式称作右关联（right association），对于赋值操作符来说是比较理想的。当堆栈中已经有1 2 且预读终结符是-，此时分析器选择移进还是归约与选择左关联还是右关联是一回事：移进将会进行右关联。指定操作符优先级Bison允许通过声明%left和%right来指定操作符优先级。每个这样的声明都包含一列终结符，这些终结符都是操作符，它们的优先级和关联性都被声明了。%left声明让所有这些操作符左关联，而%right声明让它们右关联。第三种方案是%noassoc，它声明了这是一个语法错误，表明“在一行中”找到了两个同样的操作符。不同操作符的优先级由它们的声明次序来决定。先声明的优先级低，后声明的优先级高。如果有同等优先级的呢？应该是按照其关联性来决定了是移进还是规约。优先级例子在本节给出的例子中，我们希望有如下的