yacc中的并列乘法

Question

我正在尝试实现一种允许通过并列进行乘法的语法。这用于解析 CAS 的多项式输入。

据我所知，除了少数极端情况外，它工作得很好。我发现了两个问题：

与其他规则冲突，例如，a^2 b 被（错误地）解析为 (^ a (* 2 b))，而不是 (* (^ a 2) b)。
yacc(bison) 报告 28 shift/reduce conflicts 和 8 reduce/reduce conflicts.

我很确定正确解决第一个问题也会解决第二个问题，但到目前为止我还没有成功。

以下是我正在使用的语法的要点：

%start  prgm
%union {
    double  num;
    char    *var;
    ASTNode *node;
}
%token  <num>   NUM
%token  <var>   VAR
%type   <node>  expr

%left   '+' '-'
%left   '*' '/'
%right  '^'
%%
prgm:     // nothing
    | prgm '\n'
    | prgm expr '\n'
    ;
expr:     NUM
    | VAR
    | expr '+' expr
    | expr '-' expr
    | expr '*' expr
    | expr '/' expr
    | expr '^' expr
    | expr expr %prec '*'
    | '-' expr
    | '(' expr ')'
    ;
%%

删除并置规则 (expr expr %prec '*') 解决了 shift/reduce & reduce/reduce 警告。

请注意，ab 在我的语法中应该表示 (* a b)。多字符变量前应加引号(')；这已经在 lex 文件中得到了很好的处理。词法分析器完全忽略空格（）和制表符（\t）。

我知道this question，但这里并列的使用似乎并不表示乘法。

如有任何意见或帮助，我们将不胜感激！

P.S。如果有帮助，this is the link to the entire project.

Answer 1

如您所链接问题的答案所示，很难指定并列运算符的优先级，因为没有运算符可以移动。（在您的代码中，您可以指定产生式 expr: expr expr 的优先级。但这种减少将与哪个前瞻标记进行比较？将 FIRST(expr) 中的每个标记添加到您的优先级声明中不是很可扩展，并且可能导致不需要的优先决议。

优先解决方案的另一个问题是一元减号运算符的行为（链接问题中未解决的问题），因为按照您编写的语法允许 a - b 解析为减法或作为 a 和 -b 的并列乘法。（请注意 - 在 FIRST(expr) 中，导致我在上面提到的可能不需要的解决方案之一。）

因此，按照链接问题中的建议，最好的解决方案是使用具有明确优先级的语法，例如：（在这里，我使用 juxt 作为非终端的名称，而不是 expr_sequence):

%start  prgm
%token  NUM
%token  VAR

%left   '+' '-'
%left   '*' '/'
%right  '^'
%%
prgm:     // nothing
    | prgm '\n'
    | prgm expr '\n'
expr: juxt
    | '-' juxt
    | expr '+' expr
    | expr '-' expr
    | expr '*' expr
    | expr '/' expr
    | expr '^' expr
juxt: atom
    | juxt atom
atom: NUM
    | VAR
    | '(' expr ')'

这个语法可能不是你想要的：

一元减号的处理相当简单，但有几个问题。我不认为将 -xy 解析为 -(xy) 而不是 (-x)y 有问题，但它并不理想。此外，它不允许 --x （同样，可能不是问题但不理想）。最后，它没有将 -x^y 解析为 -(x^y)，而是解析为 (-x)^y，这与通常的做法相反。
此外，它错误地将并列绑定得太紧。您可能认为 a/xy 解析为 a/(xy) 是一个问题，但您可能会反对将 2x^7 解析为 (2x)^7.

避免这些问题的最简单方法是使用一种语法，其中运算符优先级通过明确的语法规则统一实现。

这是一个实施标准优先级规则的示例（求幂优先于一元减号；并列乘法与显式乘法具有相同的优先级）。值得花几分钟仔细看看哪个非终结符出现在哪个产品中，并思考它与所需的优先级规则有何关联。

%union {
    double  num;
    char    *var;
    ASTNode *node;
}
%token  <num>   NUM
%token  <var>   VAR
%type   <node>  expr mult neg expt atom

%%
prgm:     // nothing
    | prgm '\n'
    | prgm error '\n'
    | prgm expr '\n'
expr: mult
    | expr '+' mult
    | expr '-' mult
mult: neg
    | mult '*' neg
    | mult '/' neg
    | mult expt
neg : expt
    | '-' neg
expt: atom
    | atom '^' neg
atom: NUM
    | VAR
    | '(' expr ')'

yacc中的并列乘法

Multiplication by juxtaposition in yacc

grammar

yacc

bison

shift-reduce-conflict

reduce-reduce-conflict