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 *+ + *+ ∗ *+?
! → # !$
!$ → +# !$ | ‘ # →(#$
#$ → ∗ ( #$ | ‘ ( → ! |*+