CS 3240 Homework I

Due: Mon, Jan 30 by 6pm

Total  Points : 100

Guidelines:

 

  1. Work on the homework individually. Do not collaborate or copy from others

 

  1. The homework is due on Monday, Jan 30 by 6pm. No late submissions will be entertained

 

  1. Submit your homework in the box outside Prof. Pande’s office at CCB 222 (College of Computing building)

 

  1. Do not email your answers to either the Professor or the TA. Emailed answers will not be considered for evaluation

 

 

Scanning and Parsing

 

 

Let us consider the language of arithmetic expressions

 

The alphabet of this language is the set

{+, -, *, /, (, ), x, y, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

 

Note commas are not a part of the alphabet in the above set – they are only shown to separate elements of the set. That is, strings in this language can be composed only by using one or more of  the following

 + - * / ( ) x y 0 1 2 3 4 5 6 7 8 9

 

The tokens in this language are of the following classes

 

MOPER     : * /

AOPER     : + -

CONS      : Strings made of 0 through 9

VAR       : x y

OPARAN    : (

CPARAN    : )

 

Consider a compiler that scans and parses the language of arithmetic expressions

 

Question 1: As you scan the following expression from left to right, list the tokens and the token class identified by the scanner for each of the arithmetic expressions below. Identify, explain and clearly mark the errors if any                                     (30 points)

 

a.   ( x * ( y + 100 ) + y – ( x + y – 320 ) )

b.   ( y + 100 * x + ( 2 + x^3 ) / y )

c.   x * ) 4 + / 100 - y

d.   y * ( ( x + 100

e.   (20 + x * 4 / 30y3 )

 

The grammar for the language of arithmetic expressions is as follows

 

<EXPR>    →   <TERM> AOPER <TERM>

<EXPR>    →   <TERM>

<TERM>    →   <FAC> MOPER <FAC>

<TERM>    →   <FAC>

<FAC>     →   OPARAN <EXPR> CPARAN

<FAC>     →   VAR

<FAC>     →   CONS

 

 

Question 2: What are the terminals and non-terminals in this grammar?    (10 points)

 

Question 3: For each of the expressions below, scan it from left to right; list the tokens returned by the scanner and the rules used by the parser (showing appropriate expansions of the non-terminals) for matching. Identify, explain and clearly mark the errors if any                                                                 (40 points)

 

 

a.              ( x + y )

b.              ( y * - x ) + 10

c.              ( x * ( y + 10 ) )

d.              ( x + y ) * ( y + z )

e.              ( x + ( y – ( 2 ) )

 

 

Question 4: You are asked the count the number of constants (CONS), variables (VAR) and MOPER in an expression. Insert action symbols in the grammar described before Question 2, explain what semantic actions they trigger and what each semantic action does.                                                                                                                 (20 points)