相关疑难解决方法(0)

考虑以下语法:

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.

在正式语言的乔姆斯基分类中，我需要一些Non-Linear, Unambiguous and also Non-Deterministic上下文无关语言（N-CFL）的例子吗？

1. 线性语言：对于哪些线性文法是可能的（？CFG）例如
   L ₁ = {a ⁿ b ⁿ | ? 0 }

2. 确定性上下文无关语言（D-CFG）：对于哪些确定性下推自动机（D-PDA）是可能的，例如
   L ₂ = {a ⁿ b ⁿ c ^m | ? 0，米？0 }
   L ₂是明确的。

非线性的CF 文法是非线性的。
L _nl = {w: n _a (w) = n _b (w)} 也是一个非线性 CFG。

-- 3. Non-Deterministic Context Free Language(N-CFG) : 对于哪个only Non-Deterministic Push-Down-Automata(N-PDA)是可能的，例如
L ₃ = {ww ^R | ? {a, …