Question

You are given the following context free grammar in BNF format.
1 <expression> ::= <term> | <expression> "+" <term>

2 <term> ::= <factor> | <term> "*" <factor>

3 <factor> ::= <constant> | <variable> | "(" <expression> ")"

4 <variable> ::= "x" | "y" | "z"

5 <constant> ::= <digit> | <digit> <constant>

6 <digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

a) Show how the expression 4 * (2 * x + 7) can be reduced to the start symbol of the grammar. Apply only one rule in each step and try in every step to replace the leftmost symbol you can replace.

b) Is any additional information needed to reduce this expression in a meaningful way? Explain.

Answer 1

4*12*%+7) <digibst (2*x+7) <Const>* (2*x+7) <tactor>* (2*X+7) < terms * (2*x+7) <teem? * (<digit> * X+7) <tem> * Kconst >.* X+7) <teem> *(Stactor 4* X+7) <teem 3(< ferm>* X+7)

<lam * ( <lem>*<vaciable> 4.7) <tcim> (<teem) 4 rlockor "+7) skeemo » * 1 <lema ) Lterms * (<Expiremian+7) <teems* ( clxpresionat (digit)) <teem) (expressim>+< Constant)) <teim) * (<-Exprelion >+ <foctor>) <Heim) * 1 < Expression>+<teim ») < km» я (L€xxelan>) <teems *<factors <terms <Expression> . It is reduced to start symbol Expression B) No, the BNF is in a meaningful way. This information is deefficient to reduce the string.