,Purpose - To verify the syntactic correctness of the input token
stream, reporting any errors and to produce a parse-tree and
certain tables for use by later phases of the compiler.
1. Syntactic correctness is judged by verification against
a formal grammar which specifies the language to be
recognized
2. Error messages are important and should be as
meaningful as possible (this is affected by parsing
technique chosen)
3. Parse tree and tables will vary depending on compiler
implementation technique and source language
Method - Match token stream using manually or automatically
generated parser
, Implementation
Parser implementations are commonly divided into two classes:
1. Top-down - attempt to recognize the goal symbol by
recognizing its constituent symbols
E.g. recursive-descent parsers
– Commonly used in Q&D applications
Also LL parsers - of more practical usefullness
2. Bottom-Up - attempt to match previously recognized
symbols to the RHS of some production thereby
recognizing the LHS symbol of the production
E.g. LR parsers
– Commonly used in commercial compilers
Parsers in either class may be generated automatically using
parser generators such as YACC.