EBNF中的递归

Question

问题是：

a.编写一个名为mp的直接递归EBNF规则，该规则描述所有具有匹配括号的符号：()、()()()、()(()())和((())())(()(()))()。它不应该承认(、())(或(()()是合法的。

编写表格证明及其派生树，说明()(()())是如何被确认为合法的。

到目前为止，我已经想出了一个可行的解决方案。我不确定这是正确的，还是我遗漏了什么。

<mp> ::= "" | ( <mp> "(" <mp> ")" ) 

有什么建议吗？

Answer 1

但是，在它结束之前，我要说的是：

mp := ( mp ) mp
mp := ''

使用n >= 0和m >= 0的第二个示例不在BNF中。不过，你的第一个应该是可以接受的。

这是我的()(()())派生树

mp
( mp ) mp
( '' ) mp
()( mp ) mp
()( mp ) ''
()(( mp ) mp )
()(( '' ) mp )
()(()( mp ) mp )
()(()( mp ) '' )
()(()( '' ))
()(()())