Exercise Postfix..Prefix..Infix

I) Infix to Prefix Notation Translation for Expressions
• Translation defined inductively as: Prefix(E) where E is an expression

1) If E is a variable or constant then Prefix(E)=E
2) If E is E1 op E2 then Prefix (E) = Prefix (E1 op E2) = op Prefix (E1) Prefix (E2)
3) If E is (E1) then Prefix(E1) = Prefix(E1)

Example:

Infix A*B+C/D to Prefix +*AB/CD

Prefix ((A*B)+(C/D))
+ prefix(A*B) prefix (C/D)
+* prefix (A) prefix (B) / prefix (C) prefix (D)
Ans: +*AB/CD

II a)Prefix to Infix

• Translation defined inductively as: Prefix(E) where E is an expression

1) If E is a variable or constant then Infix(E)=E
2) If E is E1 op E2 then Infix (E) = Infix (op E1 E2) = Infix (E1) op Infix (E2)
3) If E is (E1) then Infix(E1) = Infix(E1)

Example:
Infix( - ( / A B ) (* C D) )
= ( Infix ( / A B ) - Infix( * C D ) )
= ( ( Infix (A) * Infix (B) ) - ( ( Infix (C) / Infix (D) )
Ans: ( ( A / B ) - ( C * D ) )
II b). Postfix to Infix
1) If E is a variable then Infix(E) = E
2) If E is E1 E2 op then Infix(E) = Infix(E1 E2 op) = Infix (E1) op Infix (E2)
3) If E is (E1) then Infix(E) = Infix (E1)
Example:
Infix( ( A B + ) C + )
= ( Infix(A) + Infix(B) ) + Infix(C)
Ans: ( A + B ) + C


III) Postfix to Prefix Notation Translation for Expressions
• Translation defined inductively as: Prefix(E) where E is an expression

1) If E is a variable or constant then Prefix(E)=E
2) If E is E1 op E2 then Prefix (E) = Prefix (E1 E2 op) = op Prefix (E1) Prefix (E2)
3) If E is (E1) then Prefix(E1) = Prefix(E1)

Example:
a) From Postfix((AB*)(CD/)+)
Prefix ((AB*)(CD/)+)
= + Prefix((AB*)) Prefix((CD/))
= + Prefix(AB*) Prefix(CD/)
= + * Prefix (A) Prefix (B) / Prefix (C) Prefix (D)

Ans: + * AB / CD or (+(*AB)(/CD))

Chapter 2 Exercises

2.1 Consider the following context-free grammar

S -> S S + S S * a

a. show how the string aa+a* can be generated by this grammar.

ans: S -> SS*
Sa*
SS+ a *
a a + a *

b. Constuct a parse tree for this string

ans:
S
/ \
S S *
/ \
S S + a

a a

c. What language is generated by this grammar? Justify you answer

ans: The language defined by this grammar consists of two (2) consecutive a separated by plus and minus signs.


2.2 What language is generated by the following grammar? In each case justify you answer.

a. S -> 0 S 1 0 1

The language that is generated by this gramma is compose of digits number one (1) and zero (0).


b. S -> + S S - S S a

The language that is generated by this grammar is compose of a's separated by plus and minus signs.

c. S -> S ( S ) S є

The language that is generated by this grammar is compose of є.

d. S -> a S b S b S a S є

The language that is generated by this grammar is compose of a, b, and є.


e. S -> a S + S S S S * ( S )

The language that is generated by this grammar is compose of infinite consecutive S with plus (+) and * signs.

2.3