|
==Implementation==
* Compute the [[Wirth–Weber precedence relationship]] table for a grammar with initial symbol S.
* Start withInitialize a stack with only the '''starting marker''' $.
* StartAppend withan '''ending marker''' $ to the string being parsed ('''Input''') ended with an '''ending marker''' $.
* WhileUntil not (Stack equals to"$ $S" and Input equals to "$) (S = Initial symbol of the grammar)"
** Search in the table for the relationship between Top(stack) and NextToken(Input)
** if the relationship is &esdotltdot; or <dotesdot;
*** '''Shift''':
*** Push(Stack, relationship)
*** '''Reduce''':
*** SearchProductionToReduce(Stack)
*** RemovePivot(Remove the Pivot from the Stack)
*** Search in the table for the relationship between the Non terminalnonterminal from the production and first symbol in the stack (Starting from top)
*** Push(Stack, relationship)
*** Push(Stack, Non terminal)
SearchProductionToReduce (Stack)
* searchFind the '''Pivot'''topmost ⋖ in the stack; this and all the nearestsymbols ⋖above fromit are the top'''Pivot'''.
* search inFind the productionsproduction of the grammar which one have the same right side thanhas the '''Pivot''' as its right side.
==Example==
| 