grammar - 构建语言的语法

Question

我有一个关于这个问题的问题：

L= 空，其中字母为 {a,b}

如何为此创建语法？怎么会有生产规则？提前致谢

Answer 1

文法 G 是一个有序的 4 元组 {S, N, E, e, P}，其中：

1. N 是一组非终结符号
2. E 是一组终端符号
3. N 和 E 不相交
4. E 是 L(G) 的字母表的超集
5. e 是空字符串
6. P 是 (NUEU e) 的一组有序元素对；也就是说，P 是 (NUEU e) X (NUEU e)* 的子集。
7. S，起始符号，在 N 中

G 中的推导是 (NUEU e)* 的元素序列，使得：

1. 第一个元素是 S
2. 相邻元素 w[i] 和 w[i+1] 可以写成 w[i] = uxv 和 w[i+1] = uyv 使得 (x, y) 在 P

如果 G 中有一个推导，其最后一个元素是 (EU e)* 上的字符串 w[n]，我们说 G 生成 w[n]；也就是说，w[n] 在 L(G) 中。

现在，我们要定义一个文法 G，使得 L(G) 是空集。我们固定字母表 E = {a, b}。我们仍然必须定义：

1. N，非终结符的集合
2. S，开始符号
3. P、产品

我们不妨把 S 作为我们的开始符号。所以N至少包含S；N 是 {S} 的超集。如果我们确定需要它们，我们只会添加更多的非终结符。让我们把注意力转向 L(G) 为空的情况。

如果 L(G) 为空，则意味着 G 中没有导致仅包含终端符号的字符串的推导。我们可以很容易地做到这一点，确保我们所有的产品在任何终端上都至少产生一个非终端。或者根本不生产终端。所以以下语法都可以工作：

S := S

或者

S := aSb

或者

S := aXb | XXSSX
X := aabbXbbaaS

等等。所有这些文法的 L(G) 都是空的，因为它们都不能导出非终结符字符串。