Editing Packrat parser (section)

=== Cut operator ===
Another operator called ''cut'' has been introduced to Packrat to reduce its average space complexity even further. This operator utilizes the formal structures of many programming languages to eliminate impossible derivations. For instance, control statements parsing in a standard programming language is mutually exclusive from the first recognized token, e.g.,<math>\{\mathtt{if, do, while, switch}\}</math>.<ref name=":5">{{Cite book |last1=Mizushima |first1=Kota |last2=Maeda |first2=Atusi |last3=Yamaguchi |first3=Yoshinori |title=Proceedings of the 9th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering |chapter=Packrat parsers can handle practical grammars in mostly constant space |date=2010-05-06 |chapter-url=https://doi.org/10.1145/1806672.1806679 |series=PASTE '10 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=29–36 |doi=10.1145/1806672.1806679 |isbn=978-1-4503-0082-7|s2cid=14498865 }}</ref>
{| class="wikitable"
!Operator 
!Semantics
|-
|Cut
<math>\begin{array}{l} 
\alpha \uparrow \beta  / \gamma \\
(\alpha \uparrow \beta)*
\end{array}
  </math>
|if <math>\alpha
  </math> is recognized but <math>\beta
  </math> is not, skip the evaluation of the alternative.

In the first case don't evaluate <math>\gamma
  </math> if <math>\alpha
  </math> was recognized
The second rule is can be rewritten as <math>N \rightarrow \alpha \uparrow \beta N / \epsilon
  </math> and the same rules can be applied. 
|}
When a Packrat parser uses cut operators, it effectively clears its backtracking stack. This is because a cut operator reduces the number of possible alternatives in an ordered choice. By adding cut operators in the right places in a grammar's definition, the resulting Packrat parser only needs a nearly constant amount of space for memoization.<ref name=":5" />