29-11-2012, 04:22 PM
Compiler Construction A Practical Approach
CompilerConstruction.pdf (Size: 2.15 MB / Downloads: 41)
Abstract
Plenty of literature is available to learn about compiler construction,
but most of it is either too easy, covering only the very basics, or
too dicult and accessible only to academics. We nd that, most
notably, literature about code generation is lacking and it is in this
area that this book attempts to ll in the gaps.
In this book, we design a new language (Inger), and explain how
to write a compiler for it that compiles to Intel assembly language.
We discuss lexical analysis (scanning), LL(1) grammars, recursive
descent parsing, syntax error recovery, identication, type checking
and code generation using templates and give practical advice on
tackling each part of the compiler.
Introduction
This book is about constructing a compiler. But what, precisely, is a compiler?
We must give a clear and complete answer to this question before we can begin
building our own compiler.
In this chapter, we will introduce the concept of a translator, and more
specically, a compiler. It serves as an introduction to the rest of the book and
presents some basic denitions that we will assume to be clear throughout the
remainder of the book.
Translation and Interpretation
A compiler is a special form of a translator:
A translator is a program, or a system, that converts an input text some language
to a text in another language, with the same meaning.
One translator could translate English text to Dutch text, and another could
translate a Pascal program to assembly or machine code. Yet another translator
might translate chess notation to an actual representation of a chess board, or
translate a web page description in HTML to the actual web page. The latter
two examples are in fact not so much translators as they are interpreters:
Denition 1.2 (Interpreter)
An interpreter is a translator that converts an input text to its meaning, as
dened by its semantics.
A BASIC-interpreter like GW-BASIC is a classic and familiar example of
an interpreter. Conversely, a translator translates the expression 2+3 to, for
example, machine code that evaluates to 5. It does not translate directly to 5.
The processor (CPU) that executes the machine code is the actual interpreter,
delivering the nal result. These observations lead to the following relationship:
Sometimes the dierence between the translation of an input text and its
meaning is not immediately clear, and it can be dicult to decide whether a
certain translator is an interpreter or not.
A compiler is a translator that converts program source code to some target
code, such as Pascal to assembly code, C to machine code and so on. Such
translators dier from translators for, for example, natural languages because
their input is expected to follow very strict rules for form (syntax) and the
meaning of an input text must always be clear, i.e. follow a set of semantic
rules.
Many programs can be considered translators, not just the ones that deal
with text. Other types of input and output can also be viewed as structured text
(SQL queries, vector graphics, XML) which adheres to a certain syntax, and
therefore be treated the same way. Many conversion tools (conversion between
graphics formats, or HTML to LATEX) are in fact translators. In order to think
of some process as a translator, one must nd out which alphabet is used (the
set of allowed words) and which sentences are spoken. An interesting exercise
is writing a program that converts chess notation to a chess board diagram.