Search code examples
recursioncontext-free-grammarbnfebnfcontext-free-language

Recursion in EBNF

The problem is:

a. Write a directly recursive EBNF rule named mp that describes all symbols that have matching parentheses: (), ()()(), ()(()()), and ((())())(()(()))(). It should not recognize (, ())(, or (()() as legal.
b. Write a tabular proof and its derivation tree showing how ()(()()) is recognized as legal.

So far I've thought of one plausible solution. I am not sure if it is correct or if I am missing something.

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

Any suggestions?

Solution

  • But, before it closes, here's what I'd have:

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

    Your second example, with n >= 0 and m >= 0 is not in BNF. Your first one should be acceptable however.

    Here's my derivation tree for ()(()()):

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