如何编写一个高效的Java表达式求值程序
如何编写一个高效的 Java 表达式求值程序虽然这个标题略显夸张，但我确实完成了这样一个目标（关于是否完全相信基准测试结果，那是另一个话题）。上周，我一直在寻找一个小型、实用的数学表达式计算类库。偶然间，我在 StackOverflow 上看到了一个帖子，里面推荐的库（Expr）确实很快，且基本拥有我需要的所有特性。但不幸的是，它不支持限制变量范围（在虚拟机里面，所有变量都位于一个全局命名空间）。于是，我做了一件通常不建议做的事情：重新发明轮子，自己编写一个解析器和执行器。那是一个下雨的周六，我想到用一个小型递归向下的解析器，构建一个简化版的、可计算表达式的抽象语法树（AST）。抽象语法树配合一个小型变量管理助手，看起来并没有什么大不了，但它并非无用。我做出了一个初步的实现，执行速度特别快。在进行了一些测试后，结果更让我充满信心：它执行的所有运算都正确无误。我想与前面提到的类库相比，确认这个计算器到底有多快。在没有对每个内部循环和其他执行细节进行优化前，我并不报太大期望，毕竟有不少类库是成熟的商业软件。但当我看到测试结果时，我感到很惊讶。下面的清单展示了一个小的基准测试，使用不同的类库计算同一个表达式。parsii 是我编写的库，测试时用的是最终版本。这个版本做了一些简化，比如预先计算了常量表达式，但没有使用任何“黑魔法”，比如生成字节码或者其他类似的操作。性能基准测试在性能评估中，用例是执行表达式 2 + (7 – 5) * 3.14159 * x^(12-10) + sin(-3.141)。其中变量 x 的取值范围测试参考了 Expr 的相关设定，迭代次数为 0 到 1,000,000。测试时先运行 10 次对 JIT 进行预热，然后再运行 15 次计算平均时间：类库平均耗时 (ms)PARSII28.3EXPR37.2MathEval7748.5JEP647.0MESP220.8JFEP274.3现在我敢肯定，每一个类库都有自己的优势，所以不能直接对它们进行绝对比较。尽管如此，令人吃惊的是一个简单实现的程序可以拥有这么好的表现。核心架构如果读者对于编译器的原理不太了解，下面是一个关于编译器运行机制的简单介绍。词法分析 (Tokenizer)同其他的解析器或者编译器一样，parsii 使用了传统的 分词器。它将字符流转化成词法单元流（Token Stream）。例如 "4 + 38"，也就是字符数组 '4', ' ', '+', ' ', '3', ' ', ' ', '8' 被转化成：4 (整数)+ (符号)38 (整数)分词器读取一个字符，接着判断是一个什么类型的词法单元，然后再读入属于该词法单元的所有字符。每一个词法单元都有类型、文本内容，并且知道起始位置（行号和字符偏移）。网上有很多深入的教程，所以在这里就不详细讲解了。你可以看一下源代码，但正如我说的，它只是一个初步的实现。语法解析 (Parser)解析器 用来将传入的词法单元流翻译成可以执行的 AST（抽象语法树）。它是一个传统的自上而下递归解析器（Recursive Descent Parser）。这是实现解析器最简单的方式，完全手写，没有利用工具生成。像这样的解析器只拥有一个包含所有语法规则的方法。错误处理同样，关于这种类型的解析器有很多教程，但是如何恰当地处理错误却缺少相关的示例。除了解析表达式的速度和正确性外，优秀的错误处理机制是一个优秀解析器的最核心因素之一。正如在源代码里看到的那样，实现起来并不是太困难。因为解析器在解析表达式的过程中从来不会立即抛出异常，所有的错误都被收集起来，并且继续尽可能进行解析。即使在第一个错误发生以后已经不能成功解析生成 AST，重要的是要能够尽可能继续解析，因为在一次的执行中我们需要报告尽可能多的错误。这样的方法也同样用在了分词器报告上，比如报告非法格式的词法单元（例如带有两个小数点的浮点数），将它们放到同样的错误列表中。表达式执行执行一个解析完成后的抽象语法树非常简单。每一个抽象语法树节点都包含一个计算方法，调用从根节点开始，父节点会调用子节点的该方法。这里的执行结果就是表达式的结果。一个简单的例子就是 算数运算，包含了 +、-、* 等操作。性能优化为了减少执行时间，程序里运用了 3 种优化措施：常量折叠 (Constant Folding)在完成解析 AST 后，在根节点上进行一个简化的方法调用，并且会扩散到每一个子节点。每一个节点判断自己的子表达式中是否有简化的表达形式。例如：对于 算数运算，我们检查两个操作数是不是都是常量（数字）。如果是数字，我们将计算表达式并且返回一个包含计算结果的常量。对于函数，如果所有的参数都是常量的话，也会进行此类优化。变量缓存 (Variable Caching)在表达式中使用变量时会执行第二种优化。这里使用 map 用来在需要的时候对变量的值进行读写。这肯定是有效的，但会进行很多次的查找。所以我们有一个叫做 Variable 类，它包含了变量名称和变量值。在进行表达式解析时，变量在作用域范围内（仅是一个 map）只被 查找 一次，之后就可以一直使用。由于每次查找都返回相同的实例，所以在计算表达式值时变量的访问就像读写字段一样廉价，因为我们刚刚获取了 Variable 类的 值。延迟运算 (Lazy Evaluation)第三个也是最后一个优化很可能不是经常起作用，但由于易于实现，还是应用了这种优化。它的功能基本上和名字“延迟运算”一样，主要用于函数调用。函数不会自动计算所有参数值并且调用函数，而“延迟运算”会检查所有的参数，自行决定哪些参数需要计算。在 if 函数 中可以看到它应用的实例。开源许可与源代码parsii 遵循 MIT 许可证授权。在 GitHub 上可以找到所有的源代码，并且包含了预编译的 jar 包。原文链接：dzone说明：本文内容基于较早的技术背景与基准测试数据，文中提及的部分第三方类库（如 JEP、MathEval 等）版本可能已更新，性能表现仅供参考。代码示例与架构思路适用于理解表达式求值原理，实际生产环境请结合最新技术栈评估。
使用 Antlr 开发领域语言 - 开发一个完整的应用
一个完整的应用在使用 ANTLR 开发领域语言的 前一篇文章 中，我们简要介绍了 ANTLR 的一些特性，并以算术表达式为例说明了其在词法分析、语法分析、解释和编译等方面的用法。本文中，我们将共同开发一个更为复杂的领域语言。在确定语言的运算能力之后，首先使用 ANTLR 定义语言的文法，实现词法分析和语法分析，并生成对应的抽象语法树（Abstract Syntax Tree, AST）；之后基于树分析器开发一个类型检查器，检查语言的类型是否合法；然后基于树分析器开发一个代码生成器，将语言编译为一种中间代码。图 1 详细描述了这一工作过程。图 1. 工作流程（查看大图）上述四个步骤与 ANTLR 紧密结合，每一步都用到了 ANTLR 的相关技术。在完成中间代码的生成后，工作并没有结束。最后我们将实现一个虚拟机，该虚拟机使用堆栈来操纵数据，对之前产生的中间代码解释执行，完成最终的运算。我们将该虚拟机命名为抽象堆栈机。语言定义首先，我们需要确定领域语言应该具备哪些运算能力。清单 1 和清单 2 给出了两个目标语言的例子。清单 1. 领域语言示例一max(a, b){ if(a>b) return a ; return b; } main(){ return max(x, y); }清单 2. 领域语言示例二sum(a) { sum = 0 ; while(a>0) { sum = sum + a; a = a - 1; } return sum ; } main(){ return sum(x)/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)*; （4）将（4）代入（2），最终原文法（1）被改写成如下形式：A -> b (a)*; （5）算符的结合性在定义语言时，有些算符是左结合的，比如算术运算符 +，a + b + c 等价于 (a + b) + c；有些算符是右结合的，比如赋值运算符 =，a = b = c 等价于 a = (b = c)。在 LL 识别器中，左结合算符通过指定重复匹配进行定义，如清单 3 所示：清单 3. 左结合算符的文法expr : atom (('+' |'-' ) atom )* ;右结合文法通过尾递归文法定义，如清单 4 所示：清单 4. 右结合算符的文法expr : id '=' expr;算符的优先级在 LL 文法识别器中，算符的优先级要通过文法的嵌套定义来体现。优先级低的算符要优先声明，相同优先级的算符可以在同一个规则中描述。比如加减运算的优先级比乘除运算的优先级低，加减法要先于乘除法定义，文法定义方式如清单 5 所示：清单 5. 考虑算符优先级的文法additiveExpr : multExpr (('+' |'-' ) multExpr )* ; multExpr : atom (('*' |'/' ) atom)* ;文法定义使用 ANTLR 定义文法时，综合考虑前面提到的三种因素（左递归、算符结合性和算符优先级），我们把领域语言的文法最终定义成清单 6 所示的形式。清单 6. 语法定义// 为体现文法支持函数调用，将文法命名为 Function。 grammar Function; // prog 是文法的入口，一个 prog 有一个或多个函数定义组成。 prog: funDecl+; // 函数定义，有函数名 ID、参数列表和语句块构成。 funDecl : ID '(' paramDeclList ')' block; // 参数列表有 0 个或多个参数定义。 paramDeclList : (paramDecl (',' paramDecl)*)?; // 参数定义对应一个词法符号 ID paramDecl : ID ; // 语句块由花括号和语句列表组成。 block : '{' stmtList '}'; // 语句列表由 0 个或多个语句组成。 stmtList: stmt* ; // 语句有返回语句、条件语句、三类循环语句、语句块和表达式语句组成。 stmt options{ backtrack=true; } : RETURN expr ';' | ifStmt | WHILE '(' expr ')' stmt | 'do' stmt WHILE '(' expr ')' | 'for' '(' expr ';' expr ';' expr ')' | block | expr ';' ; // 条件语句有 4 种形式：if …、if … else …、unless …、unless … else …。 ifStmt options{ backtrack=true; } : IF '(' expr ')' stmt 'else' stmt | 'unless' '(' expr ')' stmt 'else' stmt | IF '(' expr ')' stmt | 'unless' '(' expr ')' stmt ; // 表达式包含赋值表达式和逻辑或表达式。其中赋值表达式中 = 是右结合算符，使用尾递归定义文法。 expr options{ backtrack=true; } : ID '=' expr | orExpr ; // 从逻辑或表达式开始，依据算符的优先级，依次定义了逻辑或表达式、逻辑与表达式、关系表达式、算术表达式、 // 逻辑非表达式和取反表达式。 orExpr : andExpr ('||' andExpr)* ; andExpr : equalityExpr ('&&' equalityExpr)* ; equalityExpr: comparisonExpr (('=='|'!=') comparisonExpr)* ; comparisonExpr: additiveExpr (('>'|'<'|'<='|'>=') additiveExpr)* ; additiveExpr: multExpr (('+' |'-' ) multExpr )* ; multExpr : notExpr (('*' |'/' ) notExpr )* ; notExpr : ('!')? negationExpr ; negationExpr: ('-')? primary ; // 基本项有原子项和用于改变运算优先级的括号加表达式构成。 primary : atom | '(' orExpr ')'; // 原子项有常数、函数调用和变量组成。 atom options{ backtrack=true; } : NUMBER | ID '(' exprList ')' | ID ; // 函数调用实参列表，包含 0 个或多个表达式 exprList: (orExpr (',' orExpr)*)?;从上述文法定义中，可以看出整个语言由若干函数定义组成。每个函数定义包括函数名、参数列表和函数体。函数体由若干语句构成，包括返回语句、条件语句、循环语句、赋值语句和表达式运算语句等。表达式定义了语言支持的若干运算，语言中的运算能力主要由表达式定义来体现。词法定义语言的词法定义包括文法定义用到的 3 个关键字记号：IF、WHILE 和 RETURN，以及其他 4 个记号：变量 ID、数字 NUMBER、换行符 NEWLINE 和空白字符 WS。其中换行符 NEWLINE 和空白字符 WS 不需要作为词法记号向语法分析器传递，使用 skip() 方法将其跳过。清单 7 给出了详细定义。清单 7. 词法定义IF : 'if' ; WHILE : 'while' ; RETURN : 'return' ; BREAK : 'break' ; ID : ('a'..'z' |'A'..'Z' )('a'..'z' |'A'..'Z'|'0'..'9')* ; NUMBER : ('0'..'9')+ ('.' ('0'..'9')+)? ; NEWLINE : '\r' ? '\n' ; WS : (' ' |'\t' |'\n' |'\r' )+ {skip();} ;抽象语法树基础抽象语法树（AST）是语言的结构化表示形式，它的每个节点代表源程序中的某种构造。抽象语法树往往忽略语言中的某些细节，比如括号 ()。当括号用于表示计算的优先级时，树形结构已经拥有了优先级信息，可以去掉；当括号用于表示分隔符时，比如函数声明和函数调用，分隔符在抽象语法树中不需要存在，可以去掉。抽象语法树不同于语法分析树，后者代表语法分析器分析的完整过程，而抽象语法树往往使用最少的信息来表示语言本身的结构。可以在定义文法的同时，使用 ANTLR 树构造语法来建立抽象语法树。我们语言中的抽象语法树节点主要有以下几类：使用占位符作为根节点建立树节点。 占位符的作用只是一个特定符号，用于区分不同的树节点。清单 8 给出了一个示例，参数定义用 PARAM 作为占位符，区别于其他节点。清单 8. 用占位符作为根节点paramDecl : ID -> ^(PARAM ID) ;使用算符作为根节点建树节点。 清单 9 中，逻辑与算符（||）、加法算符（+）和减法算符（-）分别作为树的根节点去创建语法树。清单 9. 用算符作为根节点orExpr : andExpr ('||'^ andExpr)* ; additiveExpr: multExpr (('+' |'-' )^ multExpr )* ;依据语义规则条件的不同，建立不同的树节点。 在清单 10 中，依据一元算符逻辑非（!）是否存在创建了两个不同的树节点。清单 10. 依据语义规则创建不同的树节点notExpr : (op='!')? negationExpr -> {$op != null}? ^(NOT negationExpr) -> negationExpr通过文法规则重写建立树节点，去掉相关的分隔符号。 清单 11 中，我们在 primary 和 ifStmt 规则的语法树构造中，去掉了括号。清单 11. 改写文法规则建立树节点primary : '(' expr ')' -> expr ; ifStmt: IF '(' e1=expr ',' e2=expr ',' e3=expr ')' -> ^(IF $e1 $e2 $e3);抽象语法树定义完整的抽象语法树定义如清单 12 所示，用到了前面讲到的 4 种建树方法：清单 12. 抽象语法树定义grammar Function; options{ output = AST; ASTLabelType = CommonTree; } // tokens 列表定义了若干符号，用于区别语法树的节点。 tokens{ FUNCTION; PARAMATERS; PARAM; BLOCK; STMTS; ASSIGN; NOP; EXPR; NUM; VAR; NOT; NEGATE; CALL; } // prog 语法树规则和文法规则相同，无需指定。 prog: funDecl+; // 函数定义的语法树，以 FUNCTION 为根节点，函数名，参数列表和语句块为子节点；其中参数列表的语法树又以 // PARAMATERS 为根节点，参数列表自身为子节点。 funDecl : name=ID '(' paramDeclList ')' act=block -> ^(\ FUNCTION $name ^(PARAMATERS paramDeclList)? $act) ; // 参数列表的语法树，通过规则改写指定，去掉逗号分隔符。 paramDeclList : (paramDecl (',' paramDecl)*)? -> paramDecl* ; // 参数的语法树指定 PARAM 为根，ID 为叶子。 paramDecl : ID -> ^(PARAM ID) ; // 语句块的语法树指定了两个根节点，分别是 BLOCK 和 STMTS, 语句列表作为子节点。 block : '{' stmts=stmtList '}' -> ^(BLOCK ^(STMTS $stmts)) ; // 语句列表的语法树规则和文法规则相同，无需指定。 stmtList: stmt* ; // 返回语句指定 RETURN 为根节点，表达式为子节点 // 3 类循环语句在创建语法树时，根据其语义规则，被统一为一种树结构，根节点都是 WHILE, 子节点是条件判断表 // 达式和循环体语句。通过这种改写屏蔽了语法的差异，把不同的语法用语义相同的抽象语法树表示，没有改变语 // 言的语义，简化了后续处理。 stmt options{ backtrack=true; } : RETURN expr ';' -> ^(RETURN expr) | ifStmt | WHILE '(' expr ')' stmt -> ^(WHILE expr stmt) | 'do' stmt WHILE '(' expr ')' -> stmt ^(WHILE expr stmt) | 'for' '(' ini=expr ';' tes=expr ';' inc=expr ')' \ stmt -> $ini ^(WHILE $tes ^(BLOCK ^(STMTS stmt $inc))) | block | expr ';' -> expr ; // 条件语句的语法树创建和循环语句有着类似之处。我们将 4 种不同的语法形式统一到一个相同的树节点上来。用 // IF 作为根节点，条件判断表达式和两个语句作为子节点。如果 IF 语句缺少 else，则第二个语句用占位符号 // NOP 代替。unless 表示 if not，所以它的语法树创建使用和 IF 一样的树节点，颠倒两个语句的次序，就保证了 // 原有的语义。 ifStmt options{ backtrack=true; } : IF '(' expr ')' c1=stmt 'else' c2=stmt -> ^(IF expr $c1 $c2) | 'unless' '(' expr ')' c1=stmt 'else' c2=stmt -> ^(IF expr $c2 $c1) | IF '(' expr ')' c1=stmt -> ^(IF expr $c1 NOP) | 'unless' '(' expr ')' c1=stmt -> ^(IF expr NOP $c1) ; // 赋值表达式指定了用 ASSIGN 作为根节点，ID 和表达式分别为子节点。 expr options{ backtrack=true; } : ID a='=' expr -> ^(ASSIGN ID expr) | orExpr ; // 用算符 || 作为根节点 orExpr : andExpr ('||'^ andExpr)* ; // 用算符 && 作为根节点 andExpr : equalityExpr ('&&'^ equalityExpr)* ; // 用算符 ('=='|'!=') 作为根节点 equalityExpr: comparisonExpr (('=='|'!=')^ comparisonExpr)* ; // 用算符 ('>'|'<'|'<='|'>=') 作为根节点 comparisonExpr: additiveExpr (('>'|'<'|'<='|'>=')^ additiveExpr)* ; // 用算符 ('+' |'-' ) 作为根节点 additiveExpr: multExpr (('+' |'-' )^ multExpr )* ; // 用算符 ('*' |'/' ) 作为根节点 multExpr : notExpr (('*' |'/' )^ notExpr )* ; // 依据逻辑非算符的存在性，创建不同的树节点 notExpr :(op='!')? negationExpr -> {$op != null}? ^(NOT negationExpr) -> negationExpr ; // 依据取反算符的存在性，创建不同的树节点 negationExpr : (op='-')? primary -> {$op != null}? ^(NEGATE primary) -> primary ; // 用于改变运算优先级的括号在创建语法树时应该去掉。 primary : atom | '(' orExpr ')' -> orExpr ; // 原子项分别指定了常数、函数调用和变量的树节点形式。 atom options{ backtrack=true; } : NUMBER -> ^(NUM NUMBER) | ID '(' exprList ')' -> ^(CALL ID exprList) | ID -> ^(VAR ID) ; // 参数调用列表的语法树，通过规则改写指定，去掉逗号分隔符。 exprList:(expr (',' expr)*)? -> expr* ;使用上述定义的抽象语法树文法，当输入语言为清单 1 中的领域语言时，可以得到如下的抽象语法树。如图 2 所示。图 2. 示例语言对应的抽象语法树类型检查为了减少运行时错误，需要对语言进行静态类型检查。静态类型检查基于抽象语法树，通过在抽象语法树中为各个树节点添加类型属性来完成最终的类型检查。在 ANTLR 中通过构造 Tree Parser，为语法树中的每一个节点指定附加动作，由这些动作完成属性收集和类型检查。Tree Parser 的工作原理是深度优先遍历抽象语法树，当访问到树的叶子节点时，为叶子节点添加类型属性值；当访问到非叶子节点时，执行类型检查，并且为非叶子节点赋类型值，用于后续的检查。在我们的应用中，为了类型检查的需要，为抽象语法树的部分节点定义了类型属性，类型属性通过节点的返回值体现。在我们的领域语言中定义了两个类型值，分别是 number 和 bool 用于表示数值型和布尔型。变量和常量的类型对于抽象语法树中的叶子节点，直接定义其类型属性。为叶子节点定义属性 clazz，用于记录其类型值，我们规定变量和常量的类型为 number 类型。参见清单 13：清单 13. 变量和常量的类型atom returns[String clazz] : ^(NUM n=NUMBER) {$clazz = number;} | ^(VAR v=ID){$clazz = number;}表达式的类型检查对于表达式运算节点，必须先检查其子节点的属性是否为特定属性，然后再定义表达式运算节点自身的类型属性，其类型属性是和运算符号相关的。比如算术运算节点的左右两个子节点的类型必须为 number，其自身类型属性仍然是 number 类型。而关系运算节点的左右两个子节点的类型必须为 number，其自身类型属性却是 bool 类型。逻辑运算节点的左右两个子节点的类型必须为 bool，其自身类型属性仍然是 bool 类型。如清单 14 所示：清单 14. 表达式的类型检查expr returns[String type]: ^(t=('||'|'&&')e1=expr e2=expr) { checkType(bool, e1.type, $text); checkType(bool, e2.type, $text); $type = bool;} | ^(t=('=='|'!='|'>'|'<'|'<='|'>=') e1=expr e2=expr) { checkType(number, e1.type, $text); checkType(number, e2.type, $text); $type = bool;} | ^(t=('+'|'-'|'*'|'/') e1=expr e2=expr) { checkType(number, e1.type, $text); checkType(number, e2.type, $text); $type = number;}checkType 函数的第一个参数为期望的类型，第二个参数为子节点的实际类型，当两者不符时，就会抛出类型错误异常。第三个参数是当前上下文，当抛出异常时用于指定错误发生的位置。语句的类型检查循环语句 whileStmt，需要检查 while 语句的条件判断表达式 expr 的类型为 bool，如其类型不为 bool，抛出类型错误异常。条件语句 ifStmt 的检查项和 whileStmt 类似。如清单 15 所示：清单 15. 语句的类型检查whileStmt : ^(WHILE e=expr { checkType(bool, e.type, $text); } stmt) ; ifStmt : ^(IF e=expr { checkType(bool, e.type, $text); } (stmt) (stmt|NOP)) ;使用该类型检查器，可以发现如同 a<b&&(c-d)，a>b>c，if(a+b){} 这样的静态类型错误。其中 a<b&&(c-d) 违反了逻辑与算符右侧必须为布尔值的检查；a>b>c 第 2 个大于操作违反了左操作数必须为数值型的检查；if(a+b){} 违反了 if 语句中的判断表达式必须为布尔值的检查。代码生成这一节我们基于树分析器开发一个代码生成器，其作用是在遍历抽象语法树的过程中，根据不同的树节点，输出不同的中间代码。狭义上的编译器主要工作就是代码生成，在本节中代码生成器和编译器表示同一个概念。为了深入了解代码生成器的工作原理，在开始介绍生成器之前，先来熟悉一下我们的中间代码指令集。目前一共定义了 23 种指令，其对应的语义如表 1 所示。在下一节里，我们会用 Java 实现一个虚拟机来解释执行这些指令，到时将会更好的理解每一条指令的语义。表 1. 虚拟机的指令集指令名称操作数个数语义指令类型ldv取变量 load variable一个操作数（变量名称）从 IO 取数、入栈指令指针加 1取数指令ldc取常量 load constant一个操作数（常量值）常数入栈指令指针加 1取数指令halt停机指令0 个操作数栈顶元素出栈，并输出置指令指针为无穷大停机指令call函数调用指令2 个操作数指令指针加 1动态链接被调用函数，创建新的虚拟机帧 (Frame)同时把参数从上一帧传递到当前帧函数调用指令ret函数调用返回 return0 个操作数栈顶元素赋给上一帧当前帧出栈函数调用指令add加法0 个操作数从栈中出栈两个元素，加法运算结果入栈指令指针加 1算术运算指令sub减法0 个操作数从栈中出栈两个元素，减法运算结果入栈指令指针加 1算术运算指令mul乘法0 个操作数从栈中出栈两个元素，乘法运算结果入栈指令指针加 1算术运算指令div除法0 个操作数从栈中出栈两个元素，除法运算结果入栈指令指针加 1算术运算指令gt大于0 个操作数从栈中出栈两个元素，大于运算结果入栈指令指针加 1关系运算指令ge大于等于0 个操作数从栈中出栈两个元素，大于等于运算结果入栈指令指针加 1关系运算指令lt小于0 个操作数从栈中出栈两个元素，小于运算结果入栈指令指针加 1关系运算指令le小于等于0 个操作数从栈中出栈两个元素，小于等于运算结果入栈指令指针加 1关系运算指令eq等于0 个操作数从栈中出栈两个元素，等于运算结果入栈指令指针加 1关系运算指令neq不等于0 个操作数从栈中出栈两个元素，不等于运算结果入栈指令指针加 1关系运算指令and逻辑与0 个操作数从栈中出栈两个元素，与运算结果入栈指令指针加 1逻辑运算指令or逻辑或0 个操作数从栈中出栈两个元素，或运算后结果入栈指令指针加 1逻辑运算指令not逻辑非0 个操作数从栈中出栈一个元素，求非结果入栈指令指针加 1逻辑运算指令rem注释 remark用于生成代码的跟踪验证0 个操作数指令指针加 1辅助指令jmp无条件跳转 jump一个操作数（指令行数）指令指针跳转到指定指令行数跳转指令jzjump if zero一个操作数（指令行数）栈顶元素出栈如果栈顶元素的值非零，指令指针加 1否则指令指针跳转到指定指令行数跳转指令asn赋值 assign一个操作数栈顶元素出栈，存储于数据存储器中指令指针加 1赋值指令dup复制栈顶元素0 个操作数栈顶元素再次入栈指令指针加 1栈操作类指令清单 1 所示的领域语言，最终将被编译成如清单 16 所示的形式。在开始介绍代码生成器之前，先来看一个 Java 类 Instruction，用于表示一条虚拟机指令。一个 Instruction 由指令序号、指令名称和若干操作数组成。清单 16 中示例的指令中，最左边是当前指令的序号，之后是指令名称，再之后是若干操作数。语言中每一个函数的编译都是独立进行的。在编译过程使用了一个整型实例变量 seqNum，用于记录当前指令的序号，seqNum 的值在遇到函数定义时被重置为 0。清单 16. 示例语言对应的中间代码max 0 rem beginIf 1 ldv t0 2 ldv t1 3 gt 4 jz 9 5 ldv t0 6 ret 7 jmp 9 8 rem endIf 9 ldv t1 10 ret main 0 ldv t0 1 ldv t1 2 call max 2 3 halt常量和变量的编译常量可以直接作为运算数；变量值需要依据变量的名称，从 IO 中取得对应的值，作为运算数。在编译时给常量和变量指定了不同的指令，便于解释执行时互相区分。如清单 17 所示：清单 17. 编译为取数指令atom: ^( NUM n=NUMBER) { new Instruction(seqNum++, "ldc", n.getText());} | ^(VAR v=ID) { new Instruction(seqNum++, "ldv", v.getText());}表达式的编译表达式中主要涉及到运算符的编译，二元算符和一元算符的编译规则是一致的，只需将算符转换为对应的运算指令即可。只有取反算符略有不同，用当前表达式和 -1 相乘，达到取反的目的。清单 18 给出了具体实现。清单 18. 编译为运算指令expr: ^('+' expr expr) {new Instruction(seqNum++, "add");} | ^('-' expr expr) {new Instruction(seqNum++, "sub");} | ^('*' expr expr) {new Instruction(seqNum++, "mul");} | ^('/' expr expr) {new Instruction(seqNum++, "div");} | ^('>' expr expr) {new Instruction(seqNum++, "gt");} | ^('>=' expr expr) {new Instruction(seqNum++, "ge");} | ^('<' expr expr) {new Instruction(seqNum++, "lt");} | ^('<=' expr expr) {new Instruction(seqNum++, "le");} | ^('==' expr expr) {new Instruction(seqNum++, "eq");} | ^('!=' expr expr) {new Instruction(seqNum++, "neq");} | ^('||' expr expr) {new Instruction(seqNum++, "or");} | ^('&&' expr expr) {new Instruction(seqNum++, "and");} | ^(NOT e=expr) {new Instruction(seqNum++, "not");} | ^(NEGATE e=expr) { new Instruction(seqNum++, "ldc", "-1"); new Instruction(seqNum++, "mul");}if 语句的编译if 语句的编译不像前面的编译那样简单，只把生成指令的动作插入在语法树节点的末尾，其编译过程中用到了控制指令，需要在深度优先遍历子树的过程中，根据语义的变化插入不同的语义动作。在 if 语句开始之前，定义了两个指令。其中 instruction1 用来表示 jz 条件跳转指令，用于跳过语句 s1 直接执行语句 s2，它在遍历完判断表达式 expr 之后加入指令列表，但是其要跳转的目标指令行，在 if 语句的第一个语句 s1 遍历完之后才能确定。遍历完语句 s1 时，当前指令行就是跳过语句 s1 的指令行；instruction2 表示 jmp 无条件跳转指令，用于语句 s1 执行完毕后直接跳过语句 s2，它在 if 语句的第一个语句树 s1 遍历完之后，加入指令列表，但其要跳转的目标指令行在整个 if 语句遍历完成之后才能确定。遍历完整个 if 语句时，当前指令行就是跳过语句 s2 的指令行。一图胜千言，图 3 if 语句的编译用图形描述了上述过程。清单 19 给出了具体实现。图 3. if 语句的编译清单 19. if 语句的编译ifStmt : {Instruction instruct1 = null, instruct2 = null; } ^(IF expr{instruct1 =new Instruction(seqNum++, "jz"); insList.add(instruct1);} s1=stmt{instruct2 =new Instruction(seqNum++, "jmp");insList.add(instruct2);} {int seq = seqNum;instruct1.oprand1=seq;} s2=stmt){int seq2=seqNum;instruct2.oprand1=seq2; } ;while 语句的编译循环语句 whileStmt 的编译其实和 if 语句非常类似，也需要两次跳转。一次条件跳转发生在判断表达式之后，如判断结果非真，则跳出循环。另一次无条件跳转发生在循环体内的语句执行完之后，要跳向 while 语句的开始，接着执行条件判断，决定是否继续循环。整个原理和 ifStmt 的编译一模一样，只是跳转指令的目标地址的指定时机不同而已。图 4 和清单 20 分别用不同的方式，对 while 语句的编译过程做了描述。图 4. while 语句的编译清单 20. while 语句的编译whileStmt : {Instruction instruct1 = null, instruct2 = null; int whileTestLine = seqNum;} ^(WHILE expr {instruct1 =new Instruction(seqNum++, "jz"); insList.add(instruct1);} stmt) {instruct2 =new Instruction(seqNum++, "jmp", whileTestLine);insList.add(instruct2);} {int seq = seqNum;instruct1.oprand1=seq;} ;函数调用语句的编译当抽象语法的树节点为函数调用时，需要用到 call 指令去编译该节点。使用 call 指令时，除了要指定被调用的函数名之外，还必须统计出调用函数时传递的实际参数的个数。比如 max(a, b) 的调用最终编译出来的指令为：call max 2，表示要用 2 个参数去调用 max 函数。清单 21. 函数调用语句的编译atom : ^(CALL v=ID el=exprList) {new Instruction(seqNum++, "call", \ v.getText(), $el.paramNum); } exprList returns[Integer paramNum] @init { $paramNum =0; } : (vars+=expr)* {$paramNum =$vars.size();} ;此外函数调用返回时，遇到 return 语句，我们使用 ret 指令去编译。如果当前的函数是 main 函数，用 halt 指令去替代 ret；其他任何函数调用都被编译成 ret。指令 ret 表示函数调用的返回；而指令 halt 表示整个计算的结束。虚拟机实现虚拟机结构虚拟机的实现，本身和 ANTLR 没有太多关系，实现虚拟机的目的是为了解释执行之前生成的指令，完成运算任务。虚拟机主要基于堆栈来完成所有的相关计算，为此给虚拟机命名为抽象堆栈机。为了便于理解，先不考虑函数调用。在 上一节表 1 所示的指令集中，暂不考虑 call 和 ret 的实现。对于其他 21 条指令，我们考虑使用如下方式实现。引入 4 个数据结构：指令数组：这是一个只读结构，用于存放编译得到的指令列表，在 Java 中使用 List 来实现。指令指针：用于标识当前执行的指令行数，用一个整型变量来表示。局部变量表：在 Java 中使用 Map 来实现，key 是变量的名字，value 为变量的值。操作数堆栈（运算堆栈）：所有的计算都围绕堆栈展开，在 Java 中用 Stack 类即可，抽象堆栈机的得名正是因为运算堆栈的存在。有了上述数据结构之后，虚拟机的原型已经非常明了。当遇到 ldv 取变量指令时，我们先从局部变量表中取值，如在表中不存在，则从 IO 中取值（示例代码中，简单起见，用一个随机数为其赋值），最终把变量的值入栈即可。遇到 ldc 取常数指令时，把常数直接入栈。13 类运算指令（4 个算术指令、6 个关系指令和 3 个逻辑指令）的实现方式非常类似，除了逻辑非（not）指令外，其他 12 个指令对应的都是二元算符，有两个操作数，所以从栈中出栈两个元素，做对应的运算，计算结果入栈；逻辑非（not）指令只有一个操作数，所以从栈中出栈一个元素，求非后结果入栈。两个跳转指令，jmp 根据目标指令行直接修改指令指针的值；jz 根据栈顶元素的值判断决定指令指针的值，如为真，指令指针加一，指令继续顺序执行，否则跳转到指定的指令行去。赋值指令 asn 将一个栈顶元素出栈，放入局部变量表中，局部变量表是一个 Map 结构，变量的名字为 key，出栈的元素本身为 value。复制栈顶元素指令 dup，得到操作数栈顶元素，再次入栈，指令指针加一。停机指令 halt，将栈顶元素作为计算的最终结果返回，然后修改指令指针为无穷大，停止虚拟机的计算。指令 rem 是一个注释，在解释执行时，它没有任何的含义，通过将指令指针加一，直接跳过该指令即可。图 5. 运行时环境当加入 call 和 ret 指令后，对虚拟机略做扩充。引入一个数据结构帧 Frame。之前我们定义的四个数据结构，都属于帧。一个帧代表一个函数的运行时环境，而整个虚拟机是由帧构成的堆栈组成。当开始计算时，虚拟机先用 main 函数的指令列表初始化一个帧，当遇到 call 指令时，动态加载被调用函数的指令列表，初始化出新的帧；当函数调用返回（遇到 ret 指令）时，被调用函数代表的当前帧出栈，返回到前一个调用函数中，继续执行后续指令。图 5 给出了虚拟机运行时刻的一个图形化描述。指令解析举例虚拟机的初始化从 main 函数编译后指令列表开始，我们定义了抽象堆栈机类 AbstractMachine，它的构造函数如清单 22 所示。参数 functionMap 是用户自定义函数编译结果，key 为函数名，比如 main，max 等，value 为函数编译后的指令列表。我们用 main 函数的指令列表构造虚拟机帧并入栈，至此虚拟机已经做好准备，可以开始解析执行各种指令。清单 22. 虚拟机的构造函数public AbstractMachine(Map<String, List<Instruction>> functionMap) { super(); List<Instruction> insList = functionMap.get("main"); Frame mainFrame = new Frame("main"); mainFrame.setInslist(insList); stack.push(mainFrame); this.functionMap = functionMap; }ldv 指令从局部变量表中取值，或者用随机数赋值，然后值入栈，指令指针加一。这里 ActiveOperand 是自定义的一个类，它对放入运算堆栈的元素做了包装，防止运行时类型错误。ldv 指令的实现如清单 23 所示。ldc 和 ldv 非常类似，用字面量常数构造 ActiveOperand 入栈即可。清单 23. ldv 指令的解析private void ldv(Instruction ins) { String s = ins.getOprand1(); ActiveOperand ao = currentFrame().getActiveOperand(s); if(null == ao){ Random rand = new Random(); ao = new ActiveOperand(Integer.class, rand.nextInt(10)); System.out.println("rand value :" +s + " "+ao.getValue()); currentFrame().putActiveOperand(s, ao); } currentFrame().pushActiveOperand(ao); currentFrame().incIr(); }13 类运算指令，不用再做过多的解释，用其中一个指令 add 来说明。add 对应的二元运算符 +，所以从栈中连续出栈两个元素，分别作为加法运算的右操作数和左操作数参与计算，计算结果入栈，指令指针加一。参见清单 24。清单 24. add 指令的解析private void add(Instruction ins) { ActiveOperand ao1 = currentFrame().popActiveOperand(); ActiveOperand ao2 = currentFrame().popActiveOperand(); ActiveOperand ao = null; if(ao1.getClazz() == Integer.class && ao2.getClazz() == Integer.class) { ao = new ActiveOperand(Integer.class, (Integer)ao2.getValue()+(Integer)ao1.getValue()); }else { ao = new ActiveOperand(Double.class, Double.parseDouble(ao2.getValue().toString())\ + Double.parseDouble(ao1.getValue().toString())); } currentFrame().pushActiveOperand(ao); currentFrame().incIr(); }条件跳转指令 jz 的实现如清单 25 所示，需要根据当前栈顶元素判断后续指令的位置。如栈顶元素为布尔值 true，则指令顺序执行，无需跳转，否则需要跳转到指令中指定的位置。jmp 的实现和 jz 比起来更加简单，直接修改指令指针的值，跳转到指定位置即可。清单 25. jz 指令的解析private void jz(Instruction ins) { String s = ins.getOprand1(); if ((Boolean)currentFrame().popActiveOperand().getValue()) { currentFrame().incIr(); } else { currentFrame().setIr(Integer.parseInt(s)); } }函数调用指令 call 做的工作较多一点，首先它需要动态加载被调用函数的指令列表，构造新的虚拟机帧；其次根据指令的第二个参数，得到要传递的参数个数，由于在编译时，所有函数的局部变量都被编译成形如 t0，t1 这样的临时变量，所以通过强制命名的方法完成参数的传递。参见清单 26。清单 26. call 指令的解析private void call(Instruction ins) { currentFrame().incIr(); String fun = ins.getOprand1(); List<Instruction> insList = functionMap.get(fun); Frame frame = new Frame(fun); frame.setInslist(insList); String paramNum = ins.getOprand2(); for(int i= Integer.parseInt(paramNum)-1; i>=0 ; i--) { ActiveOperand ao = currentFrame().popActiveOperand(); frame.putActiveOperand("t"+i, ao); } stack.push(frame); }函数调用返回指令 ret 把当前帧中栈顶的元素作为函数的返回值，压入了前一帧的运算栈中，这样就完成了函数返回值的传递。如清单 27 所示。清单 27. ret 指令的解析private void ret(Instruction ins) { ActiveOperand ao = currentFrame().popActiveOperand(); stack.pop(); currentFrame().pushActiveOperand(ao); }最后，停机指令 halt 的作用就是，输出当前运算堆栈中栈顶元素的值，简单起见，直接输出到控制台，然后置指令指针为无穷大，结束运算。如清单 28 所示。清单 28. halt 指令的解析private Object halt(Instruction ins) { ActiveOperand ao = currentFrame().popActiveOperand(); System.out.println("compute result : " + ao.getValue()); currentFrame().setIr(Integer.MAX_VALUE); return ao.getValue(); }至此虚拟机的实现全部完成，更全面的实现请参考附件示例代码中 AbstractMachine、Frame 和 ActiveOperand 这三个 Java 类。虚拟机完成计算的完整过程体现在 TestMachine.java 中，至此我们把之前做的所有工作都串了起来。首先使用词法分析器完成词法记号的分离，接着使用语法分析器完成语法分析和创建抽象语法树，然后使用类型检查器检查类型是否合法，之后使用代码生成器生成中间代码，最终使用虚拟机解释执行中间代码完成计算。词法分析、语法分析、抽象语法树创建、类型检查、中间代码生成和虚拟机解释执行这 6 个步骤，构成了一个整体，各自发挥作用，共同完成了领域语言的计算。详细的实现请参考示例代码中的 TestMachine.java。结束语本文中我们结合 ANTLR 完成了语言定义、类型检查和代码生成，将语言编译为一种中间代码，并实现了一个基于堆栈的虚拟机，解释中间代码，完成运算。整个工作一方面展示了 ANTLR 在领域语言处理方面的强大能力和使用技巧；另一方面，我们的工作也提供了一种实现领域语言的思路。将语言的实现分为前端和后端，前端完成语言定义、类型检查和中间代码生成，后端完成中间代码的解释执行。在整个流程中，中间代码是前端和后端的纽带，后端相对稳定，一次实现后可以反复使用；而面对复杂多变的业务规则，前端的领域语言可能千变万化，将这些多变的语言编译为统一的中间代码，势必减少领域语言的开发工作量，提高开发效率和质量。下载资源示例代码 (antlr_app.zip | 1907KB)相关主题使用 Antlr 开发领域语言，作者的另一篇关于 Antlr 的文章，介绍了 Antlr 在领域语言开发方面的基本知识，包括 Antlr 的安装，AntlrWorks 的使用等。Antlr 全球站点，有关于 Antlr 的最全面的参考资料。包含大量介绍 Antlr 的文章和应用范例。The Definitive ANTLR Reference（Building Domain-Specific Languages）: Terence Parr 最新的 Antlr 著作，Antlr 开发者必备的参考书。编译原理第二版（Alfred V. Aho 等著，赵建华 等译，2009，机械工业出版社），编译原理方面的权威教材；类型检查和复杂语句（if、while）的编译方案参考了该书。The JavaTM Virtual Machine Specification Second Edition，Java 虚拟机规范第二版；将语言编译为中间代码，由虚拟机解释执行的想法来源于 Java 虚拟机。Domain Specific Languages（Martin Fowler，Addison-Wesley，2010 年）：Fowler 的新书。介绍了领域语言的若干特性。developerWorks Java 技术专区：这里有数百篇关于 Java 编程各个方面的文章。说明：本文基于 ANTLR v3 版本编写（使用了树文法 Tree Grammar 和 output=AST 等特性）。ANTLR v4 及更高版本已移除对树文法的直接支持，推荐使用 Listener 或 Visitor 模式遍历语法树。文中部分外部链接（如 IBM DeveloperWorks）可能因网站归档而失效，示例代码请以实际下载资源为准。
编者注：本文为历史博文归档；涉及 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 ')' # parenExpr | expr ('*'|'/') expr # multOrDiv | expr ('+'|'-') 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') ('+'|'-')? 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 CalculatorVisitor.java使用 Visitor 模式Visitor 的使用是最为简单方便的，继承 CalculatorBaseVisitor 类即可，内部的方法与 .g4 文件定义相对应，对照即可理解。public class MyCalculatorVisitor extends CalculatorBaseVisitor<Object> { @Override public Object visitParenExpr(CalculatorParser.ParenExprContext ctx) { return visit(ctx.expr()); } @Override public Object visitMultOrDiv(CalculatorParser.MultOrDivContext ctx) { Object obj0 = ctx.expr(0).accept(this); Object obj1 = ctx.expr(1).accept(this); if ("*".equals(ctx.getChild(1).getText())) { return (Float) obj0 * (Float) obj1; } else if ("/".equals(ctx.getChild(1).getText())) { return (Float) obj0 / (Float) obj1; } return 0f; } @Override public Object visitAddOrSubstract(CalculatorParser.AddOrSubstractContext ctx) { Object obj0 = ctx.expr(0).accept(this); Object obj1 = ctx.expr(1).accept(this); if ("+".equals(ctx.getChild(1).getText())) { return (Float) obj0 + (Float) obj1; } else if ("-".equals(ctx.getChild(1).getText())) { return (Float) obj0 - (Float) obj1; } return 0f; } @Override public Object visitFloat(CalculatorParser.FloatContext ctx) { return Float.parseFloat(ctx.getText()); } }实现了 Visitor 之后，就可以完成一个简单的计算器了。import org.antlr.v4.runtime.ANTLRInputStream; import org.antlr.v4.runtime.CommonTokenStream; public class Driver { public static void main(String[] args) { String query = "3.1 * (6.3 - 4.51) + 5 * 4"; CalculatorLexer lexer = new CalculatorLexer(new ANTLRInputStream(query)); CalculatorParser parser = new CalculatorParser(new CommonTokenStream(lexer)); CalculatorVisitor visitor = new MyCalculatorVisitor(); System.out.println(visitor.visit(parser.expr())); // 25.549 } }集成 MavenANTLR 4 提供了 Maven Plugin，可以通过配置来进行编译。语法文件 .g4 放置在 src/main/antlr4 目录下即可，配置依赖的 antlr4 和 plugin 即可。生成 Visitor 在 Plugin 配置 visitor 参数为 true 即可。注意：ANTLR 4 的库版本要与 Plugin 版本对应，ANTLR 4 对生成文件用的版本与库本身的版本会进行对照，不匹配会报错。... <properties> <antlr4.version>4.7.2</antlr4.version> </properties> <dependencies> <dependency> <groupId>org.antlr</groupId> <artifactId>antlr4</artifactId> <version>${antlr4.version}</version> </dependency> </dependencies> ... <build> <plugins> <plugin> <groupId>org.antlr</groupId> <artifactId>antlr4-maven-plugin</artifactId> <version>${antlr4.version}</version> <configuration> <visitor>true</visitor> </configuration> <executions> <execution> <id>antlr</id> <goals> <goal>antlr4</goal> </goals> </execution> </executions> </plugin> </plugins> </build> ...总结本文较为简单地说了一个计算器的例子，只介绍了 Visitor 的大致使用方法，最后还介绍了 Maven Plugin 的使用方法。笔者还在学习 ANTLR 4 以及编译原理，想用好语法生成器工具，还是需要对编译原理有一定的理解。本文的计算器实现代码可以在 这里 上找到。参考文档antlrANTLR 4 权威指南ANTLR 快餐教程 (2) - ANTLR 其实很简单版本说明工具版本：文中命令行示例使用的是 ANTLR 4.5 版本 Jar 包，而 Maven 配置示例使用的是 4.7.2 版本，实际使用时请保持版本一致。API 变更：代码示例中使用的 ANTLRInputStream 在较新版本中已标记为 deprecated，建议在新项目中查阅官方文档使用 CharStream 相关 API。时效性：外部链接与图片资源可能随时间失效，请以官方最新文档为准。
一种可扩展的表达式解析及计算方法
一种可扩展的表达式解析及计算方法概述在应用软件开发领域，表达式计算有着非常广泛的应用。例如，在报表开发中，经常为用户提供公式输入功能，从而实现更灵活的报表汇总；在工作流应用软件中，经常利用逻辑条件进行动态配置，从而提供更加灵活的流程配置；另外，在某些 UI 开发中，需要通过某个属性的表达式计算结果来动态控制 UI 组件的显示。所有这些应用都可以归结为一个通用模型，即表达式的解析以及计算。本文旨在提供一种可扩展的表达式解析及其计算方法。表达式解析的一般条件及因素本文所讲的表达式是一种以一定的运算规则组合所表达的字符串；另外，通过解析表达式字符串并以其代表的运算规则可以得到一个结果。表达式解析一般需要满足下列条件：支持的操作符集合操作符的优先级操作符所代表的操作规则集合支持的分隔符集合以及分隔符所代表的意义支持的数据类型集合语法约束，如命名规则、分隔符所代表的语法规则等表达式解析除了以上必须满足的条件之外，在有些表达式环境中，可能还支持函数、变量。结合本文所要解决的问题，如下列出可选的条件：支持的内部函数集合支持的内部全局变量支持函数定制支持自定义变量支持函数以及操作符重载以上最后三个可选条件，是一个表达式解析引擎的可扩展支持需要满足的条件。编译原理简述一般的编译过程主要包括词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成，如下图所示。其中，词法分析主要任务是输入源程序，对构成源程序的字符进行扫描和分解，识别出一个一个的单词。单词是语言中具有独立意义的最基本结构。一般这些单词包括程序语言所支持的保留字、数据类型、操作符、分隔符以及程序定义的标识符、常量等。语法分析的主要任务是在词法分析的基础上，根据语言的语法规则把单词序列组合成各类语法单位（一般表示成语法树）。语义分析的主要任务是进一步分析语法结构正确的程序是否符合源程序的上下文约束、运算相容性等语义约束规则。图 1. 编译一般过程上述只是非常简要地介绍了一般的编译原理知识，详细知识需要参考编译原理相关的书籍和文档。对于本文所讲的表达式解析，笔者认为其与程序编译具有本质上的相似，只是在问题的复杂性上会简单很多。表达式解析同样需要首先把输入的表达式字符串分解成一个一个的单词，然后把单词序列组合成语法单位，最后依据表达式的语言环境所定义的语义约束对这些语法单位进行分析计算。因此，我们可以将有选择的程序编译基本方法运用到表达式解析上。中缀表达式、前缀表达式与后缀表达式前缀表达式（又叫波兰式）是一种不含括号的 表达式，并且将 运算符 放在 操作数 前面的表达式。对于一个前缀表达式的求值而言，所有的计算按运算符出现的顺序，严格从左向右进行。后缀表达式（又叫逆波兰式）也是一种不含括号的 表达式，并且 运算符 放在操作数的后面。对于一个后缀表达式的求值而言，所有的计算按运算符出现的顺序，严格从左向右进行。中缀表达式是一个通用的算术或逻辑公式表示方法，操作符是以中缀形式处于操作数的中间。中缀表达式不容易被计算机解析，但它符合人们的普遍用法。与前缀或后缀记法不同的是，中缀记法中括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来，用于指示运算的次序。前缀表达式和后缀表达式是一种十分有用的表达式，它可以依靠简单的操作就能得到运算结果的表达式。通常解析程序一般都会将中缀表达式转换为前缀表达式或后缀表达式，方便表达式计算。表达式树前面讲过，表达式是一种以一定的运算规则组合所表达的字符串。每一个表达式的基本组成单位都是由一个操作符和操作数组成的操作单位，操作数可以是一个或者多个。所以一个表达式基本操作单位可以表示为一棵树，下图所示为一个 N 元操作符的树表示，该操作符代表的运算需要 N 个操作数：图 2. N 元操作符的树表示每个基本操作单位可以表示为一棵树，每个操作单位的运算结果为其它操作符的一个操作数，从而一个含有多个操作符的表达式可以表示成一棵更大的树，其每一棵子树皆为一个子表达式。如表达式 a*b+c/d 可以表示为：图 3. 表达式 a*b+c/d 的树表示从编译原理的知识可以得出这样一个结论：一个表达式可能推导出多棵树，呈现出二义性。因此，需要通过对表达式的语言环境增加语义约束规则，消除二义性，保证从表达式只能推导出唯一的表达式树。通常的语义约束规则包括设定操作符的优先级、括号的使用等。表达式解析引擎的基本结构设计图 4. 解析引擎的基本结构设计查看大图如 图 4 所示，展示了一个表达式解析引擎的基本结构设计。整个表达式解析引擎内部结构主要包括：表达式解析引擎的语言环境定义、操作符处理器管理、表管理器、表达式解析器、表达式校验器、表达式解析异常定义等。本文后续部分将详细解释。表达式解析引擎实现说明定义表达式解析引擎的语言环境对于表达式解析，首先必须定义表达式所存在的语言环境。主要包括表达式所支持的数据操作、数据类型、合法的操作符集合、保留字、分隔符等。另外还包括内部自定义并可供表达式引用的全局变量、函数等。所有这些语言环境因素都通过表格管理器进行统一管理，如 图 4 所示 TableManager 类。表格管理器主要用于符号管理，主要管理如下四类符号数据：操作符管理操作符管理主要管理表达式所支持的所有操作符，包括内置操作符以及用户自定义的操作符。其中，用户自定义的操作符属于表达式解析引擎中可扩展特性，需要注册到表格管理器，以便表达式引用。操作符具备一般的符号特性，包括操作符标识字符串、操作数以及操作数个数。另外，不同的操作符具有不同的操作优先级。语法保留字管理语法保留字管理主要存储表达式所支持的各种关键字、分隔符等，属于表达式构成的一部分。如 (、)、,、const、var 等。函数管理函数管理主要管理表达式所支持的所有函数，包括内置函数以及用户自定义的函数。其中，用户自定义的函数属于表达式解析引擎中可扩展特性，需要注册到表格管理器，以便表达式引用。变量管理变量管理主要管理表达式解析引擎内置的全局变量以及用户自定义的变量。其中，用户自定义的变量属于表达式解析引擎中可扩展特性，需要注册到表格管理器，以便表达式引用。对于表格管理中的可扩展特性将在本文稍后部分讲解。下面给出符号定义结构示例：图 5. 符号定义结构查看大图Symbol 类定义了表格管理中一般性符号，包括标识字符串 identifier 和转义字符串 escape 两个属性。OperationSymbol 类定义了一般性的操作符号，包括操作数个数 dimension 以及操作数集合 operands。前面讲过，表达式中任何操作都可以抽象归纳为操作符以及零或多个操作数两部分。本文涉及的操作主要包括基本操作符、函数以及取值符所代表的操作。当然，操作数包括数据类型、数据值等属性，用 Variable 类型的对象表示。需要注意的是，任何一个表达式一般都是一个字符串。所以，表达式解析过程需要正确解析字符串表达式中各个操作数的数据类型。Operator 类定义了表达式解析引擎中基本的操作符号，如 +、-、*、/、&&、|| 等。Operator 类包括操作符优先级 priority 以及操作处理器 handler。Function 类代表函数，包括函数实现类 clazz 属性以及用于判断函数是否静态的 isStatic 属性。ValueOperator 类定义了表达式中的取值操作符。因为一个解析引擎通常仅仅只有一个取值操作符，所以该类属于一个单例模型，包括一个 ValueOperator 对象实例属性以及取值操作符处理器 handler。本节阐述了表格管理器的内容，以下 清单 1 所示给出一个表格管理器示例，简要列出表格管理器属性及操作。清单 1. 表格管理器public class TableManager { // 管理 / 存储表达式语言环境涉及的操作符，包括解析引擎保留操作符以及用户注册的自定义操作符 private static Hashtable<String, Operator> tblOperator = new Hashtable<String, Operator>(); // 管理 / 存储表达式语言环境涉及的语法关键字 private static Hashtable<String, Symbol> tblSyntaxKey = new Hashtable<String, Symbol>(); // 管理 / 存储表达式语言环境定义的函数，包括解析引擎内部函数以及用户注册的自定义函数 private static Hashtable<String, Function> tblFunction = new Hashtable<String, Function>(); // 管理 / 存储表达式语言环境定义的变量，包括解析引擎内部全局变量以及用户注册的自定义变量 private static Hashtable<String, Variable> tblGlobalVar = new Hashtable<String, Variable>(); // 标示符最大长度，方便表达式解析过程中的回溯处理 private static int MAX_IDENTIFIER_LEN = 1; // 操作符是否可被重写处理器 private static boolean isOverridable = false; // 根据标示符号字符串取得操作符 public static Operator getOperator(String identifier) { // 省略代码 .... } // 根据标示符号字符串取得函数 public static Function getFunction(String identifier) { // 省略代码 .... } // 根据标示符号字符串取得标示符 public static Symbol getIdentifier(String identifier) { // 省略代码 .... } // 注册操作符 public static boolean regOperator(Operator oper) { // 省略代码 .... } // 注册语法关键字 public static boolean regSyntaxKeys(Symbol identifier) { // 省略代码 .... } // 注册函数 public static boolean regFunction(Function func) { // 省略代码 .... } // 判断是否存在某标示符 public static boolean existIdentifier(String identifier) { // 省略代码 .... } // 判断是否存在某操作符 public static boolean existOperator(String identifier) { // 省略代码 .... } // 判断是否存在某函数 public static boolean existFunc(String identifier) { // 省略代码 .... } // 取得操作符优先级 public static int getPriority(String identifier) { // 省略代码 .... } // 取得操作符定义的操作数个数 public static int getDimension(String identifier) { // 省略代码 .... } // 取得最大标示符长度 public static int getMaxIdentifierLen() { return MAX_IDENTIFIER_LEN; } // 取得单词类型 public static TokenType getTokenType(String token) { // 省略代码 .... } // 判断是否为取值操作符 public static boolean isValueOperator(String token) { // 省略代码 .... } // 根据变量名取得已注册的变量 public static Variable getVariable(String varName) { // 省略代码 .... } // 判断是否存在某变量 public static boolean existVariable(String varName) { // 省略代码 .... } // 注册变量 public static boolean regVariable(Variable var) { // 省略代码 .... } }操作符处理器以及可扩展的问题在表达式解析过程中，除了正确解析出各种操作符以及操作数，还需要能依据这些操作符所代表的操作语义正确地进行数据的操作处理。在本文的"表达式解析的一般条件及因素"部分，提出了三个可选条件作为解析引擎的扩展支持，从而增强解析引擎的功能。本文所提出的设计方案主要采用 Bridge 设计模式和反射模式实现操作符处理以及扩展支持。图 6. 操作符处理器及可扩展处理结构查看大图如 图 6 所示，提供了一个操作符处理器及可扩展处理的设计结构。组成表达式的操作单元主要包括基本操作符运算、变量取值、函数调用等。在 图 7 所示的结构中，表格管理器 TableManager 主要用于管理各种操作符、函数、变量等并以表的形式进行存储。至于表的实现，具体有很多种方法，如利用哈希表等。在基本操作符 Operator 和取值操作符 ValueOperator 的定义结构中，都定向聚集关联了一个操作处理器对象 handler。Operator 类的操作处理器类型为 IExpressionHandler 接口类型，ValueOperator 类的操作处理器类型为 IValueOperatorHandler 接口类型。通过该设计方法，除了表达式解析引擎内部实现的缺省操作处理器，用户同样可以通过实现 IExpressionHandler 接口和 IValueOperatorHandler 接口，向表管理器 TableManager 中注册个性化业务相关的操作符处理以及取值处理。具体如下：操作符处理：用户可以自定义操作符或者进行操作符重载。首先，用户通过实现 IExpressionHandler 接口实现用户第三方操作符处理；然后，定义或重载操作符对象，并且引用指向用户实现的第三方操作符处理器；最后，通过 TableManager 提供的注册方法注册该操作符。取值符处理：实现解析引擎内部的全局变量取值以及第三方业务相关的取值处理。对于全局变量的取值，首先需要注册自定义的全局变量，从而保证在表达式的计算过程中能通过查找表管理器 TableManager 中的全局变量表来获得变量的值。对于第三方业务相关的取值处理，首先需要实现 IValueOperatorHandler 接口来实现第三方取值处理，然后通过表管理器 TableManager 注册第三方处理器到取值符中（前面讲过，解析引擎通常仅仅只有一个取值操作符，所以单独注册取值处理器到取值操作符中）。函数处理：实现解析引擎内部函数调用以及第三方自定义函数调用。函数处理主要通过在运行时状态下利用反射方法动态调用。表达式可利用的每个函数都需要通过表管理器 TableManager 注册到函数表中。在表达式解析计算过程中，当遇到函数调用时，函数处理器通过查询函数表得到函数相关信息，然后利用这些函数信息反射调用函数，从而得到函数的执行结果。如 清单 2 所示，为一个加法处理器代码示例。该加法处理器能处理整型数字、浮点数以及字符串相加。清单 2. 加法 + 操作符处理器/** * 加法操作符处理器，支持数值相加以及字符串相加 * @author Wang Jianguang */ public class PlusOperatorHandler implements IExpressionHandler { /* * 加法操作符处理器方法 * @param oper : 操作符号 * @return : Variable 类型的操作符处理结果 */ public Variable operate(OperationSymbol oper) { Variable res = null; if (!validate(oper)) { return res; } String identifier = oper.getIdentifier(); if (!identifier.equals("+")) { return res; } Variable[] operands = oper.getOperands(); if (operands.length != 2) { return res; } boolean isStrOp = containStrOperand(operands); Object val0 = operands[0].getValue(); Object val1 = operands[1].getValue(); if (isStrOp) { res = new Variable(DataType.STRING); res.setValue(val0.toString() + val1.toString()); } else { boolean isFloatResult = operands[0].getType() == DataType.FLOAT || operands[1].getType() == DataType.FLOAT; if (isFloatResult) { float fvalue = Float.parseFloat(val0.toString()) + Float.parseFloat(val1.toString()); res = new Variable(DataType.FLOAT); res.setValue(fvalue); } else { int ivalue = Integer.parseInt(val0.toString()) + Integer.parseInt(val1.toString()); res = new Variable(DataType.INT); res.setValue(ivalue); } } return res; } }表达式解析及计算方法要正确解析表达式，首先必须通过词法分析能识别出表达式中一个一个的单词，这些单词包括基本操作符、关键字、分隔符和操作数，还可能包括函数、变量等。一般给定一个待计算的表达式，通常是符合某种语言环境所提供的语法结构；往往这种语法并不一定适合计算机内部计算，或者说，对计算机计算而言比较复杂。所以，对于表达式的分析与计算，通常需要把表达式转换为可以依靠简单的操作就能得到运算结果的表达式。前面讲过，通常解析程序一般都会将中缀表达式转换为前缀表达式或后缀表达式，方便表达式计算。本文正是将表达式转换为后缀表达式来进行分析与计算的。图 7. 表达式解析与计算过程如 图 7 所示，展示了表达式的解析与计算过程。下面就该过程的每部分进行简要说明。词法分析：识别出表达式中合法的单词，一般利用回溯算法进行分析，并利用表管理器来辅助识别。生成后缀表达式栈：将表达式（一般为中缀表达式）转换为后缀表达式，并以栈结构进行存储，方便后续构造表达式树。清单 3. 生成后缀表达式栈/** * 构造后缀表达式栈。通过词法分析，获得各种类别的单词，从而依据语法规则构造 * 后缀表达式栈 * @param expr 输入表达式 * @return 由各个单词构成的表达式栈 */ public Stack<String> buildPostExpressionStack(String expr) { Stack<String> retStack = new Stack<String>(); Stack<String> stack = new Stack<String>(); stack.push("ENDFLAG"); int iPointer = 0; while (iPointer < expr.length()) { // 词法分析，得到单词 String token = this.getToken(expr, iPointer); int step = token.length(); if (token.equals("(")) { stack.push(token); } else if (TableManager.existOperator(token)) { // 分析操作符 String lastToken = stack.lastElement(); while (TableManager.existFunc(lastToken) || TableManager.isValueOperator(token) || TableManager.getPriority(lastToken) >= TableManager.getPriority(token)) { retStack.push(stack.pop()); lastToken = stack.lastElement(); } stack.push(token); } else if (TableManager.existFunc(token) || TableManager.isValueOperator(token)) { // 分析函数或取值符号 stack.push(token); } else if (token.equals(",")) { while (!stack.lastElement().equals("(")) { retStack.push(stack.pop()); } } else if (token.equals(")")) { while (!stack.lastElement().equals("(")) { retStack.push(stack.pop()); } stack.pop(); String lastToken = stack.lastElement(); if (TableManager.existFunc(lastToken)) { retStack.push(stack.pop()); } } else { retStack.push(token); } iPointer += step; } while (!stack.lastElement().equals("ENDFLAG")) { retStack.push(stack.pop()); } adjust(retStack); return retStack; }生成表达式树：前面讲过，一个含有多个操作符的表达式可以表示成一棵树。此过程正是利用此结论来构造一棵表达式树，方便后续的分析与计算结构。树的每个节点都保存每个操作符或操作数的相关信息。以树的结构存储表达式还方便扩展分析处理。如 清单 4 所示为生成表达式树代码。清单 4. 生成表达式树/** * 构造表达式树。首先通过词法分析构造表达式栈，然后构造表达式树。 * @param expr 输入表达式 * @return 表达式树 */ public TreeNode buildTree(String expr) { Stack<String> postExprStack = buildPostExpressionStack(expr); Stack<String> tmpStack = reverseStack(postExprStack); Stack<TreeNode> nodeStack = new Stack<TreeNode>(); while (!tmpStack.isEmpty()) { String token = tmpStack.pop(); TreeNode node = new TreeNode(token); TokenType nodeType = TableManager.getTokenType(token); node.setNodeType(nodeType); if (nodeType == TokenType.FUNCTION || nodeType == TokenType.OPERATOR || nodeType == TokenType.VARIABLE) { int dimension = TableManager.getDimension(token); TreeNode[] children = new TreeNode[dimension]; for (int j = dimension - 1; j >= 0; j--) { children[j] = nodeStack.pop(); } node.setChildren(children); nodeStack.push(node); } else { nodeStack.push(node); } } TreeNode root = nodeStack.pop(); return root; }分析与计算：该过程结合表管理器，通过递归分析与计算表达式树，得到表达式计算结果。清单 5. 表达式分析与计算/** * 计算表达式。通过递归解析计算表达式树得到计算结果。 * @param expr 输入表达式 * @return 计算结果 */ public Variable computeExpression(String expr) { Variable value = null; if (expr == null) { return value; } // 构造表达式树 TreeNode tree = buildTree(expr); if (tree == null) { return value; } // 解析计算表达式树 value = computeSubTree(tree); return value; } /** * 解析计算表达式子树 * @param node 子树根节点 * @return 子树计算结果 */ public Variable computeSubTree(TreeNode node) { Variable varRet = null; if (node == null) { return null; } String value = node.getValue(); if (!TableManager.existOperator(value) && !TableManager.existFunc(value) && !TableManager.isValueOperator(value)) { return ParserUtil.getValue(value); } TreeNode[] children = node.getChildren(); if (children == null || children.length == 0) { return ParserUtil.getValue(value); } Variable[] operands = new Variable[children.length]; for (int i = 0; i < children.length; i++) { operands[i] = computeSubTree(children[i]); } OperationSymbol op = getOperationSymbol(node, value); if (op != null) { op.setOperands(operands); varRet = op.operate(); } return varRet; }表达式校验器：在表达式分析与计算的每一个过程中，都需要利用表达式校验器来保证其数据的合法性，如操作符是否合法、语法是否正确、分析得到的操作数数据类型是否正确、函数的参数类型是否正确等等。每当遇到校验失败的情况，都会抛出各种类型的异常，并中止解析过程，表示解析失败。下面给出一个表达式解析引擎应用示例，如 清单 6 所示。清单 6. 表达式解析引擎应用public class ExpressionParserTester { /* * 初始化：注册用户自定义的函数以及变量到表达式解析引擎 */ public static void init() { TableManager.regFunction( new Function("test", "com.gavin.parser.expression.test.Test", new DataType[]{DataType.INT, DataType.INT, DataType.INT}, DataType.INT, true)); TableManager.regFunction( new Function("test2", "com.gavin.parser.expression.test.Test", new DataType[]{DataType.STRING}, DataType.INT, true)); TableManager.regVariable(new Variable(DataType.INT, "GB_VAR", 31)); } public static void main(String[] args) { init(); String expr = "1+2*test($GB_VAR,test((1+3)+4*(5+6 ),2,(2+3)%2), test(-10,10,11*(1+test(3,4,5))))+test2('300')*3"; TExprParser parser = TExprParser.getInstance(); // 测试 1: 建立后缀表达并打印 String postExp = parser.buildPostExpression(expr); System.out.println(postExp); // 测试 2: 解析以及计算表达式并打印结果 String value = parser.parse(expr); System.out.println(value); } public static int test(int a, int b, int c) { return a + b + c; } public static int test2(String param) { return Integer.valueOf(param).intValue(); } }总结本文以一种循序渐进的方式阐述了一种表达式解析与计算方法，并提供了一个支持可扩展的表达式解析与计算的设计实例。首先本文提出定义了表达式的一般模型及相关概念；然后从引入编译原理一般过程开始，逐步介绍了表达式的三种类型及表达式树的概念。最后提供一个设计实例来介绍表达式解析与计算的方法与步骤。笔者希望籍以本文为读者抛砖引玉，在表达式解析方面能提供些许指引。相关主题《表达式计算：分析与设计》：Nikola Stepan，文章分析了 W3Eval 与经典表达式算法所不同的求值步骤，并通过展示代码片段详细地介绍其中的算法逻辑。《快速精确的对数学表达式求值》：介绍了如何基于 Windows 平台进行软件开发。《利用 Java 实现组合式解析器》：孙鸣，邓辉，文章介绍了如何基于 DSL 设计思想来构建一个字符串解析器，并提供了一个用该解析器识别 H.248 协议中 NAME 语法的具体实现。《Java 性能优化之 String 篇》：杨博文，应乐年，杨雯雯，文章从 String 在 JVM 的存储结构出发，介绍了 Java String API 使用中的性能问题以及对应的解决方法。更多编译原理知识可参考 Alfred V.Aho, Monica S.Lam, Ravi Sethi, Jeffrey D.Ullman 编写的《编译原理》一书。说明：本文涉及的部分技术实现（如 Java Hashtable）及外部链接（IBM DeveloperWorks）可能随时间推移已过时，仅供参考学习原理。
java公式解析器学习与开发（2）——前缀表达式
1 释义前缀表达式即 前序表达式。它是一种不含括号的 算术表达式，特点是将 运算符 写在前面，操作数 写在后面。为纪念其发明者波兰数学家 Jan Lukasiewicz，也称为“波兰式”。例如，- 1 + 2 3 等价于 1-(2+3)。2 求值方法对于前缀表达式的求值，需遵循从右至左扫描表达式的原则：从右边第一个字符开始判断。如果当前字符是数字，则一直记录到数字串末尾。如果是 运算符，则将右边离得最近的两个“数字串”作相应运算，以此作为一个新的“数字串”并记录下来。一直扫描到表达式的最左端，最后运算的值即为表达式的值。示例： 前缀表达式 - 1 + 2 3 的求值过程：扫描到 3 时，记录数字串 3。扫描到 2 时，记录数字串 2。扫描到 + 时，将 + 右移作为相邻两数字串的 运算符，记为 2+3，结果为 5，记录新数字串 5。继续向左扫描，扫描到 1 时，记录数字串 1。扫描到 - 时，将 - 右移作为相邻两数字串的运算符，记为 1-5，结果为 -4。所以表达式的值为 -4。3 公式用法前缀表达式是一种十分有用的表达式，它将中缀表达式转换为可以依靠简单操作就能得到运算结果的表达式。例如，(a+b)*(c+d) 转换为 *,+,a,b,+,c,d。优势： 只用两种简单的操作（入栈和 出栈）就可以解决任何中缀表达式的运算。运算方式：如果当前字符（或字符串）为数字或 变量，则压入栈内。如果是 运算符，则将栈顶两个元素弹出栈外并作相应运算，再将结果压入栈内。当前缀表达式扫描结束时，栈里的就是中缀表达式运算的最终结果。4 相关例子a+b ---> +,a,ba+(b-c) ---> +,a,-,b,ca+(b-c)*d ---> +,a,*,-,b,c,da=1+3 ---> =,a,+,1,35 转换算法将中缀表达式转换为前缀表达式的算法步骤如下：构造栈：首先构造一个运算符栈（也可放置括号），运算符（以括号分界点）在栈内遵循越往栈顶优先级不降低的原则进行排列。扫描表达式：从右至左扫描中缀表达式，从右边第一个字符开始判断：数字：如果当前 字符 是数字，则分析到数字串的结尾并将数字串直接输出。运算符：如果是运算符，则比较优先级。如果当前运算符的优先级大于等于栈顶运算符的优先级（当栈顶是括号时，直接入栈），则将运算符直接入栈。否则，将栈顶运算符 出栈 并输出，直到当前运算符的优先级大于等于栈顶运算符的优先级（当栈顶是括号时，直接入栈），再将当前运算符入栈。括号：如果是括号，则根据括号的方向进行处理。如果是右括号 )，则直接入栈。如果是左括号 (，则遇左括号前将所有的运算符全部 出栈 并输出，遇左括号后将左右的两括号一起删除。结束处理：重复上述操作直至扫描结束，将栈内剩余运算符全部 出栈 并输出，再逆缀输出字符串。中缀表达式也就转换为前缀表达式了。6 实例分析将中缀表达式 1+((2+3)*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+-)*(，参考①(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 运算符优先级)：直接入栈(：遇 ) 前，将运算符全部出栈并输出；遇 ) 后，将两括号一起删除①+、-：优先级 1*、/、%：优先级 2^：优先级 3
简介还记得在您的第一台科学计算器上使用逆波兰表示法（RPN）时的挣扎吗？W3Eval 并非旨在让您信赖的 HP-41 计算器更易用，正如它的名称所暗示，它是一个仅运行于 Web 的表达式求值程序。但它的确提供了一种方法——一种人类更易于遵循的、对表达式一步一步的求值方式。W3Eval 的方法与传统计算器不同，却和人类的计算方式一致。当您用传统的计算器计算时，每输入一个新数，前一个数就看不到了。如果在输入一个长表达式中出了错，就得全部重来。有了 W3Eval，您就能看到参与计算的所有东西，还能轻松地编辑表达式。它独特的能力（一步一步地对表达式求值）非常容易实现，因为用户能看到求值的每一步，包括临时结果。本文将让您从头至尾认识 W3Eval 功能性的要点；您将看到一些用于表达式求值的代码。不过，我们还是先看看表达式求值的经典算法，这样您就会明白 W3Eval 方法的差异究竟有多少。表达式求值的经典算法编写代码对算术表达式求值的经典方法由 Donald Knuth 描述于 1962 年（请参阅 参考资料）。Knuth 将此概括为三个步骤：对中缀表达式进行语法分析中缀表达式到后缀表达式的转换对后缀表达式求值注意到我们谈到的这个经典算法有些简化：算术表达式只包含操作数、二元操作符和一种括号。此外，对于每个操作数和操作符，只用单个字符表示，使语法分析直观。表达式表示法算术表达式中最常见的表示法形式有 中缀、前缀 和 后缀 表示法。中缀表示法是书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。中缀表示法 中缀表示法是算术表达式的常规表示法。称它为 中缀 表示法是因为每个操作符都位于其操作数的中间，这种表示法只适用于操作符恰好对应两个操作数的时候（在操作符是二元操作符如加、减、乘、除以及取模的情况下）。对以中缀表示法书写的表达式进行语法分析时，需要用括号和优先规则排除多义性。Syntax: operand1 operator operand2 Example: (A+B)*C-D/(E+F)前缀表示法 前缀表示法中，操作符写在操作数的前面。这种表示法经常用于计算机科学，特别是编译器设计方面。为纪念其发明家 — 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)+C Right associativity : A^B^C = A^(B^C)转换过程包括用下面的算法读入中缀表达式的操作数、操作符和括号：初始化一个空堆栈，将结果字符串变量置空。从左到右读入中缀表达式，每次一个字符。如果字符是操作数，将它添加到结果字符串。如果字符是个操作符，弹出（pop）操作符，直至遇见开括号（opening parenthesis）、优先级较低的操作符或者同一优先级的右结合符号。把这个操作符压入（push）堆栈。如果字符是个开括号，把它压入堆栈。如果字符是个闭括号（closing parenthesis），在遇见开括号前，弹出所有操作符，然后把它们添加到结果字符串。如果到达输入字符串的末尾，弹出所有操作符并添加到结果字符串。后缀表达式求值对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中，不需要括号，而且操作符的优先级也不再起作用了。您可以用如下算法对后缀表达式求值：初始化一个空堆栈从左到右读入后缀表达式如果字符是一个操作数，把它压入堆栈。如果字符是个操作符，弹出两个操作数，执行恰当操作，然后把结果压入堆栈。如果您不能够弹出两个操作数，后缀表达式的语法就不正确。到后缀表达式末尾，从堆栈中弹出结果。若后缀表达式格式正确，那么堆栈应该为空。W3Eval：一种新的方法W3Eval 的方法与上面概括的经典算法不同。不是把中缀表达式转换为后缀表示法；恰恰相反，它对中缀表达式直接求值。这种方法比传统方法稍微复杂了些，但它支持一步一步的求值，在执行时您能看到每一步。求值过程类似于手工计算：如果表达式中包含括号，先求嵌套最深的括号对中的子表达式的值。所有括号内的子表达式都求值完毕后，表达式的其它部分再求值。求值过程分为三个步骤：表达式语法分析表达式检查一步一步的求值表达式语法分析W3Eval 的数学表达式由数字、变量、操作符、函数和括号组成。除了缺省的十进制计数制外，W3Eval 还支持二进制、八进制和十六进制。这些以其它计数制计数的数必须以 # 开头，并紧跟 b、o 或者 h 来分别表示二进制、八进制或十六进制。W3Eval 的变量是不限长度的大写字母和数字序列，其首字符必须是字母。W3Eval 有一些预定义的变量，不过它也支持用户定义的变量。W3Eval 支持带有固定或不定数量自变量的函数。函数可分为以下几组：三角函数（sin、cos、tan、cot、sec、csc）反三角函数（asin、acos、atan、atan2、acot、asec、acsc）双曲线函数（sinh、cosh、tanh、coth、sech、csch）反双曲线函数（asinh、acosh、atanh、acoth、asech、acsch）指数函数（log、log2、log10、exp、exp2、exp10、sqrt、cur）组合学函数（Combinatoric）（comb、combr、perm、permr、var、varr）统计函数（sum、avg、min、max、stddev、count）其它（abs、ceil、fact、floor、pow、random、rint、round、sign、frac、hypot、deg、rad、trunc、int）W3Eval 对表达式进行 语法分析，也就是指它识别出表达式的算术成分，并将它们转化成语言符号（token），然后把它们放入向量。表达式一旦处于这种状态，就为下面两步做好了准备：表达式检查和求值。W3Eval 的 符号（token） 是算术表达式的组成部分；记号（mark） 是独立的字符，由 applet 使用，作为识别各种符号的内部标志。每种符号有唯一的 mark 与之对应。W3Eval 的表达式由表 1 所示的符号组成。表 1. W3Eval 的符号TokenMark类十进制数 Double二进制数 String十六进制数 String八进制数 String变量 Variable函数 Function操作符 Operator开括号 String闭括号 String逗号 String用以表示函数、操作符和变量类的定义如清单 1 所示：清单 1. Function、Operator 和 Variable 类的定义public class Function { public String function; public int number_of_arguments; public Function( String function, int number_of_arguments ) { this.function = function; this.number_of_arguments = number_of_arguments; } public String toString() { return function; } } public class Operator { public String operator; public byte priority; public Operator( String operator, byte priority ) { this.operator = operator; this.priority = priority; } public String toString() { return operator; } } public class Variable { public String variable; public double value; public Variable( String variable, double value ) { this.variable = variable; this.value = value; } public String toString() { return variable; } }Token 类如清单 2 所示。清单 2. Token 类public class Token { public Object token; public char mark; public int position; public int length; public Token ( Object token, char mark, int position, int length ) { this.token = token; this.mark = mark; this.position = position; this.length = length; } public String toString() { return token.toString() + " ; " + mark + " ; " + position + " ; " + length + "\n"; } }表达式检查检查正规表达式正确性的所有代码都在一个独立的类中。详细的表达式检查能够确定错误确切的类型和位置。错误检查有七类：括号检查。 W3Eval 的表达式可以包含三种括号：标准圆括号、方括号和花括号。如果表达式包含相同数量的开括号和闭括号，并且每个开括号与一个相应的同种闭括号相匹配，则表达式的括号语法正确。三种括号在语义上等价，如下面的代码段所示。清单 3. 三种括号import java.util.Stack; public class Parentheses_check { public static boolean is_open_parenthesis( char c ) { if ( c=='(' || c=='[' || c=='{' ) return true; else return false; } public static boolean is_closed_parenthesis( char c ) { if ( c==')' || c==']' || c=='}' ) return true; else return false; } private static boolean parentheses_match( char open, char closed ) { if ( open=='(' && closed==')' ) return true; else if ( open=='[' && closed==']' ) return true; else if ( open=='{' && closed=='}' ) return true; else return false; } public static boolean parentheses_valid( String exp ) { Stack s = new Stack(); int i; char current_char; Character c; char c1; boolean ret = true; for ( i=0; i < exp.length(); i++ ) { current_char = exp.charAt( i ); if ( is_open_parenthesis( current_char ) ) { c = new Character( current_char ); s.push( c ); } else if ( is_closed_parenthesis( current_char ) ) { if ( s.isEmpty() ) { ret = false; break; } else { c = (Character)s.pop(); c1 = c.charValue(); if ( !parentheses_match( c1, current_char ) ) { ret = false; break; } } } } if ( !s.isEmpty() ) ret = false; return ret; } }token 检查。 检查表达式语法。确保表达式所有部分都被认为是合法的。表达式开头的检查（请参阅 清单 4）。确保表达式从合法的符号开始。不可以用操作符、逗号或闭括号作为表达式的开始符。清单 4. 正确的表达式开头的检查private static boolean begin_check( Vector tokens, Range r, StringBuffer err ) { char mark; Token t; t = (Token)tokens.elementAt( 0 ); mark = t.mark; if ( mark == 'P' ) err.append( Messages.begin_operator ); else if ( mark == ')' ) err.append( Messages.begin_parenthesis ); else if ( mark == 'Z' ) err.append ( Messages.begin_comma ); else return true; r.start = 0; r.end = t.length; return false; }表达式末尾的检查。 确保表达式以合法符号结束。不可以用操作符、函数、逗号或开括号作为表达式结束符。符号序列的检查。 检查表达式中的符号序列。在下面的表格中，若 X 轴上的符号和 Y 轴上的符号对应的交界处用 X 作了记号，则相应 X 轴上的符号可以接在 Y 轴上符号的后面。表 2. 合法的符号序列_DBHOVFP()ZD______犠_犠犠B______犠_犠犠H______犠_犠犠O______犠_犠犠V______犠_犠犠F_______犠__P犠犠犠犠犠犠_犠__(犠犠犠犠犠犠_犠__)______犠_犠犠Z犠犠犠犠犠犠_犠__函数检查。 确保表达式中所有函数的自变量数量正确。逗号检查。 逗号只能用于分隔函数的自变量。若用于表达式其它地方，就不合法。一步一步的求值只有能顺利通过以上概括的所有检查的表达式，W3Eval 才求值。从而确保内建于 W3Eval 中的前提条件不会出现问题。后面的算法用于单步执行表达式求值：找出嵌入最深的那对括号。在这对括号中，找出优先级最高的操作符。若这对括号中没有操作符：如果表达式再不包含任何其它的括号，求值（过程）完成。如果表达式包含括号，但不包含操作符，则存在一个函数。对函数求值，然后转到步骤 5。获取操作数并执行运算。从向量中除去用过的符号并在同一位置放入结果。除去冗余括号。将向量中剩余的符号结合到字符串并在屏幕上显示结果。现在，我们将更为详细的查看算法的每一步，同时查看大部分有意思的代码片段。步骤 1： 为避免括号的处理，W3Eval 确定哪个子表达式处于嵌套最深的那对括号中。这项任务需要两步。第一步，W3Eval 必须找出第一个闭括号：清单 5. 找出第一个闭括号public static int pos_first_closed_parenthesis( Vector tokens ) { Token t; for ( int i=0; i<tokens.size(); i++ ) { t = (Token)tokens.elementAt( i ); if ( t.mark == ')' ) return i; } return 0; }第二步，找出与第一步找到的闭括号相匹配的开括号，如 清单 6 所示。清单 6. 找出匹配的开括号public static int pos_open_parenthesis( Vector tokens, int closed_parenthesis ) { int i; Token t; i = closed_parenthesis - 2; while ( i >= 0 ) { t = (Token)tokens.elementAt( i ); if ( t.mark == '(' ) { return i; } i--; } return 0; }步骤 2： 要实现求值的单步执行，W3Eval 在嵌套最深的那对括号中找出优先级最高的操作符。（操作符的优先级已硬编码到 applet 中；请参阅 参考资料 以获取完整的代码清单。）清单 7. 找出优先级最高的操作符public static int pos_operator( Vector tokens, Range r ) { byte max_priority = Byte.MAX_VALUE; int max_pos = 0; byte priority; String operator; Token t; for ( int i = r.start + 2; i <= r.end - 2; i++ ) { t = (Token)tokens.elementAt( i ); if ( t.mark != 'P' ) continue; priority = ((Operator)t.token).priority; operator = ((Operator)t.token).operator; if ( priority < max_priority || ( operator.equals("^") || operator.equals("**") ) && priority == max_priority ) { max_priority = priority; max_pos = i; } } return max_pos; }步骤 3： 如果表达式中不包含其它括号，求值的过程就完成。如果表达式包含括号，但不包含操作符，则存在需要求值的函数。清单 8. 检查是否还有其它操作符... int poz_max_op = pos_operator( tokens, range ); // if there are no operators if ( poz_max_op == 0 ) { if ( no_more_parentheses ) { return false; } else { double result; result = function_result( tokens, range.start - 1 ); function_tokens_removal( tokens, range.start - 1 ); t = new Token ( new Double(result), 'D', 0, 0 ); tokens.setElementAt( t, range.start - 1 ); parentheses_removal( tokens, range.start - 1 ); return true; } } ...步骤 4： 所有的操作符都是二元的，也就是说第一个操作数位于操作符之前，第二个操作数位于操作符之后。清单 9. 获取操作数并执行运算... double operand1, operand2; // first operand is before... t = (Token)tokens.elementAt( poz_max_op - 1 ); operand1 = operand_value( t ); // ...and second operand is after operator t = (Token)tokens.elementAt( poz_max_op + 1 ); operand2 = operand_value( t ); // operator t = (Token)tokens.elementAt( poz_max_op ); String op = ((Operator)t.token).operator; double result = operation_result( operand1, operand2, op ); tokens.removeElementAt( poz_max_op + 1 ); tokens.removeElementAt( poz_max_op ); t = new Token ( new Double(result), 'D', 0, 0 ); tokens.setElementAt( t, poz_max_op - 1 ); parentheses_removal( tokens, poz_max_op - 1 ); ...操作数可以是变量，还可以是十进制、十六进制、八进制或二进制数。清单 10. 获取操作数public static double operand_value( Token t ) { if ( t.mark == 'V' ) return ((Variable)t.token).value; else if ( t.mark == 'D' ) return ((Double)t.token).doubleValue(); else if ( t.mark == 'H' ) return base_convert( ((String)t.token).substring(2), 16 ); else if ( t.mark == 'O' ) return base_convert( ((String)t.token).substring(2), 8 ); else if ( t.mark == 'B' ) return base_convert( ((String)t.token).substring(2), 2 ); }接下来的方法将不同计数制的数转化为十进制的形式。清单 11. 将数转化为十进制数public static long base_convert( String s, int base ) { long r = 0; int i, j; for ( i = s.length() - 1, j = 0; i >= 0; i--, j++ ) r = r + digit_weight( s.charAt( i ) ) * (long)Math.pow( base, j ); return r; } public static int digit_weight( char c ) { if ( Character.isDigit( c ) ) return c - 48; else if ( 'A' <= c && c <= 'f' ) return c - 55; else if ( 'a' <= c && c <= 'f' ) return c - 87; return -1; }一旦确定操作数和操作符后，就可以执行运算了，如 清单 12 所示。步骤 5： 在这步中，W3Eval 从向量中除去用过的符号并在同一位置放入结果。对于函数求值这类情况，除去的是函数、括号、自变量和逗号；而对于操作符求值这类情况而言，除去的则是操作数和操作符。步骤 6： 在求值的这一步，W3Eval 从表达式中除去冗余括号。清单 13. 除去冗余括号private static void parentheses_removal( Vector tokens, int pos ) { if ( pos > 1 && ((Token)tokens.elementAt( pos - 2 )).mark != 'F' && ((Token)tokens.elementAt( pos - 1 )).mark == '(' && ((Token)tokens.elementAt( pos + 1 )).mark == ')' || pos == 1 && ((Token)tokens.elementAt( 0 )).mark == '(' && ((Token)tokens.elementAt( 2 )).mark == ')' ) { tokens.removeElementAt( pos + 1 ); tokens.removeElementAt( pos - 1 ); } return; }步骤 7： 在求值的最后一步，向量中剩余的符号被结合到字符串，并在屏幕上显示。清单 14. 结合符号并显示结果public static String token_join( Vector tokens ) { String result = new String(); Token t; for ( int i = 0; i < tokens.size(); i++ ) { t = (Token)tokens.elementAt( i ); if ( t.mark == 'D' ) { double n = ((Double)t.token).doubleValue(); result = result + formated_number( n ); } else result = result + t.token; if ( result.endsWith( ".0" ) ) result = result.substring( 0, result.length() - 2 ); result = result + " "; } return result; }结论本文分析了一个 applet，它能一步一步的对算术表达式求值。同时还按顺序回顾了最有意思的代码片段，并论述了两种不同的表达式求值方法。下一版 W3Eval 有望在各方面得到增强，包括有能力添加用户定义的功能；支持分数、复数和矩阵；改良的图形用户界面（GUI）；大小和速度优化以及安全性方面的增强。我鼓励您提供您自己对于增强方面的设想。我希望您会发现 W3Eval 是个对表达式求值有益的在线工具，它在某种程度上比经典的方法更简单自然。我还期待这里谈到的代码和算法使您明白 Java 语言有助于处理数学问题。说明：本文涉及的 Java Applet 技术已过时，现代主流浏览器不再支持直接运行 Applet。文中代码逻辑与算法思想仍具有参考价值，但实际部署需结合现代 Web 技术（如 JavaScript 或 WebAssembly）进行重构。*相关主题您可以参阅本文在 developerWorks 全球站点上的 英文原文。W3Eval applet 是免费的，它的 帮助 有助于您解决问题。这张表格展示了 W3Eval 操作符的优先级。请阅读波兰数学家 Jan Lukasiewicz 的传记。Donald Knuth，计算机科学领域卓越的学者，曾详尽的就算法的设计和分析撰写和演讲。他的 主页 提供最近出版的有关其作品的论文和信息的链接。您会觉得 Java FAQ 很有用。还有很多有关 applet 的信息在 Peter Van Der Linden（Prentice Hall PTR/Sun Microsystems 出版社出版，1998 年 12 月）的 Just Java 2 中。由 Ken Arnold、James Gosling 和 David Holmes 撰写的 The Java Programming Language（Addison Wesley 出版社出版，2000 年 12 月）包含有益的关于集合的信息。学习 Martin Bastiaan 的 “A Walk in the Park”（developerWorks，1998 年 1 月），了解更多有关 applet 的知识。VisualAge for Java 使 applet 的开发变得轻而易举。developerWorks Java 技术专区：这里有数百篇关于 Java 编程各个方面的文章。
从零开始实现一个玩具版浏览器渲染引擎
引言浏览器渲染原理是前端开发者必须掌握的核心知识点之一，在技术面试中经常被问及。许多前端书籍或培训课程也会提及此主题，例如 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) { return { tagName, attributes: {}, children: [], nodeType: NodeType.Element, } as Element } export function text(data: string) { return { nodeValue: data, nodeType: NodeType.Text, } as Text }这两个函数在解析到元素节点或者文本节点时调用，调用后会返回对应的 DOM 节点。解析流程下图展示了整个 HTML 解析器的执行过程：HTML 解析器的入口方法为 parse()，从这开始执行直到遍历完所有 HTML 文本为止：判断当前字符是否为 <，如果是，则当作元素节点来解析，调用 parseElement()，否则调用 parseText()。parseText() 比较简单，一直往前遍历字符串，直至遇到 < 字符为止。然后将之前遍历过的所有字符当作 Text 节点的值。parseElement() 则相对复杂一点，它首先要解析出当前的元素标签名称，这段文本用 parseTag() 来解析。然后再进入 parseAttrs() 方法，判断是否有属性节点。如果该节点有 class 或者其他 HTML 属性，则会调用 parseAttr() 把 HTML 属性或者 class 解析出来。至此，整个元素节点的前半段已经解析完了。接下来需要解析它的子节点。这时就会进入无限递归循环回到第一步，继续解析元素节点或文本节点。当所有子节点解析完后，需要调用 parseTag()，看看结束标签名和元素节点的开始标签名是否相同。如果相同，则 parseElement() 或者 parse() 结束，否则报错。核心方法详解入口方法 parse()HTML 的入口方法是 parse(rawText)：parse(rawText: string) { this.rawText = rawText.trim() this.len = this.rawText.length this.index = 0 this.stack = [] const root = element('root') while (this.index < this.len) { this.removeSpaces() if (this.rawText[this.index].startsWith('<')) { this.index++ this.parseElement(root) } else { this.parseText(root) } } }入口方法需要遍历所有文本。在一开始它需要判断当前字符是否是 <，如果是，则将它当作元素节点来解析，调用 parseElement()，否则将当前字符作为文本来解析，调用 parseText()。解析元素节点 parseElement()private parseElement(parent: Element) { // 解析标签 const tag = this.parseTag() // 生成元素节点 const ele = element(tag) this.stack.push(tag) parent.children.push(ele) // 解析属性 this.parseAttrs(ele) while (this.index < this.len) { this.removeSpaces() if (this.rawText[this.index].startsWith('<')) { this.index++ this.removeSpaces() // 判断是否是结束标签 if (this.rawText[this.index].startsWith('/')) { this.index++ const startTag = this.stack[this.stack.length - 1] // 结束标签 const endTag = this.parseTag() if (startTag !== endTag) { throw Error(`The end tagName ${endTag} does not match start tagName ${startTag}`) } this.stack.pop() while (this.index < this.len && this.rawText[this.index] !== '>') { this.index++ } break } else { this.parseElement(ele) } } else { this.parseText(ele) } } this.index++ }parseElement() 会依次调用 parseTag() 和 parseAttrs() 解析标签和属性，然后再递归解析子节点，终止条件是遍历完所有的 HTML 文本。解析文本节点 parseText()private parseText(parent: Element) { let str = '' while ( this.index < this.len && !(this.rawText[this.index] === '<' && /\w|\//.test(this.rawText[this.index + 1])) ) { str += this.rawText[this.index] this.index++ } this.sliceText() parent.children.push(text(removeExtraSpaces(str))) }解析文本相对简单一点，它会一直往前遍历，直至遇到 < 为止。比如这段文本 test! ，经过 parseText() 解析后拿到的文本是 test!。解析标签 parseTag()在进入 parseElement() 后，首先调用就是 parseTag()，它的作用是解析标签名：private parseTag() { let tag = '' this.removeSpaces() // get tag name while (this.index < this.len && this.rawText[this.index] !== ' ' && this.rawText[this.index] !== '>') { tag += this.rawText[this.index] this.index++ } this.sliceText() return tag }比如这段文本 test! ，经过 parseTag() 解析后拿到的标签名是 div。解析属性节点 parseAttrs()解析完标签名后，接着再解析属性节点：// 解析元素节点的所有属性 private parseAttrs(ele: Element) { // 一直遍历文本，直至遇到 '>' 字符为止，代表 这一段文本已经解析完了 while (this.index < this.len && this.rawText[this.index] !== '>') { this.removeSpaces() this.parseAttr(ele) this.removeSpaces() } this.index++ } // 解析单个属性，例如 class="foo bar" private parseAttr(ele: Element) { let attr = '' let value = '' while (this.index < this.len && this.rawText[this.index] !== '=' && this.rawText[this.index] !== '>') { attr += this.rawText[this.index++] } this.sliceText() attr = attr.trim() if (!attr.trim()) return this.index++ let startSymbol = '' if (this.rawText[this.index] === "'" || this.rawText[this.index] === '"') { startSymbol = this.rawText[this.index++] } while (this.index < this.len && this.rawText[this.index] !== startSymbol) { value += this.rawText[this.index++] } this.index++ ele.attributes[attr] = value.trim() this.sliceText() }parseAttr() 可以将这样的文本 class="test" 解析为一个对象 { class: "test" }。其他辅助方法有时不同的节点、属性之间有很多多余的空格，所以需要写一个方法将多余的空格清除掉。protected removeSpaces() { while (this.index < this.len && (this.rawText[this.index] === ' ' || this.rawText[this.index] === '\n')) { this.index++ } this.sliceText() }同时为了方便调试，开发者经常需要打断点看当前正在遍历的字符是什么。如果以前遍历过的字符串还在，那么是比较难调试的，因为开发者需要根据 index 的值自己去找当前遍历的字符是什么。所以所有解析完的 HTML 文本，都需要截取掉，确保当前的 HTML 文本都是没有被遍历：protected sliceText() { this.rawText = this.rawText.slice(this.index) this.len = this.rawText.length this.index = 0 }sliceText() 方法的作用就是截取已经遍历过的 HTML 文本。用下图来做例子，假设当前要解析 div 这个标签名：那么解析后需要对 HTML 文本进行截取，就像下图这样：小结至此，整个 HTML 解析器的逻辑已经讲完了。所有代码加起来 200 行左右，如果不算 TS 各种类型声明，代码只有 100 多行。第二阶段：CSS 解析器CSS 样式表是一系列的 CSS 规则集合，而 CSS 解析器的作用就是将 CSS 文本解析为 CSS 规则集合。div, p { font-size: 88px; color: #000; }例如上面的 CSS 文本，经过解析器解析后，会生成下面的 CSS 规则集合：[ { "selectors": [ { "id": "", "class": "", "tagName": "div" }, { "id": "", "class": "", "tagName": "p" } ], "declarations": [ { "name": "font-size", "value": "88px" }, { "name": "color", "value": "#000" } ] } ]每个规则都有一个 selector 和 declarations 属性，其中 selectors 表示 CSS 选择器，declarations 表示 CSS 的属性描述集合。export interface Rule { selectors: Selector[] declarations: Declaration[] } export interface Selector { tagName: string id: string class: string } export interface Declaration { name: string value: string | number }每一条 CSS 规则都可以包含多个选择器和多个 CSS 属性。解析 CSS 规则 parseRule()private parseRule() { const rule: Rule = { selectors: [], declarations: [], } rule.selectors = this.parseSelectors() rule.declarations = this.parseDeclarations() return rule }在 parseRule() 里，它分别调用了 parseSelectors() 去解析 CSS 选择器，然后再对剩余的 CSS 文本执行 parseDeclarations() 去解析 CSS 属性。解析选择器 parseSelector()private parseSelector() { const selector: Selector = { id: '', class: '', tagName: '', } switch (this.rawText[this.index]) { case '.': this.index++ selector.class = this.parseIdentifier() break case '#': this.index++ selector.id = this.parseIdentifier() break case '*': this.index++ selector.tagName = '*' break default: selector.tagName = this.parseIdentifier() } return selector } private parseIdentifier() { let result = '' while (this.index < this.len && this.identifierRE.test(this.rawText[this.index])) { result += this.rawText[this.index++] } this.sliceText() return result }选择器我们只支持标签名称、前缀为 # 的 ID、前缀为 . 的类名或上述的某种组合。如果标签名称为 *，则表示它是一个通用选择器，可以匹配任何标签。标准的 CSS 解析器在遇到无法识别的部分时，会将它丢掉，然后继续解析其余部分，主要是为了兼容旧浏览器和防止发生错误导致程序中断。我们的 CSS 解析器为了实现简单，没有做这方面的错误处理。解析 CSS 属性 parseDeclaration()private parseDeclaration() { const declaration: Declaration = { name: '', value: '' } this.removeSpaces() declaration.name = this.parseIdentifier() this.removeSpaces() while (this.index < this.len && this.rawText[this.index] !== ':') { this.index++ } this.index++ // clear : this.removeSpaces() declaration.value = this.parseValue() this.removeSpaces() return declaration }parseDeclaration() 会将 color: red; 解析为一个对象 { name: "color", value: "red" }。小结CSS 解析器相对来说简单多了，因为很多知识点在 HTML 解析器中已经讲到。整个 CSS 解析器的代码大概 100 多行，如果你阅读过 HTML 解析器的源码，相信看 CSS 解析器的源码会更轻松。第三阶段：构建样式树本阶段的目标是写一个样式构建器，输入 DOM 树和 CSS 规则集合，生成一棵样式树 Style Tree。样式树的每一个节点都包含了 CSS 属性值以及它对应的 DOM 节点引用：interface AnyObject { [key: string]: any } export interface StyleNode { node: Node // DOM 节点 values: AnyObject // style 属性值 children: StyleNode[] // style 子节点 }先来看一个简单的示例： test div { font-size: 88px; color: #000; }上述的 HTML、CSS 文本在经过样式树构建器处理后生成的样式树如下：{ "node": { // DOM 节点 "tagName": "div", "attributes": {}, "children": [ { "nodeValue": "test", "nodeType": 3 } ], "nodeType": 1 }, "values": { // CSS 属性值 "font-size": "88px", "color": "#000" }, "children": [ // style tree 子节点 { "node": { "nodeValue": "test", "nodeType": 3 }, "values": { // text 节点继承了父节点样式 "font-size": "88px", "color": "#000" }, "children": [] } ] }遍历 DOM 树现在我们需要遍历 DOM 树。对于 DOM 树中的每个节点，我们都要在样式树中查找是否有匹配的 CSS 规则。export function getStyleTree(eles: Node | Node[], cssRules: Rule[], parent?: StyleNode) { if (Array.isArray(eles)) { return eles.map((ele) => getStyleNode(ele, cssRules, parent)) } return getStyleNode(eles, cssRules, parent) }匹配选择器匹配选择器实现起来非常容易，因为我们的 CSS 解析器仅支持简单的选择器，只需要查看元素本身即可判断选择器是否与元素匹配。/** * css 选择器是否匹配元素 */ function isMatch(ele: Element, selectors: Selector[]) { return selectors.some((selector) => { // 通配符 if (selector.tagName === '*') return true if (selector.tagName === ele.tagName) return true if (ele.attributes.id === selector.id) return true if (ele.attributes.class) { const classes = ele.attributes.class.split(' ').filter(Boolean) const classes2 = selector.class.split(' ').filter(Boolean) for (const name of classes) { if (classes2.includes(name)) return true } } return false }) }当查找到匹配的 DOM 节点后，再将 DOM 节点和它匹配的 CSS 属性组合在一起，生成样式树节点 styleNode：function getStyleNode(ele: Node, cssRules: Rule[], parent?: StyleNode) { const styleNode: StyleNode = { node: ele, values: getStyleValues(ele, cssRules, parent), children: [], } if (ele.nodeType === NodeType.Element) { // 合并内联样式 if (ele.attributes.style) { styleNode.values = { ...styleNode.values, ...getInlineStyle(ele.attributes.style) } } styleNode.children = ele.children.map((e) => getStyleNode(e, cssRules, styleNode)) as unknown as StyleNode[] } return styleNode } function getStyleValues(ele: Node, cssRules: Rule[], parent?: StyleNode) { const inheritableAttrValue = getInheritableAttrValues(parent) // 文本节点继承父元素的可继承属性 if (ele.nodeType === NodeType.Text) return inheritableAttrValue return cssRules.reduce((result: AnyObject, rule) => { if (isMatch(ele as Element, rule.selectors)) { result = { ...result, ...cssValueArrToObject(rule.declarations) } } return result }, inheritableAttrValue) }在 CSS 选择器中，不同的选择器优先级是不同的，比如 id 选择器就比类选择器的优先级要高。但是我们这里没有实现选择器优先级，为了实现简单，所有的选择器优先级是一样的。继承属性文本节点无法匹配选择器，那它的样式从哪来？答案就是继承，它可以继承父节点的样式。在 CSS 中存在很多继承属性，即使子元素没有声明这些属性，也可以从父节点里继承。比如字体颜色、字体家族等属性，都是可以被继承的。为了实现简单，这里只支持继承父节点的 color、font-size 属性。// 子元素可继承的属性，这里只写了两个，实际上还有很多 const inheritableAttrs = ['color', 'font-size'] /** * 获取父元素可继承的属性值 */ function getInheritableAttrValues(parent?: StyleNode) { if (!parent) return {} const keys = Object.keys(parent.values) return keys.reduce((result: AnyObject, key) => { if (inheritableAttrs.includes(key)) { result[key] = parent.values[key] } return result }, {}) }内联样式在 CSS 中，内联样式的优先级是除了 !important 之外最高的。我们可以在调用 getStyleValues() 函数获得当前 DOM 节点的 CSS 属性值后，再去取当前节点的内联样式值，并对当前 DOM 节点的 CSS 样式值进行覆盖。styleNode.values = { ...styleNode.values, ...getInlineStyle(ele.attributes.style) } function getInlineStyle(str: string) { str = str.trim() if (!str) return {} const arr = str.split(';') if (!arr.length) return {} return arr.reduce((result: AnyObject, item: string) => { const data = item.split(':') if (data.length === 2) { result[data[0].trim()] = data[1].trim() } return result }, {}) }第四阶段：布局树第四阶段讲的是如何将样式树转化为布局树，也是整个渲染引擎相对比较复杂的部分。CSS 盒子模型在 CSS 中，所有的 DOM 节点都可以当作一个盒子。这个盒子模型包含了内容、内边距、边框、外边距以及在页面中的位置信息。我们可以用以下的数据结构来表示盒子模型：export default class Dimensions { content: Rect padding: EdgeSizes border: EdgeSizes margin: EdgeSizes } export default class Rect { x: number y: number width: number height: number } export interface EdgeSizes { top: number right: number bottom: number left: number }块布局和内联布局CSS 的 display 属性决定了盒子在页面中的布局方式。display 的类型有很多种，例如 block、inline、flex 等等，但这里只支持 block 和 inline 两种布局方式，并且所有盒子的默认布局方式为 display: inline。我会用伪 HTML 代码来描述它们之间的区别：<container> <c></c> <d></d> </container>块布局会将盒子从上至下的垂直排列。内联布局则会将盒子从左至右的水平排列。如果容器内同时存在块布局和内联布局，则会用一个匿名布局将内联布局包裹起来。这样就能将内联布局的盒子和其他块布局的盒子区别开来。通常情况下内容是垂直增长的。也就是说，在容器中添加子节点通常会使容器更高，而不是更宽。另一种说法是，默认情况下，子节点的宽度取决于其容器的宽度，而容器的高度取决于其子节点的高度。布局树结构布局树是所有盒子节点的集合。export default class LayoutBox { dimensions: Dimensions boxType: BoxType children: LayoutBox[] styleNode: StyleNode }盒子节点的类型可以是 block、inline 和 anonymous。export enum BoxType { BlockNode = 'BlockNode', InlineNode = 'InlineNode', AnonymousBlock = 'AnonymousBlock', }我们构建样式树时，需要根据每一个 DOM 节点的 display 属性来生成对应的盒子节点。export function getDisplayValue(styleNode: StyleNode) { return styleNode.values?.display ?? Display.Inline }如果 DOM 节点 display 属性的值为 none，则在构建布局树的过程中，无需将这个 DOM 节点添加到布局树上，直接忽略它就可以了。如果一个块节点包含一个内联子节点，则需要创建一个匿名块（实际上就是块节点）来包含它。如果一行中有多个子节点，则将它们全部放在同一个匿名容器中。function buildLayoutTree(styleNode: StyleNode) { if (getDisplayValue(styleNode) === Display.None) { throw new Error('Root node has display: none.') } const layoutBox = new LayoutBox(styleNode) let anonymousBlock: LayoutBox | undefined for (const child of styleNode.children) { const childDisplay = getDisplayValue(child) // 如果 DOM 节点 display 属性值为 none，直接跳过 if (childDisplay === Display.None) continue if (childDisplay === Display.Block) { anonymousBlock = undefined layoutBox.children.push(buildLayoutTree(child)) } else { // 创建一个匿名容器，用于容纳内联节点 if (!anonymousBlock) { anonymousBlock = new LayoutBox() layoutBox.children.push(anonymousBlock) } anonymousBlock.children.push(buildLayoutTree(child)) } } return layoutBox }遍历布局树现在开始构建布局树，入口函数是 getLayoutTree()：export function getLayoutTree(styleNode: StyleNode, parentBlock: Dimensions) { parentBlock.content.height = 0 const root = buildLayoutTree(styleNode) root.layout(parentBlock) return root }它将遍历样式树，利用样式树节点提供的相关信息，生成一个 LayoutBox 对象，然后调用 layout() 方法，计算每个盒子节点的位置、尺寸信息。在本节内容的开头有提到过，盒子的宽度取决于其父节点，而高度取决于子节点。这意味着，我们的代码在计算宽度时需要自上而下遍历树，这样它就可以在知道父节点的宽度后设置子节点的宽度。然后自下而上遍历以计算高度，这样父节点的高度就可以在计算子节点的相关信息后进行计算。layout(parentBlock: Dimensions) { // 子节点的宽度依赖于父节点的宽度，所以要先计算当前节点的宽度，再遍历子节点 this.calculateBlockWidth(parentBlock) // 计算盒子节点的位置 this.calculateBlockPosition(parentBlock) // 遍历子节点并计算对位置、尺寸信息 this.layoutBlockChildren() // 父节点的高度依赖于其子节点的高度，所以计算子节点的高度后，再计算自己的高度 this.calculateBlockHeight() }这个方法执行布局树的单次遍历，向下执行宽度计算，向上执行高度计算。一个真正的布局引擎可能会执行几次树遍历，有些是自上而下的，有些是自下而上的。计算宽度现在，我们先来计算盒子节点的宽度，这部分比较复杂，需要详细的讲解。首先，我们要拿到当前节点的 width、padding、border、margin 等信息：calculateBlockWidth(parentBlock: Dimensions) { // 初始值 const styleValues = this.styleNode?.values || {} // 初始值为 auto let width = styleValues.width ?? 'auto' let marginLeft = styleValues['margin-left'] || styleValues.margin || 0 let marginRight = styleValues['margin-right'] || styleValues.margin || 0 let borderLeft = styleValues['border-left'] || styleValues.border || 0 let borderRight = styleValues['border-right'] || styleValues.border || 0 let paddingLeft = styleValues['padding-left'] || styleValues.padding || 0 let paddingRight = styleValues['padding-right'] || styleValues.padding || 0 // 拿到父节点的宽度，如果某个属性为 'auto'，则将它设为 0 let totalWidth = sum(width, marginLeft, marginRight, borderLeft, borderRight, paddingLeft, paddingRight) // ...如果这些属性没有设置，就使用 0 作为默认值。拿到当前节点的总宽度后，还需要和父节点对比一下是否相等。如果宽度或边距设置为 auto，则可以对这两个属性进行适当展开或收缩以适应可用空间。所以现在需要对当前节点的宽度进行检查。const isWidthAuto = width === 'auto' const isMarginLeftAuto = marginLeft === 'auto' const isMarginRightAuto = marginRight === 'auto' // 当前块的宽度如果超过了父元素宽度，则将它的可扩展外边距设为 0 if (!isWidthAuto && totalWidth > parentWidth) { if (isMarginLeftAuto) { marginLeft = 0 } if (isMarginRightAuto) { marginRight = 0 } } // 根据父子元素宽度的差值，去调整当前元素的宽度 const underflow = parentWidth - totalWidth // 如果三者都有值，则将差值填充到 marginRight if (!isWidthAuto && !isMarginLeftAuto && !isMarginRightAuto) { marginRight += underflow } else if (!isWidthAuto && !isMarginLeftAuto && isMarginRightAuto) { // 如果右边距是 auto，则将 marginRight 设为差值 marginRight = underflow } else if (!isWidthAuto && isMarginLeftAuto && !isMarginRightAuto) { // 如果左边距是 auto，则将 marginLeft 设为差值 marginLeft = underflow } else if (isWidthAuto) { // 如果只有 width 是 auto，则将另外两个值设为 0 if (isMarginLeftAuto) { marginLeft = 0 } if (isMarginRightAuto) { marginRight = 0 } if (underflow >= 0) { // 展开宽度，填充剩余空间，原来的宽度是 auto，作为 0 来计算的 width = underflow } else { // 宽度不能为负数，所以需要调整 marginRight 来代替 width = 0 // underflow 为负数，相加实际上就是缩小当前节点的宽度 marginRight += underflow } } else if (!isWidthAuto && isMarginLeftAuto && isMarginRightAuto) { // 如果只有 marginLeft 和 marginRight 是 auto，则将两者设为 underflow 的一半 marginLeft = underflow / 2 marginRight = underflow / 2 }详细的计算过程请看上述代码，重要的地方都已经标上注释了。通过对比当前节点和父节点的宽度，我们可以拿到一个差值：// 根据父子元素宽度的差值，去调整当前元素的宽度 const underflow = parentWidth - totalWidth如果这个差值为正数，说明子节点宽度小于父节点；如果差值为负数，说明子节点大于父节点。上面这段代码逻辑其实就是根据 underflow、width、padding、margin 等值对子节点的宽度、边距进行调整，以适应父节点的宽度。定位计算当前节点的位置相对来说简单一点。这个方法会根据当前节点的 margin、border、padding 样式以及父节点的位置信息对当前节点进行定位：calculateBlockPosition(parentBlock: Dimensions) { const styleValues = this.styleNode?.values || {} const { x, y, height } = parentBlock.content const dimensions = this.dimensions dimensions.margin.top = transformValueSafe(styleValues['margin-top'] || styleValues.margin || 0) dimensions.margin.bottom = transformValueSafe(styleValues['margin-bottom'] || styleValues.margin || 0) dimensions.border.top = transformValueSafe(styleValues['border-top'] || styleValues.border || 0) dimensions.border.bottom = transformValueSafe(styleValues['border-bottom'] || styleValues.border || 0) dimensions.padding.top = transformValueSafe(styleValues['padding-top'] || styleValues.padding || 0) dimensions.padding.bottom = transformValueSafe(styleValues['padding-bottom'] || styleValues.padding || 0) dimensions.content.x = x + dimensions.margin.left + dimensions.border.left + dimensions.padding.left dimensions.content.y = y + height + dimensions.margin.top + dimensions.border.top + dimensions.padding.top } function transformValueSafe(val: number | string) { if (val === 'auto') return 0 return parseInt(String(val)) }比如获取当前节点内容区域的 x 坐标，计算方式如下：dimensions.content.x = x + dimensions.margin.left + dimensions.border.left + dimensions.padding.left遍历子节点在计算高度之前，需要先遍历子节点，因为父节点的高度需要根据它下面子节点的高度进行适配。layoutBlockChildren() { const { dimensions } = this for (const child of this.children) { child.layout(dimensions) // 遍历子节点后，再计算父节点的高度 dimensions.content.height += child.dimensions.marginBox().height } }每个节点的高度就是它上下两个外边距之间的差值，所以可以通过 marginBox() 获得高度：export default class Dimensions { content: Rect padding: EdgeSizes border: EdgeSizes margin: EdgeSizes constructor() { const initValue = { top: 0, right: 0, bottom: 0, left: 0, } this.content = new Rect() this.padding = { ...initValue } this.border = { ...initValue } this.margin = { ...initValue } } paddingBox() { return this.content.expandedBy(this.padding) } borderBox() { return this.paddingBox().expandedBy(this.border) } marginBox() { return this.borderBox().expandedBy(this.margin) } }export default class Rect { x: number y: number width: number height: number constructor() { this.x = 0 this.y = 0 this.width = 0 this.height = 0 } expandedBy(edge: EdgeSizes) { const rect = new Rect() rect.x = this.x - edge.left rect.y = this.y - edge.top rect.width = this.width + edge.left + edge.right rect.height = this.height + edge.top + edge.bottom return rect } }遍历子节点并执行完相关计算方法后，再将各个子节点的高度进行相加，得到父节点的高度。height 属性默认情况下，节点的高度等于其内容的高度。但如果手动设置了 height 属性，则需要将节点的高度设为指定的高度：calculateBlockHeight() { // 如果元素设置了 height，则使用 height，否则使用 layoutBlockChildren() 计算出来的高度 const height = this.styleNode?.values.height if (height) { this.dimensions.content.height = parseInt(height) } }为了简单起见，我们不需要实现外边距折叠 [4]。小结布局树是渲染引擎最复杂的部分，这一阶段结束后，我们就了解了布局树中每个盒子节点在页面中的具体位置和尺寸信息。下一步，就是如何把布局树渲染到页面上了。第五阶段：绘制绘制阶段主要是根据布局树中各个节点的位置、尺寸信息将它们绘制到页面。目前大多数计算机使用光栅（raster，也称为位图）显示技术。将布局树各个节点绘制到页面的这个过程也被称为“光栅化”。浏览器通常在图形 API 和库（如 Skia、Cairo、Direct2D 等）的帮助下实现光栅化。这些 API 提供绘制多边形、直线、曲线、渐变和文本的功能。实际上绘制才是最难的部分，但是这一步我们有现成的 canvas [5] 库可以用，不用自己实现一个光栅器，所以相对来说就变得简单了。在真正开始绘制阶段之前，我们先来学习一些关于计算机如何绘制图像、文本的基础知识，有助于我们理解光栅化的具体实现过程。计算机如何绘制图像、文本在计算机底层进行像素绘制属于硬件操作，它依赖于屏幕和显卡接口的具体细节。为了简单起见，我们可以用一段内存区域来表示屏幕，内存的一个 bit 就代表了屏幕中的一个像素。比如在屏幕中的 (x,y) 坐标绘制一个像素，可以用 memory[x + y * rowSize] = 1 来表示。从屏幕左上角开始，列是从左至右开始计数，行是从上至下开始计数。因此屏幕最左上角的坐标是 (0,0)。为了简单起见，我们用 1 bit 来表示屏幕的一个像素，0 代表白色，1 代表黑色。屏幕每一行的长度用变量 rowSize 表示，每一列的高度用 colSize 表示。绘制线条如果我们要在计算机上绘制一条直线，那么只要知道计算机的起点坐标 (x1,y1) 和终点坐标 (x2,y2) 就可以了。然后根据 memory[x + y * rowSize] = 1 公式，将 (x1,y1) 至 (x2,y2) 之间对应的内存区域置为 1，这样就画出来了一条直线。绘制文本为了在屏幕上显示文本，首先必须将物理上基于像素点的屏幕，在逻辑上以字符为单位划分成若干区域，每个区域能输出单个完整的字符。假设有一个 256 行 512 列的屏幕，如果为每个字符分配一个 11*8 像素的网格，那么屏幕上总共能显示 23 行，每行 64 个字符（还有 3 行像素没使用）。有了这些前提条件后，我们现在打算在屏幕上画一个 A：上图的 A 在内存区域中用 11*8 像素的网格表示。为了在内存区域中绘制它，我们可以用一个二维数组来表示它：const charA = [ [0, 0, 1, 1, 0, 0, 0, 0], // 按从左至右的顺序来读取 bit，转换成十进制数字就是 12 [0, 1, 1, 1, 1, 0, 0, 0], // 30 [1, 1, 0, 0, 1, 1, 0, 0], // 51 [1, 1, 0, 0, 1, 1, 0, 0], // 51 [1, 1, 1, 1, 1, 1, 0, 0], // 63 [1, 1, 0, 0, 1, 1, 0, 0], // 51 [1, 1, 0, 0, 1, 1, 0, 0], // 51 [1, 1, 0, 0, 1, 1, 0, 0], // 51 [1, 1, 0, 0, 1, 1, 0, 0], // 51 [0, 0, 0, 0, 0, 0, 0, 0], // 0 [0, 0, 0, 0, 0, 0, 0, 0], // 0 ]上面二维数组的第一项，代表了第一行内存区域每个 bit 的取值。一共 11 行，画出了一个字母 A。如果我们为 26 个字母都建一个映射表，按 ascii 的编码来排序，那么 charsMap[65] 就代表字符 A。当用户在键盘上按下 A 键时，就把 charsMap[65] 对应的数据输出到内存区域上，这样屏幕上就显示了一个字符 A。绘制布局树科普完关于绘制屏幕的基础知识后，我们现在正式开始绘制布局树（为了方便，我们使用 node-canvas [6] 库）。首先要遍历整个布局树，然后逐个节点进行绘制：function renderLayoutBox(layoutBox: LayoutBox, ctx: CanvasRenderingContext2D, parent?: LayoutBox) { renderBackground(layoutBox, ctx) renderBorder(layoutBox, ctx) renderText(layoutBox, ctx, parent) for (const child of layoutBox.children) { renderLayoutBox(child, ctx, layoutBox) } }这个函数对每个节点依次绘制背景色、边框、文本，然后再递归绘制所有子节点。默认情况下，HTML 元素按照它们出现的顺序进行绘制。如果两个元素重叠，则后一个元素将绘制在前一个元素之上。这种排序反映在我们的布局树中，它将按照元素在 DOM 树中出现的顺序绘制元素。绘制背景色function renderBackground(layoutBox: LayoutBox, ctx: CanvasRenderingContext2D) { const { width, height, x, y } = layoutBox.dimensions.borderBox() ctx.fillStyle = getStyleValue(layoutBox, 'background') ctx.fillRect(x, y, width, height) }首先拿到布局节点的位置、尺寸信息，以 x,y 作为起点，绘制矩形区域，并且以 CSS 属性 background 的值作为背景色进行填充。绘制边框function renderBorder(layoutBox: LayoutBox, ctx: CanvasRenderingContext2D) { const { width, height, x, y } = layoutBox.dimensions.borderBox() const { left, top, right, bottom } = layoutBox.dimensions.border const borderColor = getStyleValue(layoutBox, 'border-color') if (!borderColor) return ctx.fillStyle = borderColor // left ctx.fillRect(x, y, left, height) // top ctx.fillRect(x, y, width, top) // right ctx.fillRect(x + width - right, y, right, height) // bottom ctx.fillRect(x, y + height - bottom, width, bottom) }绘制边框，其实我们绘制的是四个矩形，每一个矩形就是一条边框。绘制文本function renderText(layoutBox: LayoutBox, ctx: CanvasRenderingContext2D, parent?: LayoutBox) { if (layoutBox.styleNode?.node.nodeType === NodeType.Text) { // get AnonymousBlock x y const { x = 0, y = 0, width } = parent?.dimensions.content || {} const styles = layoutBox.styleNode?.values || {} const fontSize = styles['font-size'] || '14px' const fontFamily = styles['font-family'] || 'serif' const fontWeight = styles['font-weight'] || 'normal' const fontStyle = styles['font-style'] || 'normal' ctx.fillStyle = styles.color ctx.font = `${fontStyle} ${fontWeight} ${fontSize} ${fontFamily}` ctx.fillText(layoutBox.styleNode?.node.nodeValue, x, y + parseInt(fontSize), width) } }通过 canvas 的 fillText() 方法，我们可以很方便地绘制带有字体风格、大小、颜色的文本。输出图片绘制完成后，我们可以借助 canvas 的 API 输出图片。下面用一个简单的示例来演示一下： test1! foo * { display: block; } div { font-size: 14px; width: 400px; background: #fff; margin-bottom: 20px; display: block; background: lightblue; } .lightblue { font-size: 16px; display: block; width: 200px; height: 200px; background: blue; border-color: green; border: 10px; } .foo { width: 100px; height: 100px; background: red; color: yellow; margin-left: 50px; } body { display: block; font-size: 88px; color: #000; }上面这段 HTML、CSS 代码经过渲染引擎程序解析后生成的图片如下：总结至此，这个玩具版的渲染引擎就完成了。虽然这个玩具并没有什么实际用途，但如果能通过实现它来了解真实的渲染引擎是如何运作的，从这个角度来看，它还是“有用”的。说明：本文实现的渲染引擎主要用于教学与原理演示，代码逻辑进行了大量简化（如不支持外边距折叠、选择器优先级简化等），不适用于生产环境。参考资料渲染原理：https://developer.mozilla.org/zh-CN/docs/Web/Performance/How_browsers_work#%E6%B8%B2%E6%9F%93robinson：https://github.com/mbrubeck/robinson从零开始实现一个玩具版浏览器渲染引擎：https://github.com/woai3c/tiny-rendering-engine外边距折叠：https://developer.mozilla.org/zh-CN/docs/Web/CSS/CSS_box_model/Mastering_margin_collapsingcanvas：https://github.com/Automattic/node-canvasnode-canvas：https://github.com/Automattic/node-canvasLet's build a browser engine!：https://limpet.net/mbrubeck/2014/08/08/toy-layout-engine-1.htmlrobinson：https://github.com/mbrubeck/robinson渲染页面：浏览器的工作原理：https://developer.mozilla.org/zh-CN/docs/Web/Performance/How_browsers_work关键渲染路径：https://developer.mozilla.org/zh-CN/docs/Web/Performance/Critical_rendering_path计算机系统要素：https://book.douban.com/subject/1998341/
java 公式解析器学习与开发（1）本文主要探讨如何使用 Java 实现一个简单的算术表达式求值器。以下是一个基于双栈算法（Two-Stack Algorithm）的基础实现示例。核心代码实现public class Evaluate { public static void main(String[] args) { Stack<String> ops = new Stack<String>(); Stack<Double> vals = new Stack<Double>(); // 示例表达式：完全括号化的中缀表达式，元素间以空格分隔 String[] strs = "( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )".split(" "); int i = 0; while (i < strs.length) { String s = strs[i]; if (s.equals("(")) ; // 忽略左括号 else if (s.equals("+")) ops.push(s); else if (s.equals("-")) ops.push(s); else if (s.equals("*")) ops.push(s); else if (s.equals("/")) ops.push(s); else if (s.equals("sqrt")) ops.push(s); else if (s.equals(")")) { // 遇到右括号，弹出操作符与操作数进行计算 String op = ops.pop(); double v = vals.pop(); if (op.equals("+")) v = vals.pop() + v; else if (op.equals("-")) v = vals.pop() - v; else if (op.equals("*")) v = vals.pop() * v; else if (op.equals("/")) v = vals.pop() / v; else if (op.equals("sqrt")) v = Math.sqrt(v); vals.push(v); } else vals.push(Double.parseDouble(s)); i++; } System.out.println(vals.pop()); } }使用说明与限制上述程序实现了一个简单的算术表达式计算逻辑，但在使用时有以下严格限制：必须添加括号：表达式必须是完全括号化的（Fully Parenthesized），即每个操作符及其对应的操作数都必须被括号括起来。空格分隔：各个分词（Token）之间必须有空格，以便程序通过 split(" ") 区分计算结构。只有满足以上条件，程序才能正确解析并区分出运算的层级结构。原理简述中缀表达式（Infix Expression）是人们常用的算术表示方法。在通用的中缀记法中，通常依赖运算符优先级来确定计算顺序；但在上述算法实现中，括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来，用于明确指示运算的次序。这种处理方式简化了语法解析的复杂度，无需处理运算符优先级表，即可通过栈结构直接完成求值。说明：本文代码示例使用了 Java 传统的 Stack 类。在现代 Java 开发中，Stack 类已被视为遗留类（Legacy），官方建议优先使用 Deque 接口及其实现类（如 ArrayDeque）来替代。此外，该算法适用于教学演示或特定场景，实际生产环境中的表达式解析通常涉及更复杂的词法分析与语法树构建。