1

我的一段语法代码让我发疯。

我必须编写一个允许编写具有多个输入的函数的语法

例如

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

问题在于它是这样的赋值语句

ID = 表达式。

在下面的引用中，您可以看到 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)

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

4

1 回答 1

3

Bison 至少为您提供了一个提示。在状态 9 中，除了语法本身之外，它实际上是输出中唯一相关的部分，我们看到：

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

在可能的情况下，与 , 存在 shift/reduce 冲突ID：

  1. 完成一个InstanciaFuncion(reduce)的解析

  2. 继续解析 a Sentencias(shift)

在这两种情况下，anID都是可能的。构建一个例子很容易。考虑这两个实例：

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

我们已经完成了bandc是前瞻，所以我们看不到 c 后面的符号。现在，我们已经完成了函数的解析了f吗？还是我们应该尝试更长的句子列表？没有se sabe。（没人知道。）

是的，您的语法是明确的，因此不需要消除歧义。但是，它不是 LR(1)：您无法仅通过查看下一个符号来判断该做什么。但是，它是 LR(2)，并且有一个证明比任何 LR(2) 文法都有对应的 LR(1) 文法。（对于 2 的任何值 :) ）。但是，不幸的是，实际上进行转换并不总是很漂亮。它可以机械地完成，但产生的语法可能难以阅读。（有关参考，请参阅下面的注释。）

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

InstanciasFuncion : PuntoEntrada 
                  | InstanciasFuncion PuntoEntrada
                  | InstanciasFuncion Sentencia

PuntoEntrada: ID ':' Sentencia

Sentencia : ID '=' ID

这是一个奇怪的事实，这种精确的移位/减少冲突是野牛本身语法的一个特征，因为野牛接受上面写的语法（即没有分号）。Posix 坚持这样yacc做，bison 试图效仿yacc。Bison 本身在扫描器中解决了这个问题，而不是在语法中：它的扫描器将“ID :”识别为单个标记（即使用任意空格分隔）。这也可能是你最好的选择。

在 Sippu 和 Soisalon-Soininen 中，对证明的描述比任何 LR(k) 文法都可以被 LR(1) 文法覆盖，包括构造技术和如何恢复原始解析树的简要描述，解析理论，卷。二（斯普林格出版社，1990 年）（亚马逊）。这套两卷本对理论家来说是一个很好的参考，并且有很多有价值的实用信息，但它的阅读量很大，也是一种严重的投资。如果你手边有一个大学图书馆，应该有一个可用的副本。提出的算法归功于 MD Mickunas，并于 1976 年在JACM 23:17-30（付费专区）中发表，您也应该能够在一个好的大学图书馆中找到它。做不到这一点，我发现了一个非常简短的描述Richard Marion Schell 的论文。

不过，就个人而言，我不会为这一切而烦恼。要么使用 GLR 解析器，要么使用野牛用于相同目的的相同技巧。或者使用上面答案中的简单语法，然后摆弄AST；这并不难。

于 2013-10-12T23:27:50.200 回答