Editing Packrat parser (section)

== Example ==
Given the following context, a free grammar that recognizes simple arithmetic expressions composed of single digits interleaved by sum, multiplication, and parenthesis. 

<math>\begin{cases}
    S \rightarrow A \\
    A \rightarrow M\  \texttt{'+'}\  A \ / \  M \\
    M \rightarrow P\  \texttt{'*'}\  M \ / \ P \\
    P \rightarrow \texttt{'('}\ A\ \texttt{')'}\  / \ D \\
    D \rightarrow (\texttt{'0'}-\texttt{'9'})
\end{cases}</math>

Denoted with &dashv; the line terminator we can apply the ''packrat algorithm'' 

{| class="wikitable"
|+Derivation of {{kbd|2*(3+4)&dashv;}}
!Syntax tree
!Action
!Packrat Table
|-
|[[File:Derivation of a context free grammar with packrat.svg|center|333x333px]]
|
{| class="wikitable"
!Derivation Rules
!Input shifted
|-
|<math> \begin{array}{l}
S \rightarrow A \\
A \rightarrow M\  \texttt{'+'}\  A \\
M \rightarrow P\  \texttt{'*'}\  M \\
P \rightarrow \texttt{'('}\ A\ \texttt{')'}
\end{array}
</math>
|ɛ
|-
!Notes
!Input left
|-
|Input doesn't match the first element in the derivation.
Backtrack to the first grammar rule with unexplored alternative <math display="inline"> 
P \rightarrow \texttt{'('}\ A\ \texttt{')'}\  / \ \underline{D}
</math>
| {{nowrap|{{kbd|2*(3+4)&dashv;}}}}
|}
|
{| class="wikitable"
|+
!
! colspan="7" |Index
|-
!
!1
!2
!3
!4
!5
!6
!7
|-
!'''S'''
!
!
!
!
!
!
!
|-
|'''A'''
|
|
|
|
|
|
|
|-
|'''M'''
|
|
|
|
|
|
|
|-
|'''P'''
|
|
|
|
|
|
|
|-
|'''D'''
|
|
|
|
|
|
|
|-
|
|2
|*
|(
|3
| +
| 4
|)
|}
No update because no terminal was recognized
|-
|[[File:Second_step_in_Parsing_a_CFG_with_packrat.svg|frameless|325x325px]]
|
{| class="wikitable"
!Derivation Rules
!Input shifted
|-
|<math> 
P \rightarrow D
</math><br><math> 
D \rightarrow 2
</math>
| {{kbd|2}}
|-
!Notes
!Input left
|-
|Shift input by one after deriving terminal {{mono|2}}
| {{kbd|*(3+4)&dashv;}}
|}
|
{| class="wikitable"
!
! colspan="7" |Index
|-
!
!1
!2
!3
!4
!5
!6
!7
|-
!'''S'''
!
!
!
!
!
!
!
|-
|'''A'''
|
|
|
|
|
|
|
|-
|'''M'''
|
|
|
|
|
|
|
|-
|'''P'''
|1
|
|
|
|
|
|
|-
|'''D'''
|1
|
|
|
|
|
|
|-
|
|2
|*
|(
|3
| +
| 4
|)
|}
'''Update:'''

D(1) = 1;

P(1) = 1; 
|-
|[[File:Third_step_of_recognizing_CFG_with_packrat.svg|frameless|325x325px]]
|
{| class="wikitable"
!Derivation Rules
!Input shifted
|-
|<math> M \rightarrow P\  \texttt{'*'}\  M
</math><br><math>P \rightarrow \texttt{'('}\ A\ \texttt{')'}</math>
| {{kbd|2*(}}
|-
!Notes
!Input left
|-
|Shift input by two terminal <math> 
\{\texttt{*}, \texttt{(}\}
</math>
| {{kbd|3+4)&dashv;}}
|}
|
{| class="wikitable"
!
! colspan="7" |Index
|-
!
!1
!2
!3
!4
!5
!6
!7
|-
!'''S'''
!
!
!
!
!
!
!
|-
|'''A'''
|
|
|
|
|
|
|
|-
|'''M'''
|
|
|
|
|
|
|
|-
|'''P'''
|1
|
|
|
|
|
|
|-
|'''D'''
|1
|
|
|
|
|
|
|-
|
|2
|*
|(
|3
| +
| 4
|)
|}
No update because no nonterminal was fully recognized
|-
|[[File:Fourth_step_in_recognizing_CFG_grammar_with_Packrat.svg|frameless|325x325px]]
|
{| class="wikitable"
!Derivation Rules
!Input shifted
|-
|<math>A \rightarrow M\  \texttt{'+'}\  A</math><br><math>M \rightarrow P\  \texttt{'*'}\  M</math><br><math>P \rightarrow \texttt{'('}\ A\ \texttt{')'}</math>
| {{kbd|2*(}}
|-
!Notes
!Input left
|-
|Input doesn't match the first element in the derivation.
Backtrack to the first grammar rule with unexplored alternative <math display="inline"> 
P \rightarrow \texttt{'('}\ A\ \texttt{')'}\  / \ \underline{D}
</math>
| {{kbd|3+4)&dashv;}}
|}
|
{| class="wikitable"
!
! colspan="7" |Index
|-
!
!1
!2
!3
!4
!5
!6
!7
|-
!'''S'''
!
!
!
!
!
!
!
|-
|'''A'''
|
|
|
|
|
|
|
|-
|'''M'''
|
|
|
|
|
|
|
|-
|'''P'''
|1
|
|
|
|
|
|
|-
|'''D'''
|1
|
|
|
|
|
|
|-
|
|2
|*
|(
|3
| +
| 4
|)
|}
No update because no terminal was recognized
|-
|[[File:5th step of recognizing CFG with packrat.svg|frameless|325x325px]]
|
{| class="wikitable"
!Derivation Rules
!Input shifted
|-
|<math>P \rightarrow D </math><br><math>D \rightarrow 3</math>
| {{kbd|2*(}}
|-
!Notes
!Input left
|-
|Shift input by one after deriving terminal {{mono|3}}
but the new input will not match inside <math>M \rightarrow P\  \texttt{'*'}\  M</math> so an unroll is necessary to <math> 
M \rightarrow P\  \texttt{'*'}\  M \ / \ \underline P
</math>
| {{kbd|3+4)&dashv;}}
|}
|
{| class="wikitable"
!
! colspan="7" |Index
|-
!
!1
!2
!3
!4
!5
!6
!7
|-
!'''S'''
!
!
!
!
!
!
!
|-
|'''A'''
|
|
|
|
|
|
|
|-
|'''M'''
|
|
|
|
|
|
|
|-
|'''P'''
|1
|
|
|1
|
|
|
|-
|'''D'''
|1
|
|
|1
|
|
|
|-
|
|2
|*
|(
|3
| +
| 4
|)
|}
'''Update:'''

D(4) = 1;

P(4) = 1; 
|-
|[[File:Sixth step of recognizing CFG with packrat.svg|frameless|325x325px]]
|
{| class="wikitable"
!Derivation Rules
!Input shifted
|-
|<math>M \rightarrow P </math>
| {{nowrap|{{kbd|2*(3+}}}}
|-
!Notes
!Input left
|-
|Roll Back to <math> 
M \rightarrow P\  \texttt{'*'}\  M \ / \ \underline P
</math>
And we don't expand it has we have an hit in the memoization table P(4) ≠ 0  so shift the input by P(4).
Shift also the <math>+</math> from <math>A \rightarrow M\  \texttt{'+'}\  A</math>
| {{kbd|4)&dashv;}}
|}
|
{| class="wikitable"
!
! colspan="7" |Index
|-
!
!1
!2
!3
!4
!5
!6
!7
|-
!'''S'''
!
!
!
!
!
!
!
|-
|'''A'''
|
|
|
|
|
|
|
|-
|'''M'''
|
|
|
|1
|
|
|
|-
|'''P'''
|1
|
|
|1
|
|
|
|-
|'''D'''
|1
|
|
|1
|
|
|
|-
|
|2
|*
|(
|3
| +
| 4
|)
|}
Hit on P(4)

Update M(4) = 1 as M was recognized
|-
|[[File:Seventh step of recognizing CFG with packrat.svg|frameless|325x325px]]
|
{| class="wikitable"
!Derivation Rules
!Input shifted
|-
|<math>A \rightarrow M\  \texttt{'+'}\  A</math><br><math>M \rightarrow P\  \texttt{'*'}\  M</math><br><math>P \rightarrow \texttt{'('}\ A\ \texttt{')'}</math>
| {{nowrap|{{kbd|2*(3+}}}}
|-
!Notes
!Input left
|-
|Input  doesn't match the first element in the derivation.
Backtrack to the first grammar rule with unexplored alternative <math display="inline"> 
P \rightarrow \texttt{'('}\ A\ \texttt{')'}\  / \ \underline{D}
</math>
| {{kbd|4)&dashv;}}
|}
|
{| class="wikitable"
!
! colspan="7" |Index
|-
!
!1
!2
!3
!4
!5
!6
!7
|-
!'''S'''
!
!
!
!
!
!
!
|-
|'''A'''
|
|
|
|
|
|
|
|-
|'''M'''
|
|
|
|1
|
|
|
|-
|'''P'''
|1
|
|
|1
|
|
|
|-
|'''D'''
|1
|
|
|1
|
|
|
|-
|
|2
|*
|(
|3
| +
| 4
|)
|}
No update because no terminal was recognized
|-
|[[File:Eighth step of recognizing CFG with packrat.svg|frameless|325x325px]]
|
{| class="wikitable"
!Derivation Rules
!Input shifted
|-
|<math>P \rightarrow D </math><br><math>D \rightarrow 4</math>
| {{kbd|2*(3+}}
|-
!Notes
!Input left
|-
|Shift input by one after deriving terminal {{mono|4}}
but the new input will not match inside <math>M \rightarrow P\  \texttt{'*'}\  M</math> so an unroll is necessary
| {{kbd|4)&dashv;}}
|}
|
{| class="wikitable"
!
! colspan="7" |Index
|-
!
!1
!2
!3
!4
!5
!6
!7
|-
!'''S'''
!
!
!
!
!
!
!
|-
|'''A'''
|
|
|
|
|
|
|
|-
|'''M'''
|
|
|
|1
|
|
|
|-
|'''P'''
|1
|
|
|1
|
|1
|
|-
|'''D'''
|1
|
|
|1
|
|1
|
|-
|
|2
|*
|(
|3
| +
| 4
|)
|}
'''Update:'''

D(6) = 1;

P(6) = 1; 
|-
|[[File:Ninth step of recognizing CFG with packrat.svg|frameless|325x325px]]
|
{| class="wikitable"
!Derivation Rules
!Input shifted
|-
|<math>M \rightarrow P </math>
| {{nowrap|{{kbd|2*(3+}}}}
|-
!Notes
!Input left
|-
|Roll Back to <math> 
M \rightarrow P\  \texttt{'*'}\  M \ / \ \underline P
</math>
And we don't expand it has we have an hit in the memoization table P(6) ≠ 0  so shift the input by P(6).

but the new input will not match <math>+</math> inside <math>A \rightarrow M\  \texttt{'+'}\  A </math> so an unroll is necessary
| {{kbd|4)&dashv;}}
|}
|
{| class="wikitable"
!
! colspan="7" |Index
|-
!
!1
!2
!3
!4
!5
!6
!7
|-
!'''S'''
!
!
!
!
!
!
!
|-
|'''A'''
|
|
|
|
|
|
|
|-
|'''M'''
|
|
|
|1
|
|1
|
|-
|'''P'''
|1
|
|
|1
|
|1
|
|-
|'''D'''
|1
|
|
|1
|
|1
|
|-
|
|2
|*
|(
|3
| +
| 4
|)
|}
Hit on P(6)

Update M(6) = 1 as M was recognized
|-
|[[File:Tenth step of recognizing CFG with packrat.svg|frameless|325x325px]]
|
{| class="wikitable"
!Derivation Rules
!Input shifted
|-
|<math>A \rightarrow   M  </math>
| {{nowrap|{{kbd|2*(3+4)}}}}
|-
!Notes
!Input left
|-
|Roll Back to <math>A \rightarrow M\  \texttt{'+'}\  A \ / \ \underline{M}  </math>
And we don't expand it has we have an hit in the memoization table M(6) ≠ 0  so shift the input by M(6).

Also shift <math>)</math> from <math>P \rightarrow \texttt{'('}\ A\ \texttt{')'} </math>
| {{kbd|&dashv;}}
|}
|
{| class="wikitable"
!
! colspan="7" |Index
|-
!
!1
!2
!3
!4
!5
!6
!7
|-
!'''S'''
!
!
!
!
!
!
!
|-
|'''A'''
|
|
|
|3
|
|
|
|-
|'''M'''
|
|
|
|1
|
|1
|
|-
|'''P'''
|1
|
|5
|1
|
|1
|
|-
|'''D'''
|1
|
|
|1
|
|1
|
|-
|
|2
|*
|(
|3
| +
| 4
|)
|}
Hit on M(6)

Update A(4) = 3 as A was recognized

Update P(3)=5 as P was recognized
|-
|[[File:Eleventh step of recognizing CFG with packrat.svg|frameless|325x325px]]
|
{| class="wikitable"
!Derivation Rules
!Input shifted
|-
|
| {{kbd|2*}}
|-
!Notes
!Input left
|-
|Roll Back to <math> 
M \rightarrow P\  \texttt{'*'}\  M \ / \ \underline P
</math> as terminal <math>* \neq \dashv</math>
| {{nowrap|{{kbd|(3+4)&dashv;}}}}
|}
|
{| class="wikitable"
!
! colspan="7" |Index
|-
!
!1
!2
!3
!4
!5
!6
!7
|-
!'''S'''
!
!
!
!
!
!
!
|-
|'''A'''
|
|
|
|3
|
|
|
|-
|'''M'''
|
|
|
|1
|
|1
|
|-
|'''P'''
|1
|
|5
|1
|
|1
|
|-
|'''D'''
|1
|
|
|1
|
|1
|
|-
|
|2
|*
|(
|3
| +
| 4
|)
|}
No update because no terminal was recognized
|-
|[[File:Twelfth step of recognizing CFG with packrat.svg|frameless|325x325px]]
|
{| class="wikitable"
!Derivation Rules
!Input shifted
|-
|<math>M \rightarrow  P </math>
| {{nowrap|{{kbd|2*(3+4)}}}}
|-
!Notes
!Input left
|-
|we don't expand it as we have a hit in the memoization table P(3) ≠ 0, so shift the input by P(3).
| {{kbd|&dashv;}}
|}
|
{| class="wikitable"
!
! colspan="7" |Index
|-
!
!1
!2
!3
!4
!5
!6
!7
|-
!'''S'''
!
!
!
!
!
!
!
|-
|'''A'''
|
|
|
|3
|
|
|
|-
|'''M'''
|7
|
|
|1
|
|1
|
|-
|'''P'''
|1
|
|5
|1
|
|1
|
|-
|'''D'''
|1
|
|
|1
|
|1
|
|-
|
|2
|*
|(
|3
| +
| 4
|)
|}
Hit on P(3)

Update M(1)=7 as M was recognized
|-
|[[File:13th step of recognizing CFG with packrat.svg|frameless|325x325px]]
|
{| class="wikitable"
!Derivation Rules
!Input shifted
|-
|
|
|-
!Notes
!Input left
|-
|Roll Back to <math>A \rightarrow M\  \texttt{'+'}\  A \ / \  \underline{M}</math> as terminal <math>+ \neq \dashv</math>
| {{nowrap|{{kbd|2*(3+4)&dashv;}}}}
|}
|
{| class="wikitable"
!
! colspan="7" |Index
|-
!
!1
!2
!3
!4
!5
!6
!7
|-
!'''S'''
!
!
!
!
!
!
!
|-
|'''A'''
|
|
|
|3
|
|
|
|-
|'''M'''
|7
|
|
|1
|
|1
|
|-
|'''P'''
|1
|
|5
|1
|
|1
|
|-
|'''D'''
|1
|
|
|1
|
|1
|
|-
|
|2
|*
|(
|3
| +
| 4
|)
|}
No update because no terminal was recognized
|-
|[[File:14th step of recognizing CFG with packrat.svg|frameless|325x325px]]
|
{| class="wikitable"
!Derivation Rules
!Input shifted
|-
|<math>A \rightarrow  M</math>
| {{nowrap|{{kbd|2*(3+4)&dashv;}}}}
|-
!Notes
!Input left
|-
| We don't expand it as we have a hit in the memoization table M(1) ≠ 0, so shift the input by M(1).
S was totally reduced, so the input string is recognized.
|
|}
|
{| class="wikitable"
!
! colspan="7" |Index
|-
!
!1
!2
!3
!4
!5
!6
!7
|-
!'''S'''
!7
!
!
!
!
!
!
|-
|'''A'''
|7
|
|
|3
|
|
|
|-
|'''M'''
|7
|
|
|1
|
|1
|
|-
|'''P'''
|1
|
|5
|1
|
|1
|
|-
|'''D'''
|1
|
|
|1
|
|1
|
|-
|
|2
|*
|(
|3
| +
| 4
|)
|}
Hit on M(1)

Update A(1)=7 as A was recognized

Update S(1)=7 as S was recognized
|}