computer-science - 具有嵌套和不等式的上下文无关文法

Question

我一直找不到任何具有嵌套和不等式的上下文无关语法示例。

例如，我正在尝试为以下内容编写 CFG：

{aibjckdl : (i < l) ^ (j < k)}

因此，对于，CFG 将简单地为：{aidl : (i < l)}

S -> aSd | dS | d

b 和 c 的情况类似。但我不知道如何嵌套这两个语法。任何类似的示例或指针都会有所帮助。

Answer 1

在我看来，您可以回答您的问题：

S -> Ad | aSd | Sd
A -> Ac | c | bAc

该语法背后的概念是：首先创建一个表达式的一部分，其中 a 和 d 满足给定的条件，然后在 a 和 d 之间放置一个满足 b 和 c 条件的表达式。