<<编译原理>>
词法分析Lexical analysis或Scanning：根据代码文本区分单词类型 保留字(while if else ...)，数据类型(整型，字符，浮点..)，操作符(+ - * | & ...) ，若有对应单词类型继续语法分析，否 则 词法异常
语法分析Syntax analysis或Parsin：根据给定的语法，在词法分析器给的结果分析是否符合语法规则。LL分析法和LR分析法。符合继续语义分析，否则 语法异常
四个动作 shift移入 reduce规约 accept(增广文法的接收$) error 报错
编译原理lecture 4d :hezhenfeng
语义分析semantic analysis：在语法分析的基础上，给出对应语法语句的语义规则，根据语义规则得到中间代码(eg.三地址码(类似汇编))
编译原理。自底向上分析，最优推导
----------------------------------------------------
LR(0)没FOLLOW集，
SLR(1)归约时FOLLOW集所在的全部可归约
LR(1)在产生式的归约中（即增加搜索符【新扩产生式时加入原来的终结符或结束标志】
--用于follow集无法解决的冲突--只遇到搜索符的时候才可以归约）
LALR(1)在LR(1)下增加同心合并(合并时只考虑产生式相同，搜索符合并)
----------------------------------------------------
SLR(1)有FOLLOW集计算(归约时考虑，没有搜索符)
1增广文法(的归约acept)
2消除左递归
3产生是规则 A->B 排序编号
3计算FOLLOW集，部分依赖于FIRST集。
4构造预测分析表
状态|项目集|后继符号(将移入/规约产生式)|后继状态(S移入/规约)
语义规则 A->B A.NODE=B.NODE
代码段
移入/规约reduce
==========================================
Lex 词法分析.l Yacc语法分析.y
lex 文件.l ：正则表达式 保留字 数据类型 操作符
Yacc 文件.y ：上下文无关的文法-产生式。LALR(1)
extern char *yytext; /* Correct for Flex */
extern char yytext[]; /* Correct for traditional Lex */
===========================================
http://dinosaur.compilertools.net/lex/
Lex词法分析器（先翻译的Yacc，Lex部分翻译）
把用户的表达式和actions（即源资源source）转换为目标语言。生成程序叫做yylex。
%%
[ \t]+$
开始部分用%%分界，这个规则部分包含一个正则表达式，用于匹配一个或多个的空格和退格键。
=========
2.Lex Source
Lex的原文件基本格式
{definitions}
%%
{rules}
%%
{user subroutines}
===========
3.Lex Regular Expressions 词法分析器的正则表达式
正则表的是的操作符有
" \ [ ] ^ - ? . * + | ( ) $ / { } % < >
双引号 |反斜杠|左方括号|右方括号|上尖号|减号|问号|句点|星号|加号|竖杠|左括号|右括号|美元符号|斜杠|左花括号|右花括号|百分号|左尖号|右尖号
匹配这些符号的串要进行转义。采用双引号进行转义".
比如xyz“++”匹配的是串 xyz++
操作符也可以用反斜杠进行转义即 xyz\+\+
==========
动作 REJECT 意为"跳到下一个可选规则"
==========
规则可以缩写
D [0-9]
E [DEde][-+]?{D}+
%%
{D}+ printf("integer");
{D}+"."{D}*({E})? |
{D}*"."{D}+({E})? |
{D}+{E}
==========
12.Summary of Source Format 格式总结
{definitions}
%%
{rules}
%%
{user subroutines}
1--Definitions
4--开始条件，使用下列格式
%S name1 name2 ...
5--字符集表，在格式中
%T
number space character-string
...
%T
6--更改内部数组大小，使用格式为
%x nnn
一个十进制nnn表示数组大小，x的可选参数为
字母 参数
p 位置
n states
e 树节点
a 转换数
k 字符包类数目
o 输出数组大小
Lex中使用的正则表达式操作符和释译:
x the character "x"
"x" an "x", even if x is an operator.
\x an "x", even if x is an operator.
[xy] the character x or y.
[x-z] the characters x, y or z.
[^x] any character but x.
. any character but newline.
^x an x at the beginning of a line.
<y>x an x when Lex is in start condition y.
x$ an x at the end of a line.
x? an optional x.
x* 0,1,2, ... instances of x.
x+ 1,2,3, ... instances of x.
x|y an x or a y.
(x) an x.
x/y an x but only if followed by y.
{xx} the translation of xx from the
definitions section.
x{m,n} m through n occurrences of x
**********************************************************************
编译链接库-lfl
http://dinosaur.compilertools.net/flex/manpage.html
Flex（和lex有些部分不兼容，特有的比如%option 更多见
%s 和%x作为开始在definitions声明。
开始符用BEGIN动作
默认开始条件堆栈是使用动态增涨的，因此构建没有大小限制。如果内存疲乏，程序会执行aborts中止。
如果要使用条件堆栈。你的扫描要包含%option stack 指令
http://dinosaur.compilertools.net/flex/flex_17.html#SEC17
一些%options的特定指令设置了才可以获得
http://dinosaur.compilertools.net/flex/flex_20.html#SEC20）
`always-interactive' 指示flex生成一个和输入交互的扫描器。通常，扫描每个新
输入文件时调用isatty()，以试图确定扫描的输入原文件是交互的，因此应该每次读取一个字符。当这个option使用时，不会进行这个调用。
`main'
引导flex提供一个main()作为yylex()的简单调用。该option意味着noyywrap
`never-interactive'
flex生成一个不考虑交互的扫描器。[也不调用isatyy().]和always-相反。
`stack'
启动是要用开始条件stack
`stdinit'
没有设置时，初始yyin和yyout指向空文件指针而不是标准输入输出.
`yylineno'
引导flex生成的扫描器采用当前输入文件的行数作为全局变量那个yylineno。这个歌option意味着 %option lex-compat
`yywrap'
没有设置时(即%option noyywrap)，扫描器在文件结尾前不会调用yywrap()，除非已经没有文件要扫描(直到用户的yyin指向的新文件并在此调用yylex())
flex可以扫描你的actions决定使用REJECT或者yymore()特性。reject和yymore的options可以通过重载是否适用通过%option reject确认使用或%option noyymore取消设置。
====================
***********************************************************************
https://luv.asn.au/overheads/lex_yacc/yacc.html
YACC的语言规范
%{
/* C declarations and includes */
%}
/* Yacc token and type declarations */
%%
/* Yacc Specification
in the form of grammer rules like this:
*/
symbol : symbols tokens
{ $$ = my_c_code($1); }
;
%%
/* C language program (the rest) */
Options
最新options规则版本，这些items不是真正的menu项，只是设置一些options，例如标题title和列columns。这些被定义作为struct menu的成员。当我们解析这些options时，我们不能获得正确的struct menu。我们可以用一个全局变量存储当前的menu。但是当我们达到子菜单尾部时，恢复到正确的菜单就会棘手。
解析器根据我们的使用习惯传递值更简单。
我们使用menu项作为传输title和columns的options。而后将会好似用add_item的函数来处理这些特殊的项，并释放这些结构。
***********************************************************
YACC
http://dinosaur.compilertools.net/yacc/
目录
1.规范 产生式
2.动作 action 引用变量$ 全局变量位置和命名避免
3.词法分析 Token数257宏定义 Lex
4:解析器是如何工作的[编译原理预测分析表、GOTO表]
5:歧义和矛盾
6:优先级
7:错误处理
8:Yacc环境量
9:提示准备规范
10:高级主题 类型
11:致谢
YACC是用便携C编写的。接受的规范类是一个非常普遍的规则：LALR（1）语法，具有消除歧义的规则（上下无关文法）。
==================================
1基本规范--结构 开始符 结束符
Yacc每个规范文件由三部分组成，由两个百分号%%分隔。
（百分号%作为yacc规范的转义字符）
declarations
%%
(grammar)rules
%%
programs
声明declarations部分可以为空。更甚，如果programs部分省略，%%可以省略则
%%
rules
空格 、退格、换行被忽略,除此之外，不能出现在names和大量字符的保留字中。
注释/* */，出现在name的任何位置均合法。如C和PL/I一样。
rules有一个或多个语法规则组成，形如
A:BODY;
名称可以是任意长度的，可以由字母[a-zA-Z]点[.] 顿号[、]下划线[_]和非初始数字[0-9]组成。
大写字母和小写字母是不同的。语法规则体中使用的名称可以表示记号token或非终结符nonterminal symbols。
由字符构成的错排包含在单引号中。和C语言一样，斜杠\作为错排内的转义字符，左右的C的转义字符均被识别.因此
'\n' newline换行
'\r' return回车
'\'' single quote单引号 ``'''
'\\' backslash斜杠 ``\''
'\t' tab退格
'\b' backspace空格
'\f' form feed 走纸换页
'\xxx' ‘’xxx''八进制
由于技术原因。NUL('\0' 或0)在rules中不被使用。若有非终结符(左边A)相同，可以用竖杠|避免左边的重复改写。
此外，在竖杠左边rule结束的分号可以被丢弃。
A : B C D ;
A : E F ;
A : G ;
YACC中可给定为
A : B C D
| E F
| G
;
合并不是必要的，她只是让语法可读性更强、更容易更改。
非终结符和空格串匹配，可以显示方法
empty: ;
NAME代表记号token必须声明，简记为
%token name1 name2 . . .
decalretions声明部分在(3.5.6)
Name在声明部分没有的，代表着非终结符。
每一个非终结符必须有一个规则。即在rules左边出现。
所有的非终结符，叫开始符。解析器用来识别的开始象征。
因此，开始符代表在（grammar）ruler中占据最大且最普遍的。
开始符默认为ruler部分的第一条语法规则的左值。
在declaretion部分显示的声明开始符用%start作为关键字。
%start symbol
解析器的输入结束标志token成为endmark。达到这个token但是不包含它，
这个结束标志建立一个匹配开始符号的结构，解析函数在遇到结束标志时调用
函数返回；接收输入。如果结束标志出现在其他的上下文中，是一个错误。
提供词法分析器，并在适当的时候返回结束标志。详见3.结束符通常比较明显
的I/O状态或文件结束符EOF
=============================================================
2动作
每条语法规则后可能会有一个动作
执行每条规则的识别输入时，这个动作可能会返回一个值，
可以获得之前的动作的返回值。必要的话，词法分析器lexical analyzer可以返回tokens的值。
动作可以是任意的C语句。可以做输入输出和调用子程序，改变外部变量和变量。一个动作可以
是很多语句，包含在花括号中。
A: '(' B ')'
{ hello( 1, "abc" ); }
和
XXX : YYY ZZZ
{ printf("a message\n");
flag = 25; }
带有动作的rulers。
为了方便action和解析的沟通，action语句略有修改。
$作为Yacc的信号.
为了返回一个值，action通常设置伪变量$$为一些值。例如，action没有做任何事情只是返回值1
{$$=1;}
为了获得之前的action的值以及词法解析，动作可以使用伪变量$1 ,$2 ,...。涉及到的值根据组成由
规则的右边根据左到右。例如规则
A:B C D;
$2是C返回，$3是D返回。
更复杂的
expr: '('expr')';
这个规则的返回值通常为括号内的，表明
expr: '('expr')';{$$=$2;}
默认的，规则的值为第一个元素$1。因此形如
A:B;
不需要明确的动作。
在上面的样例中，所有的动作都是他们的最后的规则。
在一个ruler被完全解析获得控制是令人满意的。Yacc允许action在规则的中间和结尾，
规则假定返回一个值，通过右边的动作容易接近这种机制。
可以获得他左边的符号，因此
A : B
{ $$ = 1; }
C
{ x = $2; y = $3; }
;
设置x=1，y为C的返回值
行动不是终止规则实际上是由 Yacc通过制造一个新的非终结符号名称,和一个新的规则匹配这个名字到空字符串。
内部动作是通过识别这一附加规则触发的动作。YACC实际上把上面的例子当作是已经写的：
$ACT : /* empty */
{ $$ = 1; }
;
A : B $ACT C
{ x = $2; y = $3; }
;
在许多应用程序中,输出是没有直接的action; 相反,一个数据结构,如一个解析树,构造在内存中,在输出之前移入被应用。 解析树尤其容易构造,
例程来构建和维护想要的树结构 。 例如,假设有一个C函数节点,叫
node( L, n1, n2 )
创建一个节点标签L,后继节点n1和n2， 返回新创建的索引节点。 然后解析树可以 由提供如下action:
expr : expr '+' expr
{ $$ = node( '+', $1, $3 ); }
在这规范
用户可以定义其他变量来被action使用。 声明和定义可以出现在声明declaretions部分,包含在标记%{和%}之间。
这些声明和定义有全局作用域,所以他们被action的语句和词法分析器Lex识别。 例如,
%{ int variable = 0; %}
可以放置在声明declaretions部分,变量可以被所有的action访问。 Yacc解析器只使用Name以yy开始的; 用户应避免这样的名字。
在这些例子中,都是整数的值:讨论 其他类型的值将会在10节。
==========================================================
3:词法分析
用户必须提供一个词法分析器读取输入流和沟通tokens(带值，如果需要的话) 给解析器。 词法分析器是一个整数值函数 叫yylex。
函数返回一个整数,token的数目, 代表读取这种token。 如果有一个相关值token,它应该分配给外部变量yylval。
解析器和词法分析器必须同意这些token号码为了他们之间的通信。这些数字可能选择的Yacc,或由用户选定。在这两种情况下,C的
#define机制定义允许用于词法分析器返回这些数字象征意义(象征性地)。例如,假设标记名数字已经Yacc的规范文件中的
declaretinos部分中定义已经定义
词法分析程序的相关部分的样子
yylex(){
extern int yylval;
int c;
. . .
c = getchar();
. . .
switch( c ) {
. . .
case '0':
case '1':
. . .
case '9':
yylval = c-'0';
return( DIGIT );
. . .
}
. . .
目的是返回一个token数量的数字,和一个值 数字的数值。 提供的词法分析程序代码的在
规范文件的program部分,DIGIT将被定义为的token数，与token相关数字。
这种机制导致清晰、容易修改词汇 分析程序; 唯一的缺陷是需要避免使用任何token NAME
的语法或C的保留字或解析器的保留字; 例如,如果用户使用token name或许
会造词法分析器的变异困难。token名错误句柄预留给错误句柄， 不应想当然的使用(见第7节)。
正如上面提到的,token数可能选择的Yacc 或由用户。 在默认情况下,数目由 Yacc选择。
默认的字面量的token数是这个本地字符集的数值。 其他名称分配token数字从257开始。
分配token数量给一个token(包括文字), 第一次出现的token name名称或字面量在declaretions
部分可以立即紧随其后的是负的整数。 这个整数是的token或者字面的数量。名称和字面量没有保持默认的定义的机制。
所有的token的数不一样是很重要的。。
由于历史原因,endmarker一定token数0或负数的。 这个token数不能用户被重新定义的 ;
因此,所有的词法分析器应该准备返回0 或负数作为作为令token数达到输入尾。
一个非常有用的构造词法分析器工具 是迈克Lesk Lex程序。 [8]这些词法分析器被设计为何Yacc解析器紧密工作。
Lex规范中使用正则表达式代替语法规则grammar rules;
Yacc A:B{action};
Lex 正则{action}
Lex可以很容易地用于产生相当复杂词法分析,
但仍有一些 语言(如FORTRAN)不适应理论框架， 词法分析器必须手工制作的。
===============================================
4:解析器是如何工作的(可联系编译原理的预测分析表理解)
Yacc规范文件转化为一个C程序, 解析输入根据给定的规范。 从规范的解析算法是复杂的, 在这里不讨论(请参阅参考更多信息)。
然而,解析器本身是相对简单的, 和不是非常严格的理解它是如何工作的,会更易于理解错误处理和恢复。
解析器产生的Yacc堆栈由一个有限状态机。解析器也能够阅读和记忆的下一个输入token(称为超前token)。
当前状态总是一个堆栈的顶部。给出了有限状态机的状态小整数标签;最初,状态是0,堆栈只包含状态0,没有先行token被读取。
这种机制只有4中action 。移入shift,规约reduce、接受accept、和错误error。解析器的移动完成如下:
1。在其当前状态的基础上,解析器决定是否它 需要一个先行token来决定应该采取什么action;
如果它需要一个token,但没有,它会调用yylex 获得下一个token。
2。在当前状态,如果需要先行token,解析器决定它的下一个action,并携带。这可能会导致状态被推压入堆栈,
或被取出的堆栈,先行token被处理或放开。
解析器最常见的动作的是移入shift。每当采取移入时,总有一个先行token。例如,在状态56可能有一个动作：
IF shift 34
在状态56，先行token是IF，当前状态56压入堆栈。状态56压入堆栈，状态变为34（栈顶），先行token被清空。
reduce规约动作在阻止堆栈没有边界的增长 。reduce,当解析器看到语法规则rule的右边，规约动作是恰当的,
zuo右边部分被左边的部分代替，他需要查阅先行token来决定是否规约,但通常不需要; 事实上,默认action(由一个表示 “.”)
通常是一个规约action。
规约action与个人的语法规则rule相关。 语法规则给出小整数数字,导致一些混乱。 这个动作
. reduce 18
是指语法规则rule18,而行动
IF shift 34
涉及状态34。
假设规则被reduce规约的是 A:x y z;
归约action取决于左手的符号(当前情况下A),符号右边的符号数量(当前情况下3)。规约时，栈顶的三个状态出栈。
通常，出栈的状态的数目等于rule右边的符号数目。 实际上, 这些状态堆栈上识别为,x, y和z,没有其他任何目的。
这些状态出栈后，一个解析器执行之前的规则的状态被发现。使用这个发现的状态 ，
二这个状态在ruler的左边，执行移入A 。新状态A获得并压栈，解析继续。但执行左边的符号和普通的token的移入
有很大的不同，左边符号的移入action 叫做goto action。在移入时先行token被清除，并且不被goto影响。
任何情况下，该发现的状态获得一个入口即
A goto 20
使得状态20被压倒到堆栈,并成为了当前状态。
实际上,reduce归约行动“时光倒流” 解析,从堆栈中取出状态，ruler右手的是先被看到。 如果ruler的右手是空的，
按规律解析器会看到左边。 ,没有状态从堆栈的出栈：发现的状态为当前状态。
reduce归约动作对于用户应用动作和值也很重要。当一个规则reduce归约时, 代码提供的规则执行堆栈调整。
堆栈出来保持状态，另有堆栈保证词法分析的值和actions与之平行。当移入操作，外部变量yylval被复制到
值得堆栈中。在返回用户代码之后，规约时会携带回。当执行goto动作时，外部变量yyval被复制到值堆栈中。
为变量$1,$2等，会指向堆栈的值。
其他两个解析器操作在概念上更加简单。 接受的行动表明整个扫描过并它匹配的规范了。 这个动作只出现
在先行token已经是结束符，并且表明解析器工作已经完全成功。而error动作，表明根据当前规范LALR(1)解析器
无法继续工作。这个输入tokens已被读取，不能被任何其他的合法的后继符号输入。解析器报告一个错误，并尝试
恢复，而重新解析：错误恢复将在7部分(而不是检测侦查错误)
这是一个例子! 根据规范
%token DING DONG DELL
%%
rhyme : sound place
;
sound : DING DONG
;
place : DELL
;
当Yacc -v 选项调用,解析器根据人类可读的描述，产生一个输出文件y.output，。对应上面的语法y.output理解
(一些统计剥去结尾)【预测分析表】:
state 0
$accept : _rhyme $end
DING shift 3
. error
rhyme goto 1
sound goto 2
state 1
$accept : rhyme_$end
$end accept
. error
state 2
rhyme : sound_place
DELL shift 5
. error
place goto 4
state 3
sound : DING_DONG
DONG shift 6
. error
state 4
rhyme : sound place_ (1)
. reduce 1
state 5
place : DELL_ (3)
. reduce 3
state 6
sound : DING DONG_ (2)
. reduce 2
注意到,出来每个状态的actions，在每个状态里都有解析rule执行过程的描述。在每个rule中，下划线 _字符
用于表明什么被扫描，以及什么将到来。输入是
DING DONG DELL
执行过程根据解析步骤是有用的。
最初,当前状态是状态0。 解析器需要根据输入的顺序决定action。第一个token,DING,被读取,成为先行token。
状态0在DING行动是“移入 3”,所以状态3压到堆栈,和先行token清除。 状态3成为当前状态。 下一个记号, DONG,被读取,
成为先行token。 在状态3，先行DONG的动作是“移入6“,因此状态6被压入堆栈，先行被清空。状态堆栈现在包含0, 3和6，
没有可以读取的的先行token， 解析器由规则2可以归约。
sound : DING DONG
这个规则有在右边两个符号,所以状态6和3,从栈中弹出,发现状态0。查询状态0时GOTO表的sound位置,
sound goto 2
获得; 因此状态2被压入堆栈,成为当前状态。
在状态2下一个token,DELL，必须读取。 这个动作是“移入5”,所以状态5压倒堆栈,现在有0、2和5,并且先行token将被清除。
在状态2的place,唯一的动作归约规则3。有一个符号在右边,所以状态5弹出堆栈，显现状态2。在状态2的goto中,左边规则3是状态4。
现在,堆栈包含0、2和4。 在状态4中,唯一的动作就是规约规则1。有两个符号在右边,所以右边两个符号将被弹出,栈顶两个状态被弹出，
显现状态0。在状态0,goto的rhyme符号解析进入状态1。 在状态1,输入被读取，获得结束符,在y.output文件中由“$end”表示。
状态1的读取结束符时动作是接收,成功地结束了解析。
面对这种不和规矩的字符串如DING DONG DONG, DING DONG, DING DONG DELL DELL,等，读者被要求了解解析器是如何工作的。
花费几分钟了解这个例子和其他简单的例子，在面临更复杂的上下文问题时会有所收获。
=========================================
5:歧义和矛盾[二义性]
如果有一些输入字符串可以用两种或更多种不同的方式来构造（一种语法），那么一组语法规则是模棱两可的。例如,语法规则
expr : expr '-' expr
表示自然表达式是一个算术表达式，由两个表达式通过减号合起来。
遗憾的是，这种语法规则并不能完全指定（所有）复杂的输入被构造的方式。例如,如果输入
expr - expr - expr
规则允许这个输入结构
( expr - expr ) - expr
或者
expr - ( expr - expr )
(第一个叫左关联[最左推导],第二种右关联[最右推导]).
Yacc 在尝试构建解析器时会检测这种模糊性。当遇到下列给出的输入时
解析器考虑这种问题是有意义的。
expr - expr - expr
当洁希提读取到第二个给expr时，输入就已经读取了：
expr - expr
匹配了语法rule的右边，解析器能够应用这条规则进行输入归约。 应用以后，
输入归约为expr(即语法rule的左边)。解析器会读取剩下的输入部分:
- expr
并且再次归约，这样是采取左关联解析的效果。
或者，当解析器读取
expr - expr
它可以推迟的直接应用规则,并继续 读取输入,直到看到了
expr - expr - expr
它可以将规则应用到右边的三个符号, 规约他们到expr和留下
expr - expr
现在规则可以再次被规约; 这是采用有关联解析的效果。因此,读取
expr - expr
解析器可以做两个合法的事情,移入或归约, 他们之间无法决定，这叫做移入规约冲突。
也可能发生两个合法的规约，这叫做归约归约冲突。一定不会发生移入移入冲突。
当存在移入归约或归约规约冲突，Yacc仍然产生解析。无论哪里都只选择其中一个有效的。
在给定的情况下选择的描述的rule称为消除歧义规则。
Yacc默认调用两个消除歧义规则:
1。 在移位/归约冲突中,默认的移位。
2。 归约/归约冲突,默认通过早期的语法规则(在输入的序列)归约
规则1意味着无任何是的选择是归约推迟。
规则2给用户对解析器的行为的粗糙控制，但要尽可能地避免归约归约冲突。
由于输入或逻辑错误，可能出现冲突, 或者因为语法规则始终一致,
需要一个比Yacc构造更复杂的解析器。如果执行action必须在解析器确认识别rule之前，
使用rules的actions也会引起冲突。 在这种情况下,不恰当的二义性消除规则的应用, 将导致错误的语法分析器。
由于这个原因, Yacc总是报道通过规则1和规则2解决移入归约和归约归约冲突的数目。
一般来说,是可以通过二义性消除规则产生正确的解析器。也可以重写语法规则rule,以便读取有相同的输入而没有冲突。
出于这个原因,大多数以前的解析器生成器 一直认为冲突是致命的错误。我们的经验建议重写有点不自然,产生慢的解析器;
因此,Yacc将生成解析器即使在存在冲突。
作为一个二义性消除规则的例子,考虑一个编程语言涉及的一个片段从“if - then - else” 构造:
stat : IF '(' cond ')' stat
| IF '(' cond ')' stat ELSE stat
;
在这些规则中,IF和ELSE是tokens，cond描述条件(逻辑)是一个非终结符，expressions和stat是描述声明的非终结符。
第一个规则将被称为simple-if,第二个if - else法则。
这两个规则形成一个二义性的结构,因为输入的形式
IF ( C1 ) IF ( C2 ) S1 ELSE S2
可以按照这些规则构造两个方法:
IF ( C1 ) {
IF ( C2 ) S1
}
ELSE S2
或
IF ( C1 ) {
IF ( C2 ) S1
ELSE S2
}
第二个解释是大多数编程语言的一种构造。 每个ELSE和最近的IF相关联。在这个歌例子里面，
这个情况解析器应该读取为
IF ( C1 ) IF ( C2 ) S1
并且读取到ELSE时，应该根据simple-if立即归约为
IF ( C1 ) stat
然后读剩下的输入,
ELSE S2
并规约为
IF ( C1 ) stat ELSE S2
根据if - else规则。 上述即为输入的第一分组。
另一方面,ELSE会被移入，并读取状态S2， 然后右边的部分
IF ( C1 ) IF ( C2 ) S1 ELSE S2
可以根据if - else规则归约为
IF ( C1 ) stat
这时可以根据simple-if规则归约。 上述便是输入第二分组。即，所期望的。
一旦解析器再次可以做两个有效的事情——就会有移位归约冲突。 此时消除二义性规则1就会告诉解释器进行移入，
即所期望的分组。
这种移位/归约冲突发生只有当有一个特定的输入符号,ELSE，否则,并且特性的输入已经被读取,如
IF ( C1 ) IF ( C2 ) S1
一般来说,可能会有许多冲突,每一个与一个输入符号和之前读取输入集合相关。 之前读取的输入根据解析器的状态来表征。
对Yacc的冲突消息最好的理解是通过输出的测试详细文件(- v)选项。 例如,输出对应于上述冲突状态可能是:
23: shift/reduce conflict (shift 45, reduce 18) on ELSE
state 23
stat : IF ( cond ) stat_ (18) stat : IF ( cond ) stat_ELSE stat
ELSE shift 45 . reduce 18
第一行描述了冲突,给出了状态和输入符号。 紧跟普通状态的描述,当前状态语法规则rule语态,
以及解析器actions。下划线_标记语法规则rule被读取的部分 。 因此,在这个例子中,在状态23时解析器已读取可以理解为
IF ( cond ) stat
此时展示的两个语法规则是活跃的。解析器可以做两种可能的事情。 如果输入符号ELSE, 有可能移入状态45。 状态45作为描述的一部分,
stat : IF ( cond ) stat ELSE_stat
因为这个状态下ELSE会移入。 在状态23岁的可供选择的action,由描述为". ",是 如果输入符号没有明确的提及上面的action;
在这种情况下,如果输入符号不是ELSE, 解析器可以根据语法规则18进行归约:
stat : IF '(' cond ')' stat
再次,注意“移入”命令后面的数字涉及的是状态，而“规约”后面的数字是语法规则数。
在文件y.output中，rules被归约之后的规则数会被打印。大多数状态中,尽可能多的状态是归约action,这是默认的命令。
用户在遇到不可预料的移入归约冲突时会尽可能地查看详细的输出文件决定默认的actions是否合适。
在非常困难的情况下,用户可能需要知道比这里更多语法解析器的相关行为和构造。
这时,理论参考文献之一[2、3、4]可能咨询;本地的GURU服务业是适合的。
========================================
6:优先级
在相同的情况下，上面给出的解决冲突是不够的。这里有一个算是表达式的解析。算术表达式最常用的是根据操作符的优先级，以及左结合或右结合信息。 事实证明,二义性语法与带有歧义的规则的解析器相较于消除二义性的解析器更快和且更容易编写 。 基于这个概念写出的语法规则形式
expr : expr OP expr
和
expr : UNARY expr
所有二元和一元运算符。 这将创建一个二义性的语法,存在很多解析冲突。 作为二义性规则,用户对左右的操作符以及二元操作符的结合性指定优先级,或强约束。 实现期待的优先级和结合性这些信息对于Yacc 解决器依照这些解决规则冲突, 和构造一个解析器是很重要的 。
优先级和结合性依附于在声明declarations部分的tokens。这些通过一系列的YACC的关键字开始：
%left, %right, or %nonassoc 后面紧跟着一系列的tokens.左右的tokens在同一行。
假定有同样的优先级和结合性，优先级和捆绑随着行数的增加而增强。 因此,
%left '+' '-'
%left '*' '/'
描述了四种运算的优先级和结合性 操作符。 +-左结合，并且比也是左结合的* \较低优先级。 关键字%right用于描述右结合, 而关键字% nonassoc用于描述操作，例如在Fortran的.LT的操作 ,可能不会互相关联; 因此,
A .LT. B .LT. C
在Fortran是非法的,和这样的操作在YACC将被以关键字% nonassoc 描述 。 作为一个例子declaration的行为 ，描述为
%right '='
%left '+' '-'
%left '*' '/'
%%
expr : expr '=' expr
| expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| NAME
;
如果输入为
a = b = c*d - e - f*g
则等价:
a = ( b = ( ((c*d)-e) - (f*g) ) )
在一般情况下, 给定一个优先级中，一元操作符必须使用这种机制,。 有时一个一元运算符和一个元操作符有相同的符号表征,但是不同的优先级。 一个例子; 一元操作符和二元操作符负号-；一元操作符-和乘法有相同的等级而二元操作符负号较低。 关键字% prec改变特定的语法规则优先级别 。 % prec在 的语法规则(grammar)rules的体部分之后，action和分号之前直接出现,并被一个token name或字面量紧随其后。 它导致语法规则优先级成为下列的token name 或字面量。 例如, 一元负号和乘法规则相同的优先级类似
%left '+' '-'
%left '*' '/'
%%
expr : expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| '-' expr %prec '*'
| NAME
;
一个token不一定需要声明%left, %right, and %nonassoc，但可能，也会被%token声明
优先级和结合性被YACC用于解决解析冲突；是消除二义性规则的提升。正式的，规则工作如下：
1 tokens和字面量具有优先级和结合性被记录
2 优先级和结合性和每条语法规则关联时，是在规则rule体body的最后的token或字面量。如果使用了%prec构造，将覆盖默认值。一些语法规则rule可以没有使用优先级和结合性。
3 当出现归约归约或移入归约冲突时，输入的符号或者没有优先级和结合性的语法规则，消除二义性规则将会被使用，并且会报告冲突。
4 如果有移位/归约冲突,和语 规则和输入字符有与之相关优先级和结合性 ,那么冲突解决的action(移入或规约)采用优先级更高的那方。 如果优先级是相同的,那么使用结合性左结合意味着归约reduce, 儿右结合意味着移入shift，nonassociating暗示错误error。
YACC采用优先级的解决移入归约和归约归约冲突的报告不计数。意味着优先级规范中的问题可能会掩盖输入语法中的错误。这是一个很好的 节约用的判例,并在使用它们
在基本的'COOKBOOK'中使用简洁的优先级，除非已经很有经验。 y.output用于判断解析器实际的操作是非常有用的。
======================================
7:错误处理
错误处理是一个非常困难的领域,语义中存在许多问题。 当发现一个错误, 例子中,可能需要重新解析树存储, 删除或修改符号表实体，代表性的设置开关避免避免深层输出。
发生错误时停止所有的执行是不可接受的。更有用的继续扫描输入 找到更多的语法错误。 这就导致一个错误后的 解析器“重启”问题。 一个一般类的算法包括从输入字符串丢弃一个数量的tokens,并试图解析器,以便调整解析器以便可以继续输入。
允许用户控制这个过程,Yacc提供 一个简单的,相当一般功能。 token name “error”是用于错误处理预留。 可以 在语法规则使用这个name; 实际上,它表明错误的地方是可预期,而且可以恢复。 解析器弹出它的堆栈,直到它进入token的“error”是合法的状态。 然后它表现为当前的先行token为“error”，执行遇到的action。先行token会重置这个token造成的错误。 如果没有 特殊的错误规则指定,当检测到一个错误处理中断 。
为了防止嵌套的错误消息,解析器, 检测到一个错误,之后依然在错误的状态,直到三个 token已经成功地读取和移入。 如果解析器已经发现错误状态,没有给出消息，输入token将被默默删除。
作为一个例子,一个规则的形式
stat : error
实际上,意味着语法错误解析器会 试图跳过被视为错误的语句。 更准确地说,今后的解析器将扫描,寻找三个token可能合法地语句,并开始处理第一个; 如果语句的开端不够充分详细,这可能造成一个中间语句错误的开始,结束后报告实际没有错误第二个错误。
这些特殊错误规则可能会使用action。 这些action可能会尝试重新启动表,回收表空间等。
上面是非常一般错误规则,但控制困难。 有些简单规则如
stat : error ';'
在这里,当有一个错误,解析器试图略过语句,会通过跳过下一个';'。 在错误之后且在 “;”之前,的所有的token不能被移入而是被丢弃。 当“;”被读取，这条规则被规约，与之相关的与之相关的任何“清理”被执行。
另一种形式的错误规则出现在交互式应用程序中, 它允许在错误之后重新加入令人满意的一行, 一个可能的错误规则
input : error '\n' { printf( "Reenter last line: " ); } input
{ $$ = $4; }
这种方法有一个潜在的困难; 必须确认解析器在允许正确的同步错误之后能正确执行三个token的输入(error ‘\n’ input)。 在前两个tokens(error ‘\n’ )中，如果重入行包含一个error，解析器删除厌弃的token,
不给任何消息; 这是显然不能接受的。 由于这个原因,有一个机制 可以强制使解析器相信错误已经完全恢复。 该语句是
yyerrok ;
在一个动作重置解析器到正常模式。 最后一个例子，更好的形式
input : error '\n'
{ yyerrok;
printf( "Reenter last line: " ); }
input
{ $$ = $4; }
;
正如上面提到的,在input token中发现error之后立即读取token，有时是不适当。例如，错误恢复action可能需要承担找到恢复输入的正确位置。此时，之前的先行token必须被清除。语句
yyclearin ;
在一个行动会有这种效果。 例如,假设操作错误后调用一些复杂的用户提供的再同步例程,试图在下一个有效语句开始时预先输入 在这例程之后 ，下一个被yylex返回的token将是一个合法语句的第一个token。旧的非法的touken会被丢弃，错误状态被重置，规则rule可以如：
stat : error
{ resynch();
yyerrok ;
yyclearin ; }
;
无可否认,这些机制公认粗糙的，但是对于解析器从许多错误恢复时简单的、相当有效的; 此外,对用户在program部分根据需求处理错误的行为 。
===================================
8:Yacc环境量
当用户输入一个规范Yacc,输出 一个文件的C程序,称为y.tab.c(基于大多数系统 本地文件系统约定,名称可能根据安装 不同而不同)。 Yacc的产生函数是 yyparse; 这是一个返回值为一个整型的函数。 当它被调用时,它会轮询的反复调用yylex,即用户提供词法分析器 (见第3节)来获取输入输入tokens。 最终, 要么检测到一个错误,在这种情况下(可能没有错误恢复 )yyparse返回值1,要么词法分析器返回结束符tendmarker token并且解析器接受，这时,yyparse返回值0。
用户必须提供一定数量的环境量，以便这个解析器嫩能够获得一个工作程序 例如, 作为一个C程序,必须定义一个主程序, 用于yyparse的调用。 此外,一个例程用于发现语法错误时调用 yyerror输出一条消息。
这两个例程必须在被用户提供的一种或另一种形式中。 为了简单使用Yacc初始化，提供一个库用于main和yyerror的默认版本。这个库名称是依赖于系统的；多数系统可以通过参数 -ly 加载获得 。简略的默认程序的源代码如下所示:
main(){
return( yyparse() );
}
和
# include <stdio.h>
yyerror(s) char *s; {
fprintf( stderr, "%s\n", s );
}
yyerror的参数是一个字符串包含一个错误消息, 通常字符串“语法错误”。 一般的应用程序 想要做得更好。 通常,当检测到语法错误时，程序应该跟踪输入的行号并打印消息出来 。在 错误被侦测到时， external外部的整数变量yychar包含先行token数; 这在提供更好的诊断中式一些感兴趣的。 从用户提供的主程序(读参数等)Yacc库library在小项目或大项目最初阶段中是非常有用的 。
external外部整数变量yydebug正常时设置为0。 如果它被设置为非零值,解析器将输出其行为actions一个冗长描述,包括讨论的被读取的输入符号,以及解析器的行动是什么。 根据操作环境,它可能会设置被调试系统使用的变量。
============================================
9:提示准备规范
本节包含各种各样的暗示准备效率, 更易变更,清理规范。 这个是特色部分是独立的。
输入风格
提供带有大量的actions的规则但要仍旧保持可读性的规范文件时非常难的。
下列额风格提示来自Brian Kernighan
a使用大写字母表征token name，所有的小写字母作为非终结names。这个规则使得有出错时可以
通过下划线知道归咎方。
b把语法规则和行为放在不同行。 这使得改变一个而不会对另一个造成无意识的改变。
c把规则相同的左边的合起来。左边只出现一次，用竖线|作为规则分隔 。
d分号;仅出现在给定最后一个规则之后，且分号单独一行。这使得新的规则的增加更简单。
e规则体rule bodies定位由两个退格键，而动作体action bodies 由三个退格键。
附录A中的例子依据这种风格写的, 也是本文的例子(空间允许)。 用户必须自己注意这些体裁上的问题。更核心的是，这样使得缠在一起的action代码中的规则更明显。
左递归
Yacc解析器使用的算法激励叫做‘左递归’语法规则:规则的形式
name : name rest_of_rule ;
这些规则在编写序列和列表的规范时经常出现：
list : item
| list ',' item
;
和
seq : item
| seq item
;
在这些情况下,仅有第一个item将根据第一个规则归约 ，第二个item或者所有后继item根据第二条规则归约。
右递归规则如
seq : item
| item seq
;
解析器将会很大,items从右开始读取，直到归约。 更严重的是, 如果有很长串被读取，解析器内部堆栈将溢出。 因此,这就是用户应该使用左递归的原因。
值得考虑的是一个序列带有0个元素是否有意义，如果有,考虑写一个带有空规则的序列规范:
seq : /* empty */
| seq item
;
开头,在读取第一个item时第一个规则总是会归约一次,后序每次读取到一个item第二个规则归约一次。 允许空序列常常会导致增加通用性。 然而,如果Yacc还没有读取足量时被要求读取空序列而做裁决可能产生冲突！
词汇联系
一些词汇的决定取决于上下文。 例如,
词法分析器可能想要正常地删除空格,但不是在引用的字符串里面。 或名字可能会进入declarations中的一个符号表,但不是在表达式。
处理这种情况的一种方法是创建一个全局性的标志用于此法分析器的测试，并在actions的设置。 例如,假设一个程序由0或多个声明组成,紧随其后的是0或多个语句。 考虑:
%{
int dflag;
%}
... other declarations ...
%%
prog : decls stats
;
decls : /* empty */
{ dflag = 1; }
| decls declaration
;
stats : /* empty */
{ dflag = 0; }
| stats statement
;
... other rules ...
除了在第一个语句中的第一个token，当标志dflag是0是读取statements，当1时读取declarations。 这个token可以知道declaration部分被解析器读取的开始和结束。 在许多情况下,这一个token不影响词法扫描。
这种“后门”的方法可以被精心制作成有害的。 然而,它展现了一些难以理解的，如果不是必要的，不这样做（if not impossible, to do otherwise）。
保留字
一些编程语言允许用户使用这样的词 “if”,通常保留,如标签或变量名, 在程序语言中提供这样的names是合法的。Yacc的框架是相当难的。告诉词法分析器’if这个关键字实际是个变量‘是困难的。用户可以 是用最后的最后一个小节描述的分段机制制造一个透传， 但它很困难。
使这些更简单的多种方式的正在研讨中。 在那之前,最好的是保留关键字; 也就是说, 禁止用作变量名。 这个涉及到很强的文本因素
=================================
10:高级主题
本节讨论的Yacc的一些 高级特性。
模拟误差和接受行为
通过使用宏YYACCEPT和YYERROR一个动作，解析可以模拟操作错误和接受 。 YYACCEPT原因 yyparse返回值0; YYERROR使解析器 像如果当前输入符号语法错误; yyerror叫做,错误恢复。 这些机制 可用于模拟和多个endmarkers或解析器吗 上下文敏感的语法检查。
在封闭的规则获取值。
一个动作涉及的返回值可以通过action引用当前规则的左边。机制与普通的actions是一样的 ,一个美元符号$,后跟一个数字,但在 这种情况下,数字可能是0或负的。 考虑
sent : adj noun verb adj noun
{ look at the sentence . . . }
;
adj : THE { $$ = THE; }
| YOUNG { $$ = YOUNG; }
. . .
;
noun : DOG
{ $$ = DOG; }
| CRONE
{ if( $0 == YOUNG ){
printf( "what?\n" );
}
$$ = CRONE;
}
;
. . .
在CRONE这个词后的行动,是检查之前的移入的token不是YOUNG.。 显然,唯一的可能是大量了解noun符号之前的输入。 以及明显的非结构化味道。 然而,有时这种机制，将会节省大量的麻烦,尤其是当几个组合用于被一个regular的结构排除。
支持任意值类型
默认情况下,action和词法分析器Lex的返回的值是整数。 Yacc还可以支持其他的类型值,包括结构。 此外,Yacc跟踪类型,并插入适当的union成员的名字，以便解析器结果将进行严格的类型检查。 Yacc值 堆栈(见第4节)被声明在一个有各种期望出现的类型值得union中。 用户声明了union,并且union的成员名联系各个token和非终结符的值。当值是引用中的$$或$n结构 ，Yacc会自动地插入适当的union名，避免了不必要的转换。 另外,类型检查命令如Lint[5]将会更沉默。
有三个机制用于提供类型。
第一,定义union的方式; 这必须来自用户的其他程序,词法分析器必须的了解union成员的名字。
第二,一个union和tokens和非终结符关联。
第三,当Yacc不能简单的决定值的类型时使用描述机制（引用关联）。
【Yacc语法的声明部分】
在declarations部分的用户包含include声明:
%union {
body of union ...
}
这个声明Yacc值栈,外部变量 yylval 和yyval的类型,等于这个union类型。 如果Yacc是 使用- d选项调用,union会复制到 y.tab. h文件。 另外,union可以被声明在头文件，并且一个typedef使用变量
【yacc的使用C语言声明部分】
YYSTYPE表示这个union。 因此,头文件可以为:
typedef union {
body of union ...
} YYSTYPE;
头文件必须包含在声明部分, 使用C语言声明部分的分块符% {和% }间。
一旦定义YYSTYPE,union成员名称必须是 与各种终结符和非终结符相关。结构
< name >
是用来表示一个union成员的名字。 如果后面跟着关键字%token,%left,%right%nonassoc, 这个union的名字是与token相关列出。 因此，如
%left <optype> '+' '-'
将会导致的任何引用返回值这两个token 贴上的union成员的名字optype。 另一个关键字, %type,关联union的成员名和非终结符。 因此,这个会是
%type <nodetype> expr stat
仍有一些情况下,这些机制不够的。 如果一个规则rule中有一个action，这个action返回的值没有先验类型。 同样,上下文中剩余的引用值(比如$0 -见前面的小节) Yacc不能用简单的方法知道类型。 这种情况下,可以在使用<type>在引用中插入union的成员名应用类型，并在紧跟$之后，使用样例
rule : aaa { $<intval>$ = 3; } bbb
{ fun( $<intval>2, $<other>0 ); }
;
这种情况很少出现，不推荐这个语法。
附录中C给出了一个示例规范的。 在示例中不触发本章节,除非他们被使用: %type的使用将打开这些机制。 当它们被使用时,会进行一个相当严格的检查。 例如, $n或$$引用使用没有定义类型的诊断。 如果不触发,Yacc值栈是保持int的。
--------翻译结束
11:致谢---机器翻译
Yacc很大程度上要归功于一个最刺激用户的集合, 那些驱使我超出我的倾向,经常超越 我的能力,在他们没完没了的寻找“一个特性”。 他们的刺激性不愿意学习如何照我的方法做事 通常导致我的做事方式; 大多数时候, 他们是对的。 b·w·克尼汉,p . j . Plauger s I。 费尔德曼,c . Imagna m . e . Lesk和斯奈德将认识一些 当前版本的Yacc的他们的想法。 c·b·哈雷的贡献 错误恢复算法。 b d·m·里奇。W。 克尼汉,和m·o·哈里斯帮助翻译这个文件 英语。 艾尔·霍也为将值得特别信贷 山穆罕默德和其他好处。
1。 b·w·克尼汉和d·m·里奇,C编程 语言,新世纪,恩格尔伍德悬崖,新泽西,1978。
2。 a . v .阿霍和s c·约翰逊,LR解析、Comp。调查, 6卷,没有。 2,页99 - 124,99年6月。
3所示。 a . v .阿霍s c·约翰逊和j . d . Ullman”确定的 模棱两可的语法解析,“通讯Assoc。。 Comp。马赫。 18卷,没有。 8日,第452 - 441页,441年8月。
4所示。 a . v .霍和j . d . Ullman编译器设计的原则, addison - wesley、阅读质量。 ,1977年。
5。 美国C·约翰逊,线头,C程序检查器,“Comp。科学。 技术。 众议员65号,1978。]。 更新版本TM 78-1273-3
6。 s . c·约翰逊”便携式编译器:理论与实践》 Proc,5日美国电脑。 在编程语言的原则, 第104 - 97页,97年1月。
7所示。 b·w·克尼汉和l . l .樱桃”排版系统 数学,“通讯Assoc。。 广告样稿,马赫。 18卷,第157 - 151页, 新泽西州贝尔实验室,默里希尔1975年3月 。]。
8。 m . e . Lesk“Lex -一个词法分析器生成器”Comp。科学。 贝尔实验室技术。众议员39号,新泽西州默里希尔 1975年10月)。
附录A:一个简单的例子
这个例子给出了完整的Yacc规范 小型台式计算器; 台式计算器有26个寄存器, 标记为“一个”通过“z”,并接受算术表达式 由运算符+、-、*、/、%(mod操作符),&(逐位 和)|(按位或)和任务。 如果一个表达式 顶层是一个赋值,这个值是不打印; 否则 它是。 在C语言中,一个整数始于0(零) 八进制; 否则,它被认为是小数。
作为一个Yacc规范的例子,台式计算器 一个合理的工作展示的判例和歧义 使用,证明简单的错误恢复。 主要的 简单化是词法分析阶段 比对于大多数应用程序简单,输出 立即,逐行。 注意十进制、八进制的方式 读取整数的语法规则; 这个工作可能是 更好的通过词法分析器。
%{
# include <stdio.h>
# include <ctype.h>
int regs[26];
int base;
%}
%start list
%token DIGIT LETTER
%left '|'
%left '&'
%left '+' '-'
%left '*' '/' '%'
%left UMINUS /* supplies precedence for unary minus */
%% /* beginning of rules section */
list : /* empty */
| list stat '\n'
| list error '\n'
{ yyerrok; }
;
stat : expr
{ printf( "%d\n", $1 ); }
| LETTER '=' expr
{ regs[$1] = $3; }
;
expr : '(' expr ')'
{ $$ = $2; }
| expr '+' expr
{ $$ = $1 + $3; }
| expr '-' expr
{ $$ = $1 - $3; }
| expr '*' expr
{ $$ = $1 * $3; }
| expr '/' expr
{ $$ = $1 / $3; }
| expr '%' expr
{ $$ = $1 % $3; }
| expr '&' expr
{ $$ = $1 & $3; }
| expr '|' expr
{ $$ = $1 | $3; }
| '-' expr %prec UMINUS
{ $$ = - $2; }
| LETTER
{ $$ = regs[$1]; }
| number
;
number : DIGIT
{ $$ = $1; base = ($1==0) ? 8 : 10; }
| number DIGIT
{ $$ = base * $1 + $2; }
;
%% /* start of programs */
yylex() { /* lexical analysis routine */
/* returns LETTER for a lower case letter, yylval = 0 through 25 */
/* return DIGIT for a digit, yylval = 0 through 9 */
/* all other characters are returned immediately */
int c;
while( (c=getchar()) == ' ' ) {/* skip blanks */ }
/* c is now nonblank */
if( islower( c ) ) {
yylval = c - 'a';
return ( LETTER );
}
if( isdigit( c ) ) {
yylval = c - '0';
return( DIGIT );
}
return( c );
}
附录B:Yacc输入语法
这个附录Yacc输入的描述语法, Yacc规范。 不考虑上下文依赖性等。 具有讽刺意味的是,Yacc输入规范语言 最自然指定为LR(1)文法; 棘手的部分 当一个标识符在一个规则,之后 一个动作。 如果该标识符后跟一个冒号,它是 开始下一条规则; 否则它的延续 当前的规则,这恰好嵌入了一个动作 它。 实现,看到后向前看的词法分析器 一个标识符,并决定是否下一个记号(跳过 空格、换行、注释等)是一个冒号。 如果是这样,它返回 令牌C_IDENTIFIER。 否则,它将返回标识符。 文字(引用字符串)也作为标识符返回,但是 从不C_IDENTIFIERs的一部分。
/* grammar for the input to Yacc */
/* basic entities */
%token IDENTIFIER /* includes identifiers and literals */
%token C_IDENTIFIER /* identifier (but not literal) followed by colon */
%token NUMBER /* [0-9]+ */
/* reserved words: %type => TYPE, %left => LEFT, etc. */
%token LEFT RIGHT NONASSOC TOKEN PREC TYPE START UNION
%token MARK /* the %% mark */
%token LCURL /* the %{ mark */
%token RCURL /* the %} mark */
/* ascii character literals stand for themselves */
%start spec
%%
spec : defs MARK rules tail
;
tail : MARK { In this action, eat up the rest of the file }
| /* empty: the second MARK is optional */
;
defs : /* empty */
| defs def
;
def : START IDENTIFIER
| UNION { Copy union definition to output }
| LCURL { Copy C code to output file } RCURL
| ndefs rword tag nlist
;
rword : TOKEN
| LEFT
| RIGHT
| NONASSOC
| TYPE
;
tag : /* empty: union tag is optional */
| '<' IDENTIFIER '>'
;
nlist : nmno
| nlist nmno
| nlist ',' nmno
;
nmno : IDENTIFIER /* NOTE: literal illegal with %type */
| IDENTIFIER NUMBER /* NOTE: illegal with %type */
;
/* rules section */
rules : C_IDENTIFIER rbody prec
| rules rule
;
rule : C_IDENTIFIER rbody prec
| '|' rbody prec
;
rbody : /* empty */
| rbody IDENTIFIER
| rbody act
;
act : '{' { Copy action, translate $$, etc. } '}'
;
prec : /* empty */
| PREC IDENTIFIER
| PREC IDENTIFIER act
| prec ';'
;
附录C:一个先进的例子
这个附录给出了一个使用一些语法 10节讨论的高级特性。 桌上的计算器 附录A中的示例修改提供台式计算器 浮点区间算术。 计算器 理解浮点常量,算术运算 +、-、*、/、一元-,=(赋值),26日浮动 点变量”、“一个”通过“z”。 此外,它也能理解 间隔,写
( x , y )
其中x是小于或等于y。有26个区间值 变量的一个“通过”“Z”,也可以使用。 使用 是类似于附录A; 作业没有返回值, 和打印,同时打印(浮动或表达 间隔)的价值。
这个例子中探索一些有趣的特性 Yacc和c .间隔由结构组成 左和右端点值,存储为的两倍。 这 结构类型名称,间隔,通过使用类型定义。 的 Yacc值栈也可以包含浮点标量、和 整数(用于索引数组变量 值)。 注意,整个战略强烈依赖 能够分配结构和工会在c。事实上,很多 调用函数返回结构的操作。
同样值得注意的是使用YYERROR处理错误 条件:包含0部门由一个间隔,间隔 提出了错误的订单。 事实上,错误恢复 Yacc机制用于扔掉剩下的冒犯 null
除了栈上的值类型的混合 语法还演示了一个有趣的使用语法 跟踪的类型(如标量或间隔)的中间体 表达式。 注意,可以自动晋升为一个标量 一个区间,如果上下文要求一个区间值。 这 导致大量的语法运行时的冲突 Yacc:18移位/归约和26减少/减少。 这个问题 可以看到通过查看两个输入行:
2.5 + ( 3.5 - 4. )
和
2.5 + ( 3.5 , 4. )
请注意,2.5是被用在一个区间值表达式 在第二个例子中,但这一事实,直到不知道 “,”阅读; 此时,2.5完成,解析器不能 回去改变主意。 更一般的,它可能是
需要向前看任意数量的令牌来决定 是否一个标量转换为一个区间。 这个问题是 逃避有两个规则为每个二进制区间值算子: 当左操作数是一个标量,和一个在左边 操作数是一个区间。 在第二种情况下,正确的操作数 必须是一个区间,所以自动转换将被应用。 尽管逃税,仍有许多情况 转换可以适用与否,导致上面的冲突。 他们是通过清单产生的规则来解决 标量首先在规范文件; 通过这种方式,冲突 将解决的方向保持标量值吗 表达式的标量值,直到他们被迫成为间隔。
这种方式处理多种类型是非常有益的,但是 不是很一般。 如果有多种表达式类型, 而不是两个,所需的规则数量会增加 明显,冲突更加显著。 因此, 虽然这个例子很有启发性,它是更好地实践 正常编程语言环境类型 信息的价值,而不是语法的一部分。
最后,对词法分析一个词。 唯一的 不寻常的特性是浮点常量的治疗。 C库例程atof用来做实际的转换 从字符串到双精度值。 如果词汇 分析仪检测到一个错误,它会返回一个令牌 是非法的在语法、引发的语法错误 解析器,和那里的错误恢复。
%{
# include <stdio.h>
# include <ctype.h>
typedef struct interval {
double lo, hi;
} INTERVAL;
INTERVAL vmul(), vdiv();
double atof();
double dreg[ 26 ];
INTERVAL vreg[ 26 ];
%}
%start lines
%union {
int ival;
double dval;
INTERVAL vval;
}
%token <ival> DREG VREG /* indices into dreg, vreg arrays */
%token <dval> CONST /* floating point constant */
%type <dval> dexp /* expression */
%type <vval> vexp /* interval expression */
/* precedence information about the operators */
%left '+' '-'
%left '*' '/'
%left UMINUS /* precedence for unary minus */
%%
lines : /* empty */
| lines line
;
line : dexp '\n'
{ printf( "%15.8f\n", $1 ); }
| vexp '\n'
{ printf( "(%15.8f , %15.8f )\n", $1.lo, $1.hi ); }
| DREG '=' dexp '\n'
{ dreg[$1] = $3; }
| VREG '=' vexp '\n'
{ vreg[$1] = $3; }
| error '\n'
{ yyerrok; }
;
dexp : CONST
| DREG
{ $$ = dreg[$1]; }
| dexp '+' dexp
{ $$ = $1 + $3; }
| dexp '-' dexp
{ $$ = $1 - $3; }
| dexp '*' dexp
{ $$ = $1 * $3; }
| dexp '/' dexp
{ $$ = $1 / $3; }
| '-' dexp %prec UMINUS
{ $$ = - $2; }
| '(' dexp ')'
{ $$ = $2; }
;
vexp : dexp
{ $$.hi = $$.lo = $1; }
| '(' dexp ',' dexp ')'
{
$$.lo = $2;
$$.hi = $4;
if( $$.lo > $$.hi ){
printf( "interval out of order\n" );
YYERROR;
}
}
| VREG
{ $$ = vreg[$1]; }
| vexp '+' vexp
{ $$.hi = $1.hi + $3.hi;
$$.lo = $1.lo + $3.lo; }
| dexp '+' vexp
{ $$.hi = $1 + $3.hi;
$$.lo = $1 + $3.lo; }
| vexp '-' vexp
{ $$.hi = $1.hi - $3.lo;
$$.lo = $1.lo - $3.hi; }
| dexp '-' vexp
{ $$.hi = $1 - $3.lo;
$$.lo = $1 - $3.hi; }
| vexp '*' vexp
{ $$ = vmul( $1.lo, $1.hi, $3 ); }
| dexp '*' vexp
{ $$ = vmul( $1, $1, $3 ); }
| vexp '/' vexp
{ if( dcheck( $3 ) ) YYERROR;
$$ = vdiv( $1.lo, $1.hi, $3 ); }
| dexp '/' vexp
{ if( dcheck( $3 ) ) YYERROR;
$$ = vdiv( $1, $1, $3 ); }
| '-' vexp %prec UMINUS
{ $$.hi = -$2.lo; $$.lo = -$2.hi; }
| '(' vexp ')'
{ $$ = $2; }
;
%%
# define BSZ 50 /* buffer size for floating point numbers */
/* lexical analysis */
yylex(){
register c;
while( (c=getchar()) == ' ' ){ /* skip over blanks */ }
if( isupper( c ) ){
yylval.ival = c - 'A';
return( VREG );
}
if( islower( c ) ){
yylval.ival = c - 'a';
return( DREG );
}
if( isdigit( c ) || c=='.' ){
/* gobble up digits, points, exponents */
char buf[BSZ+1], *cp = buf;
int dot = 0, exp = 0;
for( ; (cp-buf)<BSZ ; ++cp,c=getchar() ){
*cp = c;
if( isdigit( c ) ) continue;
if( c == '.' ){
if( dot++ || exp ) return( '.' ); /* will cause syntax error */
continue;
}
if( c == 'e' ){
if( exp++ ) return( 'e' ); /* will cause syntax error */
continue;
}
/* end of number */
break;
}
*cp = '\0';
if( (cp-buf) >= BSZ ) printf( "constant too long: truncated\n" );
else ungetc( c, stdin ); /* push back last char read */
yylval.dval = atof( buf );
return( CONST );
}
return( c );
}
INTERVAL hilo( a, b, c, d ) double a, b, c, d; {
/* returns the smallest interval containing a, b, c, and d */
/* used by *, / routines */
INTERVAL v;
if( a>b ) { v.hi = a; v.lo = b; }
else { v.hi = b; v.lo = a; }
if( c>d ) {
if( c>v.hi ) v.hi = c;
if( d<v.lo ) v.lo = d;
}
else {
if( d>v.hi ) v.hi = d;
if( c<v.lo ) v.lo = c;
}
return( v );
}
INTERVAL vmul( a, b, v ) double a, b; INTERVAL v; {
return( hilo( a*v.hi, a*v.lo, b*v.hi, b*v.lo ) );
}
dcheck( v ) INTERVAL v; {
if( v.hi >= 0. && v.lo <= 0. ){
printf( "divisor interval contains 0.\n" );
return( 1 );
}
return( 0 );
}
INTERVAL vdiv( a, b, v ) double a, b; INTERVAL v; {
return( hilo( a/v.hi, a/v.lo, b/v.hi, b/v.lo ) );
}
附录D:旧功能支持但不鼓励
这个附录提到同义词和功能支持 由于历史的连续性,但由于种种原因, 不鼓励。
1。 文字也可以使用双引号“”。
2。 文字可能不止一个字符长。 如果所有的 字符是字母、数字或_,类型的数量 定义了文字,就像文字没有 引号。 否则,很难找到 这类文字值。
多字的使用文字可能会误导 那些不熟悉Yacc,因为它表明,Yacc 做一份工作必须做的词汇 分析仪。
3所示。 大多数地方%是合法的,可以使用反斜杠“\”。 特别是,\ \ % %是一样的,\离开了一样 %,等等。
4所示。 有许多其他同义词:
%< is the same as %left
%> is the same as %right
%binary and %2 are the same as %nonassoc
%0 and %term are the same as %token
%= is the same as %prec
5。 行动也可能形式
={ . . . }
花括号可以删除,如果是一个单一的动作 C语句。
6。 C代码% {和% }之间曾经是允许的 规则的部分,以及在声明部分
![Flex实现代码分离mxml/as[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)