非终结符出现 JISON 错误

Question

我正在为 class 编写一个 JISON 文件，并尝试使用非终结符来代替声明运算符的关联性，但我完全不知道错误的真正含义，因为这是一次性分配class 而且我还没有找到在这个用例中使用非终结符的惊人示例。

我的 JISON 代码：

/* lexical grammar */
%lex
%%

\s+                   /* skip whitespace */
[0-9]+("."[0-9]+)?\b  return 'NUMBER'
"*"                   return '*'
"/"                   return '/'
"-"                   return '-'
"+"                   return '+'
"^"                   return '^'
"!"                   return '!'
"%"                   return '%'
"("                   return '('
")"                   return ')'
"PI"                  return 'PI'
"E"                   return 'E'
<<EOF>>               return 'EOF'
.                     return 'INVALID'

/lex

%start expressions

%% /* language grammar */

expressions
   : e EOF
       { typeof console !== 'undefined' ? console.log() : print();
        return ; }
    ;

e
    : NegExp
         {$$ = ;}
    | MulExp
         {$$ = ;}
    | PowExp
         {$$ = ;}
    | UnaryExp
         {$$ = ;}
    | RootExp
         {$$ = ;}
    ;


RootExp
    : ’(’ RootExp ’)’
         {$$ = ’(’ +  + ’)’;}
| NUMBER
    {$$ = Number(yytext);}
| E
    {$$ = ’E’;}
| PI
    {$$ = ’PI’;}
;

UnaryExp
    : UnaryExp '!'
        {$$ = '(' +  + '!' + ')';}
    | UnaryExp '%'
        {$$ = '(' +  + '%' + ')';}
    | '-' UnaryExp
        {$$ = '(-' +  + ')';}
    ;

 NegExp
    : NegExp '+' e
        {$$ = '(' +  + ' + ' +  + ')';}
    | NegExp '-' e
        {$$ = '(' +  + ' - ' +  + ')';}
    ;

MulExp
    : MulExp '*' e
        {$$ = '(' +  + ' * ' +  + ')';}
    | MulExp '/' e
        {$$ = '(' +  + ' / ' +  + ')';}
    ;

PowExp
    : e '^' PowExp
        {$$ = '(' +  + ' ^ ' +  + ')';}
    ;

当我运行 jison filename.jison 时，我得到了一系列错误，例如：

Conflict in grammar: multiple actions possible when lookahead token is ^ in state 26
- reduce by rule: MulExp -> MulExp / e
- shift token (then go to state 13)

和：

States with conflicts:
State 3
  e -> NegExp . #lookaheads= EOF ^ + - * /
  NegExp -> NegExp .+ e #lookaheads= EOF + - ^ / *
  NegExp -> NegExp .- e #lookaheads= EOF + - ^ / *

再次重申，我不是在找人帮我做作业，而是希望能指导我去哪里或做什么来帮助调试。

Answer 1

这是真的；找到不使用优先级声明解决歧义的表达式语法的例子并不容易。这可能是因为在此特定用例中，优先级声明非常方便，并且可能比写出明确的语法更具可读性。生成的解析器通常也稍微高效一些，因为它避免了由通常的明确语法风格强加的单元缩减链。

这种便利的另一面是它无法帮助学生理解语法的实际工作原理，如果没有这种理解，就很难将优先级声明应用于不太明确的应用程序。所以提出这个问题的练习当然是值得的。

您会在（某些）编程语言的规范中找到明确的表达式语法，因为明确的语法不依赖于解析器生成器用来解决解析冲突的算法的精确性质。不过，这些示例往往相当复杂，因为真正的编程语言通常有很多运算符。尽管如此，示例 C grammar in the jison examples directory 确实显示了算术表达式语法的标准模型。下面的摘录被大大简化了，但大部分作品只是从原作中复制粘贴而来。（我删除了许多运算符、大部分优先级以及一些处理诸如转换表达式和特殊逗号运算符之类的复杂问题，这些在这里肯定不相关。）

primary_expression
    : IDENTIFIER
    | CONSTANT
    | '(' expression ')'
    ;

postfix_expression
    : primary_expression
    | postfix_expression INC_OP
    | postfix_expression DEC_OP
    ;

unary_expression
    : postfix_expression
    | '-' unary_expression
    | INC_OP unary_expression
    | DEC_OP unary_expression
    ;

/* I added this for explanatory purposes. DO NOT USE IT. See the text. */
exponential_expression
    : unary_expression
    | unary_expression '^' exponential_expression    

multiplicative_expression
    : exponential_expression
    | multiplicative_expression '*' exponential_expression
    | multiplicative_expression '/' exponential_expression
    | multiplicative_expression '%' exponential_expression
    ;

additive_expression
    : multiplicative_expression
    | additive_expression '+' multiplicative_expression
    | additive_expression '-' multiplicative_expression
    ;

expression
    : additive_expression
    ;

C 没有求幂运算符，所以我添加了一个具有右结合性且优先级高于乘法的运算符，以用于解释目的。但是，您的作业可能也希望它具有比一元否定更高的优先级，而我没有这样做。所以不建议直接用上面的

在上述模型中需要注意的一点是，每个优先级对应一个非终结符。这些非终端使用单元产生式链接到有序链中。我们可以看到这个序列：

expression ⇒ additive_expression ⇒ multiplicative_expression ⇒ exponential_expression ⇒ unary_expression ⇒ postfix_expression ⇒ primary_expression

这确实对应于此语法的优先顺序。

语法的另一个有趣的方面是左结合运算符（除求幂外的所有运算符）是用左递归产生式实现的，而右结合运算符是用右递归产生式实现的。这不是巧合。

这是基本模型，但值得花几分钟时间尝试了解它的实际工作原理，因为事实证明它非常简单。让我们看一下乘法产生式，看看我们是否能理解为什么它意味着求幂结合更紧密而加法结合不那么紧密：

multiplicative_expression: multiplicative_expression '*' exponential_expression

这个产生式是说 multiplicative_expression 由 * 和左边的 multiplicative_expression 和右边的 exponential_expression 组成。

现在，这对 2 + 3 * 4 ^ 2 意味着什么？ 2 + 3是一个additive_expression，但是我们可以从单元生产链中看出multiplicative_expression不生产additive_expression。所以语法不包括 2 + 3 是在 * 左侧匹配的短语的可能性。然而，3（一个CONSTANT，一个primary_expression）被解析为乘法的左操作数是完全合法的。

同时，4 ^ 2是一个exponential_expression，我们的产生式清楚地表明exponential_expression可以在*的右边匹配。

一个类似的论证，检查加法和指数表达式的产生式，会表明 3 * 4 ^ 2 (a multiplicative_expression) can 在右边+ 运算符的一侧，而 2 + 3 * 4（additive_expression）和 3 * 4（multiplicative_expression）都不能位于求幂的左侧运算符。

换句话说，这个简单的语法精确而明确地定义了必须如何分解表达式。只有一种可能的解析树：

        expression
             |
            add
             |
    +--------+----------------+
    |        |                |
    |        |              mult
    |        |                |
    |        |        +-------+---------------+
    |        |        |       |               |
    |        |        |       |             power
    |        |        |       |               |
    |        |        |       |       +-------+-------+ 
    |        |        |       |       |       |       |
   add       |      mult      |     unary     |     power
   ...       |       ...      |      ...      |      ...
    |        |        |       |       |       |       |
 primary     |     primary    |    primary    |    primary
    |        |        |       |       |       |       |
    2        +        3       *       4       ^       2

希望对您有所帮助。

非终结符出现 JISON 错误

JISON errors occuring with nonterminals

debugging

jison