验证Yacc的使用

Veröffentlicht am | in | Views:

实验内容

  • 输入为一个布尔表达式，以换行结束。输出为这个布尔表达式的真值（true或false）。

  • 尝试二义文法和非二义文法两种不同的实现方式。布尔表达式二义文法为：S –> S or S | S and S | not S | (S) | true | false，其中优先级or < and < not，or 和 and 左结合，not 右结合。

  • 非二义文法请参照表达式非二义文法自己写出来。

实验过程

cal.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
%{
#include "cal.tab.h"

int yywrap(void){
  return 1;
}
%}

delim		[ \t ]
ws			{delim}+
digit   	[0-9]
num     	{digit}+

%%
0         {return FALSE;}
{num}     {return TRUE;}
"+"       {return PLUS;}
"-"       {return MINUS;}
"*"       {return TIMES;}
"/"       {return DIVIDE;}
"||"	  {return OR;}
"&&"	  {return AND;}
"!"		  {return NOT;}
"("		  {return LPAREN;}
")"		  {return RPAREN;}
{ws}	  {;}
"\n"	  {return ENTER;}
.		  {printf("\nLEX:ERROR! c=%s\n", yytext);}

二义文法

二义文法

1
2
3
4
5
6
7
8
9
10
S –> S or S | S and S | not S | (S) | true | false

表示为：

expr1   : expr1 OR expr1 {$$ = ($1) ? 1 : ($3);}
        | expr1 AND expr1 {$$ = ($1) ? ($3) : 0;}
        | NOT expr1 {$$ = ($2) ? 0 : 1;}
        | TRUE {$$ = 1;}
        | FALSE {$$ = 0;}
        ;

优先级

1
2
3
4
5
6
%token NUM LPAREN RPAREN ENTER PLUS MINUS TIMES DIVIDE AND OR NOT TRUE FALSE
%left  OR
%left  AND
%right NOT
%left  PLUS MINUS
%left  TIMES DIVIDE

cal.y

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
%{
	#include <ctype.h>
	#include <stdio.h>
	int yylex();
	int yyerror(char* s);
  #define YYSTYPE double /* 将Yacc栈定义为double类型 */
  #define YYDEBUG 1      /* 允许debug模式 */
%}

%token NUM LPAREN RPAREN ENTER PLUS MINUS TIMES DIVIDE AND OR NOT TRUE FALSE
%left  OR
%left  AND
%right NOT
%left  PLUS MINUS
%left  TIMES DIVIDE

%%

  /* 这样写prog可以让分析器每次读入一行进行分析，下一行重新分析expr */

prog : prog expln
		 | expln
		 ;

expln 	: expr ENTER {if($$) printf("true\n");else printf("false\n");}
			 	;
		 	
expr  : expr PLUS term	{$$ = $1 + $3;}
			| expr MINUS term {$$ = $1 - $3;}
			| term	
			;
 
term	:	term TIMES factor  {$$ = $1 * $3;}
			| term DIVIDE factor {$$ = $1 / $3;}
			| factor
			;
			
factor  : LPAREN expr RPAREN {$$ = $2;}
				| MINUS factor 	{$$ = - $2;}
				| NUM	{$$ = $1;}
				| expr1
				;

expr1   : expr1 OR expr1 {$$ = ($1) ? 1 : ($3);}
        | expr1 AND expr1 {$$ = ($1) ? ($3) : 0;}
        | NOT expr1 {$$ = ($2) ? 0 : 1;}
        | TRUE {$$ = 1;}
        | FALSE {$$ = 0;}
        ;
 
%%

int main(){
  // yydebug = 1;
	yyparse();
	return 0;
}

非二义文法

非二义文法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
E -> E OR T | T
T -> T AND F | F
F -> NOT F | (F) | true | false

expr1   : expr1 OR expr2 {$$ = ($1) ? 1 : ($3);}
				| expr2
				;

expr2   : expr2 AND expr3 {$$ = ($1) ? ($3) : 0;}
        | expr3
				;

expr3   : NOT expr3 {$$ = ($2) ? 0 : 1;}
        | TRUE {$$ = 1;}
        | FALSE {$$ = 0;}
        ;

cal.y

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
%{
	#include <ctype.h>
	#include <stdio.h>
	int yylex();
	int yyerror(char* s);
  #define YYSTYPE double /* 将Yacc栈定义为double类型 */
  #define YYDEBUG 1      /* 允许debug模式 */
%}

%token NUM LPAREN RPAREN ENTER PLUS MINUS TIMES DIVIDE AND OR NOT TRUE FALSE
%left  OR
%left  AND
%right NOT
%left  PLUS MINUS
%left  TIMES DIVIDE

%%

  /* 这样写prog可以让分析器每次读入一行进行分析，下一行重新分析expr */

prog : prog expln
		 | expln
		 ;

expln 	: expr ENTER {if($$) printf("true\n");else printf("false\n");}
			 	;
		 	
expr  : expr PLUS term	{$$ = $1 + $3;}
			| expr MINUS term {$$ = $1 - $3;}
			| term	
			;
 
term	:	term TIMES factor  {$$ = $1 * $3;}
			| term DIVIDE factor {$$ = $1 / $3;}
			| factor
			;
			
factor  : LPAREN expr RPAREN {$$ = $2;}
				| MINUS factor 	{$$ = - $2;}
				| NUM	{$$ = $1;}
				| expr1
				;

expr1   : expr1 OR expr2 {$$ = ($1) ? 1 : ($3);}
				| expr2
				;

expr2   : expr2 AND expr3 {$$ = ($1) ? ($3) : 0;}
        | expr3
				;

expr3   : NOT expr3 {$$ = ($2) ? 0 : 1;}
        | TRUE {$$ = 1;}
        | FALSE {$$ = 0;}
        ;
 
%%

int main(){
  // yydebug = 1;
	yyparse();
	return 0;
}

makefile

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
cal3: cal.tab.o lex.yy.o  
	gcc -o cal3 cal.tab.o lex.yy.o -ly

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

cal.tab.o: cal.tab.c
	gcc -c cal.tab.c

lex.yy.c: cal.l
	flex cal.l

cal.tab.c: cal.y
	bison -dv cal.y

cal.tab.h: cal.y
	echo "cal.tab.h was created at the same time as cal.tab.c."

clean:
	rm -f cal3.exe lex.yy.o cal.tab.o lex.yy.c cal.tab.c cal.tab.h cal3.exe.stackdump cal.output

实验结果