DESKTOP

# Algorithms for Compiler Design: A HANDLE OF A RIGHT SENTENTIAL FORM

7/24/2010 7:51:14 PM
##### 5.2 A HANDLE OF A RIGHT SENTENTIAL FORM A handle of a right sentential form γ is a production A → β and a position of β in γ. The string β will be found and replaced by A to produce the previous right sentential form in the right-most derivation of γ. That is, if S → αAβ → αγβ, then A → γ is a handle of αγβ, in the position following α. Consider the grammar: and the right-most derivation: The handles of the sentential forms occurring in the above derivation are shown in Table 1. Table 1: Sentential Form Handles Sentential Form Handle id + id * id E → id at the position preceding + E + id * id E → id at the position following + E + E * id E → id at the position following* E + E * E E → E * E at the position following + E + E E → E + E at the position preceding the end marker Therefore, the bottom-up parsing is only an attempt to detect the handle of a right sentential form. And whenever a handle is detected, the reduction is performed. This is equivalent to performing right-most derivations in reverse and is called "handle pruning". Therefore, if the right-most derivation sequence of some w is S → α1 → α2 → α3 → … → αn−1 → w, then handle pruning starts with w, the nth right sentential form, the handle βn of w is located, and βn is replaced by the left side of some production An → βn in order to obtain αn−1. By continuing this process, if the parser obtains a right sentential form that consists of only a start symbol, then it halts and announces the successful completion of parsing. EXAMPLE 1 Consider the following grammar, and show the handle of each right sentential form for the string (a,(a, a)). The right-most derivation of the string (a, (a, a)) is: Table 2 presents the handles of the sentential forms occurring in the above derivation. Table 2: Sentential Form Handles Sentential Form Handle (a, (a, a)) S → a at the position preceding the first comma (S, (a, a)) L → S at the position preceding the first comma (L, (a, a)) S → a at the position preceding the second comma (L, (S, a)) L → S at the position preceding the second comma (L, (L, a)) S → a at the position following the second comma (L, (L, S)) L → L, S, at the position following the second left bracket (L, (L)) S → (L) at the position following the first comma (L, S) L → L, S, at the position following the first left bracket (L) S → (L) at the position before the endmarker var sc_project=11388663; var sc_invisible=1; var sc_security="7db37af3"; var scJsHost = (("https:" == document.location.protocol) ? "https://secure." : "http://www."); document.write("<sc"+"ript type='text/javascript' src='" + scJsHost+ "statcounter.com/counter/counter.js'></"+"script>");
 Other

 Top 10
 -  SQL Server 2005 : Working with SQL Server Management Objects in Visual Studio (part 3) - Creating Backup-and-Restore Applications, Performing Programmatic DBCC Commands with SMO
 -  SQL Server 2005 : Working with SQL Server Management Objects in Visual Studio (part 2) - Retrieving Server Settings
 -  SQL Server 2005 : Working with SQL Server Management Objects in Visual Studio (part 1) - Iterating Through Available Servers
 -  Deploying to an iPhone, Debugging, and Testing : Distributing Your Application
 -  Visual Basic 2010 : Setup & Deployment Projects for Windows Installer (part 2) - Configuring the Setup Project
 -  Visual Basic 2010 : Setup & Deployment Projects for Windows Installer (part 1) - Creating a Setup Project
 -  Extending the Real-Time Communications Functionality of Exchange Server 2007 : Installing OCS 2007 (part 3)
 -  Extending the Real-Time Communications Functionality of Exchange Server 2007 : Installing OCS 2007 (part 2)
 -  Extending the Real-Time Communications Functionality of Exchange Server 2007 : Installing OCS 2007 (part 1)
 -  Programming .NET Compact Framework 3.5 : Creating Graphical Output - Drawing on the Display Screen
 Most View
 -  Using Non-Windows Systems to Access Exchange Server 2010 : Understanding Non-Windows–Based Mail Client Options
 -  Default Security Policy
 -  Essential Camera Skills Crash Course (Part 3)
 -  1 Month With… Sphero
 -  Musical Fidelity V-CAN II – Headphone Amplifier : Remains A Fine Product For The Money
 -  jQuery 1.3 : Developing plugins - Adding new global functions
 -  Macro Marvels (Part 3)
 -  Network Programming with Windows Sockets : Datagrams
 -  Corel Painter X : The Great Outdoors - Landscape
 -  Exchange Server 2010 : Performing Backup and Recovery for Mailbox Server Roles
 -  Windows 7 : Using Windows Defender (part 3) - Using Windows Defender Tools & Troubleshooting Windows Defender