Parsing

In this chapter we shall introduce the central concept of this monograph, namely the parsing of context-free languages. The theory of parsing plays an important role in the design of compilers for programming languages. Every compiler includes a module called the parser, which has a twofold task in the compilation process. First, the parser checks that the program text to be compiled is syntactically correct, i.e., derivable by the context-free grammar of the programming language. In doing this the parser acts as a language recognizer. Secondly, if the program text proves to be syntactically correct, the parser goes on to produce some intermediate representation of the text for use as input to the module responsible for object code generation. In doing this the parser acts as a text transformer.