Takmela: Parsing arithmetic expression example (more complicated expressions)

Arithmetic expression again, but something more complicated than 1+2+3; more resembling e.g expressions in programming languages.

e : e '+' t 
    | t ;
    
t : t '*' f 
    | f ;
        
f : 
      NUM
    | ID
    | '(' e ')'
    | ID '(' e ')'
    ;
    
ID:  [a-zA-Z]+;
NUM: [0-9]+;

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

1+f(5+x)

Trace appears confusing? This might help

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