Simple precedence parser: Difference between revisions

Revision as of 15:44, 4 August 2022

Revision as of 07:16, 2 September 2022

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]]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 ⋖⋖, ≐⋖ and ⋗⋗ are used to identify the '''pivot''', and to know when to '''Shift''' or when to '''Reduce'''.

==Implementation==

Line 9:

* Until Stack equals "$ S" and Input equals "$"

** Search the table for the relationship between Top(stack) and NextToken(Input)

** if the relationship is ⋖⋖ or ≐⋖

*** '''Shift''':

*** Push(Stack, relationship)

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

*** RemoveNextToken(Input)

** if the relationship is ⋗⋗

*** '''Reduce''':

*** SearchProductionToReduce(Stack)

Line 23:

SearchProductionToReduce (Stack)

* Find the topmost ⋖⋖ in the stack; this and all the symbols above it are the '''Pivot'''.

* Find the production of the grammar which has the '''Pivot''' as its right side.

Line 45:

|-

! E

| || || || || ||≐⋖|| || ||⋗⋗ || ||⋗⋗

|-

! E'

| || || || || || || || ||≐⋖|| ||

|-

! T

| || || || || ||⋗⋗||≐⋖|| ||⋗⋗|| ||⋗⋗

|-

! T'

| || || || || ||⋗⋗|| || ||⋗⋗|| ||⋗⋗

|-

! F

| || || || || ||⋗⋗||⋗⋗|| ||⋗⋗|| ||⋗⋗

|-

! +

| || ||⋖⋖||≐⋖||⋖⋖|| || ||⋖⋖|| ||⋖⋖ ||

|-

! *

| || || || ||≐⋖|| || ||⋖⋖|| ||⋖⋖ ||

|-

! (

|⋖⋖||≐⋖||⋖⋖||⋖⋖||⋖⋖|| || ||⋖⋖|| ||⋖⋖ ||

|-

! )

| || || || || ||⋗⋗||⋗⋗|| ||⋗⋗|| ||⋗⋗

|-

! num

| || || || || ||⋗⋗||⋗⋗||||⋗⋗|| ||⋗⋗

|-

! $

|⋖⋖|| ||⋖⋖||⋖⋖||⋖⋖|| || ||⋖⋖|| ||⋖⋖ ||

|}