Simple precedence parser: Difference between revisions

Revision as of 18:34, 18 July 2007

Revision as of 20:47, 18 July 2007

Line 1:

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 < lessdot</math>, <math>\dot =</math> and <math>\dot > gtrdot</math> are used to identify the '''pivot''', and to know when to '''Shift''' or when to '''Reduce'''.

= Implementation =

Line 17 ⟶ 15:

*** Push(Stack, NextToken(Input))

*** RemoveNextToken(Input)

** if the relationship is <Math> \dot >gtrdot</math>

*** '''Reduce''':

*** SearchProductionToReduce(Stack)

Line 48 ⟶ 46:

| ||E|| E' || T || T' || F || + ||*||(||)||num || $

|-

| E || || || || || ||<math>\dot =</math>|| || ||<math>\dot >gtrdot</math> || ||<math>\dot >gtrdot</math>

|-

| E'|| || || || || || || || ||<math>\dot =</math>|| ||

|-

| T || || || || || ||<math>\dot >gtrdot</math>||<math>\dot =</math>|| ||<math>\dot >gtrdot</math>|| ||<math>\dot >gtrdot</math>

|-

| T'|| || || || || ||<math>\dot >gtrdot</math>|| || ||<math>\dot >gtrdot</math>|| ||<math>\dot >gtrdot</math>

|-

| F || || || || || ||<math>\dot >gtrdot</math>||<math>\dot >gtrdot</math>|| ||<math>\dot >gtrdot</math>|| ||<math>\dot >gtrdot</math>

|-

| + || || ||<math>\dot <</math>||<math>\dot =</math>||<math>\dot <</math>|| || ||<math>\dot <</math>|| ||<math>\dot <</math> ||

Line 64 ⟶ 62:

| ( ||<math>\dot <</math>||<math>\dot =</math>||<math>\dot <</math>||<math>\dot <</math>||<math>\dot <</math>|| || ||<math>\dot <</math>|| ||<math>\dot <</math> ||

|-

| ) || || || || || || ||<math>\dot >gtrdot</math>|| ||<math>\dot >gtrdot</math>|| ||<math>\dot >gtrdot</math>

|-

| num|| || || || || ||<math>\dot >gtrdot</math>||<math>\dot >gtrdot</math>||||<math>\dot >gtrdot</math>|| ||<math>\dot >gtrdot</math>

|-

| $ ||<math>\dot <</math>|| ||<math>\dot <</math>||<math>\dot <</math>||<math>\dot <</math>|| || ||<math>\dot <</math>|| ||<math>\dot <</math> ||

<</math>|| ||<math>\dot <</math> ||

|}