4
Syntax Analyzer
What you will learn in this chapter
- Some basic parsing terms
- Recursive-descent Parser
- Top-down parsing
- Bottom-up parsing
- Various types of LL(1) grammars and parsers
- Shift/Reduce and Operator precedence parser
- LR(0), SLR(1), LR(1) and LALR(1) parsers
- What are conflict situations in LR parsers?
- How conflicts are resolved?
- Compiler writing tools– yacc, bison and ANTLR
Key Words
syntax analysis, parser, RDP, Top-down, Bottom-up, LL(1), LR(0), SLAR(1), LR(1), LALR(1), conflicts, resolution of conflicts, yacc, bison
Parsing is a general term meaning analyzing a sentence to arrive at its syntactic structure. From theoretical viewpoint, lexical analysis is also parsing, only the atoms of the language involved are at finer granularity.
Though a typical programming language contains several context-sensitive rules, e.g. identifier types, goto labels, number of arguments in a function, etc., there is no known parsing algorithm for context-sensitive grammars. We therefore define the programming languages in terms of regular (Chomsky type 3) and context-free (Chomsky type 2) grammars (Appendix A) and use the context-sensitive rules separately while performing the semantic analysis.
Table 4.1 Parsing: Scanner and Parser
| Item | Scanner | Parser |
|---|---|---|
| Language atoms | Characters | Tokens |
| Structure sought | Tokens for identifiers, numbers, operators | Statement expressions, control constructs |
| Usual grammar | Regular | CFG |
| Usual acceptor | FSM | PDA |
We shall assume that the reader has some background in formal languages and Automata, but it is strongly suggested that the material given in Appendix A be reviewed. We have defined and explained some of the terms – such as sentential form, phrase, simple phrase and handle – used in the discussion of parsing in Section A.5.2. Also, the definitions of an ambiguous sentence and an ambiguous grammar given there should be referred to.