yacc不使用优先规则解决移进/规约冲突的问题

一刀。

初学lex和yacc，书上有两个例子，一个是使用优先规则的运行没有问题，另一个不使用优先规则的死活跑不过去，甚至连乘法除法都有问题，请大牛指教一下

下面这个是词法分析程序

1. %{
   
2. #include "y.tab.h"
   
3. extern int yylval;
   
4. %}
   
5. 
   
6. %%
   
7. [0-9]+  { yylval = atoi(yytext); return NUMBER; }
   
8. [ \t]+  ;
   
9. \n return 0;
   
10. [_a-zA-Z][_a-zA-Z0-9]*  { return NAME; }
    
11. [=\*\/\(\)\+\-]         { return yytext[0]; }
    
12. %%
    

复制代码

下面这个是使用有限规则的语法分析程序，运行没有问题

1. %{
   
2. #include <stdio.h>
   
3. %}
   
4. 
   
5. %token NAME NUMBER
   
6. %left '-' '+'
   
7. %left '*' '/'
   
8. %nonassoc UMINUS
   
9. 
   
10. %%
    
11. statement: NAME '=' expression
    
12.   | expression { printf("= %d\n", $1); }
    
13.   ;
    
14. 
    
15. expression: expression '+' expression { $$ = $1 + $3; }
    
16.   | expression '-' expression         { $$ = $1 - $3; }
    
17.   | expression '*' expression         { $$ = $1 * $3; }
    
18.   | expression '/' expression
    
19.     {
    
20.       if($3 == 0)
    
21.         yyerror("divide by zero");
    
22.       else
    
23.         $ = $1 / $3;
    
24.     }
    
25.   | '-' expression %prec UMINUS       { $$ = -$2; }
    
26.   | '(' expression ')'                { $$ = $2; }
    
27.   | NUMBER                            { $$ = $1; }
    
28.   ;
    
29. %%
    
30. 
    
31. extern FILE *yyin;
    
32. 
    
33. int main()
    
34. {
    
35.         do
    
36.         {
    
37.                 yyparse();
    
38.         }
    
39.         while(!feof(yyin));
    
40. }
    

复制代码

下面这个是不使用优先规则的程序，乘法、除法和小括号都有问题

1. %{
   
2. #include <stdio.h>
   
3. %}
   
4. 
   
5. %token NAME NUMBER
   
6. 
   
7. %%
   
8. statement: NAME '=' expression
   
9.   | expression { printf("= %d\n", $1); }
   
10.   ;
    
11. 
    
12. expression: expression '+' mulexp { $$ = $1 + $3; }
    
13.   | expression '-' mulexp  { $$ = $1 - $3; }
    
14.   | primary                { $$ = $1; }
    
15.   ;
    
16. 
    
17. mulexp: mulexp '*' primary { $$ = $1 * $3; }
    
18.   | mulexp '/' primary
    
19.     {
    
20.       if($3 == 0)
    
21.         yyerror("divide by zero");
    
22.       else
    
23.         $$ = $1 / $3;
    
24.     }
    
25.   | primary
    
26.   ;
    
27. 
    
28. primary: '(' expression ')' { $$ = $2; }
    
29.   | '-' primary             { $$ = -$2; }
    
30.   | NUMBER                  { $$ = $1; }
    
31.   ;
    
32. 
    
33. %%
    
34. 
    
35. extern FILE *yyin;
    
36. 
    
37. int main()
    
38. {
    
39.         do
    
40.         {
    
41.                 yyparse();
    
42.         }
    
43.         while(!feof(yyin));
    
44. }
    

复制代码

cjaizss

一刀。 发表于 2012-11-12 17:42
初学lex和yacc，书上有两个例子，一个是使用优先规则的运行没有问题，另一个不使用优先规则的死活跑不过去， ...

你的乘法和除法都无法被规约成statement,当然是语法错误
在你的程序中，乘法和除法唯一可以被规约成statement的机会是
expression: expression '+' mulexp
expression: expression '-' mulexp
也就是前面必须要有加减法
所以以下都是不符合你的语法的
linux-s3hu:/tmp/compile # ./a.out
2*3
= 2
syntax error
= 3

linux-s3hu:/tmp/compile # ./a.out
2*3+1
= 2
syntax error
= 4

以下才符合你的语法
linux-s3hu:/tmp/compile # ./a.out
1+2*3
= 7

一刀。

回复 2# cjaizss


    谢谢！我把primary改成mulexp通过了。我看书不仔细

1. %{
   
2. #include <stdio.h>
   
3. %}
   
4. 
   
5. %token NAME NUMBER
   
6. 
   
7. %%
   
8. statement: NAME '=' expression
   
9.   | expression { printf("= %d\n", $1); }
   
10.   ;
    
11. 
    
12. expression: expression '+' mulexp { $$ = $1 + $3; }
    
13.   | expression '-' mulexp  { $$ = $1 - $3; }
    
14.   | mulexp                { $$ = $1; }
    
15.   ;
    
16. 
    
17. mulexp: mulexp '*' primary { $$ = $1 * $3; }
    
18.   | mulexp '/' primary
    
19.     {
    
20.       if($3 == 0)
    
21.         yyerror("divide by zero");
    
22.       else
    
23.         $ = $1 / $3;
    
24.     }
    
25.   | primary
    
26.   ;
    
27. 
    
28. primary: '(' expression ')' { $$ = $2; }
    
29.   | '-' primary             { $$ = -$2; }
    
30.   | NUMBER                  { $$ = $1; }
    
31.   ;
    
32. 
    
33. %%
    
34. 
    
35. extern FILE *yyin;
    
36. 
    
37. int main()
    
38. {
    
39.         do
    
40.         {
    
41.                 yyparse();
    
42.         }
    
43.         while(!feof(yyin));
    
44. }

复制代码