Editing LL parser (section)

=== Parser implementation in Python ===

<syntaxhighlight lang="python">
from enum import Enum
from collections.abc import Generator


class Term(Enum):
    pass


class Rule(Enum):
    pass


# All constants are indexed from 0
class Terminal(Term):
    LPAR = 0
    RPAR = 1
    A = 2
    PLUS = 3
    END = 4
    INVALID = 5

    def __str__(self):
        return f"T_{self.name}"


class NonTerminal(Rule):
    S = 0
    F = 1

    def __str__(self):
        return f"N_{self.name}"


# Parse table
table = [[1, -1, 0, -1, -1, -1], [-1, -1, 2, -1, -1, -1]]

RULES = [
    [NonTerminal.F],
    [
        Terminal.LPAR,
        NonTerminal.S,
        Terminal.PLUS,
        NonTerminal.F,
        Terminal.RPAR,
    ],
    [Terminal.A],
]

stack = [Terminal.END, NonTerminal.S]


def lexical_analysis(input_string: str) -> Generator[Terminal]:
    print("Lexical analysis")
    for c in input_string:
        match c:
            case "a":
                yield Terminal.A
            case "+":
                yield Terminal.PLUS
            case "(":
                yield Terminal.LPAR
            case ")":
                yield Terminal.RPAR
            case _:
                yield Terminal.INVALID
    yield Terminal.END


def syntactic_analysis(tokens: list[Terminal]) -> None:
    print("tokens:", end=" ")
    print(*tokens, sep=", ")
    print("Syntactic analysis")
    position = 0
    while stack:
        svalue = stack.pop()
        token = tokens[position]
        if isinstance(svalue, Term):
            if svalue == token:
                position += 1
                print("pop", svalue)
                if token == Terminal.END:
                    print("input accepted")
            else:
                raise ValueError("bad term on input:", str(token))
        elif isinstance(svalue, Rule):
            print(f"{svalue = !s}, {token = !s}")
            rule = table[svalue.value][token.value]
            print(f"{rule = }")
            for r in reversed(RULES[rule]):
                stack.append(r)
        print("stacks:", end=" ")
        print(*stack, sep=", ")


if __name__ == "__main__":
    inputstring = "(a+a)"
    syntactic_analysis(list(lexical_analysis(inputstring)))
</syntaxhighlight>

Outputs:
{{sxhl|2=output|1=
Lexical analysis
tokens: T_LPAR, T_A, T_PLUS, T_A, T_RPAR, T_END
Syntactic analysis
svalue = N_S, token = T_LPAR
rule = 1
stacks: T_END, T_RPAR, N_F, T_PLUS, N_S, T_LPAR
pop T_LPAR
stacks: T_END, T_RPAR, N_F, T_PLUS, N_S
svalue = N_S, token = T_A
rule = 0
stacks: T_END, T_RPAR, N_F, T_PLUS, N_F
svalue = N_F, token = T_A
rule = 2
stacks: T_END, T_RPAR, N_F, T_PLUS, T_A
pop T_A
stacks: T_END, T_RPAR, N_F, T_PLUS
pop T_PLUS
stacks: T_END, T_RPAR, N_F
svalue = N_F, token = T_A
rule = 2
stacks: T_END, T_RPAR, T_A
pop T_A
stacks: T_END, T_RPAR
pop T_RPAR
stacks: T_END
pop T_END
input accepted
stacks:

}}