0

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

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

  1. 与其他规则冲突，例如，a^2 b被（错误地）解析为(^ a (* 2 b))，而不是(* (^ a 2) b)。
  2. 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）。

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

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

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

4

1 回答 1

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 ')'
于 2021-03-27T17:38:11.953 回答