我发现在为语言构建语法方面存在困难，尤其是线性语法 .
任何人都可以给我一些基本的技巧/方法，我可以为任何语言构建语法吗？提前致谢
我怀疑这个问题的答案是“构建语言的线性语法：是对的
L = {a ^ n b c ^ n | n属于Natural numbers}
解：
右线性语法：
S - > aS | BA
A - > cA | ^
左线性语法：
S - > Sc |抗体
A - > Aa | ^
正如评论中指出的那样，这些语法是错误的，因为它们生成的语言不是语言 . 这是两个语法中 abcc 的派生：
abcc
S -> aS -> abA -> abcA -> abccA -> abcc S -> Sc -> Scc -> Abcc -> Aabcc -> abcc
同样如评论中所指出的，这种语言有一个简单的线性语法，其中线性语法被定义为在任何产品的RHS中至多有一个非终结符号：
S -> aSc | b
为语言构造语法有一些通用规则 . 这些是明显的简单规则或从闭包属性和语法工作方式派生的规则 . 例如：
如果 L = {a} 为字母符号 a ，则 S -> a 是 L 的gammar .
L = {a}
a
S -> a
L
如果 L = {e} 为空字符串 e ，那么 S -> e 是 L 的语法 .
L = {e}
e
S -> e
如果 L = R U T 用于语言 R 和 T ，那么 S -> S' | S'' 以及 R 和 T 的语法是 L 的语法，如果 S' 是 R 的语法的起始符号， S'' 是 T 语法的起始符号 .
L = R U T
R
T
S -> S' | S''
S'
S''
如果 L = RT 用于语言 R 和 T ，则 S = S'S'' 是 L 的语法，如果 S' 是 R 的语法的起始符号， S'' 是 T 语法的起始符号 .
L = RT
S = S'S''
如果 L = R* 用于语言 R ，则 S = S'S | e 是 L 的语法，如果 S' 是 R 的语法的起始符号 .
L = R*
S = S'S | e
如上所述，规则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
S := xYz
其中x是一串终端，Y是单个非终结符号，z是一串终端 . 如果 x 非空，则反射显示唯一有用的选择是 a ;其他任何东西都无法在语言中派生已知的字符串 . 同样，如果 z 非空，唯一有用的选择是 d . 这给出了四种情况：
x
z
d
x 为空， z 为空 . 这是没用的，因为我们现在有同样的问题要解决非终结 Y ，正如我们对 S 所做的那样 .
Y
x = a ， z 为空 . Y 现在必须完全生成 a^n' b^n' b c^m d^m ，其中 n' = n - 1 . 但是，完全相同的参数适用于其起始符号为 Y 的语法 .
x = a
a^n' b^n' b c^m d^m
n' = n - 1
x 空， z = d . Y 现在必须完全生成 a^n b^n c c^m' d^m' ，其中 m' = m - 1 . 但是，完全相同的参数适用于其起始符号为 Y 的语法 .
z = d
a^n b^n c c^m' d^m'
m' = m - 1
x = a ， z = d . Y 现在必须完全生成 a^n' b^n' bc c^m' d^m' ，其中 n' 和 m' 与2和3中的相同 . 但是，完全相同的参数适用于其起始符号为 Y 的语法 .
a^n' b^n' bc c^m' d^m'
n'
m'
对于 S 的有用 生产环境 而言，没有一种可能的选择对于让我们更接近语言中的字符串非常有用 . 因此，没有派生出任何字符串，这是一个矛盾，意味着 L 的语法不能是线性的 .
假设 L' 有一个语法 . 然后该语法必须生成 (a^n b^n)R(a^m b^m) 中的所有字符串，以及 e + R 中的字符串 . 但它不能通过上面使用的参数生成前者中的那些：任何对此目的有用的 生产环境 都会使我们不再接近语言中的字符串 .
L'
(a^n b^n)R(a^m b^m)
e + R
1 回答
正如评论中指出的那样，这些语法是错误的，因为它们生成的语言不是语言 . 这是两个语法中
abcc的派生：同样如评论中所指出的，这种语言有一个简单的线性语法，其中线性语法被定义为在任何产品的RHS中至多有一个非终结符号：
为语言构造语法有一些通用规则 . 这些是明显的简单规则或从闭包属性和语法工作方式派生的规则 . 例如：
如果
L = {a}为字母符号a，则S -> a是L的gammar .如果
L = {e}为空字符串e，那么S -> e是L的语法 .如果
L = R U T用于语言R和T，那么S -> S' | S''以及R和T的语法是L的语法，如果S'是R的语法的起始符号，S''是T语法的起始符号 .如果
L = RT用于语言R和T，则S = S'S''是L的语法，如果S'是R的语法的起始符号，S''是T语法的起始符号 .如果
L = R*用于语言R，则S = S'S | e是L的语法，如果S'是R的语法的起始符号 .如上所述，规则4和5不保持线性 . 对于左线性和右线性语法，可以保留线性（因为这些语法描述了常规语言，而常规语言在这些操作下是封闭的）;但是线性一般不能保留 . 为了证明这一点，一个例子就足够了：
假设
L有一个线性语法 . 我们必须有一个产生起始符号S，它产生一些东西 . 为了产生某种东西，我们需要一串终端和非终结符号 . 要线性，我们必须至多有一个非终结符号 . 也就是说，我们的 生产环境 必须是这种形式其中x是一串终端，Y是单个非终结符号，z是一串终端 . 如果
x非空，则反射显示唯一有用的选择是a;其他任何东西都无法在语言中派生已知的字符串 . 同样，如果z非空，唯一有用的选择是d. 这给出了四种情况：x为空，z为空 . 这是没用的，因为我们现在有同样的问题要解决非终结Y，正如我们对S所做的那样 .x = a，z为空 .Y现在必须完全生成a^n' b^n' b c^m d^m，其中n' = n - 1. 但是，完全相同的参数适用于其起始符号为Y的语法 .x空，z = d.Y现在必须完全生成a^n b^n c c^m' d^m'，其中m' = m - 1. 但是，完全相同的参数适用于其起始符号为Y的语法 .x = a，z = d.Y现在必须完全生成a^n' b^n' bc c^m' d^m'，其中n'和m'与2和3中的相同 . 但是，完全相同的参数适用于其起始符号为Y的语法 .对于
S的有用 生产环境 而言，没有一种可能的选择对于让我们更接近语言中的字符串非常有用 . 因此，没有派生出任何字符串，这是一个矛盾，意味着L的语法不能是线性的 .假设
L'有一个语法 . 然后该语法必须生成(a^n b^n)R(a^m b^m)中的所有字符串，以及e + R中的字符串 . 但它不能通过上面使用的参数生成前者中的那些：任何对此目的有用的 生产环境 都会使我们不再接近语言中的字符串 .