规范化语法中的结构差异

Question

考虑以下语法:

S ? A | B
A ? xy
B ? xyz

这是我认为LR(0)解析器在给定输入时会做的事情xyz:

    | xyz   ? shift
  x | yz    ? shift
 xy | z     ? reduce
  A | z     ? shift
 Az |       ? fail

如果我的假设是正确的,我们将规则B改为:

B ? Az

现在语法突然被LR(0)解析器接受了.我认为这个新语法描述了与本问题中第一个语法完全相同的字符串集.

• 第一个和第二个语法之间有什么区别？
• 我们如何将语法中的结构差异与他们描述的语言分开？
  • 通过规范化？
  • 什么样的规范化？

进一步澄清:

我想向解析器描述一种语言,而语法结构不起作用.我想获得一组字符串的最小/基本描述.对于LR(k)语法,我想最小化k.

Answer 1

我认为你的LR(0)解析器不是标准解析器：

\n\n

\n
• 来源
\n

\n\n

\n

LR(0) 解析器是一种移位/归约解析器，它使用零个先行标记来确定要采取的操作（因此为 0）。这意味着在解析器的任何配置中，解析器必须有一个明确的操作可供选择 - 要么移动特定的符号，要么应用特定的约简。如果有两个或多个选择要做，解析器就会失败，我们就说语法不是 LR(0)。

\n

\n\n

所以，当你有：

\n\n

S->A|B\nA->xy\nB->Az\n

\n\n

或者

\n\n

S->A|B\nA->xy\nB->xyz\n

\n\n

LR(0)永远不会检查B规则，对于他们两个来说，它都会失败。

\n\n

State0 - Clousure(S->\xc2\xb0A):\n   S->\xc2\xb0A\n   A->\xc2\xb0xy\n\n Arcs:\n  0 --> x --> 2\n  0 --> A --> 1\n-------------------------\n\nState1 - Goto(State0,A):\n   S->A\xc2\xb0\n\n Arcs:\n  1 --> $ --> Accept\n-------------------------\n\nState2 - Goto(State0,x):\n   A->x\xc2\xb0y\n\n Arcs:\n  2 --> y --> 3\n-------------------------\n\nState3 - Goto(State2,y):\n   A->xy\xc2\xb0\n\n Arcs:\n-------------------------\n

\n\n

但如果你有

\n\n

I->S\nS->A|B\nA->xy\nB->xyz                           or B->Az\n

\n\n

他们都会接受xyz，但状态不同：

\n\n

State0 - Clousure(I->\xc2\xb0S):\n   I->\xc2\xb0S\n   S->\xc2\xb0A\n   S->\xc2\xb0B\n   A->\xc2\xb0xy                           A->\xc2\xb0xy, $z\n   B->\xc2\xb0xyz                          B->\xc2\xb0Az, $\n\n Arcs:\n  0 --> x --> 4\n  0 --> S --> 1\n  0 --> A --> 2\n  0 --> B --> 3\n-------------------------\n\nState1 - Goto(State0,S):\n   I->S\xc2\xb0\n\n Arcs:\n  1 --> $ --> Accept\n-------------------------\n\nState2 - Goto(State0,A):\n   S->A\xc2\xb0                            S->A\xc2\xb0, $ \n                                    B->A\xc2\xb0z, $\n Arcs:                              2 --> z --> 5\n-------------------------\n\nState3 - Goto(State0,B):\n   S->B\xc2\xb0\n\n Arcs:\n-------------------------\n\nState4 - Goto(State0,x):\n   A->x\xc2\xb0y                            A->x\xc2\xb0y, $z\n   B->x\xc2\xb0yz\n\n Arcs:\n  4 --> y --> 5                     4 --> y --> 6\n-------------------------\n\nState5 - Goto(State4,y):            - Goto(State2,z):\n   A->xy\xc2\xb0                           B->Az\xc2\xb0, $\n\n Arcs:\n  5 --> z --> 6                     -<None>-\n-------------------------\n\nState6 - Goto(State5,z):            - Goto(State4,y)\n   B->xyz\xc2\xb0                          A->xy\xc2\xb0, $z\n\n Arcs:\n-------------------------\n

\n\n

你可以看到Goto Table和Action Table是不同的。

\n\n

[B->xyz]                                  [B->Az]\n  | Stack   | Input  | Action               | Stack   | Input  | Action\n--+---------+--------+----------          --+---------+--------+----------\n1 | 0       | xyz$   | Shift              1 | 0       | xyz$   | Shift \n2 | 0 4     | yz$    | Shift              2 | 0 4     | xy$    | Shift\n3 | 0 4 5   | z$     | Shift              3 | 0 4 6   | z$     | Reduce A->xy\n4 | 0 4 5 6 | $      | Reduce B->xyz      4 | 0 2     | z$     | Shift \n5 | 0 3     | $      | Reduce S->B        5 | 0 2 5   | $      | Reduce B->Az\n6 | 0 1     | $      | Accept             6 | 0 3     | $      | Reduce S->B\n                                          7 | 0 1     | $      | Accept\n

\n\n

只需当您更改B->xyz为您B->Az添加一个以查找您可以检查的差异（构造 LR(0) 解析表）ActionLR TableAction TableGoto Table

\n\n

\n

• 当您有A->xy时B->xyz，您有两个底部手柄 [xy或xyz]，但当您有时B->Az，您只有一个底部手柄 [ xy] 可以接受额外的z。

\n

• 我认为与局部优化有关 -c=a+b; d=a+b -> c=a+b；d=c-当你使用时B->Az你会进行B->xyz优化。

\n

\n