Parser builders
Christos K. K. Loverdos, Apostolos Syropoulos · Cambridge University Press eBooks · 2010
A parser is a piece of software capable of resolving a string into tokens and then checking whether the string belongs or not in a particular (formal) language. Constructing a parser from scratch is an interesting problem. However, a more interesting problem is that of constructing a particular parser from other (predefined?) parsers rather than from scratch. This problem can be solved by using parser builders . In the end, some of these parser builders have to be constructed from scratch, but all the complex parsers can be built from the other parser builders that parse components. Scala includes a rich library for building parsers using parser builders. In this chapter we first give an overview of some relevant notions, then we describe the library and finally we use this library to construct an interpreter for a simple programming language. Language parsers Given an alphabet (i.e., a set of symbols or characters), the closure of this alphabet is a set that has as elements all strings that consist of symbols drawn from this particular alphabet. For example, the digits 0 and 1 form an alphabet and the closure of this alphabet consists of “numbers” like 000, 101, 11, etc. A language can be considered a subset of the closure (including the empty string) of an alphabet. The language that is the closure of an alphabet is not particularly interesting since it is too large.