EBNF 中的递归

Question

问题是：

一个。编写一个名为 mp 的直接递归 EBNF 规则，描述所有具有匹配括号的符号：()、()()()、()(()()) 和 ((())())(()(()))()。它不应将 (、())( 或 (()() 识别为合法的。
b.写一个表格证明和它的推导树来展示()(()())是如何被认为是合法的。

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

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

EBNF 中的递归

Recursion in EBNF

recursion

context-free-grammar

bnf

ebnf

context-free-language