6341 Examples

CSE 6341 Simple problems

Problem 1

Consider the following context-free grammar with starting non-terminal <S> and terminal symbols a and b

<S> ::= aa<S>b |

::= ab

Part 1. Show the derivation of string aaaaabbb

Part 2. Does string aaaabbb belong to the language defined by this grammar? Explain why in 1-2 sentences.

Problem 2

Consider the following context-free grammar with starting non-terminal <program> and set of terminal symbols { ; , =, id, const }

<stmt> ::= id = const

Show the parse tree for string x = 1 ; y = 2 ; z = 3

Problem 3

Consider the following context-free grammar with non-terminal symbols <S>, <A>, , <C> and terminal symbols a, b, c

<S> ::= <A><C> <A> ::= a | a<A>2 ::= b | b2 <C> ::= c | c<C>2

We want to define an attribute grammar based on this context-free grammar. Our attribute grammar must define the language containing all and only strings of the form

at least 100 symbols a, followed by at least 200 symbols b, followed by exactly 300 symbols c

Define such an attribute grammar, but under the following restriction: for each non-terminal, you can use only one attribute, and this attribute must be inherited. Show clearly

For each non-terminal, the name of its attribute and the type of attribute values
All evaluation rules for all attributes
All conditions Cond: [...]

Problem 4

Consider the following context-free grammar (here ε denotes the empty string)

<stmtList> ::= ε | id = intconst ; <stmtList>2 | id = floatconst ; <stmtList>2

Suppose we want to enforce the following constraint: there does not exist a variable that is assigned both int and float values. For example, program x = 1; y = 2.3; x = 4; y = 5.6; satisfies this constraint, while x = 1; y = 2.3; x = 4.5; does not.

Write an attribute grammar to achieve this goal:

Assume that every id token has a predefined attribute id.lexval of type string that contains the name of the identifier
Use a synthesized attribute <stmtList>.intVars of type set of strings that contains the names of all variables that are assigned int values in the parse tree subtree rooted at this <stmtList> node. Use a similar attribute <stmtList>.floatVars for names of variables that are assigned float values.
For each production of the context-free grammar, show (1) evaluation rules for these two attributes, if any, and (2) necessary Cond: [...] checks, if any

Problem 5 (similar to Problem 4, but with inherited attributes)

Consider the following context-free grammar (here ε denotes the empty string)

<stmtList> ::= ε | id = intconst ; <stmtList>2 | id = floatconst ; <stmtList>2

We want to enforce the following constraint: there does not exist a variable that is assigned both int and float values. For example, x = 1; y = 2.3; x = 4; y = 5.6; satisfies this constraint, while x = 1; y = 2.3; x = 4.5; does not.

Write an attribute grammar to achieve this goal:

Assume that every id token has a predefined attribute id.lexval of type string that contains the name of the identifier
Use an inherited attribute <stmtList>.intVars of type set of strings that contains names of variables that are assigned int values. Use a similar inherited attribute <stmtList>.floatVars containing names of variables that are assigned float values.
For each production of the context-free grammar, show (1) evaluation rules for these two attributes, if any, and (2) necessary Cond: [...] checks, if any

Problem 6

Consider the operational semantics defined in class. Using the inference rules from the lecture notes, construct the derivation tree for the following triple:

< d = 2 - a + b * c , σ > → σ'

where the initial state σ = [a ↦ 1, b ↦ 2, c ↦ 3]. Assume that all operators are left-associative. Assume that + and - have the same precedence, which is lower than the precedence of *.

First, determine and show the new state σ'. Then show the entire derivation tree for this triple. Every level of the tree should correspond to one of the inference rules from the lecture notes.

Problem 7

Consider the abstract interpretation defined in class. Using the inference rules from the lecture notes, construct the derivation tree for the following triple:

< d = 2 - a + b * c , σa > → σa'

where the initial abstract state is σa = [a ↦ Neg, b ↦ Zero, c ↦ Pos]. Assume that all operators are left-associative. Assume that + and - have the same precedence, which is lower than the precedence of *.

First, determine and show the new abstract state σa'. Then show the entire derivation tree for this triple. Every level of the tree should correspond to one of the inference rules from the lecture notes.

Problem 8

Consider the abstract interpretation defined in class (slides 1-25; boolean expressions are ignored). Using the inference rules from the lecture notes, construct the derivation tree for the following triple:

< x = 0; y = 1; if (x<y) z = x else z = y , σa > → σa'

where the initial abstract state σa is empty. First, determine and show the new abstract state σa'. Then show the entire derivation tree for this triple. Every level of the tree should correspond to one of the inference rules from the lecture notes. Some of the relevant productions of the context-free grammar are: