The purpose of the syntactic analyzer, or parser, is to construct a parse tree using as input the stream of tokens provided by the lexer. The output of the parser is usually an abstract syntax tree. The motivation for using an abstract syntax tree, rather than a parse tree. Chapter 3 - Lexical and syntactic analysis: Syntactic analysis. | Programming Languages 2nd edition Tucker and Noonan Chapter 3 Lexical and Syntactic Analysis Syntactic sugar causes cancer of the semicolon. A. Perlis Contents Chomsky Hierarchy Lexical Analysis Syntactic Analysis Syntactic Analysis Phase also known as: parser Purpose is to recognize source structure Input: tokens Output: parse tree or abstract syntax tree A recursive descent parser is one in which each nonterminal in the grammar is converted to a function which recognizes input derivable from the nonterminal. Program Structure consists of: Expressions: x + 2 * y Assignment Statement: z = x + 2 * y Loop Statements: while (i > } while (( ) > oldSize); Check Righthand Side { boolean allNull = true; for (Symbol t : ( )) if (! (t)) allNull = false; if (allNull) (( )); } Rewrite Grammar Augmented form Abbreviate symbols Replace meta constructs with nonterminals Transformed Grammar S → A $ A → i = E ; E → T E' E' → | AO T E' AO → + | - T → F T' T' → MO F T' MO → * | / F → F' P F' → | UO UO → - | ! P → i | l | ( E ) . | Programming Languages 2nd edition Tucker and Noonan Chapter 3 Lexical and Syntactic Analysis Syntactic sugar causes cancer of the semicolon. A. Perlis Contents Chomsky Hierarchy Lexical Analysis Syntactic Analysis Syntactic Analysis Phase also known as: parser Purpose is to recognize source structure Input: tokens Output: parse tree or abstract syntax tree A recursive descent parser is one in which each nonterminal in the grammar is converted to a function which recognizes input derivable from the nonterminal. Program Structure consists of: Expressions: x + 2 * y Assignment Statement: z = x + 2 * y Loop Statements: while (i < n) a[i++] = 0; Function definitions Declarations: int i; Assignment → Identifier = Expression Expression → Term { AddOp Term } AddOp → + | - Term → Factor { MulOp Factor } MulOp → * | / Factor → [ UnaryOp ] Primary UnaryOp → - | ! Primary → Identifier | Literal | ( Expression ) First Set Augmented form: S – start symbol S' → S $ First(X) is set of .
