Simple precedence parser: Difference between revisions
Content deleted Content added
m →Example: Disambiguate Lexer to Lexer (computer science) |
unsourced and tagged since 2009 - removed all but first sentence |
||
| Line 3: | Line 3: | ||
In [[computer science]], a '''simple precedence parser''' is a type of [[bottom-up parser]] for [[context-free grammars]] that can be used only by [[simple precedence grammar]]s. |
In [[computer science]], a '''simple precedence parser''' is a type of [[bottom-up parser]] for [[context-free grammars]] that can be used only by [[simple precedence grammar]]s. |
||
The implementation of the parser is quite similar to the generic [[bottom-up parser]]. A stack is used to store a [[viable prefix]] of a [[sentential form]] from a [[rightmost derivation]]. Symbols <math>\lessdot</math>, <math>\dot =</math> and <math>\gtrdot</math> are used to identify the '''pivot''', and to know when to '''Shift''' or when to '''Reduce'''. |
|||
==Implementation== |
|||
* Compute the [[Wirth-Weber precedence relationship]] table. |
|||
* Start with a stack with only the '''starting marker''' $. |
|||
* Start with the string being parsed ('''Input''') ended with an '''ending marker''' $. |
|||
* While not (Stack equals to $S and Input equals to $) (S = Initial symbol of the grammar) |
|||
** Search in the table the relationship between Top(stack) and NextToken(Input) |
|||
** if the relationship is <Math> \dot =</math> or <Math>\lessdot</math> |
|||
*** '''Shift''': |
|||
*** Push(Stack, relationship) |
|||
*** Push(Stack, NextToken(Input)) |
|||
*** RemoveNextToken(Input) |
|||
** if the relationship is <Math>\gtrdot</math> |
|||
*** '''Reduce''': |
|||
*** SearchProductionToReduce(Stack) |
|||
*** RemovePivot(Stack) |
|||
*** Search in the table the relationship between the Non terminal from the production and first symbol in the stack (Starting from top) |
|||
*** Push(Stack, relationship) |
|||
*** Push(Stack, Non terminal) |
|||
SearchProductionToReduce (Stack) |
|||
* search the '''Pivot''' in the stack the nearest <Math>\lessdot</math> from the top |
|||
* search in the productions of the grammar which one have the same right side than the '''Pivot''' |
|||
==Example== |
|||
<pre> |
|||
Given the language: |
|||
E --> E + T' | T' |
|||
T' --> T |
|||
T --> T * F | F |
|||
F --> ( E' ) | num |
|||
E' --> E |
|||
</pre> |
|||
'''num''' is a terminal, and the [[lexer (computer science)|lexer]] parse any integer as '''num'''. |
|||
and the Parsing table: |
|||
{|border="1" cellpadding="2" |
|||
| ||E|| E' || T || T' || F || + ||*||(||)||num || $ |
|||
|- |
|||
| E || || || || || ||<math>\dot =</math>|| || ||<math>\gtrdot</math> || ||<math>\gtrdot</math> |
|||
|- |
|||
| E'|| || || || || || || || ||<math>\dot =</math>|| || |
|||
|- |
|||
| T || || || || || ||<math>\gtrdot</math>||<math>\dot =</math>|| ||<math>\gtrdot</math>|| ||<math>\gtrdot</math> |
|||
|- |
|||
| T'|| || || || || ||<math>\gtrdot</math>|| || ||<math>\gtrdot</math>|| ||<math>\gtrdot</math> |
|||
|- |
|||
| F || || || || || ||<math>\gtrdot</math>||<math>\gtrdot</math>|| ||<math>\gtrdot</math>|| ||<math>\gtrdot</math> |
|||
|- |
|||
| + || || ||<math>\lessdot</math>||<math>\dot =</math>||<math>\lessdot</math>|| || ||<math>\lessdot</math>|| ||<math>\lessdot</math> || |
|||
|- |
|||
| * || || || || ||<math>\dot =</math>|| || ||<math>\lessdot</math>|| ||<math>\lessdot</math> || |
|||
|- |
|||
| ( ||<math>\lessdot</math>||<math>\dot =</math>||<math>\lessdot</math>||<math>\lessdot</math>||<math>\lessdot</math>|| || ||<math>\lessdot</math>|| ||<math>\lessdot</math> || |
|||
|- |
|||
| ) || || || || || ||<math>\gtrdot</math>||<math>\gtrdot</math>|| ||<math>\gtrdot</math>|| ||<math>\gtrdot</math> |
|||
|- |
|||
| num|| || || || || ||<math>\gtrdot</math>||<math>\gtrdot</math>||||<math>\gtrdot</math>|| ||<math>\gtrdot</math> |
|||
|- |
|||
| $ ||<math>\lessdot</math>|| ||<math>\lessdot</math>||<math>\lessdot</math>||<math>\lessdot</math>|| || ||<math>\lessdot</math>|| ||<math>\lessdot</math> || |
|||
|} |
|||
<pre> |
|||
STACK PRECEDENCE INPUT ACTION |
|||
$ < 2 * ( 1 + 3 )$ SHIFT |
|||
$ < 2 > * ( 1 + 3 )$ REDUCE (F -> num) |
|||
$ < F > * ( 1 + 3 )$ REDUCE (T -> F) |
|||
$ < T = * ( 1 + 3 )$ SHIFT |
|||
$ < T = * < ( 1 + 3 )$ SHIFT |
|||
$ < T = * < ( < 1 + 3 )$ SHIFT |
|||
$ < T = * < ( < 1 > + 3 )$ REDUCE 4 times (F -> num) (T -> F) (T' -> T) (E ->T ') |
|||
$ < T = * < ( < E = + 3 )$ SHIFT |
|||
$ < T = * < ( < E = + < 3 )$ SHIFT |
|||
$ < T = * < ( < E = + < 3 > )$ REDUCE 3 times (F -> num) (T -> F) (T' -> T) |
|||
$ < T = * < ( < E = + = T > )$ REDUCE 2 times (E -> E + T) (E' -> E) |
|||
$ < T = * < ( < E' = )$ SHIFT |
|||
$ < T = * < ( = E' = ) > $ REDUCE (F -> ( E' )) |
|||
$ < T = * = F > $ REDUCE (T -> T * F) |
|||
$ < T > $ REDUCE 2 times (T' -> T) (E -> T') |
|||
$ < E > $ ACCEPT |
|||
</pre> |
|||
{{DEFAULTSORT:Simple Precedence Parser}} |
{{DEFAULTSORT:Simple Precedence Parser}} |
||
Revision as of 18:41, 8 July 2012
 |
 | Template:Wikify is deprecated. Please use a more specific cleanup template as listed in the documentation. |
In computer science, a simple precedence parser is a type of bottom-up parser for context-free grammars that can be used only by simple precedence grammars.
 | This programming-language-related article is a stub. You can help Wikipedia by expanding it. |