<jupyter_start><jupyter_text>Episode 17: Parsing with SLYIn our last heroic effort, we used an approach to top-down parsing called recursive descent.  Today, we'll be using a parser generator called SLY (https://github.com/dabeaz/sly) to create a bottom-up parsing state machine.SLY handles a lot of the parsing machinery that we had to work with manually in episode 16.  To use SLY, we'll have to refactor our calculator grammar a little.  First, we have to remove all our regular-expression shorthands (such as `?` for an optional clause, or `()` for a sub-clause).  Second, we have to ensure our recursive definitions avoid right recursion.  For recursive-descent we had to avoid left recursive definitions.  SLY requires us to do the exact opposite, and use left recursion instead of right.  For example:```statements : statements statement           | EMPTYstatement  : assign '\n'           | expression '\n'assign     : ID '=' expressionexpression : expression op atom           | atomatom       : ID | NUMop         : '+' | '-'```<jupyter_code>!pip install sly
# `conda install sly` also works thanks to Conda-Forge.
import nbimport
import Episode16
from sly import Lexer, Parser<jupyter_output>Requirement already satisfied: sly in /Users/jon/miniforge3/envs/ohop/lib/python3.9/site-packages (0.4)<jupyter_text>Step 1: Lexical AnalysisWriting a lexer in SLY is easier than doing it by hand...<jupyter_code>class CalcLexer(Lexer):
    tokens = { NL, ID, EQ, NUM, PLUS, MINUS }
    ignore = ' \t'
    
    NL = '\n'
    ID = r'[a-zA-Z_][a-zA-Z0-9_]*'
    EQ = r'='
    NUM = r'\d+'
    PLUS = r'\+'
    MINUS = r'-'
    
    def NL(self, tok):
        self.lineno += 1
        return tok
    
lexer = CalcLexer()
list(lexer.tokenize('1 + 2 - 3\nA = 5\n'))<jupyter_output><empty_output><jupyter_text>Step 2: Syntactic AnalysisIn SLY we use decorators to embed the grammar definition into the parser.  The job of the parsing class is simplified by no longer having to worry about interactions with the lexer or other non-terminal symbols.  What we have to do instead is tell SLY what to do with the child information it has assembled.  We write a method for each rule in the grammar definition as shown...<jupyter_code>Tree = Episode16.Tree

class CalcParser(Parser):
    tokens = CalcLexer.tokens

    @_('statements statement')
    def statements(self, children):
        '''Recognize rule `statements : statements statement`...
        '''
        return Tree('statements', [children.statements, children.statement])
    
    @_('') # EMPTY!
    def statements(self, children):
        return Tree('statements', [])

    @_('assign NL')
    def statement(self, children):
        return Tree('statement', [children.assign])
    
    @_('expression NL')
    def statement(self, children):
        return Tree('statement', [children.expression])

    @_('ID EQ expression')
    def assign(self, children):
        return Tree('assign', [Tree(children.ID, []), Tree(children.EQ, []), children.expression])

    @_('expression op atom')
    def expression(self, children):
        return Tree('expression', [children.expression, children.op, children.atom])

    @_('atom')
    def expression(self, children):
        return Tree('expression', [children.atom])

    @_('PLUS')
    def op(self, children):
        return Tree('op', [Tree(children.PLUS, [])])

    @_('MINUS')
    def op(self, children):
        return Tree('op', [Tree(children.MINUS, [])])

    @_('ID')
    def atom(self, children):
        return Tree('atom', [Tree(children.ID, [])])

    @_('NUM')
    def atom(self, children):
        return Tree('atom', [Tree(children.NUM, [])])<jupyter_output><empty_output><jupyter_text>Step 3: Tie Everything Together<jupyter_code>class CalcFrontend:
    def __init__(self):
        self.lexer = CalcLexer()
        self.parser = CalcParser()

    def __call__(self, source):
        return self.parser.parse(self.lexer.tokenize(source))


calc_frontend = CalcFrontend()
ep17_test_result = calc_frontend('1 + 2 - 3\nA = 5\n')
Episode16.tree_to_tuple(ep17_test_result)
Episode16.tree_to_tuple(Episode16.quick_test_result)
class SLYTestParser(Parser):
    tokens = CalcLexer.tokens
    
    @_('spine ID')
    def spine(self, children):
        print(children)
        return children, children.spine, children.ID
    
    @_('')
    def spine(self, children):
        return children

lexer = CalcLexer()
parser = SLYTestParser()
result = parser.parse(lexer.tokenize('A b C D'))
result
list(result[0]), result[0].spine<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup