HFUT.CT.EXP#2

LL(1).py

from collections import defaultdict
import re
from typing import Self


def error(*args) -> None:
    print(*args)
    exit(1)


class Solution:
    def __init__(self) -> None:
        self.isTerminal = lambda i: not i.isupper()

        self.NULL: str = "$"
        self.SEPARATOR: str = "|"
        self.START: str = "E"
        self.PRODUCTION: str = "(.*)->(.*)"

        self.lefts = set()
        self.rights = set()

        self.firstSet: dict[str, set] = defaultdict(set)
        self.followSet: dict[str, set] = defaultdict(set)
        self.parsingTable: dict[str, dict[str, str]] = defaultdict(dict)

        self.lines: list[str] = list()
        self.productions: dict[str, list[str]] = defaultdict(list)

        self.currentLine: int = 0
        self.histories: list[dict] = list()

    def read(self, filename: str) -> Self:
        with open(filename) as file:
            lines = file.readlines()

        for line in lines:
            self.lines.append(line.replace(" ", ""))

        return self

    def analyse(self) -> Self:
        for i, line in enumerate(self.lines):
            self.currentLine = i + 1
            _ = re.search(self.PRODUCTION, line)
            if _ is None or len(_.groups()) != 2:
                error(f"line {i}: analyse error")
            left, right = _.groups()
            self.productions[left] = right.split(self.SEPARATOR)

        for left, right in self.productions.items():
            self.lefts.add(left)
            for i in right:
                self.rights |= set(i)
            self.rights -= self.lefts

        for i in self.productions:
            self.first(i)

        for i in self.productions:
            self.follow(i)

        self.parsing()

        return self

    def first(self, sign: str) -> None:
        for i in self.productions[sign]:
            self.firstSet[sign] |= self.exprFirst(i)

    def exprFirst(self, expression: str) -> set:
        first = set()
        if self.isTerminal(expression[0]):
            first.add(expression[0])
        else:
            for c in expression:
                if c not in self.firstSet:
                    self.first(c)

                if self.NULL not in self.firstSet[c]:
                    first |= self.firstSet[c]
                    break
                else:
                    first |= self.firstSet[c] - self.NULL

            if all(self.NULL in self.firstSet[c] for c in expression):
                first.add(self.NULL)
        return first

    def follow(self, sign: str) -> None:
        self.followSet[sign].add(self.NULL)
        for left, right in self.productions.items():
            for i in right:  # i: P->...
                loc: int = i.find(sign)
                if loc == -1:
                    continue
                elif loc == len(i) - 1:  # ...A
                    if left not in self.followSet:
                        self.follow(left)
                    self.followSet[sign] |= self.followSet[left]
                else:
                    if self.isTerminal(i[loc + 1]):  # ...Ae...
                        self.followSet[sign].add(i[loc + 1])
                    else:  # ...AB...
                        self.followSet[sign] |= self.firstSet[i[loc + 1]] - {self.NULL}
                        if self.NULL in self.firstSet[i[loc + 1]]:  # $ in firstSet[B]
                            if left not in self.followSet:
                                self.follow(left)
                            self.followSet[sign] |= self.followSet[left]

    def parsing(self) -> None:
        for left, right in self.productions.items():
            for i in right:
                if i == self.NULL:
                    for c in self.followSet[left]:
                        self.parsingTable[left][c] = i
                else:
                    for c in self.exprFirst(i) - {self.NULL}:
                        self.parsingTable[left][c] = i

    def test(self, expression: str) -> Self:
        self.histories: list[dict] = list()
        symbolStack = ["#", self.START]
        procedure, action, i = "", "INIT", 0

        if expression[-1] != "#":
            procedure = action = "ERROR(1)"

        while symbolStack[-1] != "#":
            self.histories.append(
                {
                    "symbolStack": "".join(symbolStack),
                    "expression": expression[i:],
                    "procedure": procedure,
                    "action": action,
                }
            )

            if procedure.startswith("ERROR"):
                return self

            if expression[i] == "#":
                top: str = symbolStack.pop()
                if self.NULL in self.parsingTable[top]:
                    _ = self.parsingTable[top][self.NULL]
                    procedure = f"{top}->{_}"
                    action = "POP"
                else:
                    procedure = action = "ERROR(2)"

            elif self.isTerminal(symbolStack[-1]):
                if expression[i] == symbolStack[-1]:
                    symbolStack.pop()
                    i += 1
                    procedure = ""
                    action = "GETNEXT(I)"
                else:
                    procedure = action = "ERROR(3)"

            else:
                top: str = symbolStack.pop()
                if expression[i] in self.parsingTable[top]:
                    _ = self.parsingTable[top][expression[i]]
                    if _ != self.NULL:
                        symbolStack.extend(reversed(_))
                        action = f"POP, PUSH({''.join(reversed(_))})"
                    else:
                        action = "POP"
                    procedure = f"{top}->{_}"
                else:
                    procedure = action = "ERROR(4)"

        if expression[i] != "#":
            procedure = action = "ERROR(5)"
        self.histories.append(
            {
                "symbolStack": "".join(symbolStack),
                "expression": expression[i:],
                "procedure": procedure,
                "action": action,
            }
        )

        return self

    def printFirstSet(self) -> Self:
        print("[FIRST]")
        for i, j in self.firstSet.items():
            print(f"{i}: {' '.join(sorted(j))}")
        return self

    def printFollowSet(self) -> Self:
        print("[FOLLOW]")
        for i, j in self.followSet.items():
            print(f"{i}: {' '.join(sorted(j))}")
        return self

    def printParsingTable(self) -> Self:
        print("[PARSING]")
        print(f"\t" + "\t".join(sorted(self.rights)))
        for i in sorted(self.lefts):
            print(f"{i}", end="\t")
            if i not in self.parsingTable:
                continue
            for j in sorted(self.rights):
                if j not in self.parsingTable[i]:
                    print("", end="\t")
                else:
                    print(self.parsingTable[i][j], end="\t")
            print("\n", end="")
        return self

    def printHistories(self) -> Self:
        print("[HISTORY]")
        for i in self.histories:
            print(
                f"{i['symbolStack']}\t\t{i['expression']}\t\t{i['procedure']}\t\t{i['action']}"
            )
        return self


sol = Solution()
sol.read(
    "ll(1).txt"
).analyse().printFirstSet().printFollowSet().printParsingTable().test(
    "i+i*i#"
).printHistories()