Main ArticleExamples TOC

Takmela: Indirect left recursion example

This example contains both direct and indirect left recursion (consider how expr appears on the left side of term). Let's see how Takmela deals with it.

Interestingly, the algorithm doesn't know or care that there's left recursion in the grammar, as far as it is concerned it's just another parsing job.

Grammar 
expr : expr '+' term 
    | term ;
    
term : 
      NUM
    | ID
    | expr '.' ID '(' expr ')'
    ;
    

ID : [a-zA-Z]+;
NUM: [0-9]+;

WS skip: ' '*;
Input 
x.apply(5) + y

Trace appears confusing? This might help

Call start nonterminal
#0: Called expr/0 at the top level (will process)
Processing expr/0 codePos expr → • expr `+` term inputPos 0
Calling: expr/0 with Cont expr/0 ; expr → expr• `+` term [already processed]
Processing expr/0 codePos expr → • term inputPos 0
Calling: term/0 with Cont expr/0 ; expr → term• [will process]
Processing term/0 codePos term → • NUM inputPos 0
Match NUM to x, fail
Processing term/0 codePos term → • ID inputPos 0
Match ID to x, matched; inputPos now 1
Reached end of rule, success! term/0 → 1
Processing term/0 codePos term → • expr `.` ID `(` expr `)` inputPos 0
Calling: expr/0 with Cont term/0 ; term → expr• `.` ID `(` expr `)` [already processed]
New continuations:
term/0 → expr/0 ; expr → term• ; expr
expr/0 → expr/0 ; expr → expr• `+` term ; expr
expr/0 → term/0 ; term → expr• `.` ID `(` expr `)` ; term
term/0 → 1, term('x')
Iteration 0
Worklist - successes
jS term/0 → 1
Worklist - continuations
S⤚ term/0 → expr/0 ; expr → term•
nJ expr/0 → expr/0 ; expr → expr• `+` term
nJ expr/0 → term/0 ; term → expr• `.` ID `(` expr `)`
#1: JoinS: term/0 → 1 will resume cont: expr/0 ; expr → term•
Processing expr/0 codePos expr → term• inputPos 1
Reached end of rule, success! expr/0 → 1
term/0 → 1, term('x') expr/0 → 1, expr(term('x'))
Iteration 1
Worklist - successes
jS expr/0 → 1
Worklist - continuations
#2: JoinS: expr/0 → 1 will resume cont: Root/0 ; Root → expr•
×Didn't reach end of input, not a successful parse
term/0 → 1, term('x') expr/0 → 1, expr(term('x'))
#3: JoinS: expr/0 → 1 will resume cont: expr/0 ; expr → expr• `+` term
Processing expr/0 codePos expr → expr• `+` term inputPos 1
Match `+` to ., fail
term/0 → 1, term('x') expr/0 → 1, expr(term('x'))
#4: JoinS: expr/0 → 1 will resume cont: term/0 ; term → expr• `.` ID `(` expr `)`
Processing term/0 codePos term → expr• `.` ID `(` expr `)` inputPos 1
Match . to ., matched; inputPos now 2
Match ID to apply, matched; inputPos now 3
Match ( to (, matched; inputPos now 4
Calling: expr/4 with Cont term/0 ; term → expr `.` ID `(` expr• `)` [will process]
Processing expr/4 codePos expr → • expr `+` term inputPos 4
Calling: expr/4 with Cont expr/4 ; expr → expr• `+` term [already processed]
Processing expr/4 codePos expr → • term inputPos 4
Calling: term/4 with Cont expr/4 ; expr → term• [will process]
Processing term/4 codePos term → • NUM inputPos 4
Match NUM to 5, matched; inputPos now 5
Reached end of rule, success! term/4 → 5
Processing term/4 codePos term → • ID inputPos 4
Match ID to 5, fail
Processing term/4 codePos term → • expr `.` ID `(` expr `)` inputPos 4
Calling: expr/4 with Cont term/4 ; term → expr• `.` ID `(` expr `)` [already processed]
New continuations:
expr/4 → term/0 ; term → expr `.` ID `(` expr• `)` ; term(expr(term('x')), '.', 'apply', '(')
expr/4 → expr/4 ; expr → expr• `+` term ; expr
expr/4 → term/4 ; term → expr• `.` ID `(` expr `)` ; term
term/4 → expr/4 ; expr → term• ; expr
term/0 → 1, term('x') expr/0 → 1, expr(term('x')) term/4 → 5, term('5')
Iteration 2
Worklist - successes
jS term/4 → 5
Worklist - continuations
nJ expr/4 → term/0 ; term → expr `.` ID `(` expr• `)`
nJ expr/4 → expr/4 ; expr → expr• `+` term
nJ expr/4 → term/4 ; term → expr• `.` ID `(` expr `)`
S⤚ term/4 → expr/4 ; expr → term•
#5: JoinS: term/4 → 5 will resume cont: expr/4 ; expr → term•
Processing expr/4 codePos expr → term• inputPos 5
Reached end of rule, success! expr/4 → 5
term/0 → 1, term('x') expr/0 → 1, expr(term('x')) term/4 → 5, term('5') expr/4 → 5, expr(term('5'))
Iteration 3
Worklist - successes
jS expr/4 → 5
Worklist - continuations
#6: JoinS: expr/4 → 5 will resume cont: term/0 ; term → expr `.` ID `(` expr• `)`
Processing term/0 codePos term → expr `.` ID `(` expr• `)` inputPos 5
Match ) to ), matched; inputPos now 6
Reached end of rule, success! term/0 → 6
term/0 → 1, term('x') expr/0 → 1, expr(term('x')) term/4 → 5, term('5') expr/4 → 5, expr(term('5')) term/0 → 6, term(expr(term('x')),'.','apply','(',expr(term('5')),')')
#7: JoinS: expr/4 → 5 will resume cont: expr/4 ; expr → expr• `+` term
Processing expr/4 codePos expr → expr• `+` term inputPos 5
Match `+` to ), fail
term/0 → 1, term('x') expr/0 → 1, expr(term('x')) term/4 → 5, term('5') expr/4 → 5, expr(term('5')) term/0 → 6, term(expr(term('x')),'.','apply','(',expr(term('5')),')')
#8: JoinS: expr/4 → 5 will resume cont: term/4 ; term → expr• `.` ID `(` expr `)`
Processing term/4 codePos term → expr• `.` ID `(` expr `)` inputPos 5
Match `.` to ), fail
term/0 → 1, term('x') expr/0 → 1, expr(term('x')) term/4 → 5, term('5') expr/4 → 5, expr(term('5')) term/0 → 6, term(expr(term('x')),'.','apply','(',expr(term('5')),')')
Iteration 4
Worklist - successes
jS term/0 → 6
Worklist - continuations
#9: JoinS: term/0 → 6 will resume cont: expr/0 ; expr → term•
Processing expr/0 codePos expr → term• inputPos 6
Reached end of rule, success! expr/0 → 6
term/0 → 1, term('x') expr/0 → 1, expr(term('x')) term/4 → 5, term('5') expr/4 → 5, expr(term('5')) term/0 → 6, term(expr(term('x')),'.','apply','(',expr(term('5')),')') expr/0 → 6, expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')'))
Iteration 5
Worklist - successes
jS expr/0 → 6
Worklist - continuations
#10: JoinS: expr/0 → 6 will resume cont: Root/0 ; Root → expr•
×Didn't reach end of input, not a successful parse
term/0 → 1, term('x') expr/0 → 1, expr(term('x')) term/4 → 5, term('5') expr/4 → 5, expr(term('5')) term/0 → 6, term(expr(term('x')),'.','apply','(',expr(term('5')),')') expr/0 → 6, expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')'))
#11: JoinS: expr/0 → 6 will resume cont: expr/0 ; expr → expr• `+` term
Processing expr/0 codePos expr → expr• `+` term inputPos 6
Match + to +, matched; inputPos now 7
Calling: term/7 with Cont expr/0 ; expr → expr `+` term• [will process]
Processing term/7 codePos term → • NUM inputPos 7
Match NUM to y, fail
Processing term/7 codePos term → • ID inputPos 7
Match ID to y, matched; inputPos now 8
Reached end of rule, success! term/7 → 8
Processing term/7 codePos term → • expr `.` ID `(` expr `)` inputPos 7
Calling: expr/7 with Cont term/7 ; term → expr• `.` ID `(` expr `)` [will process]
Processing expr/7 codePos expr → • expr `+` term inputPos 7
Calling: expr/7 with Cont expr/7 ; expr → expr• `+` term [already processed]
Processing expr/7 codePos expr → • term inputPos 7
Calling: term/7 with Cont expr/7 ; expr → term• [already processed]
New continuations:
expr/7 → term/7 ; term → expr• `.` ID `(` expr `)` ; term
expr/7 → expr/7 ; expr → expr• `+` term ; expr
term/7 → expr/7 ; expr → term• ; expr
term/7 → expr/0 ; expr → expr `+` term• ; expr(expr(term(expr(term('x')), '.', 'apply', '(', expr(term('5')), ')')), '+')
term/0 → 1, term('x') expr/0 → 1, expr(term('x')) term/4 → 5, term('5') expr/4 → 5, expr(term('5')) term/0 → 6, term(expr(term('x')),'.','apply','(',expr(term('5')),')') expr/0 → 6, expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')) term/7 → 8, term('y')
#12: JoinS: expr/0 → 6 will resume cont: term/0 ; term → expr• `.` ID `(` expr `)`
Processing term/0 codePos term → expr• `.` ID `(` expr `)` inputPos 6
Match `.` to +, fail
term/0 → 1, term('x') expr/0 → 1, expr(term('x')) term/4 → 5, term('5') expr/4 → 5, expr(term('5')) term/0 → 6, term(expr(term('x')),'.','apply','(',expr(term('5')),')') expr/0 → 6, expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')) term/7 → 8, term('y')
Iteration 6
Worklist - successes
jS term/7 → 8
Worklist - continuations
nJ expr/7 → term/7 ; term → expr• `.` ID `(` expr `)`
nJ expr/7 → expr/7 ; expr → expr• `+` term
S⤚ term/7 → expr/7 ; expr → term•
S⤚ term/7 → expr/0 ; expr → expr `+` term•
#13: JoinS: term/7 → 8 will resume cont: expr/7 ; expr → term•
Processing expr/7 codePos expr → term• inputPos 8
Reached end of rule, success! expr/7 → 8
term/0 → 1, term('x') expr/0 → 1, expr(term('x')) term/4 → 5, term('5') expr/4 → 5, expr(term('5')) term/0 → 6, term(expr(term('x')),'.','apply','(',expr(term('5')),')') expr/0 → 6, expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')) term/7 → 8, term('y') expr/7 → 8, expr(term('y'))
#14: JoinS: term/7 → 8 will resume cont: expr/0 ; expr → expr `+` term•
Processing expr/0 codePos expr → expr `+` term• inputPos 8
Reached end of rule, success! expr/0 → 8
term/0 → 1, term('x') expr/0 → 1, expr(term('x')) term/4 → 5, term('5') expr/4 → 5, expr(term('5')) term/0 → 6, term(expr(term('x')),'.','apply','(',expr(term('5')),')') expr/0 → 6, expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')) term/7 → 8, term('y') expr/7 → 8, expr(term('y')) expr/0 → 8, expr(expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')),'+',term('y'))
Iteration 7
Worklist - successes
jS expr/7 → 8
jS expr/0 → 8
Worklist - continuations
#15: JoinS: expr/7 → 8 will resume cont: term/7 ; term → expr• `.` ID `(` expr `)`
Processing term/7 codePos term → expr• `.` ID `(` expr `)` inputPos 8
Match `.` to (eof), fail
term/0 → 1, term('x') expr/0 → 1, expr(term('x')) term/4 → 5, term('5') expr/4 → 5, expr(term('5')) term/0 → 6, term(expr(term('x')),'.','apply','(',expr(term('5')),')') expr/0 → 6, expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')) term/7 → 8, term('y') expr/7 → 8, expr(term('y')) expr/0 → 8, expr(expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')),'+',term('y'))
#16: JoinS: expr/7 → 8 will resume cont: expr/7 ; expr → expr• `+` term
Processing expr/7 codePos expr → expr• `+` term inputPos 8
Match `+` to (eof), fail
term/0 → 1, term('x') expr/0 → 1, expr(term('x')) term/4 → 5, term('5') expr/4 → 5, expr(term('5')) term/0 → 6, term(expr(term('x')),'.','apply','(',expr(term('5')),')') expr/0 → 6, expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')) term/7 → 8, term('y') expr/7 → 8, expr(term('y')) expr/0 → 8, expr(expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')),'+',term('y'))
#17: JoinS: expr/0 → 8 will resume cont: Root/0 ; Root → expr•
✓Reached end of input, successful parse!
term/0 → 1, term('x') expr/0 → 1, expr(term('x')) term/4 → 5, term('5') expr/4 → 5, expr(term('5')) term/0 → 6, term(expr(term('x')),'.','apply','(',expr(term('5')),')') expr/0 → 6, expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')) term/7 → 8, term('y') expr/7 → 8, expr(term('y')) expr/0 → 8, expr(expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')),'+',term('y')) Root/0 → 8, Root(expr(expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')),'+',term('y')))✓
#18: JoinS: expr/0 → 8 will resume cont: expr/0 ; expr → expr• `+` term
Processing expr/0 codePos expr → expr• `+` term inputPos 8
Match `+` to (eof), fail
term/0 → 1, term('x') expr/0 → 1, expr(term('x')) term/4 → 5, term('5') expr/4 → 5, expr(term('5')) term/0 → 6, term(expr(term('x')),'.','apply','(',expr(term('5')),')') expr/0 → 6, expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')) term/7 → 8, term('y') expr/7 → 8, expr(term('y')) expr/0 → 8, expr(expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')),'+',term('y')) Root/0 → 8, Root(expr(expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')),'+',term('y')))✓
#19: JoinS: expr/0 → 8 will resume cont: term/0 ; term → expr• `.` ID `(` expr `)`
Processing term/0 codePos term → expr• `.` ID `(` expr `)` inputPos 8
Match `.` to (eof), fail
term/0 → 1, term('x') expr/0 → 1, expr(term('x')) term/4 → 5, term('5') expr/4 → 5, expr(term('5')) term/0 → 6, term(expr(term('x')),'.','apply','(',expr(term('5')),')') expr/0 → 6, expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')) term/7 → 8, term('y') expr/7 → 8, expr(term('y')) expr/0 → 8, expr(expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')),'+',term('y')) Root/0 → 8, Root(expr(expr(term(expr(term('x')),'.','apply','(',expr(term('5')),')')),'+',term('y')))✓
Iteration 8
Worklist - successes
nJ Root/0 → 8
Worklist - continuations
(No new calls or successes that can be further processed)
Iteration 9 [Fixed point reached]