parser.py

from jsparagus import runtime
from jsparagus.runtime import Nt, ErrorToken

actions = [
    # 0. <empty>
    #       InitNt(goal=Nt('expr')) ::= · expr
    {'-': 1, 'NUM': 2, 'VAR': 3, '(': 4},

    # 1. "-"
    #       unary ::= "-" · unary
    {'-': 1, 'NUM': 2, 'VAR': 3, '(': 4},

    # 2. NUM
    #       prim ::= NUM ·
    {None: -9, '*': -9, '/': -9, '+': -9, '-': -9, ')': -9},

    # 3. VAR
    #       prim ::= VAR ·
    {None: -10, '*': -10, '/': -10, '+': -10, '-': -10, ')': -10},

    # 4. "("
    #       prim ::= "(" · expr ")"
    {'-': 1, 'NUM': 2, 'VAR': 3, '(': 4},

    # 5. expr
    #       InitNt(goal=Nt('expr')) ::= expr ·
    #       expr ::= expr · "+" term
    #       expr ::= expr · "-" term
    {'+': 11, '-': 12, None: -4611686018427387905},

    # 6. term
    #       expr ::= term ·
    #       term ::= term · "*" unary
    #       term ::= term · "/" unary
    {'*': 13, '/': 14, None: -1, '+': -1, '-': -1, ')': -1},

    # 7. unary
    #       term ::= unary ·
    {None: -4, '*': -4, '/': -4, '+': -4, '-': -4, ')': -4},

    # 8. prim
    #       unary ::= prim ·
    {None: -7, '*': -7, '/': -7, '+': -7, '-': -7, ')': -7},

    # 9. "-" unary
    #       unary ::= "-" unary ·
    {None: -8, '*': -8, '/': -8, '+': -8, '-': -8, ')': -8},

    # 10. "(" expr
    #       prim ::= "(" expr · ")"
    #       expr ::= expr · "+" term
    #       expr ::= expr · "-" term
    {')': 15, '+': 11, '-': 12},

    # 11. expr "+"
    #       expr ::= expr "+" · term
    {'-': 1, 'NUM': 2, 'VAR': 3, '(': 4},

    # 12. expr "-"
    #       expr ::= expr "-" · term
    {'-': 1, 'NUM': 2, 'VAR': 3, '(': 4},

    # 13. term "*"
    #       term ::= term "*" · unary
    {'-': 1, 'NUM': 2, 'VAR': 3, '(': 4},

    # 14. term "/"
    #       term ::= term "/" · unary
    {'-': 1, 'NUM': 2, 'VAR': 3, '(': 4},

    # 15. "(" expr ")"
    #       prim ::= "(" expr ")" ·
    {None: -11, '*': -11, '/': -11, '+': -11, '-': -11, ')': -11},

    # 16. expr "+" term
    #       expr ::= expr "+" term ·
    #       term ::= term · "*" unary
    #       term ::= term · "/" unary
    {'*': 13, '/': 14, None: -2, '+': -2, '-': -2, ')': -2},

    # 17. expr "-" term
    #       expr ::= expr "-" term ·
    #       term ::= term · "*" unary
    #       term ::= term · "/" unary
    {'*': 13, '/': 14, None: -3, '+': -3, '-': -3, ')': -3},

    # 18. term "*" unary
    #       term ::= term "*" unary ·
    {None: -5, '*': -5, '/': -5, '+': -5, '-': -5, ')': -5},

    # 19. term "/" unary
    #       term ::= term "/" unary ·
    {None: -6, '*': -6, '/': -6, '+': -6, '-': -6, ')': -6},

]

ctns = [
    {'expr': 5, 'term': 6, 'unary': 7, 'prim': 8},
    {'unary': 9, 'prim': 8},
    {},
    {},
    {'expr': 10, 'term': 6, 'unary': 7, 'prim': 8},
    {},
    {},
    {},
    {},
    {},
    {},
    {'term': 16, 'unary': 7, 'prim': 8},
    {'term': 17, 'unary': 7, 'prim': 8},
    {'unary': 18, 'prim': 8},
    {'unary': 19, 'prim': 8},
    {},
    {},
    {},
    {},
    {},
]

special_cases = [
]

error_codes = [
    None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None,
    None, None, None, None,
]

reductions = [
    # 0. expr ::= term => $0
    ('expr', 1, lambda builder, x0: x0),
    # 1. expr ::= expr "+" term => expr 1($0, $1, $2)
    ('expr', 3, lambda builder, x0, x1, x2: builder.expr_P1(x0, x1, x2)),
    # 2. expr ::= expr "-" term => expr 2($0, $1, $2)
    ('expr', 3, lambda builder, x0, x1, x2: builder.expr_P2(x0, x1, x2)),
    # 3. term ::= unary => $0
    ('term', 1, lambda builder, x0: x0),
    # 4. term ::= term "*" unary => term 1($0, $1, $2)
    ('term', 3, lambda builder, x0, x1, x2: builder.term_P1(x0, x1, x2)),
    # 5. term ::= term "/" unary => term 2($0, $1, $2)
    ('term', 3, lambda builder, x0, x1, x2: builder.term_P2(x0, x1, x2)),
    # 6. unary ::= prim => $0
    ('unary', 1, lambda builder, x0: x0),
    # 7. unary ::= "-" unary => unary 1($0, $1)
    ('unary', 2, lambda builder, x0, x1: builder.unary_P1(x0, x1)),
    # 8. prim ::= NUM => $0
    ('prim', 1, lambda builder, x0: x0),
    # 9. prim ::= VAR => $0
    ('prim', 1, lambda builder, x0: x0),
    # 10. prim ::= "(" expr ")" => prim 2($0, $1, $2)
    ('prim', 3, lambda builder, x0, x1, x2: builder.prim_P2(x0, x1, x2)),
]


class DefaultBuilder:
    def expr_P1(self, x0, x1, x2): return ('expr 1', x0, x1, x2)
    def expr_P2(self, x0, x1, x2): return ('expr 2', x0, x1, x2)
    def term_P1(self, x0, x1, x2): return ('term 1', x0, x1, x2)
    def term_P2(self, x0, x1, x2): return ('term 2', x0, x1, x2)
    def unary_P1(self, x0, x1): return ('unary 1', x0, x1)
    def prim_P2(self, x0, x1, x2): return ('prim 2', x0, x1, x2)


goal_nt_to_init_state = {
    'expr': 0,
}

class Parser(runtime.Parser):
    def __init__(self, goal='expr', builder=None):
        if builder is None:
            builder = DefaultBuilder()
        super().__init__(actions, ctns, reductions, special_cases, error_codes,
                         goal_nt_to_init_state[goal], builder)

walkthrough.txt

# input is: 2 + 2
#               ^
#['NUM', '+', 'NUM', None]



state = 2

stack = [('expr 1', '2', '+', '2')]
state_stack = [0]



# 'NUM'
we are in state 0
actions[0]['NUM'] is 2
push '2' to the stack
push 0 to the state_stack
jump to state 2

# receive '+'
we are in state 2
actions[2]['+'] is -9
do reduction 8 (prim ::= NUM)
pop '2' from the stack
call the lambda
push the result back onto the stack
go back to state 0
ctns[0]['prim'] is 8
go to state 8

# try again to receive '+'
we are in state 8
actions[8]['+'] is -7
do reduction 6 (unary ::= prim)
...
ctns[0]['unary'] is 7
go to state 7

# try again to receive '+'
...
...

# try again to receive '+'
we are in state 5
actions[5]['+'] is 11
SHIFT the '+' to the stack
go to state 11

# receive 'NUM'
we are in state 11
actions[11]['NUM'] is 2
SHIFT the 'NUM' to the stack
go to state 2

# try to receive None
we are in state 2
actions[2][None] is -9
do reduction 8 (prim ::= NUM)
ctns[11]['prim'] is 8
go to state 8

...
...
...

# try to receive None
we are in state 16
actions[16][None] is -2
do reduction 1 (expr ::= expr "+" term)
pop 3 values off the stack, matching [expr, "+", term]
reduce them by calling builder method
pop 2 values off the state_stack, leaving 0 on top
go back to state 0
ctns[0]['expr'] is 5
push the new 'expr' onto the stack
go to state 5