CS4613 Assignment 3

 

Sample Solution

 

  1. (15%) 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.

 

<method_head> -> [public] [(abstract | final)] class <id> [extends <id>] [implements <id> {, <id>}]

 

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.

 

      <switch> -> switch ‘(‘ <expr> ‘)’ ‘{‘ {case <literal> : <stmt_list>} [default : <stmt_list>] ‘}’

 

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>.   

 

<for> -> for ‘(‘ [[<type>] <id> = <expr> {, [<type>] <id> = <expr>}] ; [<expr>] ; [<expr> {, <expr>}] ‘)’ ‘{‘ <stmt_list> ‘}’

 

  1. (15%) Prove that the following grammar is ambiguous:

 

<S> -> <A>

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

<id> -> a | b | c

 

      Example ambiguous sentence: a + b + c

 

      Parse tree 1:

      <S>

                  <A>

                              <A>

                                          <A>

                                                      <id>

                                                                  a

                                          +

                                          <A>

                                                      <id>

                                                                  b

                              +

                              <A>

                                          <id>

                                                      c

 

      Parse tree 2:

      <S>

                  <A>

                              <A>

                                          <id>

                                                      a

                              +

                              <A>

                                          <A>

                                                      <id>

                                                                  b

                                          +

                                          <A>

                                                      <id>

                                                                  c

 

      Note in the above representation of a tree, all symbol(s) with  N column indentations are children nodes of the parent node that is immediately above these symbol(s) and has N-1 column indentations.

 

  1. (10%) Convert the following recursive BNF grammar to EBNF without recursion:

 

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

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

                 | <id> * <expr>

                 |  ( <expr> )

                 | <id>

 

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

            <expr> -> <id> {(+ | *) <term>}

            <term> -> ‘(‘ <expr> ‘)’

 

  1. (10%) Convert the following EBNF grammar to BNF:

 

S -> A { b A}

A -> a [ b ] A

 

S -> A | A B

B -> b A | b A B

A -> a A | a b A

 

  1. (30%) 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

 

a) <assign> -> <id> = <expr>

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

 

b) <expr>[1] -> <id> + <expr>[2]

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

Predicate: <expr>[1].actual_type = <expr>[1].expected_type

 

            c) <expr> -> <id> * <expr>

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

Predicate: <expr>[1].actual_type = <expr>[1].expected_type

 

            d) <expr>[1] -> ( <expr>[2] )

Semantic rule: <expr>[1].actual_type <- <expr>[2].actual_type

Predicate: <expr>[1].actual_type = <expr>[1].expected_type

 

            e) <expr> -> <id>

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

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

 

            f) <id> -> a | b | c

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

 

  1. (20%) 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.

 

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 <- <var>[2].actual_type

Predicate: <var>[2].actual_type = <var>.[3].actual_type

 

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

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

 

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

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