recursion - EBNF 中的递归

Question

问题是：

一种。编写一个名为的直接递归 EBNF 规则mp，该规则描述具有匹配括号的所有符号：()、()()()、()(()())和((())())(()(()))(). 它不应该承认(, ())(, 或(()()合法。
湾。写一个表格证明及其推导树，显示如何()(()())被认为是合法的。

到目前为止，我已经想到了一个合理的解决方案。我不确定它是否正确，或者我是否遗漏了什么。

<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 ) '' )
()(()( '' ))
()(()())