2

我有一个用于解析 C++ 表达式的 YACC 语法。这是精简版：

// yacc.y
%token IDENT

%%

expr:
    call_expr
    | expr '<' call_expr
    | expr '>' call_expr
    ;

call_expr:
    IDENT
    | '(' expr ')'
    | IDENT '<' args '>' '(' args ')'
    ;

args:
    IDENT
    | args ',' IDENT
    ;

%%

当我想支持带有模板参数的函数调用时，我遇到了shift/reduce冲突。

当我们得到 inputIDENT '<' IDENT时，yacc 不知道我们应该转移还是减少。

我想得到IDENT '<' args '>' '(' args ')'比 更高的优先级expr '<' call_expr，所以我可以解析以下表达式。

x < y
f<x>(a,b)
f<x,y>(a,b) < g<x,y>(c,d)

我看到 C++/C# 都支持这种语法。有没有办法用yacc解决这个问题？

如何修改.y文件？

谢谢！

4

1 回答 1

1

您想要-vyacc/bison 的选项。它将为您提供一个 .output 文件，其中包含有关生成的 shift/reduce 解析器的所有信息。凭借您的语法，bison 为您提供：

State 1 conflicts: 1 shift/reduce
      :
state 1

    4 call_expr: IDENT .
    6          | IDENT . '<' args '>' '(' args ')'

    '<'  shift, and go to state 5

    '<'       [reduce using rule 4 (call_expr)]
    $default  reduce using rule 4 (call_expr)

它告诉你问题出在哪里。在看到 之后IDENT，当下一个标记是 时<，它不知道是否应该减少它call_expr（最终匹配规则expr: expr '<' call_expr）或者它是否应该转移到匹配规则 6。

仅使用 1 个标记前瞻来解析它是困难的，因为您有两个不同的标记含义<（小于或开尖括号），这取决于后面的标记。

这种情况实际上更糟，因为它是模棱两可的，作为输入

a < b > ( c )

可能是两个 args 列表都是单例的模板调用，但也可能是

( a < b ) > ( c )

所以仅仅分解语法是没有帮助的。您最好的选择是使用更强大的解析方法，例如 bison 的%glr-parser选项或btyacc

于 2013-06-14T21:45:04.783 回答