PLY (Python Lex-Yacc)

To parse tokens into an Abstract Syntax Tree (AST) or other structures, define grammar rules as Python functions. Each function must have a docstring containing the grammar rule.

Key components:

• p_ <rule_name>(p): A function representing a grammar rule. The argument p is a sequence representing the rule contents.
• p[0]: The result of the rule (the value assigned to the non-terminal).
• p[1], p[2], ...: The components of the rule (the symbols matched).
• p_error(p): A function to handle syntax errors.
• yacc(): Builds the parser object.
• parser.parse(input): Executes the parsing process on the provided input string.

from ply.yacc import yacc

def p_expression(p):
    '''
    expression : term PLUS term
               | term MINUS term
    '''
    p[0] = ('binop', p[2], p[1], p[3])

def p_error(p):
    print(f'Syntax error at {p.value!r}')

parser = yacc()
ast = parser.parse('2 * 3 + 4')

By default, lex.lex() inspects the current module. You can specify a different source for your rules using the module argument.

• External Module: Pass a module object (e.g., import my_rules; lex.lex(module=my_rules)).
• Class Instance: Pass an instance of a class. Note that when using a class, you must construct the lexer from an instance, not the class itself, so that token rules are bound to that instance.

import ply.lex as lex

class MyLexer:
    tokens = ('NUMBER', 'PLUS')
    t_PLUS = r'\+'

    def t_NUMBER(self, t):
        r'\d+'
        t.value = int(t.value)
        return t

    def build(self, **kwargs):
        self.lexer = lex.lex(module=self, **kwargs)

    def test(self, data):
        self.lexer.input(data)
        while True:
            tok = self.lexer.token()
            if not tok: break
            print(tok)

m = MyLexer()
m.build()
m.test("123 + 456")

To tokenize input, define a set of tokens, regex-based matching rules (either as string variables or functions with docstrings), and an error handler. Use lex() to build the lexer object.

Key components:

• tokens: A tuple of all token names.
• t_ignore: A string containing characters to be ignored (e.g., ' ').
• t_<NAME>: A string variable containing the regex for a token.
• def t_<NAME>(t): A function used for tokens requiring actions; the regex must be in the function's docstring.
• t_error(t): A function to handle illegal characters.
• t_ignore_newline(t): A function to handle specific patterns like newlines (e.g., updating t.lexer.lineno).

from ply.lex import lex

tokens = ( 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN', 'NAME', 'NUMBER' )
t_ignore = ' \t'
t_PLUS = r'\+'

def t_NUMBER(t):
    r'\d+'
    t.value = int(t.value)
    return t

def t_error(t):
    print(f'Illegal character {t.value[0]!r}')
    t.lexer.skip(1)

lexer = lex()

PLY's yacc.py module is used to parse language syntax using a BNF (Backus-Naur Form) grammar.

Key Concepts

• Terminals: Symbols that correspond to input tokens (e.g., NUMBER, +, -, *, /).
• Non-terminals: Identifiers that refer to grammar rules composed of terminals and other rules (e.g., expression, term, factor).
• Syntax Directed Translation: A technique where attributes (like a .val attribute) are attached to grammar symbols. When a rule is recognized, a semantic action is triggered to perform computations based on these attributes.

Parsing Mechanism

yacc.py implements LR-parsing (also known as shift-reduce parsing), a bottom-up technique:

1. Shift: Moving grammar symbols from the input onto a stack.
2. Reduce: When the top of the stack matches the right-hand side of a grammar rule, the symbols are replaced by the rule's left-hand side (the non-terminal), and any associated semantic actions are executed.

A parse is successful only if the parser reaches a state where the symbol stack is empty and all input tokens have been processed.