1

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
geforce
  • 217

1 Answers1

2

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?

MY USER NAME IS A LIE
  • 737
  • Hi thanks for clearing it up for me. It makes more sense the way you described it. When you have time can you take a look at my edited answer? – geforce Jan 31 '15 at 23:22
  • Your answer does not make sense to me. I don't know what <NR> means; does it mean you are too lazy to type out <number>? If so, then your solution that begins at "My answer: a." is incomplete, because it shows <number> reducing directly to 100, but you cannot do that; you can only use rule 4, which says that <number> reduces to <unsigned> or <unsigned> . <unsigned>, and then you must use rule 5 to reduce <unsigned>. – MY USER NAME IS A LIE Jan 31 '15 at 23:46
  • I don't know what means either, in my lecture my professor used it many times but I guess its redundant. I will edit it without hashtags. – geforce Jan 31 '15 at 23:57
  • Ok i edited it, one question. At the second last line i say but it is supposed to be 100 so doesn't that mean I use 3 digits? – geforce Feb 01 '15 at 00:04
  • No, rule 6 says that <digit> can produce only one digit. it cannot produce 100. And there is no rule that says you can reduce <unsigned> to <digit><digit><digit>; the only rule you can use is rule 5, which says you can replace <unsigned> with <digit> or with <digit><unsigned>. – MY USER NAME IS A LIE Feb 01 '15 at 00:08
  • Ok then this will work with rule 5. – geforce Feb 01 '15 at 00:14
  • Your first step seems to combine two steps into one. Better separate them, or the grader might think you don't know what you are doing. – MY USER NAME IS A LIE Feb 01 '15 at 00:16
  • the expression = part? – geforce Feb 01 '15 at 00:17
  • Ok i separated it. Im guessing each line is restricted to 1 operation when changing rules? – geforce Feb 01 '15 at 00:19
  • Either way, thanks a lot. You just taught me CFGs basically because before this post I did not understand anything. – geforce Feb 01 '15 at 00:30
  • This idea is really important; it's the practical basis of all computer parsing methods. Writing parsers is something professional programmers have to do all the time. – MY USER NAME IS A LIE Feb 01 '15 at 02:02