Takmela: Left recursion due to nullable nonterminals example

This is an example of 'invisible' left-recursion; the left recursion here isn't syntactic but can appear at runtime due to b being nullable, and thus a can call itself without consuming any input. I'm not sure this example follows the formal definition of left recursion, so let's call it "left-recursion-like behavior due to nullable nonterminals"

Again, Takmela's algorithm doesn't know or care about all this, it just dutifully parses the input

a:  b a c
  | 'a'
;

b:   'b'
   | ;
   
c : 'c';
    
NUM: [0-9]+;

PLUS: '+';
WS skip: ' '*;

bacc

Trace appears confusing? This might help

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