Consider the following attribute grammar for constant declaration

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

1. Consider the following attribute grammar for constant declaration:

 

1. Syntax rule: <const-declaration> → <type> <id> = <expr> Semantic rules: <id>.type ← <type>.type

<expr>.type ← <id>.type

<id>.value ←<expr>.value

2. Syntax rule: <type> → binary Semantic rule: <type>.type ← binary

3. Syntax rule: <type> → tertiary Semantic rule: <type>.type ← tertiary

4. Syntax rule: <expr>[1] → <expr>[2] <const>

Semantic rules: <expr>[1].value ← if <expr>[1].type = binary

then <expr>[2].value * 2 + <const>.value else <expr>[2].value * 3 + <const>.value

<expr>[2].type ← <expr>[1].type

5. Syntax rule: <expr> → <const>

Semantic rule: <expr>.value ← <const>.value\

6. Syntax rule: <const> → 2 Semantic rule: <const>.value = 2

7. Syntax rule: <const> → 1 Semantic rule: <const>.value = 1

8. Syntax rule: <const> -> 0 Semantic rule: <const>.value = 0

9. Syntax rule: <id> -> A | B | C

 

a. For each semantic rule, does the rule define a synthesized, inherited or intrinsic attribute?

b. Given the input string "tertiary B = 210012"

i) Draw the parse tree representation for it. Is this input ambiguous?

ii) Draw the attribute dependency tree that shows the associated attributes at each node of the parse tree and their dependency relationships with attributes at other nodes (just like the tree in slide 59 in the week 3 lecture).

iii) Show the order of attribute evaluation according to the attribute dependencies. (just like the order of evaluations in the same slide 59 in the week 3 lecture).

iv) Draw the fully decorated (attributed) tree with evaluated attribute values at all nodes. Note: do the above steps on a single tree (akin to slide 60, week 3 lecture).

 

2. Recall the semantic function we dissected in week 3 under the denotational semantics for mapping assignment statements to states pertaining to logical pretest loops (i.e, while loops):

 

 

 

I want you to

i) Describe, in natural language (i.e., English), what this function is doing, line by line. What are Mb and Msl?

ii) Formally write a definition for Mb and Msl that make this function complete. That is:

• Mb = ?

• Msl = ?

iii) The current semantic function, Ml, is intended to model logical pretest loops. Write variation of it, Ml’, intended for logical posttest loops – do while statements; e.g., constructs that are of the form:

 

 

 

3. Derive the weakest precondition for the sequence of assignment statements and their postconditions below:

 

a) x = 3 * y + 1; y = x – 5

{y < 1}

 

b) c = 3 * (1 * b + c); b = 2 * c – 1

{b > 4}

 

4. Implement a recursive descent-parser in C, caller parser.c, for the following grammar (in EBNF) where <program> is the starting non-terminal. You can assume that the input source program is contained in an external textfile (e.g., ‘front.in’), whose path name can be read from command line or in the main program. Note that whenever a symbol is in apostrophe, such as ‘}’, it implies it is not part of the EBNF metalanguage and is part of the syntax rule itself.

 

<program> → <stmts>

 

<stmts> → <stmt> [; <stmts>]

 

<stmt> → <assign> | <if> | <for> | <while> |

 

<assign> → id = <expr>

 

<if> → if '(' <expr> ')' ( '{' <stmts> '}' | <stmt>)

 

<for> → for '(' <assign> ; <expr> ; <assign> ')' ' ( '{' <stmts> '}' | <stmt>)

 

<while> → while '(' <expr> ')' ( '{' <stmts> '}' | <stmt>)

 

<expr> → <term {(+|-) <term>}

 

<term> → <factor> {(*|/) <factor>}

 

<factor> → <const> | <id> | '(' <expr> ')'

 

<id> → <letter> {<letter> | <digit>}

 

<const> -> <digit> { <digit> }

 

<letter> -> a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

 

<digit> -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

 

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of