Compiler Writing

Scanners (Compiler Writing) Part 4

EQUIVALENCE OF REGULAR GRAMMARS AND FINITE-STATE ACCEPTORS The equivalence of regular grammars and finite-state acceptors is shown in this section. First, a method for constructing an NFA from a regular grammar is given. Then a way of converting a DFA to a regular grammar is illustrated, completing the proof that the languages accepted by finite-state […]

Scanners (Compiler Writing) Part 5

A SCANNER GENERATOR The first two sections of this topic introduced scanners and discussed the tasks which scanners usually perform. The next three sections introduced mathematical models which are useful for programming a scanner in a systematic manner and for creating a scanner using a scanner generator. This section introduces a scanner generator which uses […]

Compile-Time Error Handling Part 1

Because of the nature of the programming process, a programming language translator is more often confronted with syntactically erroneous programs than with correct ones. Thus the translator must have some strategy for dealing with source programs which are invalid with respect to the rules of the programming language. The response to errors can lie anywhere […]

Compile-Time Error Handling Part 2

ERROR REPORTING In order for effective error detection to be of any value to the users of a compiler, each error, once detected, must be clearly and precisely reported. To those who have never been involved in a large software project, it may not be obvious that error reporting requires special consideration. Small application programs […]

Compile-Time Error Handling Part 3

Secondary Error Recovery Some error-recovery strategies, especially ad hoc strategies, are not always successful in localizing and recovering from an error. Such strategies may be prone to unbounded looping and may have to be limited in order to prevent them from consuming all available time or all of the source text. In such cases, it […]

Top-Down Parsing (Compiler Writing) Part 1

In Sec. 2-4.2 the notions of top-down parsing and bottom-up parsing were introduced. Recall that top-down parsing was characterized as a parsing method which, beginning with the goal symbol of the grammar, attempted to produce a string of terminal symbols that was identical to a given source string. This matching process proceeded by successively applying […]

Top-Down Parsing (Compiler Writing) Part 2

Recursive-Descent Parsers In this section the brute-force parsing strategy just discussed is restricted so that backup is not allowed. This revised method of parsing, though less general, performs better than the brute-force method. This section also describes an approach to error detection and recovery for this modified parsing technique. Recursive-descent parsing algorithm.. The top-down parsing […]

Top-Down Parsing (Compiler Writing) Part 3

TOP-DOWN PARSING WITH NO BACKUP In this section top-down parsing with no backup is discussed. The information required during a no-backup parse is first discussed informally and then formally characterized in terms of LL(1) grammars. This class of grammars can be parsed in a deterministic manner by looking at the next input symbol in the […]

Top-Down Parsing (Compiler Writing) Part 4

LL(1) Grammars with e-Rules In this subsection we generalize the LL(1) grammars introduced in the previous subsection to include e-rules (see Sec. 2-4.3). We will see that such an inclusion defines a larger class of grammars and that the corresponding parsing algorithm is substantially more complex. Before we proceed with the discussion, however, we must […]

Top-Down Parsing (Compiler Writing) Part 5

Error Handling for LL(1) Parsers The LL(1) parser described in the previous section performs a correct parse of any valid input string. Given an erroneous string, however, it parses to the point of the first error, prints ‘UNSUCCESSFUL PARSE’, and stops. Although this is acceptable behavior for an abstract parser, it is unacceptable in a […]