Simple precedence parser: Difference between revisions

Revision as of 10:40, 14 September 2006

Revision as of 23:54, 17 July 2007

Line 2:

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'''

<pre>

Given the language:

E --> E + T | T'

T' --> T

T --> T * F | F

F --> ( E ) | [0..9]

</pre>

and the Parsing table:

<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}}