明确语法上的yacc移位/减少冲突 [英] A yacc shift/reduce conflict on an unambiguous grammar

问题描述

我的一段语法使我发疯.

A piece of code of my gramamar its driveing me crazy.

我必须编写一种语法，以允许具有多个输入的写入功能

I have to write a grammar that allow write functions with multiple inputs

例如

function
  begin
    a:
       <statments>
    b:
       <statements>
  end

---

问题在于这样的语句

---

The problem with that its that is statements that are assignments like this

ID =展示次数.

在下面的引用中，您可以看到yacc产生的输出.

in the following quote you can see the output produced by yacc.

  0  $accept : InstanciasFuncion $end

  1  InstanciasFuncion : InstanciasFuncion InstanciaFuncion
  2                    | InstanciaFuncion

  3  InstanciaFuncion : PuntoEntrada Sentencias

  4  PuntoEntrada : ID ':'

  5  Sentencias : Sentencias Sentencia
  6             | Sentencia

  7  Sentencia : ID '=' ID

State 0

    0 $accept: . InstanciasFuncion $end

    ID  shift, and go to state 1

    InstanciasFuncion  go to state 2
    InstanciaFuncion   go to state 3
    PuntoEntrada       go to state 4

State 1

    4 PuntoEntrada: ID . ':'

    ':'  shift, and go to state 5

State 2

    0 $accept: InstanciasFuncion . $end
    1 InstanciasFuncion: InstanciasFuncion . InstanciaFuncion

    $end  shift, and go to state 6
    ID    shift, and go to state 1

    InstanciaFuncion  go to state 7
    PuntoEntrada      go to state 4

State 3

    2 InstanciasFuncion: InstanciaFuncion .

    $default  reduce using rule 2 (InstanciasFuncion)

State 4

    3 InstanciaFuncion: PuntoEntrada . Sentencias

    ID  shift, and go to state 8

    Sentencias  go to state 9
    Sentencia   go to state 10

State 5

    4 PuntoEntrada: ID ':' .

    $default  reduce using rule 4 (PuntoEntrada)

State 6

    0 $accept: InstanciasFuncion $end .

    $default  accept

State 7

    1 InstanciasFuncion: InstanciasFuncion InstanciaFuncion .

    $default  reduce using rule 1 (InstanciasFuncion)

State 8

    7 Sentencia: ID . '=' ID

    '='  shift, and go to state 11

State 9

    3 InstanciaFuncion: PuntoEntrada Sentencias .
    5 Sentencias: Sentencias . Sentencia

    ID  shift, and go to state 8

    ID        [reduce using rule 3 (InstanciaFuncion)]
    $default  reduce using rule 3 (InstanciaFuncion)

    Sentencia  go to state 12

State 10

    6 Sentencias: Sentencia .

    $default  reduce using rule 6 (Sentencias)

State 11

    7 Sentencia: ID '=' . ID

    ID  shift, and go to state 13

State 12

    5 Sentencias: Sentencias Sentencia .

    $default  reduce using rule 5 (Sentencias)

State 13

    7 Sentencia: ID '=' ID .

    $default  reduce using rule 7 (Sentencia)

也许有人可以帮助我消除这种语法的歧义

Maybe somebody can help me to disambiguate this grammar

推荐答案

野牛至少为您提供了提示.在状态9中，除了语法本身，它实际上是输出中唯一相关的部分，我们看到:

Bison provides you with at least a hint. In State 9, which is really the only relevant part of the output other than the grammar itself, we see:

State 9

    3 InstanciaFuncion: PuntoEntrada Sentencias .
    5 Sentencias: Sentencias . Sentencia

    ID  shift, and go to state 8

    ID        [reduce using rule 3 (InstanciaFuncion)]
    $default  reduce using rule 3 (InstanciaFuncion)

    Sentencia  go to state 12

在可能的情况下，与ID发生移位/减少冲突:

There's a shift/reduce conflict with ID, in the context in which the possibilities are:

1. 完成InstanciaFuncion的解析(减少)

继续解析Sentencias(移位)

在这两种情况下，ID都是可能的.构造示例很容易.考虑以下两个实例:

In both of those contexts, an ID is possible. It's easy to construct an example. Consider these two instancias:

f : a = b c = d ...
f : a = b c : d = ...

我们已经完成了b的操作，并且c是超前的，所以我们看不到c后面的符号.现在，我们已经完成了对函子f的解析吗?还是我们应该尝试更长的哨兵名单?不，萨贝. (没人知道.)

We've finished with the b and c is the lookahead, so we can't see the symbol which follows the c. Now, have we finished parsing the funcion f? Or should we try for a longer list of sentencias? No se sabe. (Nobody knows.)

是的，您的语法是明确的，因此不需要明确.但是，它不是LR(1):您不能仅通过查看下一个一个符号来分辨要做什么.但是，它是LR(2)，并且有证据表明，任何LR(2)语法都具有对应的LR(1)语法. (对于2的任何值:)).但是，不幸的是，实际上进行转换并不总是很漂亮.它可以机械地完成，但是生成的语法可能很难看懂. (请参阅下面的注释以获取参考.)

Yes, your grammar is unambiguous, so it doesn't need to be disambiguated. It's not LR(1), though: you cannot tell what to do by only looking at the next one symbol. However, it is LR(2), and there is a proof than any LR(2) grammar has a corresponding LR(1) grammar. (For any value of 2 :) ). But, unfortunately, actually doing the transformation is not always very pretty. It can be done mechanically, but the resulting grammar can be hard to read. (See Notes below for references.)

在您的情况下，找到等效的语法很容易，但是解析树将需要调整.这是一个示例:

In your case, it's pretty easy to find an equivalent grammar, but the parse tree will need to be adjusted. Here's one example:

InstanciasFuncion : PuntoEntrada 
                  | InstanciasFuncion PuntoEntrada
                  | InstanciasFuncion Sentencia

PuntoEntrada: ID ':' Sentencia

Sentencia : ID '=' ID

一个奇怪的事实是，这种精确的移位/减少冲突是bison本身语法的一个特征，因为bison接受上面写的语法(即不使用分号). Posix坚持要求yacc这样做，而bison试图模仿yacc. Bison本身在扫描程序中解决了这个问题，而不是在语法上:它的扫描程序将"ID:"识别为单个令牌(即使用任意空格分隔也是如此).那可能也是您最好的选择.

It's a curious fact that this precise shift/reduce conflict is a feature of the grammar of bison itself, since bison accepts grammars as written above (i.e. without semi-colons). Posix insists that yacc do so, and bison tries to emulate yacc. Bison itself solves this problem in the scanner, not in the grammar: it's scanner recognizes "ID :" as a single token (even if separated with arbitrary whitespace). That might also be your best bet.

在Sippu& amp; amp; amp; amp; amp; amp; amp; amp;中，LR(1)语法可以覆盖任何LR(k)语法，其中包括构造技术和如何恢复原始解析树的简要说明，这是对证明的极佳描述. Soisalon-Soininen，解析理论，第1卷. II(Springer Verlag，1990年)( Amazon ) .这本两卷本的书对理论家来说是一个很好的参考，并具有许多有价值的实用信息，但阅读量很大，而且投资巨大.如果您有方便的大学图书馆，则应该有它的副本.提出的算法归因于MD Mickunas，并于1976年发布在 JACM 23:17- 30 (付费专区)，您也应该可以在好的大学图书馆中找到它.失败了，我在理查德·马里昂·谢尔(Richard Marion Schell)的论文中找到了一个非常简短的描述.

There is an excellent description of the proof than any LR(k) grammar can be covered by an LR(1) grammar, including the construction technique and a brief description of how to recover the original parse tree, in Sippu & Soisalon-Soininen, Parsing Theory, Vol. II (Springer Verlag, 1990) (Amazon). This two-volume set is a great reference for theoreticians, and has a lot of valuable practical information, but its heavy reading and its also a serious investment. If you have a university library handy, there should be a copy of it available. The algorithm presented is due to MD Mickunas, and was published in 1976 in JACM 23:17-30 (paywalled), which you should also be able to find in a good university library. Failing that, I found a very abbreviated description in Richard Marion Schell's thesis.

就我个人而言，我不会为所有这些烦恼.可以使用GLR解析器，也可以将野牛用于相同目的而使用相同的技巧.或在上面的答案中使用简单的语法，然后摆弄AST；并不是很困难.

Personally, I wouldn't bother with all that, though. Either use a GLR parser, or use the same trick bison uses for the same purpose. Or use the simple grammar in the answer above and fiddle with the AST afterwards; it's not really difficult.

这篇关于明确语法上的yacc移位/减少冲突的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！