grammar - 不受限制的语法：{ sss | s 存在于 {a,b}* }

Question

什么是为 sss 构建不受限制的语法的方法？我知道为了构造 ss，你需要构造 ss^r 然后重新反转第二个字符串，但是对于 sss 该怎么做呢？

Answer 1

这可能有一些错误，但这个想法应该让你走上正轨。

// section 1
S := LTR
T := ATWX | BTYZ | N

// section 2
WW' := W'W
WY' := Y'W
YW' := W'Y
YY' := Y'Y

// section 3
WX' := W'X'
WZ' := W'Z'
YX' := Y'X'
YZ' := Y'Z'

// section 4
XW' := W'X
XX' := X'X
XY' := Y'X
XZ' := Z'X
ZW' := W'Z
ZX' := X'Z
ZY' := Y'Z
ZZ' := Z'Z

// section 5
XR  := X'R
ZR  := Z'R

// section 6
NW' := W'N
NX' := X'N
NY' := Y'N
NZ' := Z'N
NR  := Q

// section 7
AQ  := Qa
W'Q := Qa
X'Q := Qa
BQ  := Qb
Y'Q := Qb
Z'Q := Qb
LQ  := e

第 1 节列出了基本方案。我们将用 L 和 R 标记我们工作空间的开始和结束，使其非常明确。T 是我们的工作空间，L 和 R 是左右标记。我们的工作空间可以添加三个as（这些是 A、W 和 X 稍后将变为的）或添加三个bs（这些是 B、Y 和 Z 将稍后变为）或者它可以通过生成特殊的非终结符 N 来退出。 N 将把我们的非终结符串变成一串终结符，我们稍后会看到。

所以我们xxx需要xin (a+b)*。A并且由于我们设置制作的方式而B被添加到第一个的末尾。x第 2 节的工作是确保将WandY添加到 second 的末尾x。不幸的是，我们的作品将WandY放在了第二个的开头，x因此，如果没有更正，我们最终会得到xx^R. W第 2 节通过将and向右“浮动”来纠正这个问题，Y只要它们在 a or 的左侧，W或者Y已经找到了合适的位置。Ws 和Ys 不能相互传递，因此这保证了一旦音乐停止它们将以正确的顺序结束。

第 3 节展示了第二次出现的符号如何x找到它们的正确位置。基本上，他们向右移动（基于第 2 节），直到他们x在适当的位置找到第三个符号。由于第二个x符号在第三个符号之前有其适当的位置，所以在第三个符号（或）x之前的最后一个可能的右边是第二个符号的正确位置。所以我们一直浮动到第二个结尾。xXZxx

我们在第 4 节中对第三个重复该过程x，尽管我们必须让这些符号 (X和Z) 浮过来自第二个或第三个x已经找到其正确位置的所有符号。这些符号不能自行传递，因此按照我们在第 2 节中看到的相同逻辑，我们将以正确的顺序获取符号。

第 5 节说明何时停止构成x右侧第三个的浮动符号。还记得工作空间标记的结束R吗？第三个符号的最后一个符号x一直出现在右边，就在 之前R。所以那时我们知道我们已经找到了符号的正确位置。

第 6 节开始完成我们的推导过程。我们有一串可爱的非终结符，我们想把它们变成终结符。我们要做的第一件事是N向右浮动，越过第二个和第三个xs 的正确放置的符号，一直到字符串 marker 的末尾R。我们不需要R任何东西，所以我们转换N为Q. 正如我们将在下一节中看到的，Q是什么让魔法发生了。

第 7 节概述了Q浮点数如何在整个非终结符字符串中返回，这些非终结符一直找到它们的正确位置，一路L将非终结符更改为正确的终结符。一旦找到L，它就会消除两个非终结符，只留下一串终结符。推导完成。

为了说明这个过程，让我们生成aabaabaab.

S
-> LTR 
-> LATWXR 
-> LAATWXWXR 
-> LAABTYZWXWXR
-> LAABNYZWXWXR
-> LAABNYZWXWX'R
-> LAABNYZWXW'X'R
-> LAABNYZWW'XX'R
-> LAABNYZWW'X'XR
-> LAABNYZWW'X'X'R
-> LAABNYZW'WX'X'R
-> LAABNYZW'W'X'X'R
-> LAABNYW'ZW'X'X'R
-> LAABNYW'W'ZX'X'R
-> LAABNYW'W'X'ZX'R
-> LAABNYW'W'X'X'ZR
-> LAABNYW'W'X'X'Z'R
-> LAABNW'YW'X'X'Z'R
-> LAABNW'W'YX'X'Z'R
-> LAABNW'W'Y'X'X'Z'R
-> LAABW'NW'Y'X'X'Z'R
-> LAABW'W'NY'X'X'Z'R
-> LAABW'W'Y'NX'X'Z'R
-> LAABW'W'Y'X'NX'Z'R
-> LAABW'W'Y'X'X'NZ'R
-> LAABW'W'Y'X'X'Z'NR
-> LAABW'W'Y'X'X'Z'Q
-> LAABW'W'Y'X'X'Qb
-> LAABW'W'Y'X'Qab
-> LAABW'W'Y'Qaab
-> LAABW'W'Qbaab
-> LAABW'Qabaab
-> LAABQaabaab
-> LAAQbaabaab
-> LAQabaabaab
-> LQaabaabaab
-> aabaabaab