0

我想解析一组表达式：R[3]C, R[2]C, R[3]C-R[2]C... 有一个我无法解决的冲突...

这是一部分lexer.mll：

  rule token = parse
  | 'R'            { R }
  | 'C'            { C }
  | "RC"           { RC }
  | ['0'-'9']+ as lxm { INTEGER (int_of_string lxm) }
  | '+'            { PLUS }
  | '-'            { MINUS }
  | '['            { LBRACKET }
  | ']'            { RBRACKET }
  | eof            { EOF }
  ...

的一部分parser.mly：

main:
   e_expression EOF                { $1 };

e_expression:
| ec = e_cell { EE_rc (Rc.Cell ec) }
| e_expression MINUS e_expression { EE_string_EEL ("MINUS", [$1; $3]) }

e_cell:
| R LBRACKET r = index RBRACKET C c = index { (Rc.I_relative r, Rc.I_absolute c) }
| R LBRACKET r = index RBRACKET C { (Rc.I_relative r, Rc.I_relative 0) }

index:
| INTEGER { $1 }
| MINUS INTEGER { Printf.printf "%n\n" 8; 0 - $2 }

奇怪的是，这段代码不起作用R[3]C-R[2]C，这里是parser.conflicts，我无法真正理解。

如果我注释行| R LBRACKET r = index RBRACKET C c = index ...中的行e_cell，代码可以解析R[3]C-R[2]C，where 3and 2are index，`R[3]Cand R[2]Care e_cell，and R[3]C-R[2]Cis e_expression。

有人可以帮忙吗？

4

2 回答 2

1

你的语法不是LALR(1)。事实上，它甚至不是LR(1)。

考虑以下两个有效e_expression的 s：

R[1]C-R[2]C
R[1]C-1-R[2]C

在第一种情况下，在我们移动 之后C，我们将得到以下结果：

R [ index ] C -R[2]C

然后我们希望它减少：

e_cell -R[2]C

并再次减少到

e_expression -R[2]C

接着

e_expression - e_expression

在第二种情况下，我们将得到：

R [ index ] C -1-R[2]C

接着

R [ index ] C - 1-R[2]C
R [ index ] C index -R[2]C
e_cell -R[2]C

（此时，我们已经到达了与第一个输入类似的位置，所以我将省略接下来的步骤）。

所以，在我们移动 之后C，前瞻是-，我们需要：

  1. 减少R [ index ] C到e_cell, 或

  2. 转移-，给予R [ index ] C -

如果没有更多的前瞻，我们无法分辨出哪个：以下标记必须是R（案例 1）或INTEGER（案例 2）。

所以我们可以说文法是 LALR(2)，除了关于减号的另一个移位归约冲突，这使得文法模棱两可，因此对于任何 k 都不是 LALR(k)。您可能已经使用运算符优先级声明处理过这个问题，但以防万一：

假设您已达到：

e_expression - e_expression

和前瞻是-。现在它可以减少e_expression - e_expression到e_expression然后移动-，导致：

e_expression -

或者它可以简单地改变-：

e_expression - e_expression -

无论我们阅读了多少前向上下文，都无法在这两者之间做出决定，因为它们都会导致有效的解析。第一个解析将使-左关联，第二个解析为右关联。

如果您不使用优先声明解决此问题，则可以选择以下选项之一，而不是e_expression: e_expression MINUS e_expression：

e_expression: e_cell MINUS e_expression
e_expression: e_expression MINUS e_cell

现在，如何解决原来的问题:)

如果-in-1可以被认为只是负整数的一部分，最简单的解决方案是让词法分析器处理它。然后解析器将看不到 a MINUSin R[-1]C-1，因此它不会尝试 reduce R[-1]C。

另一种解决方案是使用 GLR 解析器（显然有一个用于 OCaml，但我对此一无所知）。

最后，可以在给定 LR(2) 文法的情况下机械地创建 LR(1) 文法，以及提取原始分析树的机制。生成的语法通常臃肿且难以手写，但翻译可以自动完成。不幸的是，我不知道有任何 OCaml 工具可以做到这一点。基本思想是将每个非终结符分成一组对，这些对成为新的非终结符。您可以轻松地将所有现有规则扩展为新的非终结符集。现在，由于每个非终结符实际上都包含一个前瞻记号，因此在原始语言中，单记号前瞻等同于双记号前瞻。

于 2013-07-24T06:29:34.420 回答
0

所以问题似乎是，当它在 ] 之后看到一个“-”标记时，解析器不确定它是否正在创建索引，或者它是否正在分隔两个表达式。

即当解析器到达R[3]C-时，它不确定是否需要等待一个INTEGER 来完成e_cell 和reduce，还是现在reduce 并开始处理另一个e_expression。

解决这个问题的最好方法可能是将负整数代码移动到词法分析器中。我没有方便的 ocamllex 安装，但我想改变

['0'-'9']+

至

'-'? ['0'-'9']+

会起作用，然后从索引中删除负整数大小写（显然这会导致 Printf 语句出现问题，但您可以使内部逻辑更复杂来解决这个问题。

于 2013-07-23T22:11:35.383 回答