Compiler Writing

Bottom-Up Parsing (Compiler Writing) Part 1

A second class of parsing techniques builds parse tree from the leaves toward its root, i.e., in a bottom-up manner. Several bottom-up parsing techniques with no backup are presented in this topic. All the parsing techniques except the first are based on formal syntactic notions. Several formal classes of grammars have been created. For a […]

Bottom-Up Parsing (Compiler Writing) Part 2

OPERATOR PRECEDENCE GRAMMARS In Sec. 7-1 the technique of establishing precedence relations between symbols was used to convert infix expressions to their suffix Polish equivalents. This conversion was based on the use of the input and stack precedence functions (/ and g functions, respectively). This section describes one of the earliest formal parsing techniques which […]

Bottom-Up Parsing (Compiler Writing) Part 3

Formal Definition of Operator Precedence Relations In the previous subsection the operator precedence relations were obtained by examining syntax trees. We now redefine these relations in terms of the productions of the grammar. It is shown that these relations can be computed easily from the grammar. Definition 7-2 The operator precedence relations associated with an […]

Bottom-Up Parsing (Compiler Writing) Part 4

Error Detection in Operator Precedence Parsers Errors can be detected in operator precedence parsers by making use of the blank entries in the operator precedence matrix. When such a blank entry is referenced in the parsing algorithm, a routine can be invoked that will report the error. The error message generated depends on the nature […]

Bottom-Up Parsing (Compiler Writing) Part 5

Precedence Functions for Simple Precedence Grammars The notion of precedence functions was introduced in Sec. 7-2.4. As indicated there, memory restrictions may require a reduction in the amount of space utilized by a precedence matrix, making it necessary to use precedence functions in order to reduce the storage requirements of a compiler. In this subsection, […]

Bottom-Up Parsing (Compiler Writing) Part 6

Error Recovery for Simple Precedence Parsers The simple precedence parser described in the preceding sections performs a correct parse of any input string which is in the language generated by a particular simple precedence grammar. Furthermore, it refuses to accept any string which is not in the language. Given such a string, the parser stops […]

Bottom-Up Parsing (Compiler Writing) Part 7

Notions of Extended Precedence This subsection first examines a few example grammars that fail to be of the type simple precedence. One approach that can be used is to rewrite the given grammar into an equivalent grammar which is simple precedence. This approach, however, may not work if the language described by the original grammar […]

Bottom-Up Parsing (Compiler Writing) Part 8

LR GRAMMARS This section deals with the construction of deterministic parsers for a class of grammars called LR(k) grammars. This class of grammars is essentially the set of all unambiguous context-free grammars and properly contains other previously encountered classes of grammars such as LL(k) and precedence grammars. An LR(k) parser scans a given input string […]

Bottom-Up Parsing (Compiler Writing) Part 9

SLR (I) Parsers This subsection formulates a parsing algorithm for the simplest class of LR grammars, which are based on a lookahead of one symbol, known as the class of SLR( 1) grammars. The parser for an SLR( 1) grammar can be obtained from the LR(0) machine for that grammar and other easily obtained information […]

Bottom-Up Parsing (Compiler Writing) Part 10

Canonical LR( 1) Parsers The previous subsection gave an example of a grammar that was not SLR{1). The method of resolving inadequate states in the SLR( 1) method is to obtain lookahead information through FOLLOW set computations. Recall that the sets of lookahead symbols obtained by the FOLLOW set computations yield supersets of the sets […]

← Previous Entries

Next Entries →