# 3 The Gump Parser Generator

This chapter describes the Gump Parser Generator. As for the Gump Scanner Generator described in the last chapter, its input consists of an Oz source with embedded parser specifications and the output are Oz class definitions.

Definitions

A parser is a program that performs syntax analysis. This means that a stream of tokens is analyzed and a (unique) tree structure on the tokens in this stream is computed. The token classes are called terminal symbols; additionally, new nonterminal symbols are introduced in the specification. For each nonterminal, a set of rules is given which indicates sequences of symbols that may be replaced by this nonterminal. The token sequence is read from left to right and subsequences of symbols are replaced by nonterminal symbols according to the rules (which is called a reduction). Either the result is a special nonterminal, a start symbol, or the input is erroneous and rejected. A result is constructed during the parse by executing user-specified semantic actions each reduction.

This chapter first describes the basic concepts of the Gump Parser Generator by example in Section 3.1. Section 3.2 presents the more advanced concepts and a detailed definition of the specification language.