Editing Packrat parser (section)

=== Iterative combinator ===
The iterative combinators <math>\alpha +</math> and <math>\alpha *</math> need special attention when used in a Packrat parser: these combinators introduce a ''secret'' recursion that does not record intermediate results in the outcome matrix, which can lead to the parser operating with a superlinear behaviour. This problem can be resolved by applying the following transformation:<ref name=":3" />
{| class="wikitable"
|+
!Original
!Translated
|-
|<math>S \rightarrow \alpha +</math>
|<math>S \rightarrow \alpha S / \alpha </math>
|-
|<math>S \rightarrow \alpha *</math>
|<math>S \rightarrow \alpha S / \epsilon</math>
|}
With this transformation, the intermediate results can be properly memoized.