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):
- calculation -> expression =
- expression -> value | value operator expression
- value -> number | sign number
- number -> unsigned | unsigned . unsigned
- unsigned -> digit | digit unsigned
- digit -> 0| 1| 2| 3| 4| 5| 6| 7| 8| 9
- sign -> + | -
- 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
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 is100/2.5=, the<expression>part must reduce to100/2.5. (If100/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>. Does100/2.5look 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?