|
#REDIRECT [[Simple precedence grammar#Simple precedence parser]]
{{cleanup-context}}
{{R from merge}}
{{R to section}}
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|Simple precedence grammars]].
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]]. Simbols <math>\dot < </math>, <math>\dot =</math> and <math>\dot > </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 beeing parsed ('''Input''') ended with an '''ending marker''' $.
* While not (Stack equals to $S and Input equals to $) (S = Initial simbol of the grammar)
** Search in the table the relationship between Top(stack) and NextToken(Input)
** if the relationship is <Math> \dot =</math> or <Math> \dot <</math>
*** '''Shift''':
*** Push(Stack, relationship)
*** Push(Stack, NextToken(Input))
*** RemoveNextToken(Input)
** if the relationship is <Math> \dot ></math>
*** '''Reduce''':
*** SearchProductionToReduce(Stack)
*** RemovePivot(Stack)
*** Search in the table the relationship between the Non terminal from the production and NextToken(Input)
*** Push(Stack, relationship)
*** Push(Stack, Non terminal)
SearchProductionToReduce (Stack)
* search the '''Pivot''' in the stack the nearest <Math> \dot <</math> from the top
* search in the productions of the grammar wich 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]] parse any integer as '''num'''.
and the Parsing table:
{|border="1" cellpadding="2"
| ||E|| E' || T || T' || F || + ||*||(||)||num
|-
| E || || || || || ||<math>\dot =</math>|| || ||<math>\dot ></math> ||
|-
| E'|| || || || || || || || ||<math>\dot =</math>||
|-
| T || || || || || ||<math>\dot ></math>||<math>\dot =</math>|| ||<math>\dot ></math>||
|-
| T'|| || || || || ||<math>\dot ></math>|| || ||<math>\dot ></math>||
|-
| F || || || || || ||<math>\dot ></math>||<math>\dot ></math>|| ||<math>\dot ></math>||
|-
| + || || ||<math>\dot <</math>||<math>\dot =</math>||<math>\dot <</math>|| || ||<math>\dot <</math>|| ||<math>\dot <</math>
|-
| * || || || || ||<math>\dot =</math>|| || ||<math>\dot <</math>|| ||<math>\dot <</math>
|-
| ( ||<math>\dot <</math>||<math>\dot =</math>||<math>\dot <</math>||<math>\dot <</math>||<math>\dot <</math>|| || ||<math>\dot <</math>|| ||<math>\dot <</math>
|-
| ) || || || || || || ||<math>\dot ></math>|| ||<math>\dot ></math>||
|-
| num|| || || || || ||<math>\dot ></math>||<math>\dot ></math>||||<math>\dot ></math>||
|}
<pre>
STACK PRECEDENCE INPUT ACTION
$ < 2 * ( 1 + 3 )$ SHIFT
$ < 2 > * ( 1 + 3 )$ REDUCE (F -> 2)
$ < 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 -> 1) (T -> F) (T' -> T) (E -> T')
$ < T = * < ( < E = + 3 )$ SHIFT
$ < T = * < ( < E = + < 3 )$ SHIFT
$ < T = * < ( < E = + < 3 > )$ REDUCE 3 times (F -> 3) (T -> F) (T' -> T)
$ < T = * < ( < E = + = T > )$ REDUCE (E -> E + T)
$ < 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>
{{compu-lang-stub}}
[[Category:Parsing algorithms]]
[[es:Algoritmo de parsing por precedencia simple]]
| 