lex&&yacc技术文章

Lex & Yacc 学习笔记（4）- Yacc语法结

2018-08-30  本文已影响170人  hemny

一、背景

一个LR分析器有3个部分组成：

本文讨论yacc语法的格式并描述可用的各种特征和选项

二、yacc语法结构

yacc语法包括三部分：定义段、规则段和用户子例程段

...定义段...

%%

...规则段...

%%

...用户子例程段...

各部分由以两个百分号开头的行分开，尽管某一个部分可以为空，但是前两部分是必须的，第三部分和前面的百分号可以省略。

符号

yacc 语法由符号组成，即语法的“词”。符号是一串不以数字开头的字母、数字、句点和下划线。符号error专用于错误恢复，另外，yacc对任何符号都不会附加“先验”的意义。

由词法分析程序产生的符号叫做终结符号或者标记。定义在规则左侧的叫做非终结符号或者非终结。标记也可能是字面上引用的字符，通常遵循约定：标记大写，非终结符号小写。

定义段

定义段包括文字块，逐字拷贝到生成的C文件开头部分的C代码，通常包括声明和#include行。可能有%union %start %token %type %left %right 和 %nonassoc声明。

也可以包含普通的C语言风格的注释，所有这些都是可选的，在简单的语法分析程序中，定义段可能完全是空的。

如在定义部分定义标志：

%token INTEGER

当运行yacc后，会产生头文件，里面包含该标志的预定义，如：

#ifndef YYSTYPE 
#define YYSTYPE int 
#endif 
#define INTEGER 258 
extern YYSTYPE yylval;

lex使用该头文件中的标志定义。Yacc调用lex的yylex()来获得标志（token），与标志对应的值由lex放在变量yylval中。yylval的类型由YYSTYPE决定，YYSTYPE缺省类型是int。如：

[0-9]+ { 
yylval = atoi(yytext); 
return INTEGER; 
}

标志0-255被保留作为字符值，一般产生的token标志从258开始。如：

[-+] return *yytext; /* return operator */

返回加号或减号。注意要把减号放在前面，避免被认作是范围符号。
对于操作符，可以定义%left和%right：%left表示左相关（left-associative），%right表示右相关（right-associative）。可以定义多组%left或%right，在后面定义的组有更高的优先级。如：

%left ‘+’ ‘-‘
%left ‘*’ ‘/’

上面定义的乘法和除法比加法和减法有更高的优先级。
改变YYSTYPE的类型。如这样定义TTSTYPE：

%union
{ 
     int iValue; /* integer value */ 
     char sIndex; /* symbol table index */ 
     nodeType *nPtr; /* node pointer */ 
};

则生成的头文件中的内容是：

typedef union
{ 
     int iValue;      /* integer value */ 
     char sIndex;    /* symbol table index */ 
     nodeType *nPtr; /* node pointer */ 
} YYSTYPE; 
extern YYSTYPE yylval;

可以把标志（token）绑定到YYSTYPE的某个域。如：

%token <iValue> INTEGER 
%type <nPtr> expr

把expr绑定到nPtr，把INTEGER绑定到iValue。yacc处理时会做转换。如：

expr: INTEGER { $$ = con($1); }

转换结果为：

yylval.nPtr = con(yyvsp[0].iValue);

其中yyvsp[0]是值栈（value stack）当前的头部。

定义一元减号符有更高的优先级的方法：

%left GE LE EQ NE '>' '<' 
%left '+' '-' 
%left '*' 
%nonassoc UMINUS

%nonassoc的含义是没有结合性。它一般与%prec结合使用表示该操作有同样的优先级。如：

expr: '-' expr %prec UMINUS { $$ = node(UMINUS, 1, $2); }

表示该操作的优先级与UMINUS相同，在上面的定义中，UMINUS的优先级高于其他操作符，所以该操作的优先级也高于其他操作符计算。

规则段

规则段由语法规则和包括C代码的动作组成。

规则中目标或非终端符放在左边，后跟一个冒号（：），然后是产生式的右边，之后是对应的动作（用{}包含）。如：

%token INTEGER
%%
program: program expr '\n' { printf("%d\n", $2); } 
              ;
expr: INTEGER { $$ = $1; }  
         | expr '+' expr { $$ = $1 + $3; } 
         | expr '-' expr { $$ = $1 - $3; } 
;

%%
int yyerror(char *s) 
{ 
     fprintf(stderr, "%s\n", s); 
     return 0; 
}

其中，1表示右边的第一个标记的值，2表示右边的第二个标记的值，依次类推。$$表示归约后的值。

用户子例程段

yacc 将用户子例程段的内容完全拷贝到C文件中，通常这部分包括从动作调用的例程。
该部分是函数部分。当yacc解析出错时，会调用函数yyerror()，用户可自定义函数的实现。
main函数是调用yacc解析入口函数yyparse()。如：

int main(void) 
{ 
     yyparse(); 
     return 0; 
}

动作

动作 是yacc与在语法中规则相符时执行的C代码，动作一定是C复合语句。

动作有4种可能：

通过使用后面跟有数字的美元符号，动作可以查阅在规则中与符号有关的值,冒号后面跟的第一个符号是数字1，例如：

date：month  '/'  day   '/'  year  
           { printf ("date %d-%d-%d  found",$1,$3,$5);}

而名字，$$是指冒号左边符号的值，符号值可以有不同的C类型。

三、递归处理

递归处理有左递归和右递归。
左递归形式：

list: item 
    | list ',' item;

右递归形式：

list: item 
     | item ',' list

使用右递归时，所有的项都压入堆栈里，才开始规约；而使用左递归的话，同一时刻不会有超过三个项在堆栈里。

歧义和冲突

由于语法有歧义或者包含冲突，yacc对于语法规范的翻译可能会失败。一些情况下，语法确实有歧义，也就是说对于一个单独的输入字符串有两种可能的分析而且yacc处理不了。

另外一些情况，语法并无歧义，但yacc使用的语法分析技术不足以分析这个语法。

%%  
e: ‘X’  
     |e  '+'   e  
         ;

对于输入字符串“X+X+X” ，有两种可能的分析： “（X+X）+X”或者“X+(X+X)”，采用归约选项使得语法分析程序使用第一个分析，而采用移进选项则使用另一个。

%%  
prog:    proga | progb  
proga:       'X' ;  
progb:       'Y' ;

一个“X”可能是proga，也可能是progb。

大多数归约/归约冲突没这么明显，但是几乎在任何情况下它们在语法中都表现为错误。

%nonassoc IFX 
%nonassoc ELSE
stmt: IF expr stmt %prec IFX 
       | IF expr stmt ELSE stmt

四、特殊字符

由于yacc处理符号标记而不是文本，它的输入字符集比起lex来说就简单的多，下面列出了yacc所使用的特殊符号的列表：

%
具有两个%标记的行将yacc语法分成了几部分；
定义段的所有声明都是以%开始，包括%{ %} %union %start %token %type %left %right 和 %nonassoc声明。

\
反斜线符号是废弃的百分号同义词，在动作中，C语言字符串中有其通常作用。

$
在动作中，美元符号引入一个值引用，举例来说，$3表示规则右端第3个符号的值。

'
文字标记由一个单引号结束，例如 'z' 。

<>
在一个动作的值引用中，可以不考虑尖括号包围起来的默认类型。

"
有些yacc版本在文字标记中将单引号和双引号同等对待，这样使用根本不方便。

{}
动作中C代码在大括号中。

;
除了后面紧接着是以竖线开头的规则外，规则部分每个都是以分号结束。

|
当连续两个规则具有相同的左端，第二个规则可用一个 | 代替符号和冒号。

:
在每一条规则里，左端的每个符号后面都跟着一个冒号。

_
符号可以包括和字母、数字以及句点在一起的下划线。

.
符号可以包括与字母、数字、下划线一起的句点。

=
早期版本使用，现已不推荐。

五、Yacc 源程序的风格

建议按照如下风格来写：

  1. 终端符名全部用大写字母，非终端符全部用小写字母；
  2. 把语法规则和语义动作放在不同的行；
  3. 把左部相同的规则写在一起，左部只写一次，而后面所有规则都写在竖线“|”之后；
  4. 把分号“；”放在规则最后，独占一行；
  5. 用制表符来对齐规则和动作。
上一篇下一篇

猜你喜欢

热点阅读