330 Assignment 4 - Included in document. PDF

Preview

Summary

Included in document....

Description

Objectives:  Learn more about syntax and semantics  Learn writing CFG and BNF grammars  Construct parse trees and resolve ambiguity  Learn more about static semantics (attribute grammar)  Learn more about dynamic semantics (operational, denotational and axiomatic semantics) Part 1: Book Exercises Chapter 3: 2.Write EBNF descriptions for the following: a. A Java class definition header statement {} class [extends class_name][implements {, }] public | abstract | final b. Java method call statement {} class [extends class_name][implements {, }] public | abstract | final A C switch statement -> ( ) { case : { ; } { case : { ; }} [ default : { ; } ] } d. A C union definition -> union ; -> -> int | float | long |char | double ->

c.

e. C float literals float_num> -> -> 12.4 | 34.98 | 89.67

6. aUs i ngt heg r a mma ri nExa mpl e3 . 2 ,s ho wapa r s et r e ea ndal e f t mo s t de r i v a t i o nf o re ac hoft hef o l l o wi ngs t a t e me nt s : A = A * (B + (C * A))

Leftmost derivation:  =  A=  A=*  A=A*  A=A*()  A= A*(+)  A= A*(B+)  A= A*(B+())  A= A*(B+(*))  A= A*(B+(C*))  A= A*(B+(C*A)) Pa r s et r e e :

/

| A

| \ =

/ | \ * | A

/| \ () /

|

+

\

|

/ | \ B

() / | \ * |

|

C

| A

8.Pr o v et ha tt hef o l l o wi ngg r amma ri sambi g uo us :    A>+ < |  a|b|c

>Twopa r s et r e e sf r o m as i n g l ec on s t r u c tpr o v ei t sa mbi gu i t y . Exa mp l e :a=a+b+c 1st: 

/

/|\

|

= + |

|

/|\



+

|

|

|

|

a

a



|

|

b

c

2nd: 

/

/|\

|

= +

|

/|\

|

+

|

|

|

|

a



c

|

|

a

b

10 . De s c r i be ,i nEng l i s h,t hel a ng uag ede fine dbyt hef o l l o wi nggr a mmar :  

 a|a  b|b  c|c >Th i sgr a mma rme a n st h a tc a nbea n yn umbe rwhi c hi s>0a ndi s f o l l o we db ya n yn u mb e ro fba nda n yn umbe ro fc .Fo re x a mp l e : a b bc c c 13. Write a grammar for the language consisting of strings that have n copies of the letter a followed by the same number of copies of the letter b, where n > 0. For example, the strings ab, aaaabbbb, and aaaaaaaabbbbbbbb are in the language but a, abb, ba, and aaabb are not. → | → a → b 18. What is the difference between an intrinsic attribute and a nonintrinsic synthesized attribute? -> An intrinsic attribute is an inherent characteristic of a terminal symbol in the grammar like an identifier. Thus, the value of this attribute can only be determined from the terminal symbol. A nonintrinsic synthesized attribute is an attribute of a non-terminal symbol in the grammar. The value of this attribute depends on the values of the attributes in the children of that non-terminal symbol’s node in the parse tree.

21.Using the virtual machine instructions given in Section 3.5.1.1, give an operational semantic definition of the following: C++ if-then-else C switch c. c++ if-then-else if(condition){ ; ; } else{ ; ; }

e. C switch switch (condition){ case 1: ; break; 22. Wr i t eade no t at i o nals e ma nt i c sma ppi ngf unc t i o nf o rt hef o l l o wi ng s t a t e me nt s :

J a v aBo o l e ane xpr e s s i o ns >

J a v afor > [endif] Assume the semantics mapping functions Massign, Mbexpr, are Mstmts given. Mfor(for ( ; ; ) {}, S) = If Massign(, S) = error then error else if Mbexpr(, S’) = error then error else if Mbexpr(, S’) = false then S’ else if Mstmts(, S’) = error then error else if Massign(, S’’) = error then error else Mfor(for( ; ; ) {}, S’’’) where S’ = Massign(, S) S’’ = Mstmts(, S’) S’’’ = Massign(, S’’)

Cswitch

Msw((expr), s)== if VARMAP (X, s) == undef then error else VARMAP ((var), s) case (exp) of (cond_exp1) => if Mst (L, s) == error then error else Mst (L, s) (default_exp) => if Mst (L, s) == error then error

23 . Co mput et hewe a ke s tpr e c o ndi t i o nf o re a c ho ft hef ol l o wi ngas s i g nme nt s t a t e me nt sandpo s t c o ndi t i o ns : a = a + 2 * b - 1 {a > 1} a + 2b - 1 > 1 2b

>1-a+1 b > (2 - a) / 2 b > 1 - a/2

precondition: b > 1 - a/2

x = 2 * y + x - 1 {x > 11} 2 y+x-1>1 1 2 y>1 1-x+1 y>( 1 2-x )/2 y>6-x / 2 p r e c o nd i t i o n:y>6-x / 2 24 . Co mput et hewe a ke s tpr e c o ndi t i onf ore a c ho ft hef o l l o wi ngs e que nc e s o f as s i gnme nts t a t e me nt sa ndt he i rpo s t c o ndi t i o ns :

a=3*( 2*b+a ) ;b =2 *a -1{ b>5 } >We a k e s tp r e c o nd i t i on 2 a-1>5 2a>6 {a>3}

Po s t c o nd i t o n: 3( 2 b+a )>3 6 b+3 a>3 6 b>3–3 a { b>( 3–3a ) / 6}...