1

我发现在为该语言构建语法时遇到困难，尤其是对于线性语法。

谁能给我一些基本的技巧/方法，我可以为任何语言构建语法？提前致谢

我怀疑这个问题的答案“为语言构建线性语法：是否正确

L ={a^nbc^n | n 属于自然数}

解决方案：

右线性语法：

S--> 作为 | bA

A--> cA | ^

左线性语法：

S--> Sc | 抗体

A--> Aa | ^

4

1 回答 1

0

正如评论中所指出的，这些语法是错误的，因为它们生成的字符串不是该语言。abcc这是两种语法的推导：

S -> aS -> abA -> abcA -> abccA -> abcc
S -> Sc -> Scc -> Abcc -> Aabcc -> abcc

同样正如评论中所指出的，这种语言有一个简单的线性语法，其中线性语法被定义为在任何产生式的 RHS 中最多有一个非终结符：

S -> aSc | b

为语言构建语法有一些一般规则。这些要么是显而易见的简单规则，要么是源自闭包属性和语法工作方式的规则。例如：

  1. 如果L = {a}是一个字母符号a，那么S -> a是一个伽玛L。
  2. ifL = {e}对于空字符串e，thenS -> e是L.
  3. 如果L = R U T对于语言R和T，那么S -> S' | S''与语法一起R和T是语法L如果S'是语法的开始符号R并且S''是语法的开始符号T。
  4. ifL = RT对于语言R和T, thenS = S'S''是一个文法LifS'是文法的开始符号R并且S''是文法的开始符号 for T。
  5. ifL = R*对于语言R，thenS = S'S | e是语法，L如果S'是语法的开始符号R。

所写的规则 4 和 5 不保持线性。可以为左线性和右线性文法保留线性（因为这些文法描述了常规语言，而常规语言在这些操作下是封闭的）；但一般不能保持线性。为了证明这一点，一个例子就足够了：

R -> aRb | ab
T -> cTd | cd

L  = RT = a^n b^n c^m d^m, 0 < a,b,c,d
L' = R* = (a^n b^n)*, 0 < a,b

假设 有一个线性文法L。我们必须有一个S产生某些东西的开始符号的产生式。为了产生一些东西，我们需要一串终端和非终端符号。要成为线性的，我们最多只能有一个非终结符。也就是说，我们的生产必须是形式

S := xYz

其中 x 是一串终结符，Y 是单个非终结符，z 是一串终结符。如果x为非空，则反射显示唯一有用的选择是a; 其他任何东西都无法派生该语言中的已知字符串。同样，如果z是非空的，唯一有用的选择是d。这给出了四种情况：

  1. x空的，z空的。Y这是没用的，因为我们现在要解决非终结符的问题与解决S.
  2. x = a, 为z空。Y现在必须准确生成a^n' b^n' b c^m d^mwhere n' = n - 1。但是，完全相同的论点适用于起始符号为 的文法Y。
  3. x空，z = d。Y现在必须准确生成a^n b^n c c^m' d^m'where m' = m - 1。但是，完全相同的论点适用于起始符号为 的文法Y。
  4. x = a, z = d. Y现在必须准确地生成a^n' b^n' bc c^m' d^m'wheren'和m'are 与 2 和 3 一样。但是完全相同的参数适用于起始符号为 的文法Y。

对于有用的产生式来说，没有一个可能的选择S实际上对让我们更接近语言中的字符串有用。因此，没有导出字符串，这是矛盾的，这意味着 for 的语法L不能是线性的。

假设有一个语法L'。然后该语法必须生成 中的所有字符串(a^n b^n)R(a^m b^m)，以及 中的字符串e + R。但它不能通过上面使用的论点生成前者：任何对此有用的产生式都不会让我们更接近语言中的字符串。

于 2017-10-13T18:01:03.510 回答