Simple precedence parser: Difference between revisions

Revision as of 17:44, 18 March 2021

Revision as of 15:23, 4 August 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:

* While not (Stack equals to $S and Input equals to $) (S = Initial symbol of the grammar)

** Search in the table 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)

* search the '''Pivot''' in the stack the nearest ⋖⋖ from the top

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

Line 45:

|-

! E

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

|-

! E'

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

|-

! T

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

|-

! T'

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

|-

! F

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

|-

! +

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

|-

! *

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

|-

! (

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

|-

! )

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

|-

! num

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

|-

! $

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

|}