Here is a small ruleset that recognises a list and prints it first forwards, and then backwards, putting commas between the elements of the list. The first element is required to be a word, and subsequent elements may be either word or number:
.left()
- error output <- eof -;
- sample output <- eof -;
- word :X <- sample - list :X :X;
list :B :F ';' <- sample 'here it is forwards: ' F '\n' 'here it is backwards: ' B '\n'eom;
list :B :F word :X <- sample - list:{ X ', ' B } :{ F ', ' X };
list :B :F number :X <- sample - list:{ X ', ' B } :{ F ', ' X };
.left(20L)
.[0-9] % { repeat .[0-9] % } { option '.' % repeat [0-9] % } toNum :N <- number :N;
.[a-zA-Z] % { repeat .[a-zA-Z] % } toSym :W <- word :W;
.[ \n\t] <- - ;
.left(30R) - anything <- line - ; eof <- line eof; '\n' <- line; - line <- error '--- not understood - skipping one line\n' eom; - eom <- output ; - out <- eom - ;
Here is the ruleset in action - it has been compiled to produce leftRecursion.gdc (the .gdc extension is used for examples where the same rules are being compiled to several different executable representations - it is a D language wrapping round the lmr load format)
[peri@a4 examples]$ ./leftRecursion.gdc a 1 2 c; here it is forwards: a, 1, 2, c here it is backwards: c, 2, 1, a
In the ruleset, the following rules are used to add words and numbers to the list:
list :B :F word :X <- sample - list:{ X ', ' B } :{ F ', ' X };
list :B :F number :X <- sample - list:{ X ', ' B } :{ F ', ' X };
The second rule (as the newest) will be tried first. So when a word is used in the body of a list, these rules will always try to recognise list :B :F number :X before falling back on the alternative list :B :F word :X. It can be seen in the lm-diagram output below that this involves re-establishing two levels of right-nesting.
Fortunately the language machine is designed specifically to deal with this kind of situation in a reasonably efficient way. Where performance is important, it's best to avoid backtracks - for example:
- word :X <- item :X;
- number :X <- item :X;
list :F :B item :X <- sample - list:{ X ', ' B } :{ F ', ' X };
lm-diagram output
[peri@a4 examples]$ ./leftRecursion.gdc -W 40 -t D
a 1 2 c;
eof 'a'
? eof 'a'
.------------000001
| sample 'a'
|? sample 'a'
|.-----------000002
|| word 'a'
||? word 'a'
||.----------000003
||| % ' '
||| repeat ' '
||| [a-zA-Z] ' '
|||? [a-zA-Z] ' '
|||- [a-zA-Z] ' '
||| toSym ' '
||| : ' '
||'----------000003---------- ----------000003-------------.
|| word word |
|| : : |
|'-----------000002---------- ----------000002------------.|
| sample list ||
|? sample list ??
|.-----------000005 ||
|| : : ||
|| : : ||
|| 000002------------'|
|| 000003-------------'
|| number ' '
||? number ' '
|| number '1'
||? number '1'
||.----------000007
||| % ' '
||| repeat ' '
||| [0-9] ' '
|||? [0-9] ' '
|||- [0-9] ' '
||| option ' '
||| '.' ' '
|||? '.' ' '
|||- '.' ' '
||| toNum ' '
||| : ' '
||'----------000007---------- ----------000007-------------.
|| number number |
|| : : |
|'-----------000005---------- ----------000005------------.|
| sample list ||
|? sample list ??
|.-----------000010 ||
|| : : ||
|| : : ||
|| 000005------------'|
|| 000007-------------'
|| number ' '
||? number ' '
|| number '2'
||? number '2'
||.----------000012
||| % ' '
||| repeat ' '
||| [0-9] ' '
|||? [0-9] ' '
|||- [0-9] ' '
||| option ' '
||| '.' ' '
|||? '.' ' '
|||- '.' ' '
||| toNum ' '
||| : ' '
||'----------000012---------- ----------000012-------------.
|| number number |
|| : : |
|'-----------000010---------- ----------000010------------.|
| sample list ||
|? sample list ??
|.-----------000015 ||
|| : : ||
|| : : ||
|| 000010------------'|
|| 000012-------------'
|| number ' '
||? number ' '
|| number 'c'
||? number 'c'
||- number 'c'
|| : : ||
|| : : ||
|| 000010------------'|
|| 000012-------------'
|| word ' '
||? word ' '
|| word 'c'
||? word 'c'
||.----------000018
||| % ';'
||| repeat ';'
||| [a-zA-Z] ';'
|||? [a-zA-Z] ';'
|||- [a-zA-Z] ';'
||| toSym ';'
||| : ';'
||'----------000018---------- ----------000018-------------.
|| word word |
|| : : |
|'-----------000015---------- ----------000015------------.|
| sample list ||
|? sample list ??
|.-----------000019 ||
|| : : ||
|| : : ||
|| 000015------------'|
|| 000018-------------'
|| number ';'
||? number ';'
||- number ';'
|| : : ||
|| : : ||
|| 000015------------'|
|| 000018-------------'
|| word ';'
||? word ';'
||- word ';'
|| : : ||
|| : : ||
|| 000015------------'|
|| 000018-------------'
|| ';' ';'
|'-----------000019---------- ----------000019-------------.
| sample sample |
| output 'h' |
|? output 'h' ?
|.-----------000020 |
|| eom 'h' |
||? eom 'h' ?
||.----------000021 |
||| out 'h' |
h ||'----------000021 |
|| eom 'e' |
||? eom 'e' ?
||.----------000022 |
||| out 'e' |
e ||'----------000022 |
|| eom 'r' |
||? eom 'r' ?
||.----------000023 |
||| out 'r' |
r ||'----------000023 |
|| eom 'e' |
||? eom 'e' ?
||.----------000024 |
||| out 'e' |
e ||'----------000024 |
|| eom ' ' |
||? eom ' ' ?
||.----------000025 |
||| out ' ' |
||'----------000025 |
|| eom 'i' |
||? eom 'i' ?
||.----------000026 |
||| out 'i' |
i ||'----------000026 |
|| eom 't' |
||? eom 't' ?
||.----------000027 |
||| out 't' |
t ||'----------000027 |
|| eom ' ' |
||? eom ' ' ?
||.----------000028 |
||| out ' ' |
||'----------000028 |
|| eom 'i' |
||? eom 'i' ?
||.----------000029 |
||| out 'i' |
i ||'----------000029 |
|| eom 's' |
||? eom 's' ?
||.----------000030 |
||| out 's' |
s ||'----------000030 |
|| eom ' ' |
||? eom ' ' ?
||.----------000031 |
||| out ' ' |
||'----------000031 |
|| eom 'f' |
||? eom 'f' ?
||.----------000032 |
||| out 'f' |
f ||'----------000032 |
|| eom 'o' |
||? eom 'o' ?
||.----------000033 |
||| out 'o' |
o ||'----------000033 |
|| eom 'r' |
||? eom 'r' ?
||.----------000034 |
||| out 'r' |
r ||'----------000034 |
|| eom 'w' |
||? eom 'w' ?
||.----------000035 |
||| out 'w' |
w ||'----------000035 |
|| eom 'a' |
||? eom 'a' ?
||.----------000036 |
||| out 'a' |
a ||'----------000036 |
|| eom 'r' |
||? eom 'r' ?
||.----------000037 |
||| out 'r' |
r ||'----------000037 |
|| eom 'd' |
||? eom 'd' ?
||.----------000038 |
||| out 'd' |
d ||'----------000038 |
|| eom 's' |
||? eom 's' ?
||.----------000039 |
||| out 's' |
s ||'----------000039 |
|| eom ':' |
||? eom ':' ?
||.----------000040 |
||| out ':' |
: ||'----------000040 |
|| eom ' ' |
||? eom ' ' ?
||.----------000041 |
||| out ' ' |
||'----------000041 |
|| eom ' ' |
||? eom ' ' ?
||.----------000042 |
||| out ' ' |
||'----------000042 |
|| eom a |
||? eom a ?
||.----------000043 |
||| out a |
a ||'----------000043 |
|| eom ',' |
||? eom ',' ?
||.----------000044 |
||| out ',' |
, ||'----------000044 |
|| eom ' ' |
||? eom ' ' ?
||.----------000045 |
||| out ' ' |
||'----------000045 |
|| eom 1 |
||? eom 1 ?
||.----------000046 |
||| out 1 |
1 ||'----------000046 |
|| eom ',' |
||? eom ',' ?
||.----------000047 |
||| out ',' |
, ||'----------000047 |
|| eom ' ' |
||? eom ' ' ?
||.----------000048 |
||| out ' ' |
||'----------000048 |
|| eom 2 |
||? eom 2 ?
||.----------000049 |
||| out 2 |
2 ||'----------000049 |
|| eom ',' |
||? eom ',' ?
||.----------000050 |
||| out ',' |
, ||'----------000050 |
|| eom ' ' |
||? eom ' ' ?
||.----------000051 |
||| out ' ' |
||'----------000051 |
|| eom c |
||? eom c ?
||.----------000052 |
||| out c |
c ||'----------000052 |
|| eom '\n' |
||? eom '\n' ?
||.----------000053 |
||| out '\n' |
||'----------000053 |
|| eom 'h' |
||? eom 'h' ?
||.----------000054 |
||| out 'h' |
h ||'----------000054 |
|| eom 'e' |
||? eom 'e' ?
||.----------000055 |
||| out 'e' |
e ||'----------000055 |
|| eom 'r' |
||? eom 'r' ?
||.----------000056 |
||| out 'r' |
r ||'----------000056 |
|| eom 'e' |
||? eom 'e' ?
||.----------000057 |
||| out 'e' |
e ||'----------000057 |
|| eom ' ' |
||? eom ' ' ?
||.----------000058 |
||| out ' ' |
||'----------000058 |
|| eom 'i' |
||? eom 'i' ?
||.----------000059 |
||| out 'i' |
i ||'----------000059 |
|| eom 't' |
||? eom 't' ?
||.----------000060 |
||| out 't' |
t ||'----------000060 |
|| eom ' ' |
||? eom ' ' ?
||.----------000061 |
||| out ' ' |
||'----------000061 |
|| eom 'i' |
||? eom 'i' ?
||.----------000062 |
||| out 'i' |
i ||'----------000062 |
|| eom 's' |
||? eom 's' ?
||.----------000063 |
||| out 's' |
s ||'----------000063 |
|| eom ' ' |
||? eom ' ' ?
||.----------000064 |
||| out ' ' |
||'----------000064 |
|| eom 'b' |
||? eom 'b' ?
||.----------000065 |
||| out 'b' |
b ||'----------000065 |
|| eom 'a' |
||? eom 'a' ?
||.----------000066 |
||| out 'a' |
a ||'----------000066 |
|| eom 'c' |
||? eom 'c' ?
||.----------000067 |
||| out 'c' |
c ||'----------000067 |
|| eom 'k' |
||? eom 'k' ?
||.----------000068 |
||| out 'k' |
k ||'----------000068 |
|| eom 'w' |
||? eom 'w' ?
||.----------000069 |
||| out 'w' |
w ||'----------000069 |
|| eom 'a' |
||? eom 'a' ?
||.----------000070 |
||| out 'a' |
a ||'----------000070 |
|| eom 'r' |
||? eom 'r' ?
||.----------000071 |
||| out 'r' |
r ||'----------000071 |
|| eom 'd' |
||? eom 'd' ?
||.----------000072 |
||| out 'd' |
d ||'----------000072 |
|| eom 's' |
||? eom 's' ?
||.----------000073 |
||| out 's' |
s ||'----------000073 |
|| eom ':' |
||? eom ':' ?
||.----------000074 |
||| out ':' |
: ||'----------000074 |
|| eom ' ' |
||? eom ' ' ?
||.----------000075 |
||| out ' ' |
||'----------000075 |
|| eom c |
||? eom c ?
||.----------000076 |
||| out c |
c ||'----------000076 |
|| eom ',' |
||? eom ',' ?
||.----------000077 |
||| out ',' |
, ||'----------000077 |
|| eom ' ' |
||? eom ' ' ?
||.----------000078 |
||| out ' ' |
||'----------000078 |
|| eom 2 |
||? eom 2 ?
||.----------000079 |
||| out 2 |
2 ||'----------000079 |
|| eom ',' |
||? eom ',' ?
||.----------000080 |
||| out ',' |
, ||'----------000080 |
|| eom ' ' |
||? eom ' ' ?
||.----------000081 |
||| out ' ' |
||'----------000081 |
|| eom 1 |
||? eom 1 ?
||.----------000082 |
||| out 1 |
1 ||'----------000082 |
|| eom ',' |
||? eom ',' ?
||.----------000083 |
||| out ',' |
, ||'----------000083 |
|| eom ' ' |
||? eom ' ' ?
||.----------000084 |
||| out ' ' |
||'----------000084 |
|| eom a |
||? eom a ?
||.----------000085 |
||| out a |
a ||'----------000085 |
|| eom '\n' |
||? eom '\n' ?
||.----------000086 |
||| out '\n' |
||'----------000086 |
|| eom eom |
|'-----------000020---------- ----------000020------------.|
| output output ||
'------------000001 ||
000020------------'|
000019-------------'
eof '\n'
? eof '\n'
eof eof
[peri@a4 examples]$