Bottom-up parsing
From Wikipedia, the free encyclopedia
Bottom-up parsing is a strategy for analyzing unknown data relationships that attempts to identify the most fundamental units first, and then to infer higher-order structures from them. We are attempting to build trees upward toward the start symbol. It occurs in the analysis of both natural languages and computer languages.
- See also: top-down parsing
Within computer science, bottom-up parsing is also known as "shift-reduce parsing"
Contents |
[edit] Linguistics
In linguistics, an example of bottom-up parsing would be analyzing a sentence by identifying words first, and then using properties of the words to infer grammatical relations and phrase structures to build a parse tree of the complete sentence. This means that rather than beginning with the starting symbol and generating an input string, we shall examine the string and attempt to work our way back to the starting symbol. We can gain some power by starting at the bottom and working our way up.
[edit] Computer Science
In programming language compilers, bottom-up parsing is a parsing method that works by identifying terminal symbols first, and combines them successively to produce nonterminals. The productions of the parser can be used to build a parse tree of a program written in human-readable source code that can be compiled to assembly language or pseudocode.
Different computer languages require different parsing techniques, although it is not uncommon to use a parsing technique that is more powerful than that actually required.
It is common for bottom-up parsers to take the form of general parsing engines, that can either parse or generate a parser for a specific programming language given a specification of its grammar. Perhaps the most well known generalized parser generator is YACC.
[edit] An example using a parse tree
A trivial example illustrates the difference. Here is a trivial grammar:
S → Ax A → a A → b
For the input sentence ax, the leftmost derivation is
S ⇒ Ax ⇒ ax
which also happens to be the rightmost derivation as there is only one nonterminal ever to replace in a sentential form.
An LL(1) parser starts with S and asks "which production should I attempt?" Naturally, it predicts the only alternative of S. From there it tries to match A by calling method A (in a recursive-descent parser). Lookhead a predicts production
A → a
The parser matches a, returns to S and matches x. Done. The derivation tree is:
S / \\ A x | a
A bottom up parser is trying to go backwards, performing the following reverse derivation sequence:
ax ⇒ Ax ⇒ S
Intuitively, a top-down parser tries to expand nonterminals into right-hand-sides and a bottom-up parser tries to replace (reduce) right-hand-sides with nonterminals.
The first action of the bottom-up parser would be to replace a with A yielding Ax. Then it would replace Ax with S. Once it arrives at a sentential form with exactly S, it has reached the goal and stops, indicating success.
Just as with top-down parsing, a brute-force approach will work. Try every replacement until you run out of right-hand-sides to replace or you reach a sentential form consisting of exactly S. While not obvious here, not every replacement is valid and this approach may try all the invalid ones before attempting the correct reduction. Backtracking is extremely inefficient, but as you would expect lookahead proves useful in reducing the number of "wrong turns."
[edit] Type of Bottom-up Parsers
The common classes of bottom-up parsing are:
- LR parser
- LR(0) - No lookahead symbol
- SLR(1) - Simple with one lookahead symbol
- LALR(1) - Lookahead bottom up, not as powerful as full LR(1) but simpler to implement. YACC uses this language.
- LR(1) - Most general language, but most complex to implement.
- LR(n) - where n is an integer>=0 indicates an LR parser with n lookahead symbols; while languages can be designed that require more than 1 lookahead, practical languages try to avoid this because increasing n can threoretically require exponentially more code and data space (in practice, this may not be as bad).
- Precedence parser
- Simple precedence parser
- Operator-precedence parser
- Extended precedence parser
The most common bottom-up parsers are the so-called shift-reduce parsers. These parsers examine the input tokens and either shift them onto a stack or reduce the top of the stack, replacing a right-hand side by a left-hand side.
Definition of action table: Often a table is formed which helps the parser determine what to do next. This is also called a parse table. The following is a description of what can be held in an action table.
Actions – Shift - push token onto stack – Reduce - remove handle from stack and push on corresponding nonterminal – Accept - recognize sentence when stack contains only the distinguished symbol and input is empty – Error - happens when none of the above is possible; means original input was not a sentence!
Definition of shift and reduce: A shift-reduce parser uses a parse stack contains grammar symbols. During the operation of the parser, symbols from the input are shifted onto the stack. If a prefix of the symbols on top of the stack matches the RHS of a grammar rule which is the correct rule to use within the current context, then the parser reduces the RHS of the rule to its LHS, replacing the RHS symbols on top of the stack with the nonterminal occurring on the LHS of the rule. This shift-reduce process continues until the parser terminates, reporting either success or failure. It terminates with success when the input is legal and is accepted by the parser. It terminates with failure if an error is detected in the input.
The parser is nothing but a stack automaton which may be in one of several discrete states. A state is usually represented simply as an integer. In reality, the parse stack contains states, rather than grammar symbols. However, since each state corresponds to a unique grammar symbol, the state stack can be mapped onto the grammar symbol stack mentioned earlier.
- Shift means moving a symbol from the input to the stack
- Reduce means matching a set of symbols in the stack for a more general symbol
[edit] An Example of shift-reduce parsing
This is how it works:
1. Start with the sentence to be parsed as the initial sentential form
2. Until the sentential form is the start symbol do:
1. Scan through the input until we recognise something that corresponds to the r.h.s. of one of the production rules (this is called a handle)
2. Apply a production rule in reverse; ie. replace the r.h.s. of the rule which appears in the sentential form with the l.h.s. of the rule (an action known as a reduction)
In step 2(a) above we are ``shifting the input symbols to one side as we move through them; hence a parser which operates by repeatedly applying steps 2(a) and 2(b) above is known as a shift-reduce parser.
A shift-reduce parser is most commonly implemented using a stack, where we proceed as follows:
* start with the sentence to be parsed on top of the stack * a "shift" action correponds to pushing the current input symbol onto the stack * a "reduce" action occurrs when we have a handle on top of the stack. To perform the reduction, we pop the handle off the stack and replace it with the terminal on the l.h.s. of the corresponding rule.
Figure 1.
Take the language: Sentence --> NounPhrase VerbPhrase NounPhrase --> Art Noun VerbPhrase --> Verb | Adverb Verb Art --> the | a | ... Verb --> jumps | sings | ... Noun --> dog | cat | ... And the input: the dog jumps Then the bottom up parsing is: Stack Input Sequence () (the dog jumps) (the) (dog jumps) SHIFT word onto stack (Art) (dog jumps) REDUCE using grammar rule (Art dog) (jumps) SHIFT.. (Art Noun) (jumps) REDUCE.. (NounPhrase) (jumps) REDUCE (NounPhrase jumps) () SHIFT (NounPhrase Verb) () REDUCE (NounPhrase VerbPhrase)() REDUCE (Sentence) () SUCCESS Given the language: <Expression> --> <Term> <Term> --> <Factor> | <Factor> * <Term> <Factor> --> [ <Expression ] | 0...9 () (2 * [ 1 + 3 ]) SHIFT (2) (* [ 1 + 3 ]) REDUCE (<Factor>) (* [ 1 + 3]) SHIFT (<Factor> *) ([ 1 + 3]) SHIFT (<Factor> * [) (1 + 3]) SHIFT (<Factor> * [ 1) (1 + 3]) REDUCE (2 times..) (<Factor> * [ <Term>) (+ 3 ]) SHIFT (twice) (<Factor> * [ <Term> + 3) ( ]) REDUCE (3 times) (<Factor> * [ <Term> + <Expression>) ( ]) REDUCE (<Factor> * [ <Expression>) ( ]) SHIFT (<Factor> * [ <Expression> ]) () REDUCE (<Factor> * <Factor>) () REDUCE (<Factor> * <Term>) () REDUCE (<Term>) () REDUCE (<Expression>) () SUCCESS
[edit] A difference between top down parsing and bottom up parsing in the decisions
In a top-down parser, the main decision was which production rule to pick. In a bottom-up shift-reduce parser there are two decisions:
1. Should we shift another symbol, or reduce by some rule? 2. If reduce, then reduce by which rule?
[edit] External links
- [1] An example of shift-reduce parsing (which is a type of bottom up parsing), with a small grammar, state diagram, and c language code to implement the parser
- [2] course notes on shift reduce parsing
- [3] A good non-technical tutorial in the context of natural (human) languages
- [4] A discussion of shift-reduce conflicts in bottom up parsers. A knowledgeable but technical article.
- [5]
