编译器模式
追踪一个高速表达式求值器的演变，以演示您需要“自行编写”递归下降编译器所需的各种模式。
摘要
根据语法的复杂程度，手工编写的递归下降编译器可能是最佳选择。它的实现可能比学习一个编译器生成器系统更快，并且可以避免将编译器生成器的运行时集成到您的源代码库中。但这也存在必须仔细权衡的风险。
引言
多年前，聪明人认识到编写编译器是件难事。但是，他们也认识到编译器代码中存在许多重复的模式。当聪明人和模式结合在一起时，软件就会神奇地演变*。因此，“编译器生成器”诞生了，旨在将语法规范转换为编译器，而无需编写相同的代码一遍又一遍地处理这些模式。其中著名的编译器生成器是 YACC -- Yet Another Compiler Compiler（又一个编译器生成器）。
本文演示了编译器中的一些模式，以及如何在没有编译器生成器的情况下实现一个简单的编译器。为了使想法具体化，我们将通过构建一个表达式求值器的任务来完成。
这不是关于编译器理论或语言设计的教程。有几本关于该主题的教科书。如果您想了解更多，还可以查阅所有有用知识的存储库——维基百科。相反，本文 pragmatic 地审视了构建一个简单的递归下降编译器的模式。如果您愿意，可以下载表达式求值器的完整源代码。
但首先，一些重要的准备工作：在阅读本文并打算实现编译器之前，请遵循此流程图
Do you need to implement a fairly simple parser/compiler?
- no
{ save a link to this article, and come back when you need it.
If you're anything like me, you won't remember enough of the
details to make it worth reading anyway. Heck, I wrote it,
and I don't even remember what's in here!
}
- yes
{ Can you afford to hire someone who really understands
compilers?
- yes
{ just do it! Save yourself a lot of pain.
}
- no
{ Do you have enough time to learn to use a good
compiler-compiler?
- yes
{ this is probably the smart move. Good compiler-
compilers reduce the risk of missing things, or of
accidentally coming up with a compiler that accepts
constructs you hadn't planned on, which are
probably meaningless anyway.
}
- no
{ I feel sorry for you. Be sure you implement an
exhaustive test suite.
}
}
}
几年前，我需要为读取和处理用于复合材料层压板（如玻璃纤维或碳纤维复合材料）的行业标准堆叠顺序代码的编译器实现一个非常小的编译器，以得出最终产品的强度和刚度结果。由于语法相当小，我选择不使用我的编译器生成器（一个商业产品，名为“LALR”，由我们这个时代的巨匠之一 Paul B. Mann 编写），而是决定实现一个简单的自顶向下递归下降解析器。经过几个小时的专注思考，我让它正常工作了。
不使用编译器生成器的一个优点是，您不必引入所有（可能受许可的）解析引擎和词法分析引擎代码。另一个优点，正如我之前提到的，是它可能比学习（或重新学习）编译器生成器系统更快。据我所知，所有编译器生成器都有自己的输入语法，然后对输出文件的放置位置、如何构建生成的代码等都有要求。一旦您学会了所有这些，就可以很快地进行更改并重新生成。但是，绝对有一个学习曲线。
即使您确实使用了编译器生成器，您仍然需要实现与每个单独的语法产生式相关的动作代码。这意味着您仍然需要真正理解您试图完成什么。编译器生成器实际上只帮助您实现解析器。当解析器分解输入时，您所采取的动作仍然由您决定。您仍然需要构建后端数据结构、逻辑、编译器的输出等。
自己编写编译器（而不是使用编译器生成器）的风险在于，您是从头开始构建每个产生式的代码，并且可能会错过一些小细节，这些细节会导致您的解析器行为异常，或者在应该表现得几乎相同的相似产生式上表现不同。
好了，说了这么多，让我们冒险开始吧。
入门：项目需求
在我的表达式求值器项目中，我需要从适当的 `.ini` 文件中读取数学表达式，然后在运行时计算该表达式的结果，使用只能在运行时才知道的参数值。该表达式需要被求值数万次，因此只需要编译一次成一个中间形式，该形式的求值速度会非常快。我还希望它能够处理不同区域点公式的差异；就像真正的数学函数一样。
f(x) = {0 when x<0, x when 0 <= x <= 2, 4-x when x>2}
因此，我的目标是实现一个表达式求值器，它能够
- 接受可替换的参数
- 接受逻辑结构
- 根据逻辑结果执行分支
- 生成预编译版本以实现快速执行
对于我的应用程序，最简单的方法是引入一个可以轻松处理所有这些的脚本语言。如果您有可用的环境，使用 PERL 或 VBScript 可能会为您处理所有细节（实际上，我不知道它们是预编译表达式，还是每次求值时都重新编译表达式）。不幸的是，在我的环境中，我没有现成的可用脚本语言，所以我需要自己实现表达式求值代码。
这里有三个主要任务：
- 设计中间形式。这与编写编译器完全无关。编译器将简单地将人类编写的表达式放入该中间形式中。这项任务的一部分还包括实现求值函数，该函数将编译后的表达式加上可替换的参数转换为最终的单个数字。
- 设计一个合适的语法。这部分至关重要，它决定了运算符的优先级和结合性。如果这部分错了，其他任何东西都不会按预期工作。我将与您分享我在某些语法方面出错时所获得的乐趣，以及如何解决它们。
- 实现一个编译器，该编译器能够正确识别和解析语法，并且能够执行适当的构建动作（构建第一部分中的中间形式）。
--任务 1：设计中间形式 --
我最终确定的中间形式非常类似于 RPN（逆波兰表示法：参见 http://www.hpmuseum.org/rpn.htm），这是一种基于栈的表达式表示形式，正式称为“后缀”形式。人类以“中缀”形式书写表达式，其中运算符位于操作数之间。因此，我们经常需要添加括号来指示优先级。后缀表达式不需要括号，因为它们只是从左到右执行所有操作。这里有几个例子。
infix form : 7 + 2
postfix form: 7 2 +
infix form : 5*sqrt( 4 + 3*4 )
postfix form: 3 4 * 4 + sqrt 5 *
为了求值一个后缀表达式，后缀表达式中的一个指针代表“栈顶”。当从左到右遍历表达式时，遇到运算符时，将处理运算符左侧适当数量的操作数，并将结果替换运算符。
逐步遍历最后一个示例表达式，在识别和执行运算符时停止，表达式演变为如下所示：
3 4 * 4 + sqrt 5 *
^
3 4 12 4 + sqrt 5 *
^
3 4 12 4 16 sqrt 5 *
^
3 4 12 2 16 4 5 *
^
3 4 12 2 16 4 5 20
^
完成后，最终答案就在栈顶（后缀表达式的最后一个位置）。
使用此确切过程的问题在于，我需要能够多次重复该过程。您可以看到后缀表达式在此过程中被消耗，使其无法重复使用。此外，到目前为止，还没有为可替换参数提供任何规定。最后，表达式求值器必须识别“+”、“*”和“sqrt”是运算符，而不是操作数。这可能涉及运行时决策，为了速度，我想避免或尽可能简化它。所有这些障碍都可以使用严格的后缀习惯用法来克服，但我选择了一种稍微不同的方法。
经过一段时间的思考，我最终选择了一种混合方法，涉及四个数组：一个在编译时填充的常量数组，一个也在编译时填充的指令数组，一个在求值时传递给求值例程使用的参数数组，以及一个在求值时使用的临时数组——栈。结构看起来如下：
typedef struct ExpressionStruct {
double *constants;
int constantsLen;
int *instructions;
int instructionsLen;
} Expression_T;
对于以下输入，“6 * sqrt( 5 + 3*4 )”，生成的数组是：
constants: 3 4 5 6
instructions: PUSH_C PUSH_C MUL PUSH_C ADD SQRT PUSH_C MUL
其中 `PUSH_C` 表示“从常量数组中获取下一个常量并将其推送到局部栈”。还有一个 `PUSH_P` “推入参数”指令。请参见下面的算法。
求值例程遍历整个指令数组，根据指令，将下一个常量复制到临时栈，将一个参数复制到同一个栈，或使用栈顶附近的值执行指示的指令（如 `SQRT` 或 `ADD` 或 `MULT`）。它看起来像这样：
double evaluate( Expression_T* ep, double* parameters )
{
int constantIndex = 0; //next constant to push to stack.
int ndx; //our current position on the
//instruction stack.
double stack[50]; //50 Oreo "Double Stack" cookies.
//I'm drooling already...
int stktop = -1; //last item ON the evaluation stack.
//Nothing on the stack yet.
//for each instruction in the array,
for( ndx=0; ndx < ep->instructionLen; ndx++ )
{
//get the instruction.
int instruction = ep->instructions[ndx];
//Zero is the instruction number for "PUSH_C", which
//means "push the next constant to the stack."
if( 0 == instruction )
stack[++stktop] = ep->constants[constantIndex++] ;
//Negative instruction numbers means "push the
//indicated parameter to the stack." Convert the
//negative number to a positive, zero-based index.
else if( instruction < 0 )
stack[++stktop] = parameters[-instruction-1];
//Positive instruction numbers are the regular
//mathematical operators.
else switch( instruction )
{
case ADD: //binary operators decrement the stack by one.
stktop-- ;
//do the addition
stack[stktop] += stack[stktop+1];
break;
case MUL: //another binary operator.
stktop-- ;
//do the multiplication
stack[stktop] *= stack[stktop+1];
break;
case SQRT: //unary operators leave the stack
//height unchanged.
//do the square root operation.
stack[stktop] = sqrt( stack[stktop] );
break;
default: //print an error message and abort.
error("Unrecognized operator");
}
}
return stack[0]; //final answer will be here now.
}
实际代码要长得多，因为它包含一个更长的 `switch` 语句（更多运算符）。此外，它还包含大量的调试和跟踪代码。可以从本文其他地方的链接下载。
请注意，在本文的示例代码中，嵌入了一些硬编码的限制；例如上面的“double stack[50]”。除非您计划在每次 `PUSH` 时测试栈的高度，并在出现问题时抛出运行时错误，否则这是非常糟糕的做法。如果您使用的代码将函数暴露给外部世界，例如从 Web 表单或其他类似事物中获取中缀表达式，使用硬编码的限制会使您面临危险的运行时问题，如缓冲区溢出。例如，表达式...
"1*(1*(1*(1*(1*(...)))))"
...如果继续足够长，最终将导致 50 个元素的栈溢出。实际代码为栈以及指令和常量数组使用了动态内存。虽然我不会在文章中讨论它，但实际的栈使用可以在编译时计算，并预先分配正确的栈量，这样运行时栈溢出测试甚至就不需要了。同样，您可以在实际代码的 `addInstruction()` 函数中看到这一点。
这完成了设计编译器将生成的中间形式的任务。
--任务 2：设计表达式语法 --
我们将识别人类可读的中缀表达式。稍后在任务 3 中，我们将实现与每个语法规则相关的产生式动作，将它们转换为上面讨论的准后缀格式。现在，我们只需要编写描述语法的 BNF。
首先要指出的是，我们希望编译过程在遇到字符串结束标记（`null` 终止符）时结束。在那之前，它最好已经识别了一个“表达式”。因此，我们可以说：
goal:
-> expression '\0'
其中“`expression`”是我们打算实现的非终结符之一。
我将尝试“自下而上”地表达表达式语法。也就是说，考虑最底层、最原始的形式，然后在此基础上进行构建。
在我看来，语法中最原始的操作数将是字面数字和参数。也就是说，最终位于运算符两侧的任何内容最终都必须归结为可以简化为数字的内容。为了指示最基本的操作数，我使用非终结符名称 `t0`。随着我们向更复杂的形式发展，我们将依次使用 `t1`、`t2`、`t3` 等。
t0:
-> number
-> parameter
我还认为，在最基本的形式中，我们应该包含括号内的任何内容。因此，我们应该添加：
-> '(' expression ')'
虽然我们还没有定义表达式是什么，但它最终将是您认为的那样；一系列操作数和运算符，它们可以被简化并表示为单个数字。
我们也应该将函数调用视为最基本的形式。因此，我们应该添加：
-> funcname '(' list ')'
其中列表将是以逗号分隔的表达式列表。
最后一点：如果我们想允许命名常量，例如“`pi`”，我们应该在这里进行。我只实现了“`pi`”，但如果需要，可以添加更多。
因此，`t0` 非终结符的完整描述是：
t0:
-> number
-> parameter
-> '(' expression ')'
-> funcname '(' list ')'
-> named_constant //I'm actually only allowing pi for simplicity.
我在这里注意到，在我的第一次尝试中，我认为分支结构应该放在这里。因此，我有一个类似这样的产生式规则：
-> expression '?' expression ':' expression
您会认出 C 语言“条件”的使用。稍后会详细介绍。这里我只想指出这是一个错误，并导致解析器以非常奇怪的方式运行，寻找和处理我根本没有打算过的标记。在查看 C 语言规范以了解他们是如何实现的之后，我意识到它需要放在最低优先级，而不是最高优先级。因此，我将其从 `t0` 的定义中移除了。
确定了“原始”项后，我们开始按照旧的 PEMDAS 模式逐步增加术语的复杂度：括号、指数、乘法、除法、加法、减法（或者我的孩子们称之为“Parachute Expert My Dear Aunt Sally”）。我们已经处理了括号，所以我们可以逐步为每个优先级级别的运算符创建非终结符，同时密切关注运算符的结合性。
实际上，PEMDAS 模式并不完全正确，因为我们应该在指数运算之前应用一元求反。我想说 `-2^3` 应该意味着 `(-2)^3`，而不是 `-(2^3)`。在这个例子中，您得到相同的答案，但如果使用参数而不是字面量代替数字，会怎么样呢：例如，`-p1 ^ 3.2`，您提前知道参数 `p1` 的值是负的，并且必须在尝试将其与分数指数相乘之前改变其符号。显然，绑定应该是 `(-p1)^3.2`。
t1: //unary prefix operators.
-> t0
-> '-' t0
-> '+' t0
我的洁癖让我认为我们应该能够求反（或正化？）任何单个项，因此我们应该用递归定义重写它，如下所示：
t1:
-> t0
-> '-' t1
-> '+' t1
使其成为右递归规则（因为非终结符“`t1`”出现在（至少）一个产生式的右侧）。但我的实用主义者说：“我们应该允许……多少次…
x + - - - - + + + - - 5
……无论如何？” 因此，我推翻了我的洁癖，坚持我只允许单个求反（或正化，呃，正化，或者可能是积极地加倍化）运算符的决定，并将其保留为最初的写法。
现在处理了一元运算符，让我们做指数运算：
t2:
-> t1
-> t1 '^' t2
注意右递归。这保证了 `^` 运算符将从右到左结合。也就是说，在 `4 ^ 3 ^ 2` 这样的操作序列中，编译器将识别“4”必须保留为 `t1`，而“3 ^ 2”必须简化为 `t2`。在将“3 ^ 2”简化为 `t2` 时，它必须将“3”保留为 `t1`，但将“2”简化为 `t2`。因此，隐含的绑定将是从右到左，实现 `4^(3^(2))`。
接下来是乘法和除法。它们具有相同的优先级，因此都属于同一个非终结符，并按先到先得（从左到右）的顺序进行求值。我们将经典 PEMDAS 添加另一个运算符，并实现模运算。
t3:
-> t2
-> t3 '*' t2
-> t3 '/' t2
-> t3 '%' t2
注意左递归。这同样是强制运算符的左结合性。我们会发现我们的大多数运算符实际上是左结合的。
最后是加法和减法：同样，我们希望它们从左到右结合，所以我们需要左递归。
t4:
-> t3
-> t4 '+' t3
-> t4 '-' t3
这完成了公式求值的简单计算器部分。然而，如前所述，我希望能够进行测试，并根据这些测试将公式分支到不同的公式。因此，我们需要实现的第一个是逻辑比较：小于、大于、等于等。事实证明，逻辑等于的优先级需要低于比较运算符，所以我们需要先处理小于和大于。
t5:
-> t4
-> t5 "<" t4
-> t5 "<=" t4
-> t5 ">" t4
-> t5 ">=" t4
t6:
-> t5
-> "not" t5
通过将“`not`”放在比比较运算符低一个优先级级别的地方，
not x < 7
评估为 `not(x < 7)`，而不是 `(not x) < 7`。我相信这比让“`not`”先与 `x` 绑定更符合直觉。
请注意，通过将其放在此优先级级别，不能在需要 `t5`、`t4`、`t3`、`t2`、`t1` 或 `t0` 的上下文中使用的“`not x`”。也就是说，您不能说“`6 * not p2`”来根据 `p2` 实现 0 或 6 的切换。但您可以通过简单地将“`not p2`”括在括号中来实现这一点。“`6 * (not p2)`”确实实现了 0 或 6 的切换。因为有括号，“`(not p2)`”是一个原始项（即 `t0`），可以在任何上下文中 all ；而“`not p2`”是一个 `t6`，并且使用受限制。
另请注意，我们正在模仿一元求反（`t1`）。因此，我们只在右侧测试 `t5`。与一元求反一样，它不是递归定义的。
t7:
-> t6
-> t7 "eq" t6
-> t7 "not_eq" t6
有人可能会问，为什么不将相等性测试包含在比“`not`”更高的优先级中，以便…
not y eq x
…评估为 `not(y eq x)` 而不是它实际的评估方式：`(not y) eq x`。
答案是有一个单独的不等于运算符，为了计算不等于，我们应该只使用该运算符。同样，如果“`not y eq x`”被绑定为 `not(y eq x)`，我们该如何实现 `(not y) eq x`？我们将被迫使用括号。
我在此指出，在我进行项目的测试方面，最终（通过一个测试）意识到“`eq`”标记造成了一个轻微的冲突。考虑这个结构：
6.5eq7.0
这显然是错误的，但它说明了问题。因为我使用 `strtod()` 来读取数字，`strtod()` 函数会扫描到 `6.5e`，认为它正在读取科学计数法数字，例如 `6.5e3` 代表 `6500`。然后它会看到 'q' 并中止。是的，我可以编写自己的数字扫描函数来解决这个问题。但这似乎是小题大做。相反，我只是将 C 运算符“==”和 “!=” 添加到 `t7` 规则中，以便有人可以编写“`6.5==7.0`”并得到他们想要的结果（当然，他们也可以只添加空格：“`6.5 eq 7.0`”同样有效）。此外，当“`6.5eq`”失败时，它会抛出错误，而不是悄悄地继续并产生错误的结果。我认为这“足够好了”！
t7:
-> t6
-> t7 "eq" t6
-> t7 "==" t6
-> t7 "not_eq" t6
-> t7 "!=" t6
为了逻辑上的完整性，这里是 `and` 和 `or`：
t8:
-> t7
-> t8 "and" t7
t9:
-> t8
-> t9 "or" t8
两者都是左递归的，意味着它们从左到右结合。因为“`and`”的优先级高于“`or`”，
x and y or z and w
评估为 (`x and y`) 或 (`z and w`)
现在我们只剩下两件事：“`expression`”和用于函数参数的“`list`”。首先，左结合列表：
list:
-> expression
-> list ',' expression
请注意，除非我们允许 `null` 表达式，否则这种定义列表的方式不允许空列表。在我们的语法中，这不是问题，因为我们不会调用带有空参数列表的函数。但在更通用的语法中，如果我们想允许空参数列表，我们需要考虑实现空表达式（并考虑如何处理由此产生的复杂性）或添加另一个产生式以允许空列表。
list:
-> expression
-> list ',' expression
-> ''
但是现在我们引入了一些有趣的问题。首先，以下输入现在是合法的：
somefunc( , , 2)
除非您知道如何处理此类输入，也就是说，编译器应该针对此类输入构建什么类型的结构，它们都毫无意义，并且您不希望允许它们。
接下来，您刚刚在语法中引入了一个冲突。考虑一下这样的语法应该如何解析一个简单的函数调用：`sin( 2 )`。请注意，在“`2`”之前，有一个空字符串（长度为零）。对我们来说它是不可见的，但对解析器来说不是。解析器是应该首先接受零长度的字符串，将其归约到“列表”？还是应该首先尝试识别并接受一个表达式？对我们来说很清楚，正确的答案是先查找表达式，如果找不到，则接受空字符串作为有效的列表。但是要实现这一点，您必须注意您执行操作的顺序。
事实证明，如果您只想实现空参数列表（而不是接受像 `somefunc( , , 2))` 这样的结构），这可能不是正确的地方。您可能需要通过添加以下规则来修改 `t0` 非终结符：
-> funcname '(' ')'
当我们实现列表非终结符时，我们会进一步讨论这一点。
这完成了除了“选择哪个表达式”运算符之外的所有内容。由于只剩下“表达式”非终结符需要定义，因此这是包含分支运算符的地方。我选择使用 C 语言的 `?:` 条件运算符来实现分支。
expression:
-> t9
-> expression '?' expression ':' expression
这完成了语法。现在进入任务 3：将其实现为一个编译器。
--任务 3：构建编译器 --
解析器（输入语言识别器）大致分为两类：自顶向下或自底向上。在自底向上解析器中，为解析器所处的每个“状态”生成一个“下一个合法标记”列表。如果读取的下一个标记与列表中的某个项目不匹配，则输入中有错误。如果匹配，解析器将执行您设计为使“解析器”成为“编译器”的任何操作，然后移动到与该状态和该标记关联的下一个解析器状态。自底向上解析器可能比自顶向下解析器执行得更快，但手工构建它们很困难。
另一方面，自顶向下解析器可以以“递归下降”的方式几乎直接从语法规范构建。考虑 `t2` 非终结符，
t2:
-> t1
-> t1 '^' t2
我们可以使用以下函数非常简单地实现它。在此函数中，“`ifp`”参数是中缀表达式指针地址。我们需要指针的地址，以便在“消耗”输入中的标记时修改表达式指针的指向。如您所见，所有非终结符函数都返回一个值，该值可用于表示成功或失败：当识别到其中一个产生式规则时表示成功，当未识别到任何规则时表示失败。
int t2( Expression_T* ep, const char** ifp )
{
if( not t1(ep, ifp) ) //if not getting a t1,
{
//since both productions begin with t1, if we don't get a t1 first,
//we can't go forward.
return 0; //return failure indicator.
}
//OK, we got a t1. We at least got the first production. Now we need to
//see if we're actually getting the second production instead of the first
//by checking if there's a " ^ t2 " following the t1 we just accepted.
//Note that the t1 function moved what ifp is pointing at forward to just
//after the t1 that was just accepted.
//Before each terminal (actual input token) we can have arbitrary white
//space. Therefore, we always ltrim before looking for an actual input token.
ltrim( ifp ); //skip over white space.
if( **ifp == '^' ) //we got the '^' symbol,
{
*ifp++ ; //move the input past the '^' symbol.
if( t2(ep, ifp) )//look for a trailing t2 non-terminal. RECURSIVE CALL.
{//yes, we got the second production: "t1 '^' t2", instead of the first.
addInstruction( ep, EXPON ); //push an enumeration value indicating
//we saw an exponentiation action.
return 1; //indicate success.
}
else
{
//We got a '^' but not a t2. There are no rules in t2
//that begin with t1 '^' , so we've failed to see a t2.
return 0;
}
}
//at this point we got a t1 only which is good enough to produce a t2.
//No compiler action needed; just indicate success.
return 1;
}
模式：递归下降解析器几乎可以直接从语法定义中编写。您可以通过调用实现该非终结符的函数来检查输入中是否存在非终结符，然后测试返回值以查看它是否成功。您通过首先绕过空格，然后执行直接的“==”字符比较或 `strcmp()` 来检查文字。 当我们匹配输入文字（标记）时，我们通过将输入指针移过它们来“消耗”它们。
模式：任何时候当您有两个以相同方式开始的规则时，请确保不要过早接受较短的规则（如上例中的 `t2 -> t1`），而不检查较长的规则是否实际上存在（如上例中的 `t2 -> t1 '^' t2`）。 如果看到一个规则，如果需要，则执行构建动作（如上面的“addInstruction()”动作）。 通过返回零（失败）或非零（成功）来指示是否看到了任何规则。
保存状态
请注意，在每种返回零（未能看到有效产生式）的情况下，我们只是草率地返回，而没有将输入指针（`ifp`）恢复到我们尝试 `t1` 或 `t2` 之前的状态，即使任何一个这些动作都可能将指针推进到未知位置，并使其无法继续执行替代动作。例如，考虑以下语法：
tx:
-> first_production
-> next_production
-> last_production
first_production:
-> "hello world" ';'
next_production:
-> "hello world" '?'
我们这样实现 `first_production`：
int first_production( Expression_T* ep, const char** ifp )
{
ltrim( ifp ); //skip leading white.
if( 0 == strncmp( *ifp, "hello world", 11 ) //got "hello world"
and ( *ifp += 11, //advance past "hello world" in side-effect context
ltrim( ifp ), //advance past white space in side-effect context
';' == **ifp ) ) //GOT IT!
{
*ifp ++ ; //advance past the ';'
return 1; //indicate success.
{
else
return 0; //indicate failure.
}
现在假设实际输入如下：
"hello world?"
在 `first_production` 中，输入已向前推进到“`hello world`”，并指向 '`?`'，此时产生式失败并返回。`tx` 现在尝试 `next_production`，但由于输入指向 '`?`' 而不是“`hello world?`”，它也将失败，即使它应该成功。
显然，如果 `first_production` 失败，在尝试 `next_production` 之前，我们必须将指针恢复到函数开始时的位置。如果 `next_production` 失败，情况也一样；在尝试 `last_production` 之前，我们必须恢复输入指针（状态）。
而且，当我们谈论它时，请注意状态实际上不仅仅是输入位置指针。在我们的编译器中，状态还包括指令数组结束指针和常量数组结束指针。在更复杂的编译器中，它可能还包括其他内容。
问题是，在哪里恢复状态？也就是说，应该由哪个函数负责恢复状态：调用函数还是被调用函数？
`t2` 的实现方式表明，我们清楚地假设，如果调用链中 `t2` 之前的函数需要恢复状态，它会处理好，因为 `t2` 肯定没有这样做！
这涉及到一项设计决策：是由调用者还是被调用函数进行状态恢复。那么，让我们考虑我们语法的前几个非终结符和产生式规则：
t1: -> t0
...
t2: -> t1
...
t3: -> t2
...
t4: -> t3
...
如果我们依赖被调用函数来恢复状态，我们的代码将如下所示：
int t1( Expression_T* ep, const char** ifp )
{
State_T s;
save_state( &s, ep, ifp );
if( not t0( ep, ifp ) )
{
restore_state( &s, ep, ifp );
return 0;
}
else ...
}
int t2( Expression_T* ep, const char** ifp )
{
State_T s;
save_state( &s, ep, ifp );
if( not t1( ep, ifp ) )
{
restore_state( &s, ep, ifp );
return 0;
}
else ...
}
etc.
每个非终结符函数都必须在执行任何操作之前保存状态的本地副本。因此，保存和恢复状态成为一个相当耗时耗栈的过程，因为每个非终结符函数都会深入到下一个较低的非终结符函数。
现在假设我们让调用函数自己处理恢复状态。那么上面的示例函数将变为：
int t1( Expression_T* ep, const char** ifp )
{
if( not t0( ep, ifp ) )
{
return 0;
}
else ...
}
int t2( Expression_T* ep, const char** ifp )
{
if( not t1( ep, ifp ) )
{
return 0;
}
else ...
}
更简单，更快，并且使用更少的堆栈空间用于局部变量。
模式：如果调用函数需要恢复状态，则让它们自己恢复。任何时候存在替代规则（即，如果第一个规则的失败不会导致整个非终结符失败），该非终结符将需要保存状态，然后才能深入调用其他非终结符。
正如我们将看到的，我们的大多数语法规则将类似于上面实现的 `t2` 规则，其中，如果第一个产生式失败，就没有必要继续前进；该非终结符已经失败了。由于没有其他选择，所以在该非终结符中保存状态没有意义。
在继续编写更多代码之前，让我们更新 `Expression_T` 类型以处理那个恼人的双指针输入“`**ifp`”。
typedef struct ExpressionStruct {
double *constants;
int constantsLen;
int *instructions;
int instructionsLen;
const char* infix; //replaces **ifp that we were using.
} Expression_T;
这将允许我们只向非终结符函数传递一个参数，并使操作输入指针更容易。当我们启动编译过程时，我们将 `infix` 成员设置为用户想要编译的实际表达式。
左递归模式
现在让我们通过编写不同非终结符的函数来演示更多模式。`t2` 规则演示了右递归。现在让我们通过实现 `t4` 来演示左递归。
t4:
-> t3 //rule #1
-> t4 '+' t3 //rule #2
-> t4 '-' t3 //rule #3
在我们开始之前，请注意，从（非 `t4`）获得 `t4` 的唯一方法是看到 `t3`。如果我们不以看到 `t3` 开头，就无法前进。因此，虽然有三个单独的规则，暗示我们应该保存状态，但第一个是强制的，所以在它之前保存状态没有意义。
int t4( Expression_T* ep )
{
InstructionEnum_T ins; //which instruction (ADD or SUBT(ract)) we're seeing.
if( not t3( ep ) )
{
//notice that if we naively attempt to move on and try the next rule
// if( t4( ep ) )
// //great, got a t4 so move forward...
//we have just created an infinite loop.
//If we don't start this non-terminal by FIRST getting a t3,
//we simply don't have any basis to move forward. PERIOD.
return 0;
}
//OK, got here, so we must have gotten a t3, which is good enough from
//rule #1 to reduce to a t4. Thus, since we now have a t4, we can now
//look at the subsequent rules to see if we're actually getting one of
//them. That is, look at the next token to see if it is a '+', or a '-'.
//Note that if we DO get a successful production, it also reduces to a
//t4, and we should restart the process of again looking for one of the
//rules that begins with t4 followed by one of the '+' or '-' tokens.
while(
//We keep looping while seeing one of the last two production rules.
//Remember, we always allow arbitrary white space before tokens.
ltrim( &(ep->infix) ), //trim white in side-effect context.
//use side-effect context to store info about the token we're recognizing.
(ins=ADD , '+' == *(ep->infix))
or (ins=SUBT, '-' == *(ep->infix)) )
{
//YES, we got one of the addition or subtraction operator tokens,
ep->infix += 1; //skip past the token.
if( t3( ep ) ) //try the rest of the rule.
{
//YES, we got another "t4 OP t3" reduction.
addInstruction( ep, ins ); //push whichever instruction we got.
}
else
//Now we're in a quandary. We must have seen a t4 or we wouldn't be here.
//So we should return success, right? But then we saw a '+' or '-'
//NOT followed by a t3. We don't have any rules for which THAT should
//be considered success. If we return failure, we're indicating that
//the WHOLE rule failed, from the very first t4 -> t3, which is not
//true; that rule succeeded. Oh my, oh my! What should we do?
//Let's take a break and discuss it...
}
return 1; //at least the original t4 -> t3 rule succeeded.
}
模式：通过“`while`”循环实现语法左递归。不要通过递归调用将您带回相同代码位置的非终结符来粗心地创建无限循环！
更多状态保存
那么，对于看到“`t4 OP`”但随后未看到成功的 `t3` 非终结符之后的“`else`”子句，我们该怎么办？我知道两种可能的方法。
纯粹主义者的方法
在纯粹主义者的方法中，我们应该尝试将 `t4` 非终结符逻辑与所有其他非终结符隔离，并使其独立。这样，如果语法的其他部分发生变化，`t4` 将是稳固的，并且不需要更改。让我们考虑如何做到这一点。无论我们是否想成为纯粹主义者，它都值得研究，因为可能还有其他情况是唯一的选择。
让我们考虑如下输入：
"4 + 5 - 6 * 7"
第一个 '`4`' 是 `t0`，最终归约为 `t3`，生成规则 #1 的成功。然后我们进入 while 循环，查找 '+' 或 '-' 符号。我们在 '+' 符号处找到它。然后我们调用 `t3` 来查看 '+' 符号的右侧是什么。'`5`' 归约为 `t3` 并返回成功，这表明我们可以再次通过规则 #2 归约为 t4。然后我们继续 `while` 循环并看到 '-' 符号。我们再次调用 `t3`，现在整个“`6 * 7`”归约为 `t3`。我们继续在 `while` 循环中查找下一个 '+' 或 '-' 符号。没有了，所以 while 循环退出，我们返回 `1`（函数的最后一行）。
现在考虑这个输入：
"4 + 5 - &x"
这对于我们的表达式语法来说不是合法的输入，但如前所述，也许将来语法会被扩展，我们希望我们的规则保持独立并仍然正常工作。我们需要以某种方式指示“`4 + 5`”部分已成功归约，但为输入的“`- &x`”部分返回失败。假设我们在 `t1` 非终结符中添加一个规则：
t1: //unary prefix operators.
-> t0
-> '-' t0
-> '+' t0
-> '&' t0 //new rule
在这种情况下，由于 `t1` 的优先级高于 `t4`，“`&x`”输入将成功归约为 `t3`，一切都会正常工作：无错误！
但是，如果 `t6` 非终结符获得一个新规则：
t6:
-> t5
-> "not" t5
-> t6 '-' '&' t0 //new rule
还记得我们的输入：
"4 + 5 - &x"
在 `t4` 非终结符中，“`4 + 5`”归约为 `t4`，然后减号被消耗，`t3` 针对“`&x`”输入失败。如果我们能以某种方式指示“`4+5`”已成功归约为 `t4`，那么它又将归约为 `t5`（通过 `t5` 规则 #1），然后归约为 `t6`（通过 `t6` 规则 #1），我们就准备好继续处理规则“`t6 -> t6 '-' '&' t0`”，前提是 `t4` 非终结符中消耗的减号被替换了。
也就是说，在 `t4` 非终结符中，在 `while` 循环内，我们应该跟踪最后一个成功状态，如果我们遇到失败，则在返回成功之前恢复该状态。
让我们用这些新信息重写 `t4`（大部分注释已删除，以突出我们新发现的策略）：
int t4( Expression_T* ep )
{
InstructionEnum_T ins;
State_T s;
if( not t3( ep ) )
{
return 0;
}
while(
ltrim( &(ep->infix) ),
(ins=ADD , '+' == *(ep->infix))
or (ins=SUBT, '-' == *(ep->infix)) )
{
saveState( &s, ep ); //do this BEFORE consuming any tokens.
ep->infix += 1; //skip past the '+' or '-' (consume it).
if( t3( ep ) ) //try the rest of the rule.
{//success.
addInstruction( ep, ins );
}
else //t3 failed.
{//put things back like they were immediately after the last success.
restoreState( &s, ep );
break; //return success.
}
}
return 1;
}
这代表了我们早期不恢复状态然后返回调用函数的策略的偏差。但在这种情况下，因为我们在循环内，调用函数根本无法知道我们在看到成功的归约之前进展了多远。
实际上，由于 `while` 循环代表递归（左递归），一旦我们进入循环，此函数本身就是调用函数（也是被调用函数）。它隐式地调用自己。因此，当我们恢复状态时，`t4` 本身就是调用函数恢复上下文。所以这实际上并没有偏离早期策略。
模式：在代表左递归的 `while` 循环中，您应该在每次成功产生式之后保存状态，并且如果您在查找模式时推进状态，但模式失败，则在返回成功指示符之前恢复状态。记住，如果您看到了任何成功的规则，您就返回“`SUCCESS`”，而不是“`FAILURE`”。
实用主义的方法
我开始上一节时说有两种处理 else 子句的方法，我们刚才讨论的方式是“纯粹主义者”的方法。另一种方法是简单地环顾语法，看看 '+' 和 '-' 符号出现在哪里。事实证明它们只出现在 `t4` 规则中，以及更高优先级的 `t1` 规则中。与我们故意在低优先级规则中插入 '-' 符号的虚构示例不同，在实际语法中，一旦您得到“`t4 '-' `”，根本没有其他合法的产生式。如果您没有得到 `t3`，则输入中有错误。因此，对于我们的实际语法，我们可以进一步简化 `t4`，如果看到 '+' 或 '-' 但随后未看到 `t3`，则直接引发错误。
int t4( Expression_T* ep )
{
InstructionEnum_T ins;
const char* oldfix; //instead of the State_T variable "s"
if( not t3( ep ) )
{
return 0;
}
while(
ltrim( &(ep->infix) ),
(ins=ADD , '+' == *(ep->infix))
or (ins=SUBT, '-' == *(ep->infix)) )
{
ep->infix += 1; //skip past the input token.
oldfix = ep->infix; //to get a decent error message if needed.
if( t3( ep ) )
addInstruction( ep, ins );
else //t3 failed.
error( oldfix ); //print the bad input, and abort the compilation.
}
return 1;
}
我们仍然通过 `oldfix` 变量某种程度上保存了状态，只是状态没有那么多——它只是一个指针，而不是栈顶等。而且我们在越过 '+' 或 '-' 标记后才保存它。如果我们需要一个有意义的错误消息，如果 `t3` 确实失败了，我们就需要它。如果我们不关心告诉用户出了什么问题，我们甚至可以跳过这部分。但是，不给用户关于问题所在的一些线索是非常糟糕的做法。您的用户会讨厌您……他们会在抓狂寻找问题所在时诅咒您。他们会在晚上睡觉时梦想着对您做坏事——让您付出代价！
救救自己！看在上帝的份上，给他们一个像样的错误消息。
如前所述，此版本的 `t4` 不再独立于其余的语法。如果语法的其他部分发生更改，则需要重新检查 `t4` 以确定在此上下文中引发错误是否仍然正确。
模式：如果您知道在产生式中遇到了输入错误，您可以直接中止（当然要附带一个不错的错误消息），而不必担心返回到调用堆栈。
贪婪输入
现在让我们实现 `t5` 非终结符。您会发现它几乎与 `t4` 完全一样，除了在匹配“`<=`”而不是“`<`”，以及“`>=`”而不是“`>`”时如何匹配存在细微差别。在这里，我们必须确保在尝试消耗比较标记时使用贪婪算法。如果我们不这样做，我们可能会错误地匹配较短的标记。
t5:
-> t4
-> t5 "<" t4
-> t5 "<=" t4
-> t5 ">" t4
-> t5 ">=" t4
int t5( Expression_T* ep )
{
InstructionEnum_T ins;
const char* oldfix;
//this next variable is new to this non-terminal. It wasn't in the
//t3 or t4 nonterminals. It is the length of the matched token.
int toklen;
if( not t4( ep ) )
{
return 0;
}
//Note that in the following test section, if we search for "<" first,
//it will match both "<" and "<=" and will take precedence over "<=".
//Thus, we must use a "greedy algorithm" and search for the longest
//matching string FIRST. That is, we must search for "<=" BEFORE
//searching for "<", and for ">=" before ">".
while(
ltrim( &(ep->infix) ), //do this in side-effect context.
//Now we ALSO store TOKEN LENGTH in side effect context.
(ins=LT_EQ, toklen=2, 0 == strncmp( ep->infix, "<=", 2 )) //this first,
or (ins=LT , toklen=1, 0 == strncmp( ep->infix, "<", 1 )) //then this.
or (ins=GT_EQ, toklen=2, 0 == strncmp( ep->infix, ">=", 2 )) //this first,
or (ins=GT , toklen=1, 0 == strncmp( ep->infix, ">", 1 ))) //then this.
{
ep->infix += toklen; //skip past the token.
oldfix = ep->infix;
if( t4( ep ) ) //try the rest of the rule.
addInstruction( ep, ins ); //push whichever instruction it was.
else
{
//there are no other uses of these comparator tokens anywhere in the
//grammar. If they are not being used correctly here, it's
//definitely an error.
error( oldfix );
}
}
return 1; //at least the original t5 -> t4 rule succeeded.
}
图元
`t0`（原始项）非终结符的代码说明了规则之间存储状态的要求，并说明了在搜索函数名时使用的贪婪算法。
但在我们编写它之前，我们需要一个我们将允许的函数名列表。我们将在此列表上执行二分查找以查找匹配项，因此它必须按字母顺序排序。
const char* funcnames[] =
{ "abs", "acos", "asin", "atan", "atan2", "ceil", "cos", "cosh", "erf"
, "erfc", "exp", "fact", "floor", "gamma", "ln", "lngamma", "log10"
, "mod", "pow", "sin", "sinh", "sqrt", "tan", "tanh"
};
int t0( Expression_T* ep )
{
// implements primary terms.
// t0:
// -> number
// -> parameter
// -> "pi"
// -> '(' expression ')'
// -> funcname '(' list ')'
double val;
char* end;
const char* oldfix;
int numargs; //to confirm we got the right number of function args.
State_T s;
FindRet_T fr;
ltrim( &(ep->infix) );
oldfix = ep->infix ;
// -> number
if( val = strtod( ep->infix, &end ), (ep->infix != end) ) // got a number
{
addConstant( ep, val ); //put this number on the constants array.
addInstruction( ep, PUSH_C ); //push next constant to stack.
ep->infix = end;
}
// -> parameter
else if(('p' == *(ep->infix) or 'P' == *(ep->infix)) // -> parameter
and isdigit( *(ep->infix + 1) ) // 2'nd char is a digit: pd
and ( 0 == *(ep->infix + 2) //string ends after pd
or not isdigit( *(ep->infix + 2) ) //pdx; where x is NOT a digit
or 0 == *(ep->infix + 3) //string ends after pdd
or not isdigit( *(ep->infix + 3) )) ) //pddx; where x is NOT a digit,
{
int pnum = *(ep->infix + 1) - '0'; //convert first digit to a number.
ep->infix += 2; //skip past "pd" where d is the first digit.
if( isdigit( *(ep->infix) ) ) //got another digit,
{
pnum *= 10;
pnum += *(ep->infix) - '0' ;//add second digit.
ep->infix += 1; //skip past second digit.
}
if( 0 == pnum ) //parameter numbers begin with 1, not 0.
error( oldfix );
addInstruction( ep, (Operation_T)(-pnum) ); //negative means
//"push the numbered parameter to stack".
}
// -> "pi"
else if( 0 == strncmp(ep->infix, "pi", 2) )
{
addConstant( ep, 3.1415926535897932384626433832795 );
addInstruction( ep, PUSH_C ); //push next constant to stack.
ep->infix += 2; //skip past "pi"
}
// -> '(' expression ')'
//Up to this point in the function, as each of the previous productions
//failed, we had not called any other non-terminal functions, and had not
//advanced the input pointer. Therefore we had not needed to save state.
//In this rule, however, we're going to drill into the expression non-
//terminal, and if that fails, attempt to match the funcname rule.
//Therefore, we must save state prior to adjusting anything so that it
//will be available for us to restore before attempting the funcname rule.
else if( saveState( &s, ep ) , //save state in side-effect context
( ( '(' == *(ep->infix)) //got a leading '('
and (ep->infix++ , expression( ep )) //skipped past '(' then got an expression,
and (ltrim( &(ep->infix) ), ')' == *(ep->infix)) )) //got trailing ')'
{
ep->infix++; //advance past that last ')'. No other action req'd.
}
// -> funcname '(' list ')'
//Here we must be careful to do another greedy comparison. If we attempt
//to search the funcnames array with ep->infix pointing to "cosh(p3)...",
//a binary or linear search will match the "cos" function name UNLESS we
//tell it to search for a string of length 4, or we insist on the longest
//possible match.
//Since the standard library bsearch function does not allow us to pass
//an extra argument with the comparison function (i.e. length 4 for the
//cosh funcname), we have to come up with a different approach. We can
//either copy out the longest series of letters to a local variable, and
//then search the array with that, or use a specialized comparison function.
//I chose the second option and implemented funcAryNameCompare.
else if( restoreState( &s, ep ), //restore state from previous failed attempt,
fr = binarySearch(oldfix,funcnames,
FUNCNAMES_LENGTH,sizeof(char*),funcAryNameCompare) ,
( not fr.notfound //we DID find it in the list,
and ( ep->infix += strlen(funcnames[fr.index]), //skip past func name
ltrim( &(ep->infix) ), //skip past white space
'(' == *(ep->infix) ) //got '('
and (ep->infix++ , (numargs=list( ep ))) //skip past '('
//list() is unusual in that it returns the number of elements in the list,
and (ltrim( &(ep->infix) ), ')' == *(ep->infix)) ) //got ')'
)
{
if( numargs-1 != opStkUse[fr.index] )
error( oldfix ); //wrong number of args for this func.
ep->infix++; //advance past that last ')'.
addInstruction( ep, (Operation_T)(fr.index) ); //add a function call.
}
else
{
return False; //didn't get any of the mandatory reductions.
}
return True;
}
模式：接受语言标记之一时，始终使用贪婪输入。查找并接受最长的合法标记。
请注意，`list()` 非终结符函数返回列表中的项目数（参见包含“`numargs=list( ep )`”的行），而不是布尔值，因为所有其他非终结符都返回布尔值。您无需从任何非终结符函数中返回任何信息——包括结构，如果这样做有意义。在这里，我们需要验证传递给函数的参数数量是否正确。为此，我们将成功和失败编码在返回值中：零表示失败，否则表示 `num_items+1`。这样，我们就可以接受空参数列表，但仍然得到“成功”指示符。请记住，我们之前讨论过我们为实际接受空参数列表需要进行的其他更改。在这里，我只想指出，如果 `list` 非终结符确实接受零个参数，我们可能想如何处理它。
模式：非终结符的返回值不一定是布尔值——它可以是任何有意义的值。您只需要能够从返回值中确定非终结符是否成功或失败。
更有趣的细节
`list` 非终结符提出了一些关于空列表的有趣观点，我们应该看看。尽管在为本项目构建的表达式求值器中没有使用，但值得研究一下“空”规则可能如何处理。
让我们看两种不同的场景：第一种是我们只想接受空参数列表，并返回“`1`”表示成功，但列表中的实际项目为“`1-1`”（或零）。这是代码：
static int list( StaticExpression* ep )
{// implements
// list:
// -> expression
// -> list ',' expression
//returns the number of expressions in the list.
const char* oldfix;
int ret = 1;
if( not expression(ep) ) //didn't get the first production,
{//this next section is how we accept empty parameter lists.
//this is NOT actually part of the grammar described by
//the BNF above. It's a short-circuit way of adding another
//formal rule to the t0 non-terminal. Since the t0()
//function already knows how to deal with zero items in the
//list, it's a no-brainer to add it here.
if( ep->infix = ltrim( ep->infix ),
')' == *(ep->infix) )
{
//DON'T consume the ')' token! The funcname rule in t0 needs it.
return 1; //indicate success, but with empty list.
}
//OK, apparently it wasn't an empty list.. some other weirdness.
return 0; //can't go anywhere without getting prod1.
}
//else, got production 1.
while( ep->infix = ltrim( ep->infix ),
',' == *(ep->infix) )
{//looks like we may have (another?) production 2. Try it.
ret++ ;
ep->infix += 1; //advance past the ','.
oldfix = ep->infix;
if( not expression(ep) ) //no, apparently not production 2.
error( oldfix );
//no instruction to add.
}
return ret;
}
这是另一种尝试，但这次我们实际上容纳了空字符串产生式，它允许输入如 `somefunc( , , 1.5, )`。您需要决定为 `null` 参数执行什么 `eval()` 操作。
//alternate implementation that allows null strings to be list elements.
static int list( StaticExpression* ep )
{// implements
// list:
// -> expression //rule #1
// -> '' //rule #2
// -> list ',' expression //rule #3
// -> list ',' '' //rule #4
//returns the number of expressions in the list.
int ret = 1;
State_T s;
saveState(&s, ep);
if( not expression(ep) ) //didn't get the first rule,
{//no worries. We'll just assume an empty string (rule #2) and press forward.
restoreState(&s, ep);
addInstruction( ep, NULL_LIST_ELEMENT ); //not actually implemented.
}
//check for rule #3
while( ep->infix = ltrim( ep->infix ),
',' == *(ep->infix) )
{//looks like we may have (another?) rule #3. Try it.
ret++ ;
ep->infix += 1; //advance past the ','.
saveState(&s, ep);
if( not expression(ep) ) //apparently not rule #3.
{//assume rule #4.
restoreState(&s, ep);
addInstruction( ep, NULL_LIST_ELEMENT ); //not actually implemented.
}
}
return ret;
}
分支机制
我在这篇文章中想深入介绍的最后一件事是用于实现 `?:` 条件运算符的分支机制。它包含在“`expression`”非终结符中。
此处实现的 the branching construct 实际上是一个 `if` / `else` 结构（与简单的“`if`”结构相对）。因此，它需要两个跳转：一个条件跳转到“如果测试为 `FALSE`，则执行此操作”部分，以及一个无条件跳转到“整个事情之后”部分。流程如下：
if( test is false ) //these two lines form the
goto FALSE_SECTION; //conditional jump section.
//otherwise, just proceed.
<code for true section>
...
goto AFTER_SECTION; //unconditional jump.
FALSE_SECTION
<code for false section>
...
AFTER_SECTION
<code that follows the z?x:y construct>
...
我们将通过将指令数组和常量数组的当前状态存储在常量数组中， along with some `PUSH_C` instructions to push those constants onto the stack, then well jump to those positions by restoring the state of the two arrays. We'll do this at two different points along the parse of the `?:` construct; once at each jump. 我们将通过将指令数组和常量数组的当前状态存储在常量数组中， along with some `PUSH_C` instructions to push those constants onto the stack, then well jump to those positions by restoring the state of the two arrays. We'll do this at two different points along the parse of the `?:` construct; once at each jump。
为了帮助解释这将如何工作，以下是 `COND_JMP` 和 `UNCOND_JMP` 指令在 `evaluate` 函数中执行时的样子。您可以看到它们从栈中弹出操作数，就像所有其他操作一样。
double evaluate( Expression_T* ep, double* parameters )
{
double stack[50];
int stktop = -1; //last item ON stack.
int constantIndex = 0; //next constant to push to stack.
int indx;
...
for( indx=0; indx < ep->instructionsLen; indx++ )
{
...
switch( instruction )
{
...
//unconditional jump. Last operation executed after the "Then" part.
case UNCOND_JMP: // Binary operator with no resultant
assert( stktop >= 1 );
stktop -= 2; //totally remove this construct from the stack.
cndx = (int)stack[stktop+1]; //restore the constants array position.
indx = (int)stack[stktop+2]-1; //execute jump. The -1 is there because
//the very next action is an
//increment of this indx loop counter!
break;
//conditional jump. First operation executed as part of the ?: operator.
case COND_JMP: // Trinary operator with no resultant
assert( stktop >= 2 );
stktop -= 3; //totally remove this construct, INCLUDING the test.
if( not stack[stktop+1] ) //if the test evaluated false
{//execute jump to the "else" part; the ':' part.
cndx = (int)stack[stktop+2]; //restore the constants array position.
indx = (int)stack[stktop+3]-1; //execute jump. The -1 is there because
//the very next action is an
//increment of this indx loop counter!
}
//else, test was true: stay and do the "then" part; the '?' part.
break;
...
}
}
return stack[0]; //final answer will be here now.
}
为了做到这一切，我们将需要 `Expression_T` 结构中有更多细节。
typedef struct ExpressionStruct {
double *constants;
int constantsLen;
int cndx; //current top of constants "stack"
int *instructions;
int instructionsLen;
int indx; //current top of the instructions "stack"
const char* infix;
} Expression_T;
当调用 `addConstant()` 和 `addInstruction()` 时，我们分别增加 `cndx` 和 `indx` 成员，这应该是显而易见的。
expression:
-> t9
-> expression '?' expression : expression
int expression( Expression_T* ep )
{
if( not t9( ep ) )
return 0;
//now do the left recursive part.
while( ltrim( &(ep->infix) ), //always trim prior to a token
'?' == *(ep->infix) )
{
int condJmpConstant;
int uncondJmpConstant;
condJmpConstant = ep->cndx; //remember where we are on the constants array.
//We'll come back to this position later and put
//in the "if false" jump targets. Right now,
//we don't know what those targets are.
//we'll come back later and put in the correct target values instead of zeros.
addConstant( ep, 0 ); //where we'll put the target constants index.
addConstant( ep, 0 ); //where we'll put the target instructions index.
addInstruction( ep, PUSH_C ); //push constants index to stack.
addInstruction( ep, PUSH_C ); //push instructions index to stack.
addInstruction( ep, COND_JMP ); //the conditional jump instruction.
//Uses values on the stack to restore the
//indexes of the constants array and the
//instructions array.
ep->infix++ ; //move past '?'
oldfix = ep->infix;
//Now compile the "Then_exp" part of the if(test)Then_exp else Else_exp
if( not expression( ep ) )
{
error( oldfix ); // '?' is only used here, so must be an error.
}
//We just successfully compiled the "Then" part of the construct.
//The last instruction of the "Then" part is an unconditional jump past the "Else" part
uncondJmpConstant = ep->cndx; //remember where to put the unconditional jump targets
//we'll come back later and put in the correct target values instead of zeros.
addConstant( ep, 0 ); //where we'll put the target constants index.
addConstant( ep, 0 ); //where we'll put the target instructions index.
addInstruction( ep, PUSH_C ); //push constants index to stack.
addInstruction( ep, PUSH_C ); //push instructions index to stack.
addInstruction( ep, UNCOND_JMP ); //the UNconditional jump instruction.
//we're now completely past the "Then" phrase. Now we know what the
//"if false" jump targets are (where we are right now). Go back and
//fill them in.
ep->constants[condJmpConstant] = ep->cndx;
ep->constants[condJmpConstant+1] = ep->indx;
//continue parsing. Move past the " :" part of the production rule.
ltrim( &(ep->infix);
if( ':' != *(ep->infix) ) //didn't get the ':' expected,
{
error( oldfix ); // '?' is only used here, so must be an error.
}
ep->infix++ ; //move past the ':'
oldfix = ep->infix;
//We're ready now to compile the "Else" part.
if( not expression( ep ) )
{
error( oldfix );
}
//We just successfully compiled the "Else" part of the construct.
//That is, we're at the very end of the z?x:y construct.
//fill in where to jump to after the "Then" part; the unconditional jump.
ep->constants[uncondJmpConstant] = ep->cndx;
ep->constants[uncondJmpConstant+1] = ep->indx;
}
return True;
}
模式：您可能需要在“解析器”中编写相当多的“编译器”代码。我想不到有什么方法可以一步完全接受 `?:` 结构，然后回头填写细节。我们不得不混合着进行。
main() 例程
任何时候实现编译器，尤其是手工实现（就像我们对表达式编译器所做的那样），您都应该构建一个非常好的测试套件。虽然我不会讨论构建它，但我会说，最好从测试最简单的结构开始，然后慢慢建立在成功的基础上。“`main()`”例程中的表达式源代码包含了我的测试。
到我的软件运行起来的时候，我通常会塞满调试语句。我认为最有效的调试是交互式调试器（如 Visual C++）和日志文件生成机制的结合。日志文件让我能够快速跳转到执行过程中我试图弄清楚正在发生什么的那个位置。`expression.c` 源代码也不例外。实际代码（与我在文章中包含的示例代码相对）充满了断言和调试代码。
在编写测试例程时，最好不要在成功时填满输出屏幕，而是仅在实际错误时显示错误消息。在我的 3GHz 机器上，如果我启用了完整的调试输出，则需要大约 7 秒钟才能输出所有测试用例的数据。另一方面，如果我禁用了调试，并且只要求它运行内部测试（不进行跟踪），那么在我按下回车键后就会很快完成。如果有人想编写一个脚本来测试许多不同的库，这要好得多。
测试过程中我想到的一件事是，没有万无一失的方法可以确定表达式系统将如何编译运行时传递给它的任何特定中缀表达式。情况如下：我将表达式放入 `.ini` 文件中，读取它，编译它，然后希望表达式编译器以我期望的方式解释它！是的，我可以编写一个单独的程序来读取表达式并计算它，并与已知输出进行比较，但这似乎对这些例程的用户来说工作量很大。因此，我在 `main()` 程序中包含了一个部分，可用于交互式地进行此目的。此外，如果有人不确定编译器是否正确解析了表达式，我包含了“-trace”选项来显示求值期间栈顶的几个元素，以及操作是如何执行的。人们可以将此与手动生成的相同表达式的 RPN 版本进行比较。
我发现该程序的测试版本对日常工作非常有用，以至于我将其重命名为“`eval.exe`”并将其放在我的路径中，这样我就可以从命令行调用它。现在我经常使用它进行一些我过去使用 Windows “`calc`”程序或打开电子表格进行的快速计算。
总结（x2）
经过仔细考虑和足够简单的语法，本文中确定的模式可以用于成功地自己编写递归下降解析器/编译器。考虑到学习编译器生成器系统所需的时间，自己编写编译器可能比学习新系统更有效率。我认为本文实现的表达式语法的复杂程度处于需要调出编译器生成器的边缘。
无论您是自己编写还是使用编译器生成器，您都必须清楚地理解编译器在识别每个产生式规则时需要做什么。实现了分支构造的非终结符函数（上面“`expression()`”非终结符）应该是一个很好的例子。编译器生成器无法帮助您。编译器生成器只是帮助您正确实现语法，并将产生式动作放在正确的位置。
*最后思考
*来自引言段落：“……当聪明人处于模式的存在时，软件就会神奇地演变（眨眼）。当然，我们知道这没什么神奇的：这需要大量的思考和辛勤的工作。但是生物机器（生物），其复杂程度远高于任何软件或硬件，似乎不需要任何“智慧”（或智力）就可以进化。如果我们相信进化论者，它们只是通过纯粹的随机机会出现的。
我曾听一位非常聪明的程序员说，将事情寄托在机遇上并不是编写软件的好方法。作为一名机械工程师，我 can confirm that this principle also applies in machine design; randomly stringing mechanical components together just doesn't cut it. Apparently, however, according to evolutionists, random chance works GREAT in biological design. Pure random chance composed not just any-old biological machine, but machines so complex that they can reproduce, and one of them is so sophisticated and intelligent that it even designs computers and writes software! Just unbelievable... 作为一名机械工程师，我 can confirm that this principle also applies in machine design; randomly stringing mechanical components together just doesn't cut it. Apparently, however, according to evolutionists, random chance works GREAT in biological design. Pure random chance composed not just any-old biological machine, but machines so complex that they can reproduce, and one of them is so sophisticated and intelligent that it even designs computers and writes software! Just unbelievable...
嗯。编译器生成器“编写”软件，有点模仿生物机器的行为（它模仿所谓“人类”的行为）。我认为一个真正伟大的编译器生成器可以通过随机打乱大量的指令来获得。而且，YACC 最初不就是这样产生的吗（但它是在计算机速度较慢的时代产生的。今天，我们有更好的随机数生成器和更快的计算机，所以这个新的编译器生成器将更智能/更发达）。
我开始干了！<nbsp><nbsp>
<nbsp><nbsp>;-)
祝您构建编译器愉快！
David Qualls
历史
- 2011年11月17日：初稿
- 2011年12月5日：文章更新