上下文无关文法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

您的评论说，你想和c的数量相等，所以开始用简单的语法，做的是：

：

S -> aSc | ε 

，并在任何数量的B的前加/后/之间的那些

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

请注意，以上不含糊（甚至LR（1））。

如果您想允许不同数量的a和c，您可以使用相同的方法来避免模糊性。开始只用A和C'S：

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

和B的开始处添加和对方字符后：

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

Answer 2

做的a's和c's数需要一致吗？如果不是那么你错过了那些不同的情况，例如：aac。我觉得这样的事情应该工作：

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

的A生产用于导出不属于字符序列的c和C生产用于导出那些不属于a的字符序列。