Subject: Solutions to Practice Midterm - for class discussion 05March08 Practice Midterm - Spring 2008 CS 524 - Closed Book Midterm on Wednesday 12March2008 1) Consider the Pascal-like fixed-decimal literal with no superfluous leading or trailing zeros. That is, 0.0, 123.01 and 123005.0 are legal, but 00.0, 001.000 and 0023.100 are illegal. a) construct the determinstic machine that can recognize valid Pascal-like fixed decimal literals. one possible solution: d = [1..9] === used for accept states --- for "other states" i can't figure out a way to draw these using only ascii characters here's by best try. d --- ---- \|/| \|/ | d,0 === 0 --- |0 ---- |5|-----|7|-- \|/ | /=== --- --- | d/ /|\ | d ** transition S7->S5 on d |2|-- ---/0 --------- d/--- ---|3| ** State 5 is only accept state ** / . --- --- / ** Error if no out-arrow -> |1| / --- / \ / 0\ /. --- |4| --- b) number the state of your machine and list of the state, in order, that are passed through in recognizing 3501.3601 to recognize 3501.3601 you pass through states Input: 3 5 0 1 . 3 6 0 1 State: 1 2 2 2 2 3 5 5 7 5 accept (since we are in state 5, an accept state) ==================================================================== 2) Given the following grammar S -> S A S C | lambda A -> A a | b C -> D c D D -> d a) construct the derivation tree (parse tree) for the following input string: baadcd parse tree for baadcd S / | | \ S A S C / /| | /|\ lambda A a l D c D /| a | | A a m d d | b b d a b) give the right-most derivation, starting from the start symbol, of this phrase S -> SASC -> SASDcD -> SASDcd -> SASdcd -> SAdcd -> SAadcd -> SAaadcd -> Sbaadcd -> baadcd ================================================================= 3) given the following grammar Rule1: e ::= e + f Rule2: e ::= f Rule3: f ::= ( e ) Rule4: f ::= a [ e ] Rule5: f ::= a a) what language construct does this describe? this grammar describes expressions with array references b) construct the CFSM for this grammar state 1 : Shift State e ::= . e + f e ::= . f f ::= . ( e ) f ::= . a [ e ] f ::= . a state 2 : Shift State e ::= e . + f state 3 : Reduce State (Rule 2) e ::= f . state 4 : Shift State f ::= ( . e ) e ::= . e + f e ::= . f f ::= . ( e ) f ::= . a [ e ] f ::= . a state 5 : **** Shift/Reduce Conflict ***** Follow(f) = { + ) ] } f ::= a . is distict from shift f ::= a . [ e ] character [ state 6 : Shift State e ::= e + . f f ::= . ( e ) f ::= . a [ e ] f ::= . a state 7 : Shift State e ::= e . + f f ::= ( e . ) state 8 : Shift State f ::= a [ . e ] e ::= . e + f e ::= . f f ::= . ( e ) f ::= . a [ e ] f ::= . a state 9 : Reduce State (Rule 1) e ::= e + f . state 10 : Reduce State (Rule 3) f ::= ( e ) . state 11 : Shift State e ::= e . + f f ::= a [ e . ] state 12 : Reduce State (Rule 4) f ::= a [ e ] . c) is this grammar LR(0)? Why or why not? Be specific. no it is not LR(0) because state 5 has shift/reduce conflict d) Is this grammar SLR(1)? Why or Why not? be specific yes it is SLR(1) - see comments made in the state 5 above that the shift character, [ , is distinct from the Follow Set for the Reduction Rule f ::= a / Follow(f) = { + ) ] } e) Construct the Action and Goto tables from the CFSM Action Table [Note: ( State #, Symbol ) pairs not listed below are ERROR] action ( 1 , ( ) = shift 4 action ( 1 , a ) = shift 5 action ( 2 , + ) = shift 6 action ( 3 , eof ) = reduce 2 action ( 3 , + ) = reduce 2 action ( 3 , ) ) = reduce 2 action ( 3 , ] ) = reduce 2 action ( 4 , ( ) = shift 4 action ( 4 , a ) = shift 5 action ( 5 , eof ) = reduce 5 action ( 5 , + ) = reduce 5 action ( 5 , ) ) = reduce 5 action ( 5 , [ ) = shift 8 action ( 5 , ] ) = reduce 5 action ( 6 , ( ) = shift 4 action ( 6 , a ) = shift 5 action ( 7 , + ) = shift 6 action ( 7 , ) ) = shift 10 action ( 8 , ( ) = shift 4 action ( 8 , a ) = shift 5 action ( 9 , eof ) = reduce 1 action ( 9 , + ) = reduce 1 action ( 9 , ) ) = reduce 1 action ( 9 , ] ) = reduce 1 action ( 10 , eof ) = reduce 3 action ( 10 , + ) = reduce 3 action ( 10 , ) ) = reduce 3 action ( 10 , ] ) = reduce 3 action ( 11 , + ) = shift 6 action ( 11 , ] ) = shift 12 action ( 12 , eof ) = reduce 4 action ( 12 , + ) = reduce 4 action ( 12 , ) ) = reduce 4 action ( 12 , ] ) = reduce 4 GOTO Table: [Note: ( State #, Symbol ) pairs not listed below are ERROR] goto ( 1 , e ) = 2 goto ( 1 , f ) = 3 goto ( 4 , e ) = 7 goto ( 4 , f ) = 3 goto ( 6 , f ) = 9 goto ( 8 , e ) = 11 goto ( 8 , f ) = 3 ============================================================= 4) Given the following grammar, Action and GoTo tables 1 assign -> mem := E {assign();} 2 mem -> ident {idtoaddr();} 3 ident -> Id {pushid(yytext);} 4 E -> E + T {performop(addop);} 5 E -> T 6 T -> T * P {performop(multop);} 7 T -> P 8 P -> ( E ) 9 P -> mem {addrtoprimary();} With its corresponding Action and GoTo Tables: Action Lookahead --------------------------------------------------------- State| Id + * ( ) := eof --------------------------------------------------------- 1 S 2 S 3 R2 R2 R2 R2 R2 4 R3 R3 R3 R3 R3 5 S S 6 R9 R9 R9 R9 7 S A 8 R5 S R5 R5 9 R7 R7 R7 R7 10 S S 11 S S 12 S S 13 S S 14 R4 S R4 R4 15 R6 R6 R6 R6 16 R8 R8 R8 R8 GoTo: Symbol State| assign mem ident E T P Id + * ( ) := eof ---------------------------------------------------------- 1 | | 2 | 3 | | | | 4 | | | | | | 2 | | | | | | | | | | | | 5 | 3 | | | | | | | | | | | | | 4 | | | | | | | | | | | | | 5 | | 6 | 3 | 7 |8 |9 | 4 | | |10| | | 6 | | | | | | | | | | | | | 7 | | | | | | | |11| | | | | 8 | | | | | | | | |12| | | | 9 | | | | | | | | | | | | | 10 | | 6 | 3 | 13|8 | 9| 4 | | |10| | | 11 | | 6 | 3 | |14| 9| 4 | | |10| | | 12 | | 6 | 3 | | |15| 4 | | |10| | | 13 | | | | | | | |11| | |16| | 14 | | | | | | | | |12| | | | 15 | | | | | | | | | | | | | 16 | | | | | | | | | | | | | ----------------------------------------------------------------------- Step| Parse Stack | Remaining Input | Semantic Actions ----------------------------------------------------------------------- (1) |1 |c:=a*(b+d) | Shift; p(g(1,Id))=4 ----------------------------------------------------------------------- (2) |1,4 |:=a*(b+d) | R3 pushid | c | semstack ------- pop1;p(g(1,ident))=3 ---------------------------------------------------------------------- (3) |1,3 |:=a*(b+d) | R2 idtoaddr | *--|--> symtab(c) ------- pop1; p(g(1,mem))=2 ----------------------------------------------------------------------- (4) |1,2 |:=a*(b+d) | Shift; p(g(2,:=))=5 ----------------------------------------------------------------------- (5) |1,2,5 |a*(b+d) | Shift; p(g(5,Id))=4 ----------------------------------------------------------------------- (6) |1,2,5,4 |*(b+d) | R3 pushid | a | ------- | *--|--> symtab(c) ------- pop1; p(g(5,ident))=3 ------------------------------------------------------------------------ (7) |1,2,5,3 |*(b+d) | R2 idtoaddr | *--|--> symtab(a) ------- | *--|--> symtab(c) ------- pop1; p(g(5,mem))=6 ------------------------------------------------------------------------- (8) |1,2,5,6 |*(b+d) | R9 addrtoprimary | *--|--> exprtree->a ------- | *--|--> symtab(c) ------- pop1; p(g(5,P))=9 ------------------------------------------------------------------------- (9) |1,2,5,9 |*(b+d) | R7 pop1;p(g(5,T))=8 ------------------------------------------------------------------------- (10)|1,2,5,8 |*(b+d) | Shift; p(g(8,*))=12 ------------------------------------------------------------------------- (11)|1,2,5,8,12 |(b+d) | Shift; p(g(12,'('))=10 ------------------------------------------------------------------------- (12)|1,2,5,8,12,10 |b+d) | Shift; p(g(10,Id))=4 ------------------------------------------------------------------------- (13)|1,2,5,8,12,10,4 |+d) | R3 pushid | b | ------- | *--|--> exprtree->a ------- | *--|--> symtab(c) ------- pop1;p(g(10,ident))=3 ------------------------------------------------------------------------- (14)|1,2,5,8,12,10,3 |+d) | R2 idtoaddr | *--|--> symtab(b) ------- | *--|--> exprtree->a ------- | *--|--> symtab(c) ------- pop1; p(g(10,mem))=6 ------------------------------------------------------------------------- (15)|1,2,5,8,12,10,6 |+d) | R9 addrtoprimary | *--|--> exprtree->b ------- | *--|--> exprtree->a ------- | *--|--> symtab(c) ------- pop1;p(g(10,P))=9 -------------------------------------------------------------------------- (16)|1,2,5,8,12,10,9 |+d) | R7; pop1; p(g(10,T))=8 -------------------------------------------------------------------------- (17)|1,2,5,8,12,10,8 |+d) | R5; pop1; p(g(10,E))=13 -------------------------------------------------------------------------- (18)|1,2,5,8,12,10,13 |+d) | Shift; p(g(13,+))=11 -------------------------------------------------------------------------- (19)|1,2,5,8,12,10,13,11 |d) | Shift; p(g(11,Id))=4 -------------------------------------------------------------------------- (20)|1,2,5,8,12,10,13,11,4 |) | R3 pushid | d | ------- | *--|--> exprtree->b ------- | *--|--> exprtree->a ------- | *--|--> symtab(c) ------- pop1; p(g(11,ident))=3 --------------------------------------------------------------------------- (21)|1,2,5,8,12,10,13,11,3 |) | R2 idtoaddr | *--|--> symtab(d) ------- | *--|--> exprtree->b ------- | *--|--> exprtree->a ------- | *--|--> symtab(c) ------- pop1; p(g(11,mem))=6 ---------------------------------------------------------------------------- (22)|1,2,5,8,12,10,13,11,6 |) | R9 addrtoprimary | *--|--> exprtree->d ------- | *--|--> exprtree->b ------- | *--|--> exprtree->a ------- | *--|--> symtab(c) ------- pop1; p(g(11,P))=9 * ---------------------------------------------------------------------------- (23)|1,2,5,8,12,10,13,11,9 |) | R7; pop1; p(g(11,T))=14 * ---------------------------------------------------------------------------- (24)|1,2,5,8,12,10,13,11,14 |) | R4; performop(+) | *--|--> + | | / \ | | (d) (b) ------- | *--|--> exprtree->a ------- | *--|--> symtab(c) ------- pop3; p(g(10,E))=13 --------------------------------------------------------------------------- (25)|1,2,5,8,12,10,13 |) | Shift; p(g(13,')'))=16 * --------------------------------------------------------------------------- (26)|1,2,5,8,12,10,13,16 | | R8; pop3; p(g(12,P))=15 --------------------------------------------------------------------------- (27)|1,2,5,8,12,15 | | R6; performop(*) | *--|--> * | | / \ | | (a) + | | / \ | | (d) (b) ------- | *--|--> symtab(c) ------- pop3; p(g(5,T))=8 ---------------------------------------------------------------------------- (28)|1,2,5,8 | | R5; pop1; p(g(5,E))=7 ---------------------------------------------------------------------------- (29)|1,2,5,7 | | Accept or R1 but since this grammar can only recognize the assigment statement, this is all the grammar let's us do. you can see that the semstack has the correct data for assign. R1 would entail - pop 3 accept if in State 1 5) Consider the following code fragment package main is body -- open level 0 x,y: integer; procedure a is x,y: boolean; -- open level 1 procedure b is x: character; -- open level 2 procedure c is x,y: foogle; -- open level 3 begin -- c ... end; -- c -- close level 3 begin -- b ... end; -- b -- close level 2 begin -- a ... end; -- a -- close level 1 begin -- main; ... end; -- main; -- closel level 0 a) Draw a diagram to represent a Scope Stack of Symbol Tables for the code fragment above. b) In the body of procedure c, what is the data type of the variable y? c) In the body of the main procedure, what is the data type of the variable y? --------------- a) Scope Stacks: /|symtab with | | level 3 | ------------/ | x,y: foogle | ----------- --------------- | level 2 | ----------------------------> --------------------- ----------- | symtab with | | level 1 | -----------> --------------- | x:char; c procname| ----------- | symtab with | --------------------- | level 0 | -------\ |x,y: bool; b procname| ----------- \ ----------------------- Scope_Stack \ ----------------------- | symtab with | |x,y: int; a procname | ----------------------- b) data type of y in body of proc c is "foogle" c) data type of y in main is "integer"