Simple precedence parser: Difference between revisions

Revision as of 00:54, 9 August 2009

Revision as of 14:55, 17 December 2009

Line 1:

{{Unreferenced stub|auto=yes|date=December 2009}}

{{Wikify|date=March 2008}}

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

Line 29:

* search in the productions of the grammar which one have the same right side than the '''Pivot'''

== Example ==

<pre>

Given the language:

Line 93 ⟶ 92:

</pre>

{{DEFAULTSORT:Simple Precedence Parser}}

[[Category:Parsing algorithms]]

[[Category:Articles lacking sources (Erik9bot)]]

{{compuCompu-lang-stub}}

[[es:Analizador sintáctico de precedencia simple]]