This chapter consists of four sections. Section 17.1 conceptualizes two fundamental approaches to syntax analysis -top-down parsing and bottom-up parsing. Then, Section 17.2 describes the former approach, while Section 17.3 explores the latter. Section 17.4 explains how to implement a syntax-directed translation, which is completely driven by a parser when producing target machine language programs.

Chapter Contents:

• 17.1 General parsers
• 17.1.1 Syntax specified by context-free grammars
• 17.1.2 Top-down parsing
• 17.1.3 Bottom-up parsing
• 17.2 Top-down parsers
• 17.2.1 Predictive sets and LL grammars
• 17.2.2 LL grammars
• 17.2.3 Predictive parsing
• 17.2.4 Predictive recursive-descent parsing
• 17.2.5 Predictive table-driven parsing
• 17.2.6 Handling errors
• 17.2.7 Exclusion of left recursion
• 17.3 Bottom-up parsers
• 17.3.1 Operator-precedence parsing
• 17.3.2 Operator-precedence parser
• 17.3.3 Construction of operator-precedence parsing table
• 17.3.4 Handling errors
• 17.3.5 Operator-precedence parsers for other expressions
• 17.3.6 LR parsing
• 17.3.7 LR parsing algorithm
• 17.3.8 Construction of the LR table
• 17.3.9 Handling errors in LR parsing
• 17.4 Syntax-directed translation: an implementation

Inspec keywords: grammars; programming languages; computational linguistics

Other keywords: machine language programs; syntax analysis; programming languages; top-down parsing; bottom-up parsing; syntax-directed translation

Subjects: Natural language interfaces; Formal languages and computational linguistics; Programming languages