在 yacc 中通过并列乘法

Question

>我正在尝试实现一种允许并列乘法的语法。 这是为了解析 CAS 的多项式输入。

据我所知，它运行良好，除了少数边缘情况。 我发现了两个问题：

1. 与其他规则冲突，例如，a^2 b被(错误地)解析为(^ a (* 2 b))，而不是(* (^ a 2) b)。
2. 亚克(野牛)报告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 '*')解决了移位/减少和减少/减少警告。

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

我知道这个问题，但这里使用并列似乎并不表示乘法。

任何意见或帮助将不胜感激！

<小时 />

附言如果有帮助，这是整个项目的链接。

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 ')'