YACC嵌入式规则

184 阅读 0 评论 122 点赞

我是靠谱客的博主聪慧睫毛膏，这篇文章主要介绍YACC嵌入式规则，现在分享给大家，希望可以做个参考。

测试用例在文章末尾

嵌入式用法

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

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

复制代码

1
2
3
4
5
6
7
8
9
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也支持在规则内部嵌入动作，例如：

复制代码

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

等价写法：

复制代码

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

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

复制代码

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

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

移进/规约冲突

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

复制代码

1
2
3
4
5
thing:    abcd  |  abcz;

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

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

复制代码

1
2
3
4
5
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);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
%{

#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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
%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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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