DESKTOP

Algorithms for Compiler Design: Top-down parsing

7/24/2010 7:53:33 PM
4.1 TOP-DOWN PARSING
Top-down parsing attempts to find the left-most derivations for an input string w, which is equivalent to constructing a parse tree for the input string w that starts from the root and creates the nodes of the parse tree in a predefined order. The reason that top-down parsing seeks the left-most derivations for an input string w and not the right-most derivations is that the input string w is scanned by the parser from left to right, one symbol/token at a time, and the left-most derivations generate the leaves of the parse tree in left-to-right order, which matches the input scan order.

Since top-down parsing attempts to find the left-most derivations for an input string w, a top-down parser may require backtracking (i.e., repeated scanning of the input); because in the attempt to obtain the left-most derivation of the input string w, a parser may encounter a situation in which a nonterminal A is required to be derived next, and there are multiple A-productions, such as A α1 | α2 | | αn. In such a situation, deciding which A-production to use for the derivation of A is a problem. Therefore, the parser will select one of the A-productions to derive A, and if this derivation finally leads to the derivation of w, then the parser announces the successful completion of parsing. Otherwise, the parser resets the input pointer to where it was when the nonterminal A was derived, and it tries another A-production. The parser will continue this until it either announces the successful completion of the parsing or reports failure after trying all of the alternatives. For example, consider the top-down parser for the following grammar:

Let the input string be w = acb. The parser initially creates a tree consisting of a single node, labeled S, and the input pointer points to a, the first symbol of input string w. The parser then uses the S-production S aAb to expand the tree as shown in Figure 1.

Click To expand
Figure 1: Parser uses the S-production to expand the parse tree.

The left-most leaf, labeled a, matches the first input symbol of w. Hence, the parser will now advance the input pointer to c, the second symbol of string w, and consider the next leaf labeled A. It will then expand A, using the first alternative for A in order to obtain the tree shown in Figure2.


Figure 2: Parser uses the first alternative for A in order to expand the tree.

The parser now has the match for the second input symbol. So, it advances the pointer to b, the third symbol of w, and compares it to the label of the next leaf. If the label does not match d, it reports failure and goes back (backtracks) to A, as shown in Figure 3. The parser will also reset the input pointer to the second input symbol—the position it had when the parser encountered A—and it will try a second alternative to A in order to obtain the tree. If the leaf c matches the second symbol, and if the next leaf b matches the third symbol of w, then the parser will halt and announce the successful completion of parsing.

Click To expand
Figure 3: If the parser fails to match a leaf, the point of failure, d, reroutes (backtracks) the pointer to alternative paths from A.

Other  
 
Most View
Managing Windows Server 2012 (part 9) - Customizing the desktop and the taskbar - Configuring desktop items, Configuring the taskbar
The Hacked Man (Part 2) - Digital gold: passwords and mail addresses
Adobe Photoshop CS5 : Managing Color from Monitor to Print - Changing from Additive (RGB) to Subtractive (CMYK) Color
The Toyota GT86 – Great Fun To Drive
Enhancing Your Digital Life From The Desktop To Your Mobile (Part 3)
Sony Cybershot DSC-TX30 - Waterproof Camera (Part 1)
Asus F2A85-V PRO Mainboard - A Socket FM2 Mainboard With Good Performance (Part 5)
Windows Server 2003 : Implementing Software Restriction Policies (part 4) - Implementing Software Restriction Policies - Creating a Path Rule, Designating File Types
Intel vs AMD - The Choice Is Harder Than Ever (Part 4)
A Feature Release : Mountain Lion offers evolution, not revolution?
Top 10
The Long Road To Success - Aston Martin Vanquish - Rapidely Gaining Interest - Aston Martin Rapide S (Part 3)
Extra-Curricular Activity - BMW 218d Active Tourer SE - An Engine That’s Fit For A Juke - Nissan Juke Tekna DIG-T (Part 3)
The Long Road To Success - Aston Martin Vanquish - Rapidely Gaining Interest - Aston Martin Rapide S (Part 2)
The Long Road To Success - Aston Martin Vanquish - Rapidely Gaining Interest - Aston Martin Rapide S (Part 1)
Extra-Curricular Activity - BMW 218d Active Tourer SE - An Engine That’s Fit For A Juke - Nissan Juke Tekna DIG-T (Part 2)
Extra-Curricular Activity - BMW 218d Active Tourer SE - An Engine That’s Fit For A Juke - Nissan Juke Tekna DIG-T (Part 1) - BMW 218d Active Tourer SE
Review : Garmin Fenix 2
Middle-earth: Shadow Of Mordor
Review : Leica V-Lux (Typ 114)
Review : Apple iPad Air 2