编程语言实现模式入门：从词法分析到语法解析

实现一门语言，不一定要从复杂的编译器框架开始。许多小型工具都包含语言：配置文件里的表达式、模板中的条件、命令行过滤器、规则引擎中的判断式，乃至计算器输入。它们往往只支持有限的语法，却同样需要回答几个基本问题：输入里的字符如何组合成有意义的单元？这些单元如何构成合法结构？结构最终如何执行或转换？

本文以一个只支持加减乘除和括号的算术语言为例，介绍从词法分析到语法解析的实现模式。示例使用 Python 3 标准库，可保存为单个文件运行。它刻意保持小而完整，适合学习和改造；它不是通用表达式引擎，也不应被当成隔离恶意代码的安全沙箱。

一、从字符到结果：语言实现的基本流水线

一个常见的处理流程是：

输入校验：限制输入长度，拒绝空输入或不允许的字符。
词法分析：把字符流切分成数字、运算符、括号等记号，通常称为 token。
语法解析：检查 token 是否符合语法，并建立树形结构，或直接在解析过程中计算结果。
语义处理：检查语法正确但含义不合法的情况，例如除数为零、变量未定义或类型不匹配。
执行或转换：求值、生成字节码、构造查询，或产出其他目标格式。

小型计算器可以把解析和求值合并，代码较少；较大的语言通常会先生成抽象语法树（AST），再独立进行名称解析、类型检查和代码生成。把阶段分清的价值在于边界明确：词法分析负责识别记号，不负责判断整个表达式是否合法；解析器负责结构，不应靠字符串替换来猜测语义。

二、先定义语言，再动手写代码

本例语言支持：

整数和小数，例如 12、3.5、.25。
二元运算符 +、-、*、/。
一元正负号，例如 -3、+(2)。
括号和空白字符。

它不支持变量、函数、指数、隐式乘法或赋值。比如 2x、2 ** 3、max(1, 2) 都不是合法输入。明确限制有助于避免实现者和使用者对语言能力产生不同预期。

再把优先级写成语法规则：

expression = term (("+" | "-") term)*
term       = unary (("*" | "/") unary)*
unary      = ("+" | "-") unary | primary
primary    = NUMBER | "(" expression ")"

这组规则意味着乘除比加减优先，同一层的二元运算从左向右结合。因此 8 - 3 - 2 等价于 (8 - 3) - 2；括号则可以显式改变分组。语法规则不是注释，而是实现与测试的依据。

三、词法分析：识别记号，而不是解释整句话

词法分析器从左向右扫描字符，产出带类型和位置的 token。例如，输入 12 + .5 可以得到 NUMBER(12)、PLUS、NUMBER(.5)。保存字符位置后，遇到非法输入时就能指出错误附近，而不只是返回“表达式有问题”。

数字格式需要明确边界。本例允许 .5 和 1.25，但不把单独的 . 当作数字，也不支持指数记法。字母和其他字符会被拒绝，而不是跳过。若词法器忽略未知字符，输入 1 @ + 2 可能被错误地当成 1 + 2，这会让错误悄悄转成不同的计算结果。

四、递归下降：用函数对应语法层级

递归下降解析器是实现小型表达式语言的常见方式。上面的 expression、term、unary、primary 分别对应同名解析函数。每个函数消费符合当前规则的 token，再将结果交给更高层。

乘除放在 term 中，加减放在 expression 中，优先级自然来自调用关系，而非一段容易写错的运算符优先级判断。循环处理同一层的二元运算，则落实左结合规则。括号中的内容重新调用 expression，因此内部表达式可以完整使用同一套优先级规则。

下面是完整代码。保存为 mini_calc.py，运行 python mini_calc.py；也可以用 python mini_calc.py "2 + 3 * (4 - 1)" 传入表达式。

import sys
from dataclasses import dataclass


MAX_SOURCE_LENGTH = 4096
MAX_TOKENS = 2048
MAX_NESTING = 128
MAX_UNARY_SIGNS = 128


class CalcError(ValueError):
    """带有输入位置的词法或语法错误。"""


@dataclass(frozen=True)
class Token:
    kind: str
    text: str
    position: int


def tokenize(source):
    if len(source) > MAX_SOURCE_LENGTH:
        raise CalcError(
            f"输入超过 {MAX_SOURCE_LENGTH} 个字符"
        )

    tokens = []
    i = 0

    while i < len(source):
        ch = source[i]

        if ch.isspace():
            i += 1
            continue

        if ch.isdigit() or ch == ".":
            start = i

            if ch == ".":
                i += 1
                if i >= len(source) or not source[i].isdigit():
                    raise CalcError(f"位置 {start}: 小数点后需要数字")
                while i < len(source) and source[i].isdigit():
                    i += 1
            else:
                while i < len(source) and source[i].isdigit():
                    i += 1
                if i < len(source) and source[i] == ".":
                    i += 1
                    if i >= len(source) or not source[i].isdigit():
                        raise CalcError(f"位置 {start}: 小数点后需要数字")
                    while i < len(source) and source[i].isdigit():
                        i += 1

            tokens.append(Token("NUMBER", source[start:i], start))

        elif ch in "+-*/()":
            kinds = {
                "+": "PLUS",
                "-": "MINUS",
                "*": "STAR",
                "/": "SLASH",
                "(": "LPAREN",
                ")": "RPAREN",
            }
            tokens.append(Token(kinds[ch], ch, i))
            i += 1

        else:
            raise CalcError(f"位置 {i}: 不允许的字符 {ch!r}")

        if len(tokens) > MAX_TOKENS:
            raise CalcError(f"记号数量超过 {MAX_TOKENS}")

    tokens.append(Token("EOF", "", len(source)))
    return tokens


class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.index = 0
        self.nesting = 0
        self.unary_signs = 0

    def current(self):
        return self.tokens[self.index]

    def take(self, kind):
        token = self.current()
        if token.kind != kind:
            raise CalcError(
                f"位置 {token.position}: 期望 {kind}，实际为 "
                f"{token.text!r}" if token.kind != "EOF"
                else f"位置 {token.position}: 期望 {kind}，但输入已结束"
            )
        self.index += 1
        return token

    def parse(self):
        value = self.expression()
        token = self.current()
        if token.kind != "EOF":
            raise CalcError(
                f"位置 {token.position}: 多余的记号 {token.text!r}"
            )
        return value

    def expression(self):
        value = self.term()

        while self.current().kind in ("PLUS", "MINUS"):
            operator = self.current()
            self.index += 1
            right = self.term()
            if operator.kind == "PLUS":
                value += right
            else:
                value -= right

        return value

    def term(self):
        value = self.unary()

        while self.current().kind in ("STAR", "SLASH"):
            operator = self.current()
            self.index += 1
            right = self.unary()

            if operator.kind == "STAR":
                value *= right
            else:
                if right == 0:
                    raise CalcError(
                        f"位置 {operator.position}: 除数不能为零"
                    )
                value /= right

        return value

    def unary(self):
        token = self.current()

        if token.kind in ("PLUS", "MINUS"):
            self.unary_signs += 1
            if self.unary_signs > MAX_UNARY_SIGNS:
                raise CalcError("一元正负号嵌套过深")

            self.index += 1
            value = self.unary()
            self.unary_signs -= 1

            return value if token.kind == "PLUS" else -value

        self.unary_signs = 0
        return self.primary()

    def primary(self):
        token = self.current()

        if token.kind == "NUMBER":
            self.index += 1
            return float(token.text)

        if token.kind == "LPAREN":
            if self.nesting >= MAX_NESTING:
                raise CalcError("括号嵌套过深")

            self.index += 1
            self.nesting += 1
            value = self.expression()
            self.nesting -= 1
            self.take("RPAREN")
            return value

        if token.kind == "EOF":
            raise CalcError(f"位置 {token.position}: 缺少操作数")

        raise CalcError(
            f"位置 {token.position}: 此处需要数字或左括号"
        )


def evaluate(source):
    return Parser(tokenize(source)).parse()


def main():
    source = " ".join(sys.argv[1:]) if len(sys.argv) > 1 else input("表达式> ")

    try:
        print(evaluate(source))
    except CalcError as exc:
        print(f"错误：{exc}", file=sys.stderr)
        raise SystemExit(2)


if __name__ == "__main__":
    main()

五、阅读实现时要留意的边界

1. 解析成功不代表输入已全部消费

解析器在读到一个完整表达式后，还要确认下一个 token 是文件结束标记 EOF。如果漏掉这一步，1 + 2 3 可能只算出前半段，尾部内容被无声忽略。本例的 parse 方法会把这种多余 token 报告为错误。

2. 负数通常是运算符加操作数

词法器将 -3 切成减号和数字，解析器再由 unary 将它组合成负数。这种做法让一元负号和二元减法共用同一个字符，同时将二者的语法位置区分开。类似地，2 * -3 合法，但 2 3 因缺少运算符而不合法。

3. 错误应在发现处报告

词法错误与语法错误最好包含字符位置。除以零则属于求值阶段的语义错误：1 / 0 在词法和语法上都合法，但不能按本例定义得到正常结果。实际语言可以设计更丰富的错误类型，例如区分词法错误、解析错误和运行时错误；关键是不要把所有问题都吞掉，再返回一个看似有效的默认值。

4. 数值表示也会影响结果

示例把输入转换为 Python 的 float，所以会遇到二进制浮点数的精度特性。例如某些十进制小数无法精确表示，结果可能显示为近似值。代码也没有规定溢出、有效位数或金额舍入规则。若用于金融金额，应明确使用定点数或十进制定点表示，并定义舍入策略；不能仅凭“接受小数”就假定它适合货币计算。

六、参数限制与安全用途：限制资源，不等于沙箱

代码设置了源文本长度、token 数量、括号嵌套深度和一元符号连续递归的上限。这些限制是为了控制本实现可能消耗的资源，并让过长或过深的输入以明确错误结束。它们不是通用的 Python 运行时安全承诺，也不意味着任意规模的输入、并发请求或所有部署环境都已得到保护。

本例只解析自己定义的四则运算，没有把用户输入交给 Python 的 eval 或 exec 执行。这个选择缩小了表达能力，也减少了将任意 Python 代码当作表达式运行的风险。但“不调用 eval”不等于自动构成安全沙箱：解析器仍需审视资源消耗、数字范围、错误处理和调用频率。生产服务还应结合请求体大小限制、超时、并发控制和监控等外围措施。

本示例未加入数字位数上限，也没有定义溢出检测。在当前语法下，词法器产生的数值最终交给 Python 浮点数处理；在面向不可信输入的服务中，应根据需求增加数字长度与取值范围约束，并测试极端输入。资源限制要根据实际部署与产品要求选择，不能把示例中的常量视为适用于所有项目的标准值。

另一个容易忽视的点是实现本身。示例在括号和一元符号路径上设定了嵌套上限，但它仍是教学用小程序，并未覆盖所有运行环境下的所有资源攻击面。对外提供解析服务时，还应以部署环境进行压力测试；必要时将复杂计算放在有明确 CPU 和内存限制的独立执行环境中。自定义解析器能限制“允许什么语法”，但不自动替代进程隔离、权限控制或服务级防护。

七、从计算器扩展到 AST

直接在解析函数里计算，适合一次性求值；如果要支持变量、函数、格式化、优化或多次执行，建议改为先构造 AST。例如 1 + 2 * 3 可以表示为“加法节点，左侧为 1，右侧为乘法节点 2 和 3”。之后再由独立的解释器遍历树并计算。

AST 的主要好处是把“输入长什么样”和“如何执行”分开。解析器可以只负责验证结构；求值器可以集中处理除零、变量查找和类型规则；未来若要输出其他目标，也不必在语法函数里塞入更多副作用。不过 AST 也增加了节点类型、构造和遍历代码。对于语法很小、只求一次值的场景，直接求值通常更简单。

扩展语言时，优先更新语法定义，再添加对应 token、解析规则和测试。例如增加取模运算，需先决定它的优先级、左结合还是右结合，以及负数参与时的规则。增加变量则不仅是接受标识符，还需要定义变量作用域、名称查找失败的错误，以及变量值的类型。先写清规则，往往比直接增加一个分支更省时间。

八、用边界用例验证，而不只测正常输入

最基本的手工测试可以直接运行：

python mini_calc.py "2 + 3 * (4 - 1)"
# 11.0

python mini_calc.py "-2 * 3 + .5"
# -5.5

python mini_calc.py "8 - 3 - 2"
# 3.0

还应验证非法输入确实失败：

python mini_calc.py "1 +"
python mini_calc.py "(1 + 2"
python mini_calc.py "1 @ 2"
python mini_calc.py "1 / 0"
python mini_calc.py "2 3"

测试的重点不只是结果对不对，还包括错误发生在哪个阶段、是否有位置提示、有没有忽略尾部内容。编写自动化测试时，可以将每个输入及预期结果或预期异常整理成用例表。再针对长度上限、过深括号、过多一元符号等边界分别测试。边界测试能检验实现是否遵守已声明的限制，但并不能证明程序对所有输入都安全。

总结

从词法分析到语法解析，是构建小型语言最常见的一条入门路径：先明确语法和边界，再把字符切成 token，随后用解析器恢复结构，最后执行或转换。递归下降尤其适合表达式、配置片段和简单规则，因为代码结构能直接映射到语法层级。

实现时要特别注意未知字符、运算符优先级、结合性、未消费的尾部输入、错误位置和资源上限。对于只需有限表达能力的场景，自定义解析器通常比执行宿主语言表达式更容易收紧语法；但安全性仍需结合数值范围、资源控制和部署环境判断。先做一个边界清楚的小语言，再按需求扩展，往往比一开始追求“支持所有表达式”更可靠。

站长资讯 # 编程语言实现模式

文章版权归作者所有，未经允许请勿转载。

了解10月19日出生的人属于哪个星座：深度解析天秤座的特点与影响 (了解10月1日国庆节的会议流程)

编程语言实现模式入门：从词法分析到语法解析

编程语言实现模式入门：从词法分析到语法解析

一、从字符到结果：语言实现的基本流水线

二、先定义语言，再动手写代码

三、词法分析：识别记号，而不是解释整句话

四、递归下降：用函数对应语法层级

五、阅读实现时要留意的边界

1. 解析成功不代表输入已全部消费

2. 负数通常是运算符加操作数

3. 错误应在发现处报告

4. 数值表示也会影响结果

六、参数限制与安全用途：限制资源，不等于沙箱

七、从计算器扩展到 AST

八、用边界用例验证，而不只测正常输入

总结

编程零基础学 Python：从安装环境到写出第一个小程序

C语言程序下载后怎么打开？新手编译运行步骤

相关文章

了解10月19日出生的人属于哪个星座：深度解析天秤座的特点与影响 (了解10月1日国庆节的会议流程)

春色满城映照无边花海，探秘春城无处不飞花的诗意境界 (春色满园的下一句是什么)

增强创造力：AIGC工具激发了灵感冒官，为新的创意和想法提供了灵感。(增强创造力英语)

全面掌握交通肇事司法解释：适用范围、认定标准和责任划分 (健全交通体系)

热门网址

网址

昵图网

字幕库

酷站剪报

日本传统色

大表哥影视

最新资讯

编程语言实现模式入门：从词法分析到语法解析

编程语言实现模式入门：从词法分析到语法解析

一、从字符到结果：语言实现的基本流水线

二、先定义语言，再动手写代码

三、词法分析：识别记号，而不是解释整句话

四、递归下降：用函数对应语法层级

五、阅读实现时要留意的边界

1. 解析成功不代表输入已全部消费

2. 负数通常是运算符加操作数

3. 错误应在发现处报告

4. 数值表示也会影响结果

六、参数限制与安全用途：限制资源，不等于沙箱

七、从计算器扩展到 AST

八、用边界用例验证，而不只测正常输入

总结

编程零基础学 Python：从安装环境到写出第一个小程序

C语言程序下载后怎么打开？新手编译运行步骤

相关文章

了解10月19日出生的人属于哪个星座：深度解析天秤座的特点与影响 (了解10月1日国庆节的会议流程)

春色满城映照无边花海，探秘春城无处不飞花的诗意境界 (春色满园的下一句是什么)

增强创造力：AIGC工具激发了灵感冒官，为新的创意和想法提供了灵感。(增强创造力英语)

全面掌握交通肇事司法解释：适用范围、认定标准和责任划分 (健全交通体系)

热门网址

网址

昵图网

字幕库

酷站剪报

日本传统色

大表哥影视

最新资讯

标签云