The lm-diagram was devised by Peri Hankey during the 1970s as a way of visualising and understanding what happens when unrestricted grammar rules that have to deal with partially ambiguous input are applied to an input text. The best way to understand the diagram is to look at it in relation to some actual rules.
an extremely simple example
Here is a complete set of rules for cats, a trivially minimal subset of english:
.cats() - sentence <- eof - ; - subject verb object '.' <- sentence ;
- nounphrase <- subject ; - nounphrase <- object ;
'the ' noun <- nounphrase ; 'a ' noun <- nounphrase ;
'cat ' <- noun; 'dog ' <- noun; 'bit ' <- noun;
'bit ' <- verb; 'ate ' <- verb; 'likes ' <- verb;
' ' <- - ; '\n' <- - ;
Here is the result of applying these rules to analyse (and do nothing about) the sentence
the cat likes the dog .
lm-diagram output from cats ruleset
eof 't'
? eof 't'
.------------000001
| sentence 't'
|? sentence 't'
|.-----------000002
|| subject 't'
||? subject 't'
||.----------000003
||| nounphrase 't'
|||? nounphrase 't'
|||.---------000004
|||| 'h' 'h'
|||| 'e' 'e'
|||| ' ' ' '
|||| noun 'c'
||||? noun 'c'
||||.--------000005
||||| 'a' 'a'
||||| 't' 't'
||||| ' ' ' '
||||'--------000005---------- ----------000005-------------.
|||| noun noun |
|||'---------000004---------- ----------000004------------.|
||| nounphrase nounphrase ||
||'----------000003---------- ----------000003-----------.||
|| subject subject |||
|| 000003-----------'||
|| 000004------------'|
|| 000005-------------'
|| verb 'l'
||? verb 'l'
||.----------000006
||| 'i' 'i'
||| 'k' 'k'
||| 'e' 'e'
||| 's' 's'
||| ' ' ' '
||'----------000006---------- ----------000006-------------.
|| verb verb |
|| 000006-------------'
|| object 't'
||? object 't'
||.----------000007
||| nounphrase 't'
|||? nounphrase 't'
|||.---------000008
|||| 'h' 'h'
|||| 'e' 'e'
|||| ' ' ' '
|||| noun 'd'
||||? noun 'd'
||||.--------000009
||||| 'o' 'o'
||||| 'g' 'g'
||||| ' ' ' '
||||'--------000009---------- ----------000009-------------.
|||| noun noun |
|||'---------000008---------- ----------000008------------.|
||| nounphrase nounphrase ||
||'----------000007---------- ----------000007-----------.||
|| object object |||
|| 000007-----------'||
|| 000008------------'|
|| 000009-------------'
|| '.' '.'
|'-----------000002---------- ----------000002-------------.
| sentence sentence |
'------------000001 |
000002-------------'
eof '\n'
? eof '\n'
eof eof
elements of the lm-diagram
- the central columns show two symbols that are being matched
- the left symbol is the goal symbol
- the right symbol is the input symbol
- new rules are started when a mismatch is detected
- applying a rule is a matter of matching its left-side and substituting its right-side
- nesting on the left corresponds to nesting of left-sides of rules
- nesting on the right corresponds to nesting of right-sides of rules
- left symbols that are uncovered to the left represent an ultimate goal
- right symbols that are uncovered to the right are actual input
- no nesting appears where the left-side has length 1 or or the right-side is empty
- the full application of a rule appears as nesting first on the left and then on the right
- some rules never run to completion - an alternative has to be tried
- the "?" in a nesting level on the left indicates that a mismatch occurred
- the "-" in a nesting level on the left indicates that an alternative analysis was tried
- the "*" in a nesting level on the left indicates repetition
- the numeric labels identify mismatch events that give rise to visible nesting
a more complex example
Here the rules for fpCalc, a simple calculator that accepts input in forward polish or prefix notation. It implements basic arithmetic, and also a function called f (the factorial function).
.calc() - error output <- eof - ; - result output <- eof - ; - x :N <- result 'result: ' N '\n' eom ;
'-' x :A <- x :(-A); '+' x :A x :B <- x :(A + B); '-' x :A x :B <- x :(A - B); '*' x :A x :B <- x :(A * B); '/' x :A x :B <- x :(A / B);
'f' x :N <- x - '*' x :(N) 'f' x :(N - 1) ; 'f' x :1 <- x :1; 'f' x :0 <- x :1;
.calc(20L)
.[0-9] % { repeat .[0-9] % } { option '.' % repeat .[0-9] % } toNum :N <- x :N;
.[ \t\n] <- - ;
.calc(30R) - anything <- line - ; eof <- line eof; '\n' <- line;
- line <- error '--- not understood - skipping one line\n' output;
- eom <- output ; - out <- eom - ;
trying it out
Here are the fpCalc rules in action:
[user@machine examples]$ lm -r fpCalc.lmr 1 result: 1 * 100 / 1 3 result: 33.3333 f 0 result: 1 f 1 result: 1 f 2 result: 2 f 3 result: 6 f 4 result: 24 f 5 result: 120 f 6 result: 720 z --- not understood - skipping one line * 1 + / 1 55 * 3 22 result: 66.0182
lm-diagram output from fpCalc ruleset
[user@machine examples]$ lm -r fpCalc.lmr -W 50 -t D
/ 307 241
eof '/'
? eof '/'
.-----------------000001
| result '/'
|? result '/'
|.----------------000002
|| x '/'
||? x '/'
||.---------------000003
||| x ' '
|||? x ' '
||| x '3'
|||? x '3'
|||.--------------000005
|||| % '0'
|||| repeat '0'
|||| [0-9] '0'
|||| % '7'
||||*
|||| [0-9] '7'
|||| % ' '
||||*
|||| [0-9] ' '
||||? [0-9] ' '
||||- [0-9] ' '
|||| option ' '
|||| '.' ' '
||||? '.' ' '
||||- '.' ' '
|||| toNum ' '
|||| : ' '
|||'--------------000005---------- ----------000005------------------.
||| x x |
||| : : |
||| 000005------------------'
||| x ' '
|||? x ' '
||| x '2'
|||? x '2'
|||.--------------000009
|||| % '4'
|||| repeat '4'
|||| [0-9] '4'
|||| % '1'
||||*
|||| [0-9] '1'
|||| % '\n'
||||*
|||| [0-9] '\n'
||||? [0-9] '\n'
||||- [0-9] '\n'
|||| option '\n'
|||| '.' '\n'
||||? '.' '\n'
||||- '.' '\n'
|||| toNum '\n'
|||| : '\n'
|||'--------------000009---------- ----------000009------------------.
||| x x |
||| : : |
||'---------------000003---------- ----------000003-----------------.|
|| x x ||
|| : : ||
|'----------------000002---------- ----------000002----------------.||
| result result |||
| output 'r' |||
|? output 'r' ???
|.----------------000012 |||
|| eom 'r' |||
||? eom 'r' ???
||.---------------000013 |||
||| out 'r' |||
r ||'---------------000013 |||
|| eom 'e' |||
||? eom 'e' ???
||.---------------000014 |||
||| out 'e' |||
e ||'---------------000014 |||
|| eom 's' |||
||? eom 's' ???
||.---------------000015 |||
||| out 's' |||
s ||'---------------000015 |||
|| eom 'u' |||
||? eom 'u' ???
||.---------------000016 |||
||| out 'u' |||
u ||'---------------000016 |||
|| eom 'l' |||
||? eom 'l' ???
||.---------------000017 |||
||| out 'l' |||
l ||'---------------000017 |||
|| eom 't' |||
||? eom 't' ???
||.---------------000018 |||
||| out 't' |||
t ||'---------------000018 |||
|| eom ':' |||
||? eom ':' ???
||.---------------000019 |||
||| out ':' |||
: ||'---------------000019 |||
|| eom ' ' |||
||? eom ' ' ???
||.---------------000020 |||
||| out ' ' |||
||'---------------000020 |||
|| eom 1.27386 |||
||? eom 1.27386 ???
||.---------------000021 |||
||| out 1.27386 |||
1.27386 ||'---------------000021 |||
|| eom '\n' |||
||? eom '\n' ???
||.---------------000022 |||
||| out '\n' |||
||'---------------000022 |||
|| eom eom |||
|'----------------000012---------- ----------000012---------------.|||
| output output ||||
'-----------------000001 ||||
000012---------------'|||
000002----------------'||
000003-----------------'|
000009------------------'
eof '\n'
? eof '\n'
f 6
eof 'f'
? eof 'f'
.-----------------000024
| result 'f'
|? result 'f'
|.----------------000025
|| x 'f'
||? x 'f'
||.---------------000026
||| x ' '
|||? x ' '
||| x '6'
|||? x '6'
|||.--------------000028
|||| % '\n'
|||| repeat '\n'
|||| [0-9] '\n'
||||? [0-9] '\n'
||||- [0-9] '\n'
|||| option '\n'
|||| '.' '\n'
||||? '.' '\n'
||||- '.' '\n'
|||| toNum '\n'
|||| : '\n'
|||'--------------000028---------- ----------000028------------------.
||| x x |
||| : : |
||| 0 6 |
|||? 0 6 ?
|||- 0 6 |
||| x ' '
|||? x ' '
||| x '6'
|||? x '6'
|||.--------------000032
|||| % '\n'
|||| repeat '\n'
|||| [0-9] '\n'
||||? [0-9] '\n'
||||- [0-9] '\n'
|||| option '\n'
|||| '.' '\n'
||||? '.' '\n'
||||- '.' '\n'
|||| toNum '\n'
|||| : '\n'
|||'--------------000032---------- ----------000032------------------.
||| x x |
||| : : |
||| 1 6 |
|||? 1 6 ?
|||- 1 6 |
||| x ' '
|||? x ' '
||| x '6'
|||? x '6'
|||.--------------000036
|||| % '\n'
|||| repeat '\n'
|||| [0-9] '\n'
||||? [0-9] '\n'
||||- [0-9] '\n'
|||| option '\n'
|||| '.' '\n'
||||? '.' '\n'
||||- '.' '\n'
|||| toNum '\n'
|||| : '\n'
|||'--------------000036---------- ----------000036------------------.
||| x x |
||| : : |
||'---------------000026---------- ----------000026-----------------.|
|| x '*' ||
||? x '*' ??
||.---------------000039 ||
||| x x ||
||| : : ||
||| x 'f' ||
|||? x 'f' ??
|||.--------------000040 ||
|||| x x ||
|||| : : ||
|||| 0 5 ||
||||? 0 5 ??
||||- 0 5 ||
|||| x x ||
|||| : : ||
|||| 1 5 ||
||||? 1 5 ??
||||- 1 5 ||
|||| x x ||
|||| : : ||
|||'--------------000040---------- ----------000040----------------.||
||| x '*' |||
|||? x '*' ???
|||.--------------000041 |||
|||| x x |||
|||| : : |||
|||| x 'f' |||
||||? x 'f' ???
||||.-------------000042 |||
||||| x x |||
||||| : : |||
||||| 0 4 |||
|||||? 0 4 ???
|||||- 0 4 |||
||||| x x |||
||||| : : |||
||||| 1 4 |||
|||||? 1 4 ???
|||||- 1 4 |||
||||| x x |||
||||| : : |||
||||'-------------000042---------- ----------000042---------------.|||
|||| x '*' ||||
||||? x '*' ????
||||.-------------000043 ||||
||||| x x ||||
||||| : : ||||
||||| x 'f' ||||
|||||? x 'f' ????
|||||.------------000044 ||||
|||||| x x ||||
|||||| : : ||||
|||||| 0 3 ||||
||||||? 0 3 ????
||||||- 0 3 ||||
|||||| x x ||||
|||||| : : ||||
|||||| 1 3 ||||
||||||? 1 3 ????
||||||- 1 3 ||||
|||||| x x ||||
|||||| : : ||||
|||||'------------000044---------- ----------000044--------------.||||
||||| x '*' |||||
|||||? x '*' ?????
|||||.------------000045 |||||
|||||| x x |||||
|||||| : : |||||
|||||| x 'f' |||||
||||||? x 'f' ?????
||||||.-----------000046 |||||
||||||| x x |||||
||||||| : : |||||
||||||| 0 2 |||||
|||||||? 0 2 ?????
|||||||- 0 2 |||||
||||||| x x |||||
||||||| : : |||||
||||||| 1 2 |||||
|||||||? 1 2 ?????
|||||||- 1 2 |||||
||||||| x x |||||
||||||| : : |||||
||||||'-----------000046---------- ----------000046-------------.|||||
|||||| x '*' ||||||
||||||? x '*' ??????
||||||.-----------000047 ||||||
||||||| x x ||||||
||||||| : : ||||||
||||||| x 'f' ||||||
|||||||? x 'f' ??????
|||||||.----------000048 ||||||
|||||||| x x ||||||
|||||||| : : ||||||
|||||||| 0 1 ||||||
||||||||? 0 1 ??????
||||||||- 0 1 ||||||
|||||||| x x ||||||
|||||||| : : ||||||
|||||||| 1 1 ||||||
|||||||'----------000048---------- ----------000048------------.||||||
||||||| x x |||||||
||||||| : : |||||||
||||||'-----------000047---------- ----------000047-----------.|||||||
|||||| x x ||||||||
|||||| : : ||||||||
|||||'------------000045---------- ----------000045----------.||||||||
||||| x x |||||||||
||||| : : |||||||||
||||'-------------000043---------- ----------000043---------.|||||||||
|||| x x ||||||||||
|||| : : ||||||||||
|||'--------------000041---------- ----------000041--------.||||||||||
||| x x |||||||||||
||| : : |||||||||||
||'---------------000039---------- ----------000039-------.|||||||||||
|| x x ||||||||||||
|| : : ||||||||||||
|'----------------000025---------- ----------000025------.||||||||||||
| result result |||||||||||||
| output 'r' |||||||||||||
|? output 'r' ?????????????
|.----------------000049 |||||||||||||
|| eom 'r' |||||||||||||
||? eom 'r' ?????????????
||.---------------000050 |||||||||||||
||| out 'r' |||||||||||||
r ||'---------------000050 |||||||||||||
|| eom 'e' |||||||||||||
||? eom 'e' ?????????????
||.---------------000051 |||||||||||||
||| out 'e' |||||||||||||
e ||'---------------000051 |||||||||||||
|| eom 's' |||||||||||||
||? eom 's' ?????????????
||.---------------000052 |||||||||||||
||| out 's' |||||||||||||
s ||'---------------000052 |||||||||||||
|| eom 'u' |||||||||||||
||? eom 'u' ?????????????
||.---------------000053 |||||||||||||
||| out 'u' |||||||||||||
u ||'---------------000053 |||||||||||||
|| eom 'l' |||||||||||||
||? eom 'l' ?????????????
||.---------------000054 |||||||||||||
||| out 'l' |||||||||||||
l ||'---------------000054 |||||||||||||
|| eom 't' |||||||||||||
||? eom 't' ?????????????
||.---------------000055 |||||||||||||
||| out 't' |||||||||||||
t ||'---------------000055 |||||||||||||
|| eom ':' |||||||||||||
||? eom ':' ?????????????
||.---------------000056 |||||||||||||
||| out ':' |||||||||||||
: ||'---------------000056 |||||||||||||
|| eom ' ' |||||||||||||
||? eom ' ' ?????????????
||.---------------000057 |||||||||||||
||| out ' ' |||||||||||||
||'---------------000057 |||||||||||||
|| eom 720 |||||||||||||
||? eom 720 ?????????????
||.---------------000058 |||||||||||||
||| out 720 |||||||||||||
720 ||'---------------000058 |||||||||||||
|| eom '\n' |||||||||||||
||? eom '\n' ?????????????
||.---------------000059 |||||||||||||
||| out '\n' |||||||||||||
||'---------------000059 |||||||||||||
|| eom eom |||||||||||||
|'----------------000049---------- ----------000049-----.|||||||||||||
| output output ||||||||||||||
'-----------------000024 ||||||||||||||
000049-----'|||||||||||||
000025------'||||||||||||
000039-------'|||||||||||
000041--------'||||||||||
000043---------'|||||||||
000045----------'||||||||
000047-----------'|||||||
000048------------'||||||
000046-------------'|||||
000044--------------'||||
000042---------------'|||
000040----------------'||
000026-----------------'|
000036------------------'
eof '\n'
? eof '\n'
eof eof
[user@machine examples]$