Search code examples
grammarexpression-treesbnf

Consider the following BNF Grammar

Consider the following BNF grammer (where non-terminals are enclosed in angle-brackets and <identifier> matches to any legal Java variable identifier).

<exp> ::= <exp> + <term>
      |   <exp> - <term>
      |   <term>
<term> ::= <term> * <factor>
       |   <term> / <factor>
       |   <factor>
<factor> ::= ( <exp> )
         |   <identifier>

Produce a derivation three for the following expression:

(x - a) * (y + b)

Staring with exp:

<exp>

replace exp with term:

<term>

replace term with:

<term> * <factor>

replace term with factor:

<factor> * <factor>

replace both factors with (exp):

( <exp> ) * ( <exp> )

replace the first exp with exp - term and the second with exp + term

( <exp> - <term> ) * ( <exp> + <term> )

replace both exp's with term, and then replace all 4 terms with factors.

( <factor> - <factor> ) * ( <factor> + <factor> )

replace all factors with identifiers

( <identifier> - <identifier> ) * ( <identifier> + <identifier> )

Does this suffice?

Solution

  • You need to go one step further - <factor> is a nonterminal, and you should reduce it down to <identifier>.

    Additionally, you should be starting from <expr> (and then reducing it to <term>) rather than starting from <term> directly.