Scribd
Upload
7 views6 pages

SDD and Syntax Tree Construction Guide

The document outlines a Syntax-Directed Definition (SDD) for a basic calculator, including grammar rules for expressions and an annotated parse tree for the expression (4*7+1)*2. It explains the use of Syntax-Directed Translations (SDTs) for constructing syntax trees, provides examples of quadruples, triples, and indirect triples for a specific expression, and details SDD for control flow structures like if-else and while statements. Additionally, it covers type checking and the construction of a Directed Acyclic Graph (DAG) for a given expression involving common subexpressions.

Uploaded by

rem895964
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views6 pages

SDD and Syntax Tree Construction Guide

The document outlines a Syntax-Directed Definition (SDD) for a basic calculator, including grammar rules for expressions and an annotated parse tree for the expression (4*7+1)*2. It explains the use of Syntax-Directed Translations (SDTs) for constructing syntax trees, provides examples of quadruples, triples, and indirect triples for a specific expression, and details SDD for control flow structures like if-else and while statements. Additionally, it covers type checking and the construction of a Directed Acyclic Graph (DAG) for a given expression involving common subexpressions.

Uploaded by

rem895964
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

1.

Write SDD for a basic calculator and construct an annotated parse tree for (4*7+1)*2

Syntax-Directed Definition (SDD) for expressions:

Grammar:

E E+T { [Link] = [Link] + [Link] }

E T { [Link] = [Link] }

T T*F { [Link] = [Link] * [Link] }

T F { [Link] = [Link] }

F (E) { [Link] = [Link] }

F num { [Link] = [Link] }

Example input: (4 * 7 + 1) * 2

Parse tree (with values):

(4 * 7) = 28

(28 + 1) = 29

29 * 2 = 58

Annotated parse tree:

/ \

+ 2

/ \

* 1

/ \

4 7
2. Explain how SDTs are used for constructing syntax trees

Syntax-Directed Translations (SDTs) use semantic rules embedded in grammar productions to

guide construction of syntax trees or IR.

For instance:

E E1 + T { [Link] = newNode("+", [Link], [Link]) }

Nodes are constructed during parsing, representing computation.

3. Quadruples, Triples, Indirect Triples for a := b * -c + b * -c

Subexpressions:

t1 = -c

t2 = b * t1

t3 = b * t1

t4 = t2 + t3

a = t4

Quadruples:

('-', c, -, t1)

('*', b, t1, t2)

('*', b, t1, t3)

('+', t2, t3, t4)

(':=', t4, -, a)
Triples:

0: (-, c, -)

1: (*, b, (0))

2: (*, b, (0))

3: (+, (1), (2))

4: (:=, (3), -)

Indirect Triples:

Pointer table -> Triples with indices referencing them.

Examples:

x := y[i]

(=, y[i], -, x)

x[i] := y

(=, y, -, x[i])

4. SDD for control flow (if-else, while)

If-Else:

S if (E) S1 else S2

[Link] = newlabel()

[Link] = newlabel()

[Link] = [Link]

[Link] = [Link]

code(S) = code(E) ||
label([Link]) || code(S1) || goto([Link]) ||

label([Link]) || code(S2)

While:

S while E do S1

begin = newlabel()

[Link] = newlabel()

[Link] = [Link]

code(S) = label(begin) || code(E) ||

label([Link]) || code(S1) || goto(begin) ||

label([Link])

5. SDD for switch statement:

switch (E) {

case C1: S1;

case C2: S2;

...

default: Sd;

code:

t1 = E

if t1 == C1 goto L1

if t1 == C2 goto L2

...
goto Ld

L1: code(S1)

L2: code(S2)

Ld: code(Sd)

6. Type Checker

A type checker ensures semantic correctness via:

- Expression type evaluation

- Assignment compatibility

- Function call validation

Example rule:

x=y+z

Check type(y) == type(z)

Check type(x) == result_type(y + z)

7. DAG for a + a*(b-c) + (b-c)*d

Identify common subexpressions:

t1 = b - c

t2 = a * t1

t3 = t1 * d

t4 = a + t2

t5 = t4 + t3

DAG:
+

/\

+ *

/\ /\

a * t1 d

/\

a -

/\

b c

You might also like