Takmela: Nullable bug example from Aycock-Horspool

This is a trace of a grammar that demonstrated a bug found in earlier versions of Earley's parser, related to nullable non-terminals. Let's run it on Takmela and see if the input will be accepted!

(I found the example in John Aycock and R. Nigel Horspool's paper "Practical Earley Parsing". Here you will find the trace with the full grammar from the paper. If you would prefer a version with a simplified grammar/trace, you can find it here).

start: s;

s: a a a a;

a: 'a' | e;

e: ;

WS skip: [ \r\n\t]*;

a

Trace appears confusing? This might help

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