如何解析计算机代码，代码的出现 ay 3

解决了后来的一些《Advent of Code》挑战后，我想重新回顾第 3 天，它提出了一个有趣的解析问题。该任务涉及从嘈杂的输入中提取有效的代码，这是解析器和词法分析器开发中的一个很好的练习。和我一起探索应对这一挑战的方法。

由 Microsoft Copilot 生成的图像，显​​示我对拼图 (?) 的热爱

当我第一次写统治者DSL时，我依靠Hy进行解析。然而，我最近对生成式人工智能的探索引入了一种新的解析方法：使用 funcparserlib 库生成代码。这次“代码挑战”让我能够深入研究 funcparserlib 的复杂性，并对生成的代码的功能有更深入的掌握。

实施词法分析器（词法分析）

处理损坏的输入的第一步是词法分析（或标记化）。 词法分析器（或分词器）扫描输入字符串并将其分成单独的标记，它们是进一步处理的基本构建块。 token 表示输入中有意义的单元，按其类型进行分类。对于这个谜题，我们对这些令牌类型感兴趣：

• 运算符 (OP)： 这些代表函数名称，例如 mul、do 和 don't。例如，输入 mul(2, 3) 包含运算符标记 mul.
• 数字：这些是数值。例如，在输入 mul(2, 3) 中，2 和 3 将被识别为数字标记。
• 逗号： 逗号字符 (,) 充当参数之间的分隔符。
• 括号： 左括号（和右括号）定义函数调用的结构。
• 乱码： 此类别包含与其他标记类型不匹配的任何字符或字符序列。这就是输入的“损坏”部分出现的地方。例如，%$#@ 或任何随机字母将被视为乱码。

虽然 funcparserlib 经常在其教程中使用魔术字符串，但我更喜欢更结构化的方法。魔术字符串可能会导致拼写错误并使重构代码变得困难。使用 Enum 定义令牌类型有几个优点：更好的可读性、改进的可维护性和增强的类型安全性。以下是我如何使用枚举定义令牌类型：

from enum import Enum, auto

class Spec(Enum):
    OP = auto()
    NUMBER = auto()
    COMMA = auto()
    LPAREN = auto()
    RPAREN = auto()
    GIBBERISH = auto()

通过使用 Spec.OP、Spec.NUMBER 等，我们避免了与使用纯字符串相关的歧义和潜在错误。

为了将 Enum 与 funcparserlib 无缝集成，我创建了一个名为 TokenSpec_ 的自定义装饰器。该装饰器充当 funcparserlib 中原始 TokenSpec 函数的包装器。它通过接受 Spec Enum 中的值作为 spec 参数来简化标记定义。在内部，它提取枚举 (spec.name) 的字符串表示形式，并将其与任何其他参数一起传递给原始 TokenSpec 函数。

from enum import Enum, auto

class Spec(Enum):
    OP = auto()
    NUMBER = auto()
    COMMA = auto()
    LPAREN = auto()
    RPAREN = auto()
    GIBBERISH = auto()

使用修饰过的 TokenSpec_ 函数，我们可以定义分词器。我们使用 funcparserlib 中的 make_tokenizer 创建一个采用 TokenSpec_ 定义列表的分词器。每个定义指定一个标记类型（来自我们的规范枚举）和一个与之匹配的正则表达式。

from funcparserlib.lexer import TokenSpec

def TokenSpec_(spec: Spec, *args: Any, **kwargs: Any) -> TokenSpec:
    return TokenSpec(spec.name, *args, **kwargs)

OP正则表达式使用交替（|）来匹配不同的函数格式。具体来说：

• mul(?=(d{1,3},d{1,3}))：仅当 mul 后跟包含两个以逗号分隔的数字的括号时才匹配 mul。正向先行断言 (?=...) 确保括号和数字存在，但不会被匹配消耗。
• do(?=())：仅当后面跟有空括号时才匹配。
• dont(?=())：仅当后跟空括号时才匹配 don。

正则表达式的图形表示

最后，tokenize 函数会在分词过程中过滤掉任何乱码标记，以专注于输入的相关部分以进行进一步处理。

解释代码的过程通常涉及两个主要阶段：词法分析（或词法分析）和解析。我们已经实现了第一阶段：我们的 tokenize 函数充当词法分析器，获取输入字符串并将其转换为标记序列。这些标记是解析器用来理解代码的结构和含义的基本构建块。现在，让我们探讨一下解析器如何使用这些标记。

实现解析器

由 tokenize 函数返回的已解析令牌随后被发送到解析器进行进一步处理。为了弥补 Spec Enum 和 tok 函数之间的差距，我们引入了一个名为 tok_ 的装饰器。

from funcparserlib.lexer import make_tokenizer

def tokenize(input: str) -> tuple[Token, ...]:
    tokenizer = make_tokenizer(
        [
            TokenSpec_(
                Spec.OP, r"mul(?=\(\d{1,3},\d{1,3}\))|do(?=\(\))|don\'t(?=\(\))"
            ),
            TokenSpec_(Spec.NUMBER, r"\d{1,3}"),
            TokenSpec_(Spec.LPAREN, r"\("),
            TokenSpec_(Spec.RPAREN, r"\)"),
            TokenSpec_(Spec.COMMA, r","),
            TokenSpec_(Spec.GIBBERISH, r"[\s\S]"),
        ]
    )

    return tuple(
        token for token in tokenizer(input) if token.type != Spec.GIBBERISH.name
    )

例如，如果我们有一个 Spec.NUMBER 令牌，则返回的解析器将接受该令牌，并返回一个值，如下所示：

from funcparserlib.parser import tok

def tok_(spec: Spec, *args: Any, **kwargs: Any) -> Parser[Token, str]:
    return tok(spec.name, *args, **kwargs)

然后可以使用>>将返回的值转换为所需的数据类型。运算符，如下图：

from enum import Enum, auto

class Spec(Enum):
    OP = auto()
    NUMBER = auto()
    COMMA = auto()
    LPAREN = auto()
    RPAREN = auto()
    GIBBERISH = auto()

通常，在解析未知输入时最好使用 ast.literal_eval 以避免潜在的安全漏洞。然而，这个特定的“代码降临”谜题的限制（具体来说，所有数字都是有效整数）允许我们使用更直接、更高效的 int 函数将字符串表示形式转换为整数。

from funcparserlib.lexer import TokenSpec

def TokenSpec_(spec: Spec, *args: Any, **kwargs: Any) -> TokenSpec:
    return TokenSpec(spec.name, *args, **kwargs)

我们可以定义解析规则来强制执行特定的标记序列并将其转换为有意义的对象。例如，要解析 mul 函数调用，我们需要以下序列：左括号、数字、逗号、另一个数字、右括号。然后我们将此序列转换为 Mul 对象：

from funcparserlib.lexer import make_tokenizer

def tokenize(input: str) -> tuple[Token, ...]:
    tokenizer = make_tokenizer(
        [
            TokenSpec_(
                Spec.OP, r"mul(?=\(\d{1,3},\d{1,3}\))|do(?=\(\))|don\'t(?=\(\))"
            ),
            TokenSpec_(Spec.NUMBER, r"\d{1,3}"),
            TokenSpec_(Spec.LPAREN, r"\("),
            TokenSpec_(Spec.RPAREN, r"\)"),
            TokenSpec_(Spec.COMMA, r","),
            TokenSpec_(Spec.GIBBERISH, r"[\s\S]"),
        ]
    )

    return tuple(
        token for token in tokenizer(input) if token.type != Spec.GIBBERISH.name
    )

此规则将所需标记（OP、LPAREN、COMMA、RPAREN）的 tok_ 解析器与数字解析器结合起来。 >>然后运算符将匹配的序列转换为 Mul 对象，从索引 2 和 4 处的元组 elem 中提取两个数字。

我们可以应用相同的原则来定义 do 和 don't 操作的解析规则。这些操作不带参数（用空括号表示）并转换为 Condition 对象：

from funcparserlib.parser import tok

def tok_(spec: Spec, *args: Any, **kwargs: Any) -> Parser[Token, str]:
    return tok(spec.name, *args, **kwargs)

do 规则创建一个 can_proceed = True 的 Condition 对象，而 don't 规则创建一个 can_proceed = False 的 Condition 对象。

最后，我们使用 | 将这些单独的解析规则（do、dont 和 mul）组合到单个 expr 解析器中。 （或）运算符：

>>> from funcparserlib.lexer import Token
>>> number_parser = tok_(Spec.NUMBER)
>>> number_parser.parse([Token(Spec.NUMBER.name, '123'])
'123'

此 expr 解析器将尝试依次将输入与每个规则进行匹配，返回第一个成功匹配的结果。

我们的 expr 解析器可以处理完整的表达式，例如 mul(2,3)、do() 和 dont()。但是，输入还可能包含不属于这些结构化表达式的单独标记。为了处理这些，我们定义了一个名为 everything 的包罗万象的解析器：

>>> from funcparserlib.lexer import Token
>>> from ast import literal_eval
>>> number_parser = tok_(Spec.NUMBER) >> literal_eval
>>> number_parser.parse([Token(Spec.NUMBER.name, '123'])
123

这个解析器使用 | (或) 运算符来匹配 NUMBER、LPAREN、RPAREN 或 COMMA 类型的任何单个标记。它本质上是一种捕获不属于较大表达式的任何杂散标记的方法。

定义了所有组件后，我们现在可以定义完整程序的构成。程序由一个或多个“调用”组成，其中“调用”是可能被杂散标记包围的表达式。

调用解析器处理此结构：它匹配任意数量的杂散标记（许多（一切）），后跟单个表达式（expr），后跟任意数量的附加杂散标记。然后，operator.itemgetter(1) 函数从结果序列中提取匹配的表达式。

number = tok_(Spec.NUMBER) >> int

由程序解析器表示的完整程序由零个或多个调用组成，确保使用完成的解析器消耗整个输入。然后将解析结果转换为表达式元组。

from enum import Enum, auto

class Spec(Enum):
    OP = auto()
    NUMBER = auto()
    COMMA = auto()
    LPAREN = auto()
    RPAREN = auto()
    GIBBERISH = auto()

最后，我们将所有这些定义分组​​到一个解析函数中。该函数将标记元组作为输入并返回已解析表达式的元组。所有解析器都在函数体内定义，以防止污染全局命名空间，并且因为数字解析器依赖于 tok_ 函数。

from funcparserlib.lexer import TokenSpec

def TokenSpec_(spec: Spec, *args: Any, **kwargs: Any) -> TokenSpec:
    return TokenSpec(spec.name, *args, **kwargs)

解决难题

有了我们的解析器，解决第 1 部分就很简单了。我们需要找到所有乘法运算，执行乘法并对结果求和。我们首先定义一个处理 Mul 表达式的评估函数

from funcparserlib.lexer import make_tokenizer

def tokenize(input: str) -> tuple[Token, ...]:
    tokenizer = make_tokenizer(
        [
            TokenSpec_(
                Spec.OP, r"mul(?=\(\d{1,3},\d{1,3}\))|do(?=\(\))|don\'t(?=\(\))"
            ),
            TokenSpec_(Spec.NUMBER, r"\d{1,3}"),
            TokenSpec_(Spec.LPAREN, r"\("),
            TokenSpec_(Spec.RPAREN, r"\)"),
            TokenSpec_(Spec.COMMA, r","),
            TokenSpec_(Spec.GIBBERISH, r"[\s\S]"),
        ]
    )

    return tuple(
        token for token in tokenizer(input) if token.type != Spec.GIBBERISH.name
    )

为了解决第 1 部分，我们对输入进行标记和解析，然后使用我们刚刚定义的函数评估_skip_condition 来获得最终结果：

from funcparserlib.parser import tok

def tok_(spec: Spec, *args: Any, **kwargs: Any) -> Parser[Token, str]:
    return tok(spec.name, *args, **kwargs)

对于第 2 部分，如果遇到不条件，我们需要跳过计算 mul 操作。我们定义一个新的评估函数，evaluate_with_condition，来处理这个问题：

>>> from funcparserlib.lexer import Token
>>> number_parser = tok_(Spec.NUMBER)
>>> number_parser.parse([Token(Spec.NUMBER.name, '123'])
'123'

该函数使用reduce和自定义reducer函数来维护运行总和和布尔标志（条件）。当遇到条件表达式（do 或 don）时，条件标志会更新。仅当条件为 True 时，才会计算 Mul 表达式并将其添加到总和中。

上一次迭代

最初，我的解析方法涉及两个不同的过程。首先，我将对整个输入字符串进行标记，收集所有标记，无论其类型如何。然后，在一个单独的步骤中，我将专门执行第二次标记化和解析，以识别和处理 mul 操作。

>>> from funcparserlib.lexer import Token
>>> from ast import literal_eval
>>> number_parser = tok_(Spec.NUMBER) >> literal_eval
>>> number_parser.parse([Token(Spec.NUMBER.name, '123'])
123

改进的方法通过在一次传递中执行标记化和解析来消除这种冗余。我们现在有一个解析器可以处理所有标记类型，包括与 mul、do、dont 和其他单独标记相关的标记类型。

number = tok_(Spec.NUMBER) >> int

我们没有重新标记输入来查找 mul 操作，而是利用初始标记化过程中识别的标记类型。解析函数现在使用这些标记类型来直接构造适当的表达式对象（Mul、Condition 等）。这样就避免了对输入的冗余扫描，显着提高了效率。

本周“代码降临”的解析之旅就到此结束了。虽然这篇文章需要大量的时间投入，但重新审视和巩固我的词法分析和解析知识的过程使其成为一项值得的努力。这是一个有趣且富有洞察力的谜题，我渴望在未来几周内应对更复杂的挑战并分享我的经验。

一如既往，感谢您的阅读，下周我会再次写信。

以上是如何解析计算机代码，代码的出现 ay 3的详细内容。更多信息请关注PHP中文网其他相关文章！