[SOLVED] CS compiler Parsing

Parsing
Aditya Thakur
ECS 140A Programming Languages Winter 2019

Top-down parsing
Constructs parse tree for input string starting from the root Finds the leftmost derivation for an input string

Context-free grammar for arithmetic expressions
! # !$
!$ +# !$ | # (#$
#$ ( #$ | ( ! |*+

Can we derive the string *+ + *+ *+?
! # !$
!$ +# !$ | # (#$
#$ ( #$ | ( ! |*+

!#!$
























$ $ !+#!|
$
$$
# ( # |
( ! |*+

# (#

!#!$
























$ $ !+#!|
$
$$
# ( # |
( ! |*+

# (#

Top-down parsing
Constructs parse tree for input string starting from the root
Finds the leftmost derivation for an input string
Two types:
Recursive descent parsing Predictive parsing

Recursive-descent parsing
Consists of a procedure for each nonterminal
Execution begins with the procedure for the start symbol








Nondeterministic, might require backtracking



Typical procedure for nonterminal !

Predictive parser
Top-down parser that can correctly choose !-production by looking at at the next symbols in the input
No backtracking during parsing

LL(1) parser
Predictive parser that only looks at the next input symbol Derives the leftmost derivation

LL(1) parser




Constructs parsing table using FIRST and FOLLOW sets of the
grammar

FIRST sets
!#$% & is the set of terminals that begin strings derived from the string of grammar symbols &

FIRST sets
!#$% & is the set of terminals that begin strings derived from the string of grammar symbols &
If is a terminal, !#$%() = {}
If is a nonterminal and ./.0 .2 is a production, then everything in !#$% ./ is in !#$% .
If ./ derives 4, then add !#$% .0 to !#$%(), and so on.
If 4 is in all !#$% .5 then add 4 to !#$%() If 4 is a production, add 4 to !#$% .

FIRST sets
!#$% & is the set of terminals that begin strings derived from the string of grammar symbols &
% )
) +% ) | , % !%)
%) ! %) | , ! |./

FIRST sets
!#$% & is the set of terminals that begin strings derived from the string of grammar symbols &
% )
) +% ) | , % !%)
%) ! %) | , ! |./
First
E
E
T
T
F

FIRST sets
!#$% & is the set of terminals that begin strings derived from the string of grammar symbols &
% )
) +% ) | , % !%)
%) ! %) | , ! |./
First
E
E
T
T
F
( id

FIRST sets
!#$% & is the set of terminals that begin strings derived from the string of grammar symbols &
% )
) +% ) | , % !%)
%) ! %) | , ! |./
First
E
E
T
( id
T
F
( id

FIRST sets
!#$% & is the set of terminals that begin strings derived from the string of grammar symbols &
% )
) +% ) | , % !%)
%) ! %) | , ! |./
First
E
( id
E
T
( id
T
F
( id

FIRST sets
!#$% & is the set of terminals that begin strings derived from the string of grammar symbols &
% )
) +% ) | , % !%)
%) ! %) | , ! |./
First
E
( id
E
+,
T
( id
T
F
( id

FIRST sets
!#$% & is the set of terminals that begin strings derived from the string of grammar symbols &
% )
) +% ) | , % !%)
%) ! %) | , ! |./
First
E
( id
E
+,
T
( id
T
*,
F
( id

FOLLOW
!##$(&) is the set of terminals that can appear immediately to the right of a nonterminal & in a derivation

FOLLOW
!##$(&) is the set of terminals that can appear immediately to the right of a nonterminal & in a derivation
$ is in !##$(() where ( is the start symbol and $ is an endmarker If there is a production & *+,,
then !-.(/(,)1 is in !##$(+)
If there is a production & *+ or & *+,, where !-.(/(,) contains 1, then everything in !##$(&) is in !##$(+).

FOLLOW
!##$(&) is the set of terminals that can appear immediately to the right of a nonterminal & in a derivation
( * (+
(+ +* (+ | . * !*+
*+ ! *+ | . ! ( |01
FOLLOW
E
)$
E
)$
T
+)$
T
+)$
F
+*)$

Parsing table
Parsing table !: # % where # is the set of nonterminals, % is the set of terminals, is the set of production rules
For each production ( ): Foreachterminal*in+,-% ) ,MA,a = () If34+,-%())and74+8998:((),!(,7 =( )

! # !$
! $ + # ! $ |
# (#$
$ $
First
E
( id
E
+

T


( id

T
*
F
(id
FOLLOW
E

)$
E
)$

T
+)$
T
+)$
F
+*)$

#(#|

( ! |*+

Table-driven predictive parser

Table-driven predictive
p
a
r

r

s

e

Deriving the string ! + ! !


















Parsing table

Moves made by the parser

Deriving the string ! + ! !


















Parsing table

Moves made by the parser

Deriving the string ! + ! !


















Parsing table

Moves made by the parser

Deriving the string ! + ! !


















Parsing table

Moves made by the parser

Deriving the string ! + ! !


















Parsing table

Moves made by the parser

Deriving the string ! + ! !


















Parsing table

Moves made by the parser

Deriving the string ! + ! !


















Parsing table

Moves made by the parser

Deriving the string ! + ! !


















Parsing table

Moves made by the parser

Deriving the string ! + ! !


















Parsing table

Moves made by the parser

Deriving the string ! + ! !


















Parsing table

Moves made by the parser

Deriving the string ! + ! !


















Parsing table

Moves made by the parser

Deriving the string ! + ! !


















Parsing table

Moves made by the parser

Deriving the string ! + ! !


















Parsing table

Moves made by the parser

Deriving the string ! + ! !


















Parsing table

Moves made by the parser

Deriving the string ! + ! !


















Parsing table

Moves made by the parser

Deriving the string ! + ! !


















Parsing table

Moves made by the parser

Deriving the string ! + ! !


















Parsing table

Moves made by the parser

Not all grammars are LL(1)


Grammar




Parsing table






















Multiple rules possible in the same entry in the parsing table, because of ambiguity.
All LL(1) grammars are unambiguous.

Optional reading
Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. Compilers: principles, Techniques and tools.
Q: What type of parser is used in the Go compiler?