APG Version 5.0 - Tables
Table 2. Elementary examples of removing left and right recursion with the ABNF repetition operator.
| Type | Recursive Rule | Matching String (n>=0) |
ABNF |
|---|---|---|---|
| Left | S = S s / x | x sn | "x" *"s" |
| Right | S = s S / x | sn x | *"s" "x" |
| Left & Right | S = S s S / x | x (s x)n | "x" *("s" "x") |
| Nested | S = a S b / x | a n xb n | "a" S "b" / "x" |