CS4613 Assignment 3

 

Due: Mon. Oct. 6

 

  1. Write EBNF descriptions for the following

a)      A Java class definition header statement

 

The following is an example class header statement:

 

public class A extends B implements C, D

 

where “public” is a modifier and “A” ,”B”, “C”, and “D” are identifiers. Assume non-terminal <id> is given.

 

b)      A C/C++/Java switch statement

 

The following is an example switch statement:

 

switch (a+b)

{

case 1 : x = 7; break;

case 2 :  x = 8; break;

default : x = 9;

            }

 

            where “a+b” is an expression, “1” and “2” are literals, and “x=7;break;”, “x=8;break;” and “x=9;” are statement lists. Assume non-terminals <expr>, <literal>, and <stmt_list> are given.

 

c)      A C/C++/Java for-loop statement

 

The following is an example for statement:

 

for (int k = 0, m = 100;  k < n;  k++, m++)

{

            x = x + 1;

            y = y – 1;

}

 

where “int k = 0, m = 100” is an variable declaration, in which “int” is a type name, “k” and “m” are identifiers, and “0” and “100” are literals. If  there is no appearance of “int”, “k = 0, m = 100” are a sequence of assignments. Also, “k < n” is an expression, “k++; m++” are also expressions, and “x=x+1;y=y+1;” is a statement list.

 

Assume the following non-terminals are given: <type>, <id>, <literal>, <assign>, <expr>, and <stmt_list>.   

 

  1. Prove that the following grammar is ambiguous:

 

<S> -> <A>

<A> -> <A> + <A> | <id>

<id> -> a | b | c

 

  1. Convert the following recursive BNF grammar to EBNF without recursion:

 

<assign> -> <id> = <expr>

<expr> -> <id> + <expr>

                 | <id> * <expr>

                 |  ( <expr> )

                 | <id>

 

  1. Convert the following EBNF grammar to BNF:

 

S -> A { b A}

A -> a [ b ] A

 

  1. Given the following BNF as the basis:

 

<assign> -> <id> = <expr>

<id> -> a

<id> ->  b

<id> ->  c

<expr> -> <id> + <expr>

            <expr> -> <id> * <expr>

            <expr> -> ( <expr> )

            <expr> -> <id>

 

            and give the following attribute grammar:

 

a.       Syntax rule: <assign> -> <var> = <expr>

Sementic rule: <expr>.expected_type <- <var>.actual_type

 

b.      Syntax rule: <expr> -> <var>[2] + <var>[3]

Semantic rule: <expr>.actual_type <- if (<var>[2].actual_type = int) and (<var>[3].actual_type = int) then int else real end if

Predicate: <expr>.actual_type = <expr>.expected_type

 

c.       Syntax rule: <expr> -> <var>

Semantic rule: <expr>.actual_type <- <var>.actual_type

Predicate: <expr>.actual_type = <expr>.expected_type

 

d.      Syntax rule: <var> -> A | B | C

Semantic rule: <var>.actual_type <- look-up(<var>.string)

 

            Write an attribute grammar for the given BNF with the same semantic rules as the given attribute grammar

 

  1. Modify the attribute grammar given in Question 5 with the following new semantic rules:

 

Data types cannot be mixed in expressions, but assignment statements need not have the same type on both sides of the assignment operator.