grammar - 解析平衡括号 CNF

Question

我有语法S -> (S)S | empty

我把它转换成这样的乔姆斯基范式

S -> AS | empty
A -> LB
B -> SR
L -> (
R -> )

我不确定我是否正确转换了它，但是如何使用 CNF 解析这个输入 ()()

Answer 1

反向执行以下推导：

  S        S → AS   
→ AS       A → LB
→ LBS      L → (
→ (BS      B → SR
→ (SRS     S → ε
→ (RS      R → )
→ ()S      S → AS   
→ ()AS     A → LB
→ ()LBS    L → (
→ ()(BS    B → SR
→ ()(SRS   S → ε
→ ()(RS    R → )
→ ()()S    S → ε
→ ()()