close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Winter 2012-2013
Compiler Principles
Exercises on scanning
& top-down parsing
Mayer Goldberg and Roman Manevich
Ben-Gurion University
Scanning question 1
• Write a regular expression for positive integers
where every three consecutive digits, starting
from the right, are separated by a _
– Examples: 23 1_000 2_784_153
– Negative examples: 1_0 1_5422
2
Scanning question 1
• Write a regular expression for positive integers
where every three consecutive digits, starting
from the right, are separated by a _
– Examples: 23 1_000 2_784_153
– Negative examples: 1_0 1_5422
• Answer:
D=0|1|2…|9
Small = D | DD | DDD
Three = DDD
R = Small (_Three)*
3
Parsing question 1
• Consider the grammar below
S(L)|a
LL,S|S
1. show a parse tree for each of the following
1. (a, a)
2. (a, (a, a))
4
Answer
S
S
L
(
L
L
S
S
a
,
(
a
S
,
,a
)
5
Parsing question 2
• Consider the grammar G
LL,a|a
– What is the language generated by G?
– Eliminate the left-recursion in G
– Write a non-left-recursive version without ε
productions
– Construct an LL(1) parser and run it on a, a, a
6
Parsing question 2
• Consider the grammar G
LL,a|a
–
–
–
–
What is the language generated by G?
Eliminate the left-recursion in G
Write a non-left-recursive version with ε productions
Is the resulting grammar LL(1)?
• Answer
– The language given by the regular expression (a ,)* a
– LaM
M,aM |ε
– La|aM
M,aM |,a
– The grammar contains FIRST-FIRST conflicts for both L and M
and therefore it is not LL(1)
7
Parsing question 3
• Consider the grammar G1 below
XPP
Pa
Pb
• Q: Is it ambiguous?
8
Parsing question 3
• Consider the grammar G1 below
XPP
Pa
Pb
• Q: Is it ambiguous?
• A: since the only non-terminal with
alternatives is P and the first of its two
alternatives ({a} and {b}) the grammar is
LL(1). All LL(1) grammars are unambiguous
9
Parsing question 4
• Consider the following grammar
Ea(S)wt
Ea(S)wb
SS;c|c
– Construct an LL(1) parser, applying any
transformations necessary if the grammar is not in
LL(1)
– Hint: move the ) down to help transformations
– Apply the parser to the input
a (c; c) w b
10
Answer
• The grammar
Ea(S)wt
Ea(S)wb
SS;c|c
will have a FIRST-FIRST conflict for E, since
the first two rules start with a. We therefore
apply left-factoring and obtain
• E  a ( S ) E’
E’  w b | w t
SS;c|c
11
Answer
• The grammar
E  a ( S ) E’
E’  w b | w t
SS;c|c
Is left-recursive on S so we eliminate the leftrecursion and obtain the grammar
• E  a ( S ) E’
E’  w b | w t
Sc|c;S
12
Answer
• Let’s compute FIRST sets for
E  a ( S ) E’
E’  w b | w t
Sc|c;S
• FIRST(S  c) = FIRST(c ; S) = {c}
FIRST(w b)=FIRST(w t) = {w}
so there are FIRST-FIRST conflict. We apply left-factoring to both
E’ and S and obtain
E  a ( S ) E’
E’  w E’’
E’’  b | t
S  c S’
S’  ε | ; S
• Now if we apply substitution for S’ we will just get back to a leftrecursive grammar.
Time to use the hint
13
Answer
• Starting from
E  a ( S ) E’
E’  w E’’
E’’  b | t
Sc|c;S
Let’s move ) from E to S
• E  a ( S E’
E’  w E’’
E’’  b | t
Sc)|c;S
• Now let’s apply left-factoring to S and obtain:
E  a ( S E’
E’  w E’’
E’’  b | t
S  c S’
S’  ) | ; S
14
Answer
• Let’s compute FIRST sets for
(1) E  a (S E’
(2) E’  w E’’
(3) E’’  b
(4) E’’  t
(5) S  c S’
(6) S’  )
(7) S’  ; S
• FIRST(E) = {a}
FIRST(E’) = {w}
FIRST(E’’) = {b, t}
FIRST(S) = {c}
FIRST(S’) = {), ;}
• There are no conflicts so the grammar is in LL(1)
15
Parsing table
a
E
E’
E’’
S
S’
(
w
b
t
3
4
c
)
;
6
7
1
2
5
16
Running on a ( c; c ) w b
Input suffix
Stack content
Move
a ( c; c ) w b$
E$
predict(E, a) = E  a ( S E’
a ( c; c ) w b$
a ( S E’ $
match(a, a)
( c; c ) w b $
( S E’ $
match( ‘(‘, ‘(‘)
c; c ) w b $
S E’ $
predict(S, c) = S  c S’
c; c ) w b $
c S’ E’ $
match(c, c)
;c)wb$
S’ E’ $
predict(S’, ;) = S’  ; S
;c)wb$
; S E’ $
match( ‘(;, ‘;‘)
c)wb$
S E’ $
predict(S, c) = S  c S’
c)wb$
c S’ E’ $
match(c, c)
)wb$
S’ E’ $
predict(S’, ‘)’) = S’  )
)wb$
) E’ $
match( ‘)‘, ‘)‘)
wb$
E’ $
predict(E’, w) = E’  w E’’
wb$
w E’’ $
match(w, w)
b$
E’’ $
predict(E’’, b) = E’’  b
b$
b$
match(b, b)
$
$
17
Running on a ( c; c ) w b
Input suffix
Stack content
Move
a ( c; c ) w b$
E$
predict(E, a) = E  a ( S E’
a ( c; c ) w b$
a ( S E’ $
match(a, a)
( c; c ) w b $
( S E’ $
match( ‘(‘, ‘(‘)
c; c ) w b $
S E’ $
predict(S, c) = S  c S’
c; c ) w b $
c S’ E’ $
match(c, c)
;c)wb$
S’ E’ $
predict(S’, ;) = S’  ; S
;c)wb$
; S E’ $
match( ‘(;, ‘;‘)
c)wb$
S E’ $
predict(S, c) = S  c S’
)wb$
) E’ $
match( ‘)‘, ‘)‘)
wb$
E’ $
predict(E’, w) = E’  w E’’
wb$
w E’’ $
match(w, w)
b$
E’’ $
predict(E’’, b) = E’’  b
b$
b$
match(b, b)
$
$
c)wb$
)wb$
Since the input has been read and the stack is match(c, c)
c S’ E’ $
empty – the parsing was successful and the input is
S’ E’ $
predict(S’, ‘)’) = S’  )
accepted
18
1/--страниц
Пожаловаться на содержимое документа