上下文無關文法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的字符序列。