Trying to parse: λx.λy.x x
Tokens: [Lambda, 'x', Dot, Lambda, 'y', Dot, 'x', Space, 'x']
| Step | Op | State | Tokens |
|---|---|---|---|
| 1 | Start | [] |
[Lambda, 'x', Dot, Lambda, 'y', Dot, 'x', Space, 'x'] |
| 2 | Shift | [Lambda] |
['x', Dot, Lambda, 'y', Dot, 'x', Space, 'x'] |
| 3 | Reduce | [Lambda] |
['x', Dot, Lambda, 'y', Dot, 'x', Space, 'x'] |
| 4 | Shift | [Lambda, 'x'] |
[Dot, Lambda, 'y', Dot, 'x', Space, 'x'] |
| 5 | Reduce | [Lambda, Var<x>] |
[Dot, Lambda, 'y', Dot, 'x', Space, 'x'] |
| 6 | Reduce | [Lambda, Var<x>] |
[Dot, Lambda, 'y', Dot, 'x', Space, 'x'] |
| 7 | Shift | [Lambda, Var<x>, Dot] |
[Lambda, 'y', Dot, 'x', Space, 'x'] |
| 8 | Reduce | [Lambda, Var<x>, Dot] |
[Lambda, 'y', Dot, 'x', Space, 'x'] |
| 9 | Shift | [Lambda, Var<x>, Dot, Lambda] |
['y', Dot, 'x', Space, 'x'] |
| 10 | Reduce | [Lambda, Var<x>, Dot, Lambda] |
['y', Dot, 'x', Space, 'x'] |
| 11 | Shift | [Lambda, Var<x>, Dot, Lambda, 'y'] |
[Dot, 'x', Space, 'x'] |
| 12 | Reduce | [Lambda, Var<x>, Dot, Lambda, Var<y>] |
[Dot, 'x', Space, 'x'] |
| 13 | Reduce | [Lambda, Var<x>, Dot, Lambda, Var<y>] |
[Dot, 'x', Space, 'x'] |
| 14 | Shift | [Lambda, Var<x>, Dot, Lambda, Var<y>, Dot] |
['x', Space, 'x'] |
| 15 | Reduce | [Lambda, Var<x>, Dot, Lambda, Var<y>, Dot] |
['x', Space, 'x'] |
| 16 | Shift | [Lambda, Var<x>, Dot, Lambda, Var<y>, Dot, 'x'] |
[Space, 'x'] |
| 17 | Reduce | [Lambda, Var<x>, Dot, Lambda, Var<y>, Dot, Var<x>] |
[Space, 'x'] |
| 18 | Reduce | [Lambda, Var<x>, Dot, Lambda, Var<y>, Dot, Var<x>] |
[Space, 'x'] |
| 19 | Shift | [Lambda, Var<x>, Dot, Lambda, Var<y>, Dot, Var<x>, Space] |
['x'] |
| 20 | Reduce | [Lambda, Var<x>, Dot, Lambda, Var<y>, Dot, Var<x>, Space] |
['x'] |
| 21 | Shift | [Lambda, Var<x>, Dot, Lambda, Var<y>, Dot, Var<x>, Space, 'x'] |
[] |
| 22 | Reduce | [Lambda, Var<x>, Dot, Lambda, Var<y>, Dot, Var<x>, Space, Var<x>] |
[] |
| 23 | Reduce | [Lambda, Var<x>, Dot, Lambda, Var<y>, Dot, App<Var<x>, Var<x>>] |
[] |
| 24 | Reduce | [Lambda, Var<x>, Dot, Abs<Var<y>, App<Var<x>, Var<x>>>] |
[] |
| 25 | Reduce | [Abs<Var<x>, Abs<Var<y>, App<Var<x>, Var<x>>>>] |
[] |
On step 6 and 13, the parse tries to reduce again because the state changed from the previous reduce
On step 18, the parse don't reduces again because it does a lookahead and checks that there's a Space in the Tokens list
Reduce steps uses shift-reducing, for example, in the [Lambda, Var<x>, Dot, Lambda, Var<y>] case, it tries to reduce all those cases:
[Var<y>][Lambda, Var<y>][Dot, Lambda, Var<y>][Var<x>, Dot, Lambda, Var<y>][Lambda, Var<x>, Dot, Lambda, Var<y>]
Implementation: https://github.com/fersilva16/lcts/blob/main/src/Parse.ts