ABSTRACT
The source language syntax is specified by a grammar, which is based upon finitely many rules. By these rules, the parser of a syntax analyzer verifies that a string of tokens, produced by the lexical analyzer, represents a syntactically well-formed source program. More precisely, reading the string in a left-to-right way, the parser derives the string by the grammatical rules, and if it finds this derivation, the source program syntax is correct. Graphically, this grammatical derivation is usually displayed by a parse tree, in which each parent-children portion represents a grammatical rule, so the parser’s task can be also described as the construction of a parse tree for the string of tokens. This construction is made in a top-down or bottom-up way. A top-down parser builds the parse tree from the root and proceeds down toward the frontier while a bottom-up parser starts from the frontier and works up toward the root. By successfully completing the construction of this tree, the parser verifies that the source program is syntactically correct. Formally, a parser is usually specified by a pushdown automaton, which represents a finite automaton extended by a potentially infinite pushdown list.
