戴老师的博客 - 解释器/编译器
type: channel
link: https://www.tushu.info/tag/%E8%A7%A3%E9%87%8A%E5%99%A8-%E7%BC%96%E8%AF%91%E5%99%A8/
items: 如何编写一个高效的Java表达式求值程序
items: 使用 Antlr 开发领域语言 - 开发一个完整的应用
items: Antlr4 简介
items: 一种可扩展的表达式解析及计算方法
items: java公式解析器学习与开发（2）——前缀表达式
items: 快速精确的对数学表达式求值
items: 从零开始实现一个玩具版浏览器渲染引擎
items: java公式解析器学习与开发（1）

如何编写一个高效的Java表达式求值程序
type: item
date: 2026-07-07T08:36:33+00:00
description: 如何编写一个高效的 Java 表达式求值程序虽然这个标题略显夸张，但我确实完成了这样一个目标（关于是否完全相信基准测试结果，那是另一个话题）。上周，我一直在寻找一个小型、实用的数学表达式计算类库。偶然间，我在 StackOverflow 上看到了一个帖子，里面推荐的库（Expr）确实很快，且基本拥有我需要的所有特性。但不幸的是，它不支持限制变量范围（在虚拟机里面，所有变量都位于一个全局命名空间）。于是，我做了一件通常不建议做的事情：重新发明轮子，自己编写一个解析器和执行器。那是一个下雨的周六，我想到用一个小型递归向下的解析器，构建一个简化版的、可计算表达式的抽象语法树（AST）。抽象语法树配合一个小型变量管理助手，看起来并没有什么大不了，但它并非无用。我做出了一个初步的实现，执行速度特别快。在进行了一些测试后，结果更让我充满信心：它执行的所有运算都正确无误。我想与前面提到的类库相比，确认这个计算器到底有多快。在没有对每个内部循环和其他执行细节进行优化前，我并不报太大期望，毕竟有不少类库是成熟的商业软件。但当我看到测试结果时，我感到很惊讶。下面的清单展示了一个小的基准测试，使用不同的类库计算同一个表达式。parsii 是我编写的库，测试时用的是最终版本。这个版本做了一些简化，比如预先计算了常量表达式，但没有使用任何“黑魔法”，比如生成字节码或者其他类似的操作。性能基准测试在性能评估中，用例是执行表达式 2 + (7 – 5.html) * 3.14159 * x^(12-10.html) + sin(-3.141)。其中变量 x 的取值范围测试参考了 Expr 的相关设定，迭代次数为 0 到 1,000,000。测试时先运行 10 次对 JIT 进行预热，然后再运行 15 次计算平均时间：类库平均耗时 (ms.html)PARSII28.3EXPR37.2MathEval7748.5JEP647.0MESP220.8JFEP274.3现在我敢肯定，每一个类库都有自己的优势，所以不能直接对它们进行绝对比较。尽管如此，令人吃惊的是一个简单实现的程序可以拥有这么好的表现。核心架构如果读者对于编译器的原理不太了解，下面是一个关于编译器运行机制的简单介绍。词法分析 (Tokenizer.html)同其他的解析器或者编译器一样，parsii 使用了传统的 分词器。它将字符流转化成词法单元流（Token Stream）。例如 "4 + 38"，也就是字符数组 '4', ' ', '+', ' ', '3', ' ', ' ', '8' 被转化成：4 (整数.html)+ (符号.html)38 (整数.html)分词器读取一个字符，接着判断是一个什么类型的词法单元，然后再读入属于该词法单元的所有字符。每一个词法单元都有类型、文本内容，并且知道起始位置（行号和字符偏移）。网上有很多深入的教程，所以在这里就不详细讲解了。你可以看一下源代码，但正如我说的，它只是一个初步的实现。语法解析 (Parser.html)解析器 用来将传入的词法单元流翻译成可以执行的 AST（抽象语法树）。它是一个传统的自上而下递归解析器（Recursive Descent Parser）。这是实现解析器最简单的方式，完全手写，没有利用工具生成。像这样的解析器只拥有一个包含所有语法规则的方法。错误处理同样，关于这种类型的解析器有很多教程，但是如何恰当地处理错误却缺少相关的示例。除了解析表达式的速度和正确性外，优秀的错误处理机制是一个优秀解析器的最核心因素之一。正如在源代码里看到的那样，实现起来并不是太困难。因为解析器在解析表达式的过程中从来不会立即抛出异常，所有的错误都被收集起来，并且继续尽可能进行解析。即使在第一个错误发生以后已经不能成功解析生成 AST，重要的是要能够尽可能继续解析，因为在一次的执行中我们需要报告尽可能多的错误。这样的方法也同样用在了分词器报告上，比如报告非法格式的词法单元（例如带有两个小数点的浮点数），将它们放到同样的错误列表中。表达式执行执行一个解析完成后的抽象语法树非常简单。每一个抽象语法树节点都包含一个计算方法，调用从根节点开始，父节点会调用子节点的该方法。这里的执行结果就是表达式的结果。一个简单的例子就是 算数运算，包含了 +、-、* 等操作。性能优化为了减少执行时间，程序里运用了 3 种优化措施：常量折叠 (Constant Folding.html)在完成解析 AST 后，在根节点上进行一个简化的方法调用，并且会扩散到每一个子节点。每一个节点判断自己的子表达式中是否有简化的表达形式。例如：对于 算数运算，我们检查两个操作数是不是都是常量（数字）。如果是数字，我们将计算表达式并且返回一个包含计算结果的常量。对于函数，如果所有的参数都是常量的话…

使用 Antlr 开发领域语言 - 开发一个完整的应用
type: item
date: 2026-07-07T08:36:07+00:00
description: 一个完整的应用在使用 ANTLR 开发领域语言的 前一篇文章 中，我们简要介绍了 ANTLR 的一些特性，并以算术表达式为例说明了其在词法分析、语法分析、解释和编译等方面的用法。本文中，我们将共同开发一个更为复杂的领域语言。在确定语言的运算能力之后，首先使用 ANTLR 定义语言的文法，实现词法分析和语法分析，并生成对应的抽象语法树（Abstract Syntax Tree, AST）；之后基于树分析器开发一个类型检查器，检查语言的类型是否合法；然后基于树分析器开发一个代码生成器，将语言编译为一种中间代码。图 1 详细描述了这一工作过程。图 1. 工作流程（查看大图）上述四个步骤与 ANTLR 紧密结合，每一步都用到了 ANTLR 的相关技术。在完成中间代码的生成后，工作并没有结束。最后我们将实现一个虚拟机，该虚拟机使用堆栈来操纵数据，对之前产生的中间代码解释执行，完成最终的运算。我们将该虚拟机命名为抽象堆栈机。语言定义首先，我们需要确定领域语言应该具备哪些运算能力。清单 1 和清单 2 给出了两个目标语言的例子。清单 1. 领域语言示例一max(a, b.html){ if(a>b.html) return a ; return b; } main(){ return max(x, y.html); }清单 2. 领域语言示例二sum(a.html) { sum = 0 ; while(a>0.html) { sum = sum + a; a = a - 1; } return sum ; } main(){ return sum(x.html)/x; }示例中的语言源自日常工作中的一个真实应用，主要用于对财务金额数据的加工处理。这里需要对语言的 IO 做一个简单的说明：在真实应用中，main 函数中变量的初始值都是从数据库中根据变量的名字查询得到的，main 函数的返回值（计算结果）被存储于数据库中；在本文中为了方便演示，给 main 函数中的变量都赋予随机数，计算结果直接输出到控制台。我们的领域语言支持用户自定义函数，函数又由多条语句构成。语句包括条件语句、循环语句、赋值语句、表达式运算语句和函数调用语句等。表达式中目前主要支持 13 类运算，分别为 4 类算术运算（+、-、*、/）、6 类关系运算（>、>=、<、<=、==、!=）和 3 类逻辑运算（||、&&、!）。支持的数据类型有整数型、实数型和布尔型三种。目前有以下 7 个关键字：if、else、unless、do、for、while、return。对语言的细节不做过多的说明，下一节通过文法定义对语言做进一步描述。文法基础LL 文法任何一个 LL 文法识别器都不支持左递归文法，无论是直接左递归还是间接左递归，ANTLR 也不例外。如果定义了非 LL 文法，必须对其改写。消除左递归是 LL 文法处理常用的技术，下面是一个消除左递归的例子：A -> Aa | b; （1）式中大写字母表示文法规则，小写字母表示词法符号。规则 A 的产生式有两个，分别是 Aa 和 b。第一个产生式 Aa，最左端包含了 A，这是一个直接左递归，必须对其改写。改写之后，A 产生 bB，而 B 产生 aB 和空集。A -> bB; （2） B -> aB | ; （3）式子（3）B 产生 aB 是一个尾递归，可以把这个尾递归进一步改写。改写之后，B 产生 0 个或多个 a。B -> (a.html)*; （4）将（4）代入（2），最终原文法（1）被改写成如下形式：A -> b (a.html)*; （5）算符的结合性在定义语言时，有些算符是左结合的，比如算术运算符 +，a + b + c 等价于 (a + b.html) + c；有些算符是右结合的，比如赋值运算符 =，a = b = c 等价于 a = (b = c.html)。在 LL 识别器中，左结合算符通过指定重复匹配进行定义，如清单 3 所示：清单 3. 左结合算符的文法expr : atom (('+' |'-' .html) atom )* ;右结合文法通过尾递归文法定义，如清单 4 所示：清单 4. 右结合算符的文法expr : id '=' expr;算符的优先级在 LL 文法识别器中，算符的优先级要通过文法的嵌套定义来体现。优先级低的算符要优先声明，相同优先级的算符可以在同一个规则中描述。比如加减运算的优先级比乘除运算的优先级低，加减法要先于乘除法定义，文法定义方式如清单 5 所示：清单 5. 考虑算符优先级的文法additiveExpr : multExpr (('+' |'-' .html) multExpr )* ; multExpr : atom (('*' |'/' .html) atom)* ;文法定义使用 AN…

Antlr4 简介
type: item
date: 2026-07-07T08:35:30+00:00
description: 编者注：本文为历史博文归档；涉及 JDK、框架与工具链版本请以当前官方文档为准。引用外链图片可能失效，阅读时请注意时效性。简介ANTLR 4 是一款强大的语法生成器工具，可用于读取、处理、执行和翻译结构化的文本或二进制文件。它是目前 Java 生态中使用最为广泛的语法生成器工具之一。众多知名项目与企业均采用了 ANTLR 进行语法分析，例如：Twitter 搜索：每天处理超过 20 亿次查询。Hadoop 生态系统：Hive、Pig 等数据仓库和分析系统所使用的语言。Lex Machina：用于分析法律文本。Oracle：SQL 开发者 IDE 和迁移工具。NetBeans IDE：用于解析 C++ 代码。Hibernate：对象 - 关系映射框架（ORM）用于处理 HQL 语言。ANTLR 4 提供了大量的 官方 grammar 示例，涵盖了各种常见语言，资源非常全面，提供了丰富的学习教材。本文将通过一个简单的计算器示例，介绍 ANTLR 4 的基本用法。这个例子在很多资料中都作为入门示例，堪称 ANTLR 4 的 "Hello World"。基本概念语法分析器（Parser）是用来识别语言的程序，通常包含两个核心部分：词法分析器（Lexer） 和 语法分析器（Parser）。词法分析阶段：主要解决关键词以及各种标识符的识别，例如 INT、ID 等。语法分析阶段：基于词法分析的结果，构造一棵语法分析树（Parse Tree）。大致的流程如下图所示（参考文档 2）：因此，为了让词法分析和语法分析能够正常工作，在使用 ANTLR 4 的时候，需要定义语法（Grammar），这部分使用的是 ANTLR 元语言。元语言首先，要了解 ANTLR 4 本身定义 Grammar 的语法，相对比较简单。我们以计算器的例子为例，简单讲解其中的概念。// file: Calculator.g4 grammar Calculator; line : expr EOF ; expr : '(' expr '.html)' # parenExpr | expr ('*'|'/'.html) expr # multOrDiv | expr ('+'|'-'.html) expr # addOrSubstract | FLOAT # float ; WS : [ \t\n\r]+ -> skip; FLOAT : DIGIT+ '.' DIGIT* EXPONET? | '.' DIGIT+ EXPONET? | DIGIT+ EXPONET? ; fragment DIGIT : '0'..'9' ; fragment EXPONET : ('e'|'E'.html) ('+'|'-'.html)? DIGIT+ ;第一行：定义了 Grammar 的名字，名字需要与文件名对应。语法规则：接下来的 line 和 expr 就是定义的语法，会使用到下方定义的词法。注意 # 后面的名字（如 # parenExpr），是可以在后续访问和处理的时候使用的标签（Label）。一个语法有多种规则的时候可以使用 | 来进行配置。优先级：在 expr 这行，我们注意到四则运算分为了两个非常相似的语句，这样做的原因是为了实现优先级，乘除的优先级高于加减。空白字符：WS 定义了空白字符，后面的 skip 是一个特殊的标记，表示空白字符会被忽略。浮点数：FLOAT 是定义的浮点数，包含了整数，与编程语言中的浮点数略有不同，更类似 Number 的定义。片段规则：最后的 fragment 定义了两个在词法定义中使用到的符号，它们不会被单独生成 Token，仅供其他规则引用。在语法定义的文件中，大部分的地方使用了正则表达式。生成代码配置 ANTLR 4 工具，先从官网下载 ANTLR 4 的 Jar 包，点击 下载地址 进行下载。alias antlr4="java -jar /path/to/antlr-4.5-complete.jar"通过命令行工具可以生成 Lexer、Parser、Visitor、Listener 等文件。注意：Visitor 是默认不生成的，需要带上参数 -visitor。$ antlr4 -visitor Calculator.g4 # 生成文件如下： Calculator.interp CalculatorBaseListener.java CalculatorLexer.interp CalculatorLexer.tokens CalculatorParser.java Calculator.tokens CalculatorBaseVisitor.java CalculatorLexer.java CalculatorListener.java…

一种可扩展的表达式解析及计算方法
type: item
date: 2026-07-07T08:30:13+00:00
description: 一种可扩展的表达式解析及计算方法概述在应用软件开发领域，表达式计算有着非常广泛的应用。例如，在报表开发中，经常为用户提供公式输入功能，从而实现更灵活的报表汇总；在工作流应用软件中，经常利用逻辑条件进行动态配置，从而提供更加灵活的流程配置；另外，在某些 UI 开发中，需要通过某个属性的表达式计算结果来动态控制 UI 组件的显示。所有这些应用都可以归结为一个通用模型，即表达式的解析以及计算。本文旨在提供一种可扩展的表达式解析及其计算方法。表达式解析的一般条件及因素本文所讲的表达式是一种以一定的运算规则组合所表达的字符串；另外，通过解析表达式字符串并以其代表的运算规则可以得到一个结果。表达式解析一般需要满足下列条件：支持的操作符集合操作符的优先级操作符所代表的操作规则集合支持的分隔符集合以及分隔符所代表的意义支持的数据类型集合语法约束，如命名规则、分隔符所代表的语法规则等表达式解析除了以上必须满足的条件之外，在有些表达式环境中，可能还支持函数、变量。结合本文所要解决的问题，如下列出可选的条件：支持的内部函数集合支持的内部全局变量支持函数定制支持自定义变量支持函数以及操作符重载以上最后三个可选条件，是一个表达式解析引擎的可扩展支持需要满足的条件。编译原理简述一般的编译过程主要包括词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成，如下图所示。其中，词法分析主要任务是输入源程序，对构成源程序的字符进行扫描和分解，识别出一个一个的单词。单词是语言中具有独立意义的最基本结构。一般这些单词包括程序语言所支持的保留字、数据类型、操作符、分隔符以及程序定义的标识符、常量等。语法分析的主要任务是在词法分析的基础上，根据语言的语法规则把单词序列组合成各类语法单位（一般表示成语法树）。语义分析的主要任务是进一步分析语法结构正确的程序是否符合源程序的上下文约束、运算相容性等语义约束规则。图 1. 编译一般过程上述只是非常简要地介绍了一般的编译原理知识，详细知识需要参考编译原理相关的书籍和文档。对于本文所讲的表达式解析，笔者认为其与程序编译具有本质上的相似，只是在问题的复杂性上会简单很多。表达式解析同样需要首先把输入的表达式字符串分解成一个一个的单词，然后把单词序列组合成语法单位，最后依据表达式的语言环境所定义的语义约束对这些语法单位进行分析计算。因此，我们可以将有选择的程序编译基本方法运用到表达式解析上。中缀表达式、前缀表达式与后缀表达式前缀表达式（又叫波兰式）是一种不含括号的 表达式，并且将 运算符 放在 操作数 前面的表达式。对于一个前缀表达式的求值而言，所有的计算按运算符出现的顺序，严格从左向右进行。后缀表达式（又叫逆波兰式）也是一种不含括号的 表达式，并且 运算符 放在操作数的后面。对于一个后缀表达式的求值而言，所有的计算按运算符出现的顺序，严格从左向右进行。中缀表达式是一个通用的算术或逻辑公式表示方法，操作符是以中缀形式处于操作数的中间。中缀表达式不容易被计算机解析，但它符合人们的普遍用法。与前缀或后缀记法不同的是，中缀记法中括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来，用于指示运算的次序。前缀表达式和后缀表达式是一种十分有用的表达式，它可以依靠简单的操作就能得到运算结果的表达式。通常解析程序一般都会将中缀表达式转换为前缀表达式或后缀表达式，方便表达式计算。表达式树前面讲过，表达式是一种以一定的运算规则组合所表达的字符串。每一个表达式的基本组成单位都是由一个操作符和操作数组成的操作单位，操作数可以是一个或者多个。所以一个表达式基本操作单位可以表示为一棵树，下图所示为一个 N 元操作符的树表示，该操作符代表的运算需要 N 个操作数：图 2. N 元操作符的树表示每个基本操作单位可以表示为一棵树，每个操作单位的运算结果为其它操作符的一个操作数，从而一个含有多个操作符的表达式可以表示成一棵更大的树，其每一棵子树皆为一个子表达式。如表达式 a*b+c/d 可以表示为：图 3. 表达式 a*b+c/d 的树表示从编译原理的知识可以得出这样一个结论：一个表达式可能推导出多棵树，呈现出二义性。因此，需要通过对表达式的语言环境增加语义约束规则，消除二义性，保证从表达式只能推导出唯一的表达式树。通常的语义约束规则包括设定操作符的优先级、括号的使用等。表达式解析引擎的基本结构设计图 4. 解析引擎的基本结构设计查看大图如 图 4 所示，展示了一个表达式解析引擎的基本结构设计。整个表达式解析引擎内部结构主要包括：表达式解析引擎的语言环境定义、操作符处理器管理、表管理器、表达式解析器、表达式校验器、表达式解析异常定义等。本文后续部分将详细解释。表达式解析引擎实现说明定义表达式解析引擎的语言环境对于表达式解析，首先必须定义表达式所存在的…

java公式解析器学习与开发（2）——前缀表达式
type: item
date: 2026-07-07T08:28:31+00:00
description: 1 释义前缀表达式即 前序表达式。它是一种不含括号的 算术表达式，特点是将 运算符 写在前面，操作数 写在后面。为纪念其发明者波兰数学家 Jan Lukasiewicz，也称为“波兰式”。例如，- 1 + 2 3 等价于 1-(2+3.html)。2 求值方法对于前缀表达式的求值，需遵循从右至左扫描表达式的原则：从右边第一个字符开始判断。如果当前字符是数字，则一直记录到数字串末尾。如果是 运算符，则将右边离得最近的两个“数字串”作相应运算，以此作为一个新的“数字串”并记录下来。一直扫描到表达式的最左端，最后运算的值即为表达式的值。示例： 前缀表达式 - 1 + 2 3 的求值过程：扫描到 3 时，记录数字串 3。扫描到 2 时，记录数字串 2。扫描到 + 时，将 + 右移作为相邻两数字串的 运算符，记为 2+3，结果为 5，记录新数字串 5。继续向左扫描，扫描到 1 时，记录数字串 1。扫描到 - 时，将 - 右移作为相邻两数字串的运算符，记为 1-5，结果为 -4。所以表达式的值为 -4。3 公式用法前缀表达式是一种十分有用的表达式，它将中缀表达式转换为可以依靠简单操作就能得到运算结果的表达式。例如，(a+b.html)*(c+d.html) 转换为 *,+,a,b,+,c,d。优势： 只用两种简单的操作（入栈和 出栈）就可以解决任何中缀表达式的运算。运算方式：如果当前字符（或字符串）为数字或 变量，则压入栈内。如果是 运算符，则将栈顶两个元素弹出栈外并作相应运算，再将结果压入栈内。当前缀表达式扫描结束时，栈里的就是中缀表达式运算的最终结果。4 相关例子a+b ---> +,a,ba+(b-c.html) ---> +,a,-,b,ca+(b-c.html)*d ---> +,a,*,-,b,c,da=1+3 ---> =,a,+,1,35 转换算法将中缀表达式转换为前缀表达式的算法步骤如下：构造栈：首先构造一个运算符栈（也可放置括号），运算符（以括号分界点）在栈内遵循越往栈顶优先级不降低的原则进行排列。扫描表达式：从右至左扫描中缀表达式，从右边第一个字符开始判断：数字：如果当前 字符 是数字，则分析到数字串的结尾并将数字串直接输出。运算符：如果是运算符，则比较优先级。如果当前运算符的优先级大于等于栈顶运算符的优先级（当栈顶是括号时，直接入栈），则将运算符直接入栈。否则，将栈顶运算符 出栈 并输出，直到当前运算符的优先级大于等于栈顶运算符的优先级（当栈顶是括号时，直接入栈），再将当前运算符入栈。括号：如果是括号，则根据括号的方向进行处理。如果是右括号 )，则直接入栈。如果是左括号 (，则遇左括号前将所有的运算符全部 出栈 并输出，遇左括号后将左右的两括号一起删除。结束处理：重复上述操作直至扫描结束，将栈内剩余运算符全部 出栈 并输出，再逆缀输出字符串。中缀表达式也就转换为前缀表达式了。6 实例分析将中缀表达式 1+((2+3.html)*4)-5 转换为前缀表达式。中缀表达式前缀表达式（栈顶）运算符栈（栈尾）说明55空5，是数字串直接输出-5--，栈内无运算符，直接入栈)5-))，直接入栈45 4-)4，是数字串直接输出*5 4-)**，栈顶是括号，直接入栈)5 4-)*))，直接入栈35 4 3-)*)3，是数字串直接输出+5 4 3-)*)++，栈顶是括号，直接入栈25 4 3 2-)*)+2，是数字串直接输出(5 4 3 2+-.html)*(，参考①(5 4 3 2+*-(，参考①+5 4 3 2+*-++，优先级大于等于栈顶运算符，直接入栈15 4 3 2+*1-+1，是数字串直接输出空5 4 3 2+*1+-空扫描结束，将栈内剩余运算符全部出栈并输出空- + 1 * + 2 3 4 5空逆缀输出字符串7 运算符优先级)：直接入栈(：遇 .html) 前，将运算符全部出栈并输出；遇 ) 后，将两括号一起删除①+、-：优先级 1*、/、%：优先级 2^：优先级 3

快速精确的对数学表达式求值
type: item
date: 2026-07-07T08:27:01+00:00
description: 简介还记得在您的第一台科学计算器上使用逆波兰表示法（RPN）时的挣扎吗？W3Eval 并非旨在让您信赖的 HP-41 计算器更易用，正如它的名称所暗示，它是一个仅运行于 Web 的表达式求值程序。但它的确提供了一种方法——一种人类更易于遵循的、对表达式一步一步的求值方式。W3Eval 的方法与传统计算器不同，却和人类的计算方式一致。当您用传统的计算器计算时，每输入一个新数，前一个数就看不到了。如果在输入一个长表达式中出了错，就得全部重来。有了 W3Eval，您就能看到参与计算的所有东西，还能轻松地编辑表达式。它独特的能力（一步一步地对表达式求值）非常容易实现，因为用户能看到求值的每一步，包括临时结果。本文将让您从头至尾认识 W3Eval 功能性的要点；您将看到一些用于表达式求值的代码。不过，我们还是先看看表达式求值的经典算法，这样您就会明白 W3Eval 方法的差异究竟有多少。表达式求值的经典算法编写代码对算术表达式求值的经典方法由 Donald Knuth 描述于 1962 年（请参阅 参考资料）。Knuth 将此概括为三个步骤：对中缀表达式进行语法分析中缀表达式到后缀表达式的转换对后缀表达式求值注意到我们谈到的这个经典算法有些简化：算术表达式只包含操作数、二元操作符和一种括号。此外，对于每个操作数和操作符，只用单个字符表示，使语法分析直观。表达式表示法算术表达式中最常见的表示法形式有 中缀、前缀 和 后缀 表示法。中缀表示法是书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。中缀表示法 中缀表示法是算术表达式的常规表示法。称它为 中缀 表示法是因为每个操作符都位于其操作数的中间，这种表示法只适用于操作符恰好对应两个操作数的时候（在操作符是二元操作符如加、减、乘、除以及取模的情况下）。对以中缀表示法书写的表达式进行语法分析时，需要用括号和优先规则排除多义性。Syntax: operand1 operator operand2 Example: (A+B.html)*C-D/(E+F.html)前缀表示法 前缀表示法中，操作符写在操作数的前面。这种表示法经常用于计算机科学，特别是编译器设计方面。为纪念其发明家 — Jan Lukasiewicz（请参阅 参考资料），这种表示法也称 波兰表示法。Syntax : operator operand1 operand2 Example : -*+ABC/D+EF后缀表示法 在后缀表示法中，操作符位于操作数后面。后缀表示法也称 逆波兰表示法（reverse Polish notation，RPN），因其使表达式求值变得轻松，所以被普遍使用。Syntax : operand1 operand2 operator Example : AB+C*DEF+/-前缀和后缀表示法有三项公共特征：操作数的顺序与等价的中缀表达式中操作数的顺序一致不需要括号操作符的优先级不相关中缀表达式到后缀表达式的转换要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式，必须了解操作符的优先级和结合性。优先级 或者说操作符的强度决定求值顺序；优先级高的操作符比优先级低的操作符先求值。如果所有操作符优先级一样，那么求值顺序就取决于它们的 结合性。操作符的结合性定义了相同优先级操作符组合的顺序（从右至左或从左至右）。Left associativity : A+B+C = (A+B.html)+C Right associativity : A^B^C = A^(B^C.html)转换过程包括用下面的算法读入中缀表达式的操作数、操作符和括号：初始化一个空堆栈，将结果字符串变量置空。从左到右读入中缀表达式，每次一个字符。如果字符是操作数，将它添加到结果字符串。如果字符是个操作符，弹出（pop）操作符，直至遇见开括号（opening parenthesis）、优先级较低的操作符或者同一优先级的右结合符号。把这个操作符压入（push）堆栈。如果字符是个开括号，把它压入堆栈。如果字符是个闭括号（closing parenthesis），在遇见开括号前，弹出所有操作符，然后把它们添加到结果字符串。如果到达输入字符串的末尾，弹出所有操作符并添加到结果字符串。后缀表达式求值对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中，不需要括号，而且操作符的优先级也不再起作用了。您可以用如下算法对后缀表达式求值：初始化一个空堆栈从左到右读入后缀表达式如果字符是一个操作数，把它压入堆栈。如果字符是个操作符，弹出两个操作数，执行恰当操作，然后把结果压入堆栈。如果您不能够弹出两个操作数，后缀表达式的语法就不正确。到后缀表达式末尾，从堆栈中弹出结果。若后缀表达式格式正确，那么堆栈应该为空。W3Eval：一种新的方法W3E…

从零开始实现一个玩具版浏览器渲染引擎
type: item
date: 2026-07-07T08:26:13+00:00
description: 引言浏览器渲染原理是前端开发者必须掌握的核心知识点之一，在技术面试中经常被问及。许多前端书籍或培训课程也会提及此主题，例如 MDN 文档中就有关于渲染原理 [1] 的相关描述。作为一名工作多年的前端工程师，我虽然了解渲染原理的理论知识，但缺乏实践层面的深入理解。因此，我决定动手实现一个玩具版（Toy Version）的渲染引擎。渲染引擎是浏览器的核心组件，负责将网页内容（HTML、CSS、JavaScript 等）转化为用户可阅读、观看和听到的形式。独自实现一个完整的渲染引擎工作量巨大且难度极高，所以我决定退一步，实现一个简化版的玩具引擎。GitHub 上有一个开源的 Rust 语言玩具版渲染引擎 robinson [2]，我决定模仿其源码，使用 JavaScript 重新实现一遍，并将项目开源在 GitHub 上：从零开始实现一个玩具版浏览器渲染引擎 [3]。整体架构这个玩具版渲染引擎的实现一共分为五个阶段：具体流程分别是：解析 HTML：生成 DOM 树。解析 CSS：生成 CSS 规则集合。生成 Style 树：将样式与 DOM 节点关联。生成布局树：计算节点在页面中的位置和尺寸。绘制：将布局树渲染到屏幕上。每个阶段的代码在仓库中都用独立的分支来表示。由于直接查看整个渲染引擎的代码可能比较困难，建议大家从第一个分支开始学习，由易到难，以获得更好的学习效果。接下来，我们先看一下如何编写一个 HTML 解析器。第一阶段：HTML 解析器HTML 解析器的作用是将一连串的 HTML 文本解析为 DOM 树。例如，将以下 HTML 文本： test! 解析为一个 DOM 树结构：{ "tagName": "div", "attributes": { "class": "lightblue test", "id": "div", "data-index": "1" }, "children": [ { "nodeValue": "test!", "nodeType": 3 } ], "nodeType": 1 }编写解析器通常需要掌握编译原理知识，如词法分析、语法分析等。但我们的玩具版解析器非常简单，即使不懂相关理论，通过阅读源码也能理解。回到上面的 HTML 文本，其整个解析过程可以用下图表示，每一段 HTML 文本都有对应的方法去解析：为了让解析器实现起来更简单，我们需要对 HTML 的功能进行约束：标签必须要成对出现： ... 。HTML 属性值必须要有引号包起来： ... 。不支持注释。尽量不做错误处理。只支持两种类型节点：Element 和 Text。对解析器的功能进行约束后，代码实现就变得简单多了。节点类型首先，为这两种节点 Element 和 Text 定义适当的数据结构：export enum NodeType { Element = 1, Text = 3, } export interface Element { tagName: string attributes: Record<string, string> children: Node[] nodeType: NodeType.Element } interface Text { nodeValue: string nodeType: NodeType.Text } export type Node = Element | Text然后为这两种节点各写一个生成函数：export function element(tagName: string.html) { return { tagName, attributes: {}, children: [], nodeType: NodeType.Element, } as Element } export function text(data: string.html) { return { nodeValue: data, nodeType: NodeType.Text, } as Text }这两个函数在解析到元素节点或者文本节点时调用，调用后会返回对应的 DOM 节点。解析流程下图展示了整个 HTML 解析器的执行过程：HTML 解析器的入口方法为 parse()，从这开始执行直到遍历完所有 HTML 文本为止：判断当前字符是否为 <，如果是，则当作元素节点来解析，调用 parseElement()，否则调用 parseText()。parseText() 比较简单，一直往前遍历字符串，直至遇到 < 字符为止。然后将之前遍历过的所有字符当作 Text 节点的值。parseElement() 则相对复杂一点，它首先要解析出当前的元素标签名称，这段文本用 parseTag() 来解析。然后再进入 parse…

java公式解析器学习与开发（1）
type: item
date: 2026-07-07T08:26:12+00:00
description: java 公式解析器学习与开发（1）本文主要探讨如何使用 Java 实现一个简单的算术表达式求值器。以下是一个基于双栈算法（Two-Stack Algorithm）的基础实现示例。核心代码实现public class Evaluate { public static void main(String[] args.html) { Stack<String> ops = new Stack<String>(); Stack<Double> vals = new Stack<Double>(); // 示例表达式：完全括号化的中缀表达式，元素间以空格分隔 String[] strs = "( 1 + ( ( 2 + 3 .html) * ( 4 * 5 .html) ) )".split(" ".html); int i = 0; while (i < strs.length) { String s = strs[i]; if (s.equals("(".html)) ; // 忽略左括号 else if (s.equals("+".html)) ops.push(s.html); else if (s.equals("-".html)) ops.push(s.html); else if (s.equals("*".html)) ops.push(s.html); else if (s.equals("/".html)) ops.push(s.html); else if (s.equals("sqrt".html)) ops.push(s.html); else if (s.equals(".html)")) { // 遇到右括号，弹出操作符与操作数进行计算 String op = ops.pop(); double v = vals.pop(); if (op.equals("+".html)) v = vals.pop() + v; else if (op.equals("-".html)) v = vals.pop() - v; else if (op.equals("*".html)) v = vals.pop() * v; else if (op.equals("/".html)) v = vals.pop() / v; else if (op.equals("sqrt".html)) v = Math.sqrt(v.html); vals.push(v.html); } else vals.push(Double.parseDouble(s.html)); i++; } System.out.println(vals.pop(.html)); } }使用说明与限制上述程序实现了一个简单的算术表达式计算逻辑，但在使用时有以下严格限制：必须添加括号：表达式必须是完全括号化的（Fully Parenthesized），即每个操作符及其对应的操作数都必须被括号括起来。空格分隔：各个分词（Token）之间必须有空格，以便程序通过 split(" ".html) 区分计算结构。只有满足以上条件，程序才能正确解析并区分出运算的层级结构。原理简述中缀表达式（Infix Expression）是人们常用的算术表示方法。在通用的中缀记法中，通常依赖运算符优先级来确定计算顺序；但在上述算法实现中，括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来，用于明确指示运算的次序。这种处理方式简化了语法解析的复杂度，无需处理运算符优先级表，即可通过栈结构直接完成求值。说明：本文代码示例使用了 Java 传统的 Stack 类。在现代 Java 开发中，Stack 类已被视为遗留类（Legacy），官方建议优先使用 Deque 接口及其实现类（如 ArrayDeque）来替代。此外，该算法适用于教学演示或特定场景，实际生产环境中的表达式解析通常涉及更复杂的词法分析与语法树构建。