Recursive ascent parser: Difference between revisions

Revision as of 01:43, 24 March 2009

Revision as of 03:35, 24 March 2009

Line 5:

Intuitively, recursive ascent is a literal implementation of the [[LR parser|LR parsing]] concept. Each function in the parser represents a single LR [[Finite state machine|automaton]] state. Within each function, a multi-branch statement is used to select the appropriate action based on the current token popped off the input stack. Once the token has been identified, action is taken based on the state being encoded. There are two different fundamental actions which may be taken based on the token in question:

* '''Shift''' - Encoded as a function call, effectively jumping to a new automaton state. This call must involve an increment of the "shift counter", an integer value which tracks the number of tokens shifted in a given production prior to each reduce.

* '''Reduce''' - Encoded differently according to the [[semantic action routine]] for the relevant production. The result of this routine is wrapped in an [[Algebraic data type|ADT]] which is returned to the caller. The reduce action must also record the number of tokens which were shifted ''prior'' to the reduce, passing this value back to the caller along with the reduce value. This shift counter determines at which point up the call stack the reduce should be handled.