Reference no: EM132313953
Assignment -
1. What is a compiler?
2. Why we need study compiler design?
3. List steps or phases of compiler and identify which type of errors identified by each phase.
4. What are the differences between Analysis (front end) and Synthesis (back end)?
5. What are the differences between top down and bottom up parser (explain your answer by using appropriate example)?
6. Clearly define Token, pattern, lexeme and give examples for each term.
7. Convert the following NFA of identifier into the corresponding DFA. letter(letter|digit)*
8. Draw DFAs for the string matched by the following definition:
digit =[0-9]
nat=digit+
signednat=(+|-)?nat
number=signednat("."nat)?(E signedNat)?
9. Construct NFA for the following regular repression and convert it to DFA: (a|b|c)*abc
10. Using the grammar below, draw a parse tree for the following string:
"( ( id . id ) id ( id ) ( ( ) ) )"
S → E
E → id
|( E . E )
|( L )
|( )
L → L E
|E
11. Give a rightmost derivation for the string given in (10).
12. Give a leftmost derivation for the string given in (10).
13. Consider the following grammar and Draw the parse tree for the input "y+++y++" using RDP (show all necessary stapes)
S → A
A→ A + A |B++
B → y
14. Using the grammar below, draw a parse tree for the following string using RDP algorithm: ( ( id . id ) id ( id ) ( ( ) ) )
S → E
E → id
| ( E . E )
|( L )
|( )
L → L E
|E
15. Consider the following grammar over the alphabet {g,h,i,b}
A→ BCD
B → bB|ε
C→Cg |g |Ch |i
D→ AB |ε
Fill in the table below with the FIRST and FOLLOW sets for the terminals and non-terminals in this grammar:
|
|
FIRST
|
FOLLOW
|
|
A
|
|
|
|
B
|
|
|
|
C
|
|
|
|
D
|
|
|
|
BCD
|
|
|
|
bB
|
|
|
16. Let G be the following grammar:
S → [ SX ]|a
X→ε |+SY |Yb
Y→ε | -SXc
A. Find FIRST and FOLLOW sets for the non-terminals in this grammar.
B. Construct predictive parsing table for the grammar above.
C .Show a top down predictive parse of the string [a+a-ac]
17. Consider the following grammar G:
A'→ A
A→ xA|yA|y
a. Find FIRST and FOLLOW sets for G:
b. Construct the LL(1) parse table for this grammar.
c. Explain why this grammar is not LL(1).
d. Transform the grammar into a grammar that is LL(1).
e. Give the parse table for the grammar created in (d).
18. Given the following grammar:
S →WAB|ABCS
A→B|WB
B →ε|yB
C→z
W →x
a. Find FIRST and FOLLOW sets of the grammar.
b. Construct the LL(1) parse table.
c. Is the grammar LL(1)? Justify your answer.
19. Given the following grammar:
PROGRAM→ procedure STMT-LIST
STMT-LIST →STMT STMT-LIST | STMT
STMT →do VAR = CONST to CONST begin STMT-LIST end | ASSN-STMT
ASSN-STMT → VAR = CONST | VAR = VAR
CONST →0 | 1 | ...|100
VAR → i | j | x | y
a. Check whether the following fragment of code is correct or not.
b. Show the parse tree for the following code fragment:
procedure
do i=1 to 100 begin
x=10
y=x
end
x=2
20. Given the following grammar
E → TR
R→ +TR
R→ -TR
R→ε
T →0|1|...|9
a. Using panic mode error recovery how to the following inputs are accepted (show all necessary steps)
i. 0+1-2-+3
ii. +2-3+4
iii. 3+2+5-
iv. +2-44++6-7
21. Given the following Grammar:
S → A
S → B
A→ a A b
A→ 0
B → a B b b
B → 1
a. Construct the SLR parsing table.
b. Write the action of an LR parse for the following string "aa1bbbb"
22. Given the following Grammar:
S → S + A
S → A
A → A * B
A → B
B → ( S )
B → a
a. Construct the SLR parsing table.
b. Write the action of an LR parse for the following string
"a * a + a * ( a + a)"
23. Check the given grammar is SLR or not and justify your answer.
a. E→A
E→B
A→+B
A→id
R→A
b. E→DaDbDc
E→FcFbFa
D→ε
F→ε