Context free grammar of calculator

10.5k Views Asked by At

Consider a grammar for calculator language.

This language consists of all arithmetic expressions that can be evaluated by a calculator, i.e. expressions of the form

             expression=

where "expression" is an arithmetic expression (without variables) to be evaluated. Examples of such expressions:

         6/-2=  or 12.5* 2+5=,

The grammar

     G=<V,T,P,calculation>

for the calculator language is defined by:

V={calculation, expression, value, number, unsigned, digit, sign, operator} T={0,1,2,3,4,5,6,7,8,9,+,-,*,/,=,.}

P consists of the following productions (rules):

  1. calculation -> expression =
  2. expression -> value | value operator expression
  3. value -> number | sign number
  4. number -> unsigned | unsigned . unsigned
  5. unsigned -> digit | digit unsigned
  6. digit -> 0| 1| 2| 3| 4| 5| 6| 7| 8| 9
  7. sign -> + | -
  8. operator -> +| -| *| /

Show:

(a) 100/2.5= is in the calculator language;

My answer:

a.

<calculation>

  => <expression> =
  => <value> <operator> <expression>  
  => <value> / <expression>
  => <number> / <expression>
  => <number> / <value>
  => <number> / <number>
  => <unsigned> / <unsigned . unsigned>
  => <digit><unsigned> / <digit . digit>
  => 1<digit><unsigned> / 2.5
  => 10<digit> / 2.5
  => 100 / 2.5
1

There are 1 best solutions below

11
On BEST ANSWER

The whole thing must be a <calculation>, because you are given that <calculation> is the start symbol. The symbol <calculation> must reduce , by rule 1, to <expression> =, because that is the only rule for reducing a <calculation>. Since your target string is 100/2.5=, the <expression> part must reduce to 100/2.5. (If 100/2.5= did not end with an = sign, there would be no way to match the grammar to the target string, and you would stop right away and report that the string was not in the language.)

Now because of rule 2, <expression> could reduce to <value>, or to <value> <operator> <expression>. Does 100/2.5 look to you like a single <value>, or does it look like a <value> followed by an <operator> followed by another <expression>?

Can you take it from here?