grammar - 上下文无关文法 BNF

Question

需要非扩展 BNF 语法的帮助：

Σ = {a,b,c}

L = {ω ɛ Σ^* | such that all a's (if any) comes before all c's(if any)}

例如，字符串 aba、cbc 和 abacbc 在语言中，但字符串 abcabc 不是。

这是我到目前为止所拥有的（正确吗？如果我错了，请纠正我）：

s->asbsc|bsasc|ascsb|ɛ

Answer 1

数量a's和c's需要相同吗？如果不是，那么您错过了它们不同的情况，例如：aac. 我认为这样的事情应该有效：

S -> AC
A -> aA | bA | ε
C -> bC | cC | ε

A产生式用于导出不是 a 的字符序列，产生式用于导出不是 ac的字符C序列a。

Answer 2

你的评论说你想要相等数量的 a 和 c，所以从简单的语法开始：

S -> aSc | ε

并在它们之前/之后/之间添加任意数量的 b：

S -> BaScB | B
B -> Bb | ε

请注意，上述内容并不模棱两可（甚至是 LR(1)）。

如果您想允许不同数量的 a 和 c，您可以使用相同的方法来避免歧义。从 a 和 c 开始：

S -> AC
A -> Aa | ε
C -> Cc | ε

并在开头和每个字符之后添加 b：

S -> BAC
A -> AaB | ε
C -> CcB | ε
B -> Bb | ε