YACC嵌入式规则

103 阅读 0 评论 68 点赞

我是靠谱客的博主聪慧睫毛膏，最近开发中收集的这篇文章主要介绍YACC嵌入式规则，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

测试用例在文章末尾

嵌入式用法

YACC语法分析只允许动作在规则的末端，例如：

（其中{}内部为定义好的规则）

expr: T_INT							{ $$ = $1; }
			| expr T_PLUS expr		{ $$ = $1 + $3; }
			| expr T_MINUS expr		{ $$ = $1 - $3; }
			| expr T_MULTIPLY expr	{ $$ = $1 * $3; }
			| T_LEFT expr T_RIGHT	{ $$ = $2; }
			| T_PLUS expr			%prec UMINUS	{ $$ = $2; }
			| T_MINUS expr			%prec UMINUS	{ $$ = -$2; }
			;

但YACC也支持在规则内部嵌入动作，例如：

test1: T_INT {printf("seen an test1-1n");} T_INT {printf("seen an test1-2n");};

等价写法：

test2: T_FLOAT fakename T_FLOAT;
fakename: /* EMPTY */ 
    {printf("seen an test2n");}

嵌入式规则也同样占用符号位置，例如：

thing:     A { $$ = 17; } B C { printf("%d", $2); } ;

会打印17。当前$1表示A、$3表示B、$4表示C。

移进/规约冲突

嵌入式规则等于在匹配规则的过程中就执行一些动作（正常动作是在规则整体匹配完了再执行）。这样会导致规约的动作有可能要比没有嵌入式的规则提前做，例如：

thing:    abcd  |  abcz;

abcd:  ‘A'  'B'  'C'  'D' ;
abcz:  ‘A'  'B'  'C'  'Z'

如果加入嵌入式语法就会有冲突：

thing:    abcd  |  abcz;

abcd:  ‘A'  'B' { func(); } 'C'  'D' ;
abcz:  ‘A'  'B'  'C'  'Z'

原因是：

第一种情况下，yacc在看到4个字符之前不需要决定匹配abcd还是abcz，reduce动作可以在收到4个字符之后再做。
第二种情况下，在收到A、B之后，就必须做出决定了，因为abcd规则有嵌入式规则要执行，但是只收到两个字符无法决定走哪个分支，所以发生冲突。

用例

calc.y

%{

#include <stdio.h>
#include <stdlib.h>

extern int yylex();
extern int yyparse();
extern FILE* yyin;

void yyerror(const char* s);
%}

%union
{
	int ival;
	float fval;
}

%token<ival>	T_INT
%token<fval>	T_FLOAT

%token		T_PLUS T_MINUS T_MULTIPLY T_DIVIDE T_LEFT T_RIGHT
%token		T_NEWLINE T_QUIT

%left		T_PLUS T_MINUS
%left		T_MULTIPLY T_DIVIDE
%nonassoc	UMINUS

%type<ival> expr test1 fakename
%type<fval> fexpr test2

%start calculation

%%

calculation:
			| calculation line
			;

line: T_NEWLINE
			| fexpr T_NEWLINE
				{
					printf("tResult: %fn", $1);
				}
			| expr T_NEWLINE
				{
					printf("tResult: %in", $1);
				}
			| T_QUIT T_NEWLINE
				{
					printf("bye!n"); exit(0);
				}
			| test1 T_NEWLINE
				{
					printf("test1!n"); exit(0);
				}
			| test2 T_NEWLINE
				{
					printf("test2!n"); exit(0);
				}
			;

fexpr: T_FLOAT								{ $$ = $1; }
			| fexpr T_PLUS fexpr			{ $$ = $1 + $3; }
			| fexpr T_MINUS fexpr			{ $$ = $1 - $3; }
			| fexpr T_MULTIPLY fexpr		{ $$ = $1 * $3; }
			| fexpr T_DIVIDE fexpr			{ $$ = $1 / $3; }
			| T_LEFT fexpr T_RIGHT			{ $$ = $2; }
			| expr T_PLUS fexpr				{ $$ = $1 + $3; }
			| expr T_MINUS fexpr			{ $$ = $1 - $3; }
			| expr T_MULTIPLY fexpr			{ $$ = $1 * $3; }
			| expr T_DIVIDE fexpr			{ $$ = $1 / $3; }
			| fexpr T_PLUS expr				{ $$ = $1 + $3; }
			| fexpr T_MINUS expr			{ $$ = $1 - $3; }
			| fexpr T_MULTIPLY expr			{ $$ = $1 * $3; }
			| fexpr T_DIVIDE expr			{ $$ = $1 / $3; }
			| expr T_DIVIDE expr			{ $$ = $1 / (float)$3; }
			;

expr: T_INT							{ $$ = $1; }
			| expr T_PLUS expr		{ $$ = $1 + $3; }
			| expr T_MINUS expr		{ $$ = $1 - $3; }
			| expr T_MULTIPLY expr	{ $$ = $1 * $3; }
			| T_LEFT expr T_RIGHT	{ $$ = $2; }
			| T_PLUS expr			%prec UMINUS	{ $$ = $2; }
			| T_MINUS expr			%prec UMINUS	{ $$ = -$2; }
			;

test1: T_INT {printf("seen an test1-1n");} T_INT {printf("seen an test1-2n");};
test2: T_FLOAT fakename T_FLOAT;
fakename: /* EMPTY */ {printf("seen an test2n");}
%%

int main() 
{
	yyin = stdin;

	do
	{
		yyparse();
	} while(!feof(yyin));

	return 0;
}

void yyerror(const char* s)
{
	fprintf(stderr, "Parse error: %sn", s);
	exit(1);
}

calc.l

%option noyywrap

%{
#include <stdio.h>

#define YY_DECL int yylex()

#include "calc.tab.h"

%}

whitespace		[ t]
newline			[n]
digit			[0-9]
integer			{digit}+
decimal			(({digit}*.{digit}+)|({digit}+.{digit}*))

%%

{whitespace}	{
					/* ignore */
				}

{newline}		{
					return T_NEWLINE;
				}

{integer}		{
					yylval.ival = atoi(yytext);
					return T_INT;
				}

{decimal}		{
					yylval.fval = atof(yytext); 
					return T_FLOAT;
				}


"+"				{return T_PLUS;}
"-"				{return T_MINUS;}
"*"				{return T_MULTIPLY;}
"/"				{return T_DIVIDE;}
"("				{return T_LEFT;}
")"				{return T_RIGHT;}
"exit"			{return T_QUIT;}
"quit"			{return T_QUIT;}

%%

Makefile

all: calc

calc.tab.c calc.tab.h:	calc.y
	bison -t -v -d calc.y

lex.yy.c: calc.l calc.tab.h
	flex calc.l

calc: lex.yy.c calc.tab.c calc.tab.h
	gcc -o calc calc.tab.c lex.yy.c

clean:
	rm calc calc.tab.c lex.yy.c calc.tab.h calc.output