1

我正在尝试解析不带分隔符的表达式序列，以便能够解析 ML/F# 样式的函数调用：

myfunc expr1 expr2 expr3

但是，表达式序列给了我一个移位/减少冲突的列表。

我的猜测是冲突是由我的语法的递归性质引起的，但我不知道如何解决这些冲突。

我的（简化的）优先规则和语法如下所示：

/* Lowest precedence */
%left PLUS
%left TIMES
%left LPAR
/* Highest precedence */

Expr: 
  | CSTINT                                { CstI $1                   }
  | LPAR Expr RPAR                        { $2                        }
  | Expr TIMES Expr                       { Prim("*", $1, $3)         }
  | Expr PLUS Expr                        { Prim("+", $1, $3)         }
  | NAME ExprList                         { Call(Var $1, $2)          }

ExprList:
  |                                      { []                        }
  | Expr ExprList                        { $1::$2                    }

当我将它传递给 fsyacc 时，我会得到一个 shift/reduce 和 reduce/reduce 冲突列表。一个示例移位/减少冲突是

state 11: shift/reduce error on PLUS

状态 11 的 fsycc 的输出是：

state 11:
  items:
    Expr -> Expr . 'TIMES' Expr
    Expr -> Expr . 'PLUS' Expr
    ExprList -> Expr . ExprList

  actions:
    action 'EOF' (noprec):   reduce ExprList --> 
    action 'LPAR' (explicit left 10000):   shift 6
    action 'RPAR' (noprec):   reduce ExprList --> 
    action 'COMMA' (noprec):   reduce ExprList --> 
    action 'PLUS' (explicit left 9998):   shift 13
    action 'TIMES' (explicit left 9999):   shift 12
    action 'NAME' (noprec):   shift 14
    action 'CSTINT' (noprec):   shift 5
    action 'error' (noprec):   reduce ExprList --> 
    action '#' (noprec):   reduce ExprList --> 
    action '$$' (noprec):   reduce ExprList --> 

  immediate action: <none>
 gotos:
    goto Expr: 11
    goto ExprList: 16

自从我学习编译器理论课程以来已经有一段时间了，所以虽然我知道什么是移位/归约和归约/归约冲突，但我不习惯思考它们。特别是，我看不到减少如何PLUS导致有效的解析。总而言之，对以下一个或多个问题的任何见解都将受到高度赞赏：

  1. 为什么我的语法看起来模棱两可？
  2. 我可以使用优先级和/或关联性规则来修复它吗，或者，如果不是，
  3. 我是否需要重写语法，如果需要，大致上，我该怎么做？
  4. yacc 是适合这种构造的工具吗？
4

1 回答 1

3

1. 为什么我的语法看起来模棱两可？

你的语法模棱两可。这不是错觉。

假设 f 是一个函数。

f  x + 7

是这样f(x) + 7还是f(x+7)？。你的语法产生了两者。

IIRC，功能应用程序绑定非常紧密并关联到左侧。所以上面的表达式应该解析为f(x) + 7.

2. 我可以使用优先级和/或关联性规则来修复它吗，或者如果不是，

您可以使用优先级和关联性规则来消除函数应用的歧义；你只需要为它声明一个优先级%prec。然而，它最终看起来有点丑陋和......

3. 是否需要改写语法，如果需要，大致如何改写？

...我不认为将功能应用程序表示为Name ExprList. 如果您一次对参数进行一个柯里化会更干净，至少在构建 AST 时是这样，如果您在语法而不是优先规则中执行它看起来更漂亮，这实际上不是为隐形运算符设计的。见下文。

4. yacc 是否适合这样的构造？

当然，为什么不呢？

这是两个有效的（据我所知）yacc 语法。第一个对所有内容都使用优先级声明；第二个分离出功能应用程序，我认为它更干净：

// grammar1.y:

%left '+'
%left '*'
%left ATOM ';' '(' ')'

%%

program: /* empty */           { $$ = ""; }
       | program statement ';' { std::cout << $2 << std::endl; }
       | program ';'
       ;

statement: expr
         ;

expr: ATOM
    | '(' expr ')'             { $$ = $2; }
    | expr expr %prec ATOM     { $$ = '(' + $1 + ' ' + $2 + ')'; }
    | expr '+' expr            { $$ = "(+ " + $1 + ' ' + $3 + ')'; }
    | expr '*' expr            { $$ = "(* " + $1 + ' ' + $3 + ')'; }
    ;

// grammar2.y

%token ATOM

%left '+'
%left '*'

%%

program: /* empty */           { $$ = ""; }
       | program statement ';' { std::cout << $2 << std::endl; }
       | program ';'
       ;

statement: expr
         ;

term : ATOM
     | '(' expr ')'             { $$ = $2; }
     ;

apply: term
     | apply term              { $$ = '(' + $1 + ' ' + $2 + ')'; }
     ;

expr : apply
     | expr '+' expr            { $$ = "(+ " + $1 + ' ' + $3 + ')'; }
     | expr '*' expr            { $$ = "(* " + $1 + ' ' + $3 + ')'; }
     ;
于 2013-07-29T22:49:53.010 回答