IQRA UNIVERSITY ISLAMABAD

DEPARTMENT OF COMPUTING & TECHNOLOGY

Assignment 03
COURSE: Compiler construction
Batch:CS-SP-22 Semester: 6th Instructor: Muhammad Mukhtar Qureshi

Total Marks: 20 Issue Date: 09-Jan-2025 Due Date: 16-Jan-2025

Q.1 : What are the:

i) Conditions for L-attributed Grammar.
ii) Conditions for S-attributed Grammar.

Q.2
Write an attribute grammar for the floating point value of a decimal number given by the
following grammar. (Hint: use a count attribute to count the number of digits to the right of the
decimal point.)
dnum → num.num
num → num digit | digit
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Q. 3
Consider the following expression grammar as it would be written for a predictive parser.
and
exp term exp'
exp' + term exp' | - term exp' | ∈
term factor term'
term'* factor term' | ∈
factor (exp) | number

a) Write an attribute equation for the value of an expression given by this grammar.
b) Draw the dependency graph w.r.t each rule of the above grammar according to attribute
equations of part (a).
c) Make the annotated parse tree for the string 3*(4+5)*6.

Q. 4
Consider the following grammar for integer binary trees (in linearized form):
btree → ( number btree btree ) | nil

Write an attribute grammar to check that a binary tree is ordered, that is, that the values
of the numbers of the first subtree are ≤ the value of the current number and the values
of all the numbers of the second subtree are > the value of the current number.
For example, (2 (1 nil nil) (3 nil nil)) is ordered, but (1 (2 nil nil) (3 nil nil)) is not.

Q. 5
suppose that we have a production A → BCD. Each of the four non-terminals A, B, C and D
have two attributes: s is a synthesized attribute, and i is an inherited attribute. For each of the sets
of rules below tell whether:
( i ) the rules are consistent with an S-attributed definition.
( ii ) the rules are consistent with an L-attributed definition.

a) A.s = B.i + C.s

b) A.s = B.i + C.s and D.i = A.i + B.s
c) A.s = B.s + D.s
-----------------------------------------------------------------------------------------
Q. 6
Consider the following grammar.

decl  var-list : type

var-list var-list , id | id
type  integer | real

i) Write an attribute grammar for the type of a variable.

ii) Rewrite it so that the type of a variable can be defined as a purely synthesized attribute, and
give a new attribute grammar for the type that has this property.
-----------------------------------------------------------------------------------------------------------
Q.7
Show that, given the attribute grammar,
Grammar rule semantic rules
decl  type var-list var-list.dtype= type.dtype
type  int type.dtype= integer
type  float type.dtype= real
var-list1  id , var-list2 id. dtype= var-list1.dtype
var-list2. dtype= var-list1.dtype
var-list id id.dtype= var-list.dtype

If the attribute type.dtype is kept on the value stack during an LR parse, then this value can not
be found at a fixed position in the stack when reductions by the rule var-list→id occur.
-----------------------------------------------------------------------------------------------------------------------
Q. 8
Determine whether the following syntax directed definition is L-attributed or not.
PRODUCTION SEMANTIC RULES
 1) T →F T ' T '.inh = F.val
T.val = T’. syn
2) T ' → ∗F T1' T1'.inh = T '.inh ×F.val
T’. syn = T1'.syn
3) T ' → ∈ T’.syn = T’. inh
4) F →digit F.val = digit. Lexval
---------------------------------------------------------------------------------------------------
Q.9
Determine whether the syntax-directed definition containing following production and rules is an L-
attributed grammar?
PRODUCTION SEMANTIC RULES
A → B C A.s = B.b ;
B.i = f ( C.c, A.s)
---------------------------------------------------------------------------------------------------------------
Q.10
Consider the following attribute grammar:
Grammar Rule Semantic Rule
S→ABC B.u=S.u
A.u=B.v + C.v
S.v=A.v
A→a A.v = 2 * A.u
B→b B.v = B.u
C →c C.v = 1
a) Draw the parse tree for the string abc (the only string in the language) and draw the
dependency graph for the associated attributes. Describe a correct order for the evaluation
of the attributes.
b) Suppose that S.u is assigned the value 3 before attribute evaluation begins. What is the
value S.v when evaluation has finished?
c) Suppose the attribute equations are modified as follows:
Grammar Rule Semantic Rule
S→ABC B.u=S.u
C.u= A.v
A.u=B.v + C.v
S.v=A.v
A→a A.v = 2 * A.u
B → b B.v = B.u
C →c C.v = C.u – 2
What value does S.v have after attribute evaluation, if S.u=3 before evaluation begins?
Q.11
Consider the following grammar
S → exp
exp → exp / exp | num | num.num

a. Write an attribute grammar / semantic rules w.r.t. each production of the grammar.
 b. Draw dependency graphs for the above grammar rules.
c. Draw D.A.G. required to compute the attributes on the syntax tree for the input of 5/2/2.0.
-----------------------------------------------------------------------------------------------------
Q.12
i) Ex. 5.1.1.
Production Semantic Rules.
s
1 L→ En L.val = E.val
2 E → E1+T E.val = E1.val+ T.val
3 E→ T E.val = T.val
4 T → T1 * F T.val = T1.val × F.val
5 T→ F T.val = F.val
6 F → (E) F.val = E.val
7 F → digit F.val = digit.lexval
For the Syntax-Directed Definition of the above Figure, give annotated parse tree for the
following expression. a) (3+4) * (5+6) n. b) 1*2*3*(4+5)n.
ii) Ex. 5.1.2.

T′.inh = F. val
Productions Semantic Rules.

T.val = T'.syn
1 T →F T'

2 T′→ * F T1' T1′.inh = T'.inh ×

F.val
T′. syn = T1'. Syn
3 T'→ ∈ T′. syn = T1'. Inh
4 F→ digit F.val = digit . lexval
For the Syntax-Directed Definition of the above Figure, give annotated parse tree for the
following expression. 4*2*3.
Q.13
Consider the following grammar where numbers may be octal or decimal that is indicated by one
character suffix o (for octal) or d (for decimal).
based-numnum basechar
basechar o | d
numnum digit | digit
digit 0|1|2|3----------|8|9

a) Write the attribute grammar / semantic rules w.r.t. each production of the grammar.
b) Draw a parse tree showing attribute computations of the above grammar for the string 3450 .
c) Draw the dependency graph for the above string 3450 .
Q.14
Consider the following syntax-directed definition over the grammar defined by G = ({S, A, Sign},
S, {‘,’, ‘-‘, ‘+’, ‘n’}, P) with P the set of production and the corresponding semantic rules depicted
below. There is a special terminal symbol “n” that is lexically matched by any string of one numeric
digit and whose value is the numeric value of its decimal representation. For the non-terminal
 symbols in G we have defined two attributes, sign and value. The non-terminal A has these two
attributes whereas S only has the value attribute and Sign only has the sign attribute.
S → A Sign || S.val = A.val; A.sign = Sign.sign; print(A.val);
Sign → + || Sign.sign = 1
Sign → - || Sign.sign = 0
A → n || A.val = value(n)
A → A1 , n || A1.sign = A.sign;
if(A.sign = 1) then
A.val = max (A1.val,value(n));
else
A.val = min(A1.val,value(n));

a) Explain the overall operation of the above syntax-directed definition and indicate (with a brief
explanation) which of the attributes are either synthesized or inherited.
b) Give an attributed parse tree for the source string “5,2,3-“ and evaluate the attributes in the
attributed parse tree depicting the order in which the attributes need to be evaluated (if more than
one order is possible indicate one.)
c) Suggest a modified grammar and actions exclusively using synthesized attributes. Explain its
basic operation.
---------------------------------------------------------------------------------------------------------------------
Q. 15.
This Question is motivated by languages for typesetting mathematical formulas. Eqn is an early
example of such a language; ideas from Eqn are still found in the TEX typesetting system, that is still
used to produce this book.
We shall concentrate on only the capability to define subscripts, subscripts of subscripts, and so
on, ignoring superscripts, built-up fractions, and all other mathematical features.
B → B1 B2 | B1 sub B2 | (B1) | text
In the Eqn language, one writes a sub i sub j to set the expression aij. A simple grammar for
boxes (elements of text bounded by a rectangle) is Corresponding to these four productions, a
box can be either
1. Two boxes, juxtaposed, with the first, B1, to the left of the other, B2 •
2. A box and a subscript box. The second box appears in a smaller size, lower, and to the right of
the first box.
3. A parenthesized box, for grouping of boxes and subscripts. Eqn and 'lEX both use curly braces
for grouping, but we shall use ordinary, round parentheses to avoid confusion with the braces
that surround actions in SDT's.
4. A text string, that is, any string of characters.
This grammar is ambiguous, but we can still use it to parse bottom-up if we make subscripting
and juxtaposition right associative, with sub taking precedence over juxtaposition. Expressions
will be typeset by constructing larger boxes out of smaller ones .
In the following Fig, the boxes for El and .height are about to be juxtaposed to form the box for
El.height.The left box for El is itself constructed from the box for E and the subscript 1. The
subscript 1 is handled by shrinking its box by about 30%, lowering it, and placing it after the box
for E. Although we shall treat .height as a text string, the rectangles within its box show how it
can be constructed from boxes for the individual letters.
Figure: Constructing larger boxes from smaller ones.

In this question, we concentrate on the vertical geometry of boxes only. The horizontal geometry
- the widths of boxes - is also interesting, especially when different characters have different
widths. It may not be readily apparent, but each of the distinct characters in the above Fig. has a
different width.
The values associated with the vertical geometry of boxes are as follows:
a) The point size is used to set text within a box. We shall assume that characters not in
subscripts are set in 10 point type, the size of type in this book. Further, we assume that if a box
has point size p, then its subscript box has the smaller point size 0.7p. Inherited attribute B.ps
will represent the point size of block B. This attribute must be inherited, because the context
determines by how much a given box needs to be shrunk, due to the number of levels of
subscripting.
b) Each box has a baseline, which is a vertical position that corresponds to the bottoms of lines
of text, not counting any letters, like "g" that extend below the normal baseline. In the above
Fig., the dotted line represents the baseline for the boxes E, .height, and the entire expression.
The baseline for the box containing the subscript 1 is adjusted to lower the subscript.
c) A box has a height, which is the distance from the top of the box to the baseline. Synthesized
attribute B.ht gives the height of box B.
d) A box has a depth, which is the distance from the baseline to the bottom of the box.
Synthesized attribute B.dp gives the depth of box B.
a) Define Semantic rules(SDD) for computing point sizes, heights, and depths.
Production 1 is used to assign B.ps the initial value 10.
Production 2 handles juxtaposition. Point sizes are copied down the parse tree; that is, two sub-
boxes of a box inherit the same point size from the larger box. Heights and depths are computed
up the tree by taking the maximum. That is, the height of the larger box is the maximum of the
heights of its two component s, and similarly for the depth.
Production 3 handles subscripting and is the most subtle. In this greatly simplified example, we
assume that the point size of a subscripted box is 70% of the point size of its parent. Reality is
much more complex, since subscripts cannot shrink indefinitely; in practice, after a few levels,
the sizes of subscripts shrink hardly at all. Further, we assume that the baseline of a subscript box
drops by 25% of the parent's point size; again, reality is more complex.
Production 4 copies attributes appropriately when parentheses are used. Finally,
production 5 handles the leaves that represent text boxes. In this matter too, the true situation is
complicated, so we merely show two unspecified functions getHt and getDp that examine tables
created with each font to determine the maximum height and maximum depth of any characters
in the text string.
The string itself is presumed to be provided as the attribute lexval of terminal text .
b) Turn that SDD into an appropriate SDT, following the rules for an L-attributed SDD, that we
wrote as a first step.
----------------------------------------------------------------------------------------------------------------
Q.16
Consider the following grammar for integer binary trees (in linearized form):
S→aSb|aS|cSacS|∈

i. Write an attribute grammar with semantic rules(i.e. Syntax Directed Definition).

 ii. Make annotated Parse Tree for the following Input. acaacabb
----------------------------------------------THE END
---------------------------------------------------------------------