c - 编译器中的抽象语法树 : how exactly to represent a function?

Question

我们正在创建一种非常简单的编程语言，使用 Flex 和 Bison 进行解析和语法分析，并使用 C 构建编译器。
在直接进行汇编之前，我们将根据语言规则创建一个抽象语法树。但是我们很难从语言中表示一个特定的功能。
函数描述如下:

FILTERC: It takes a condition and an expression list as input and it returns how many of those expressions match the condition. It can be a single or compund condition. It is used in this form: FILTERC (condition, [expression list]) The condition has to have an underscore before each element, representing where the expressions should be placed for comparison. Example: FILTERC ( _>4 and _<=6.5 , [a+c,b,c-a,d])

这就是 BNF 规则中“filterc”函数的表达方式(我们实际上在 Flex 中使用了标记，但我用实际字符对其进行了简化，因为这不是重点，并且 Bison 正确完成了语法分析):

filter ::= FILTERC ( condition_filter , [ expression_list ] )
;
condition_filter ::= comparison_filter | comparison_filter AND comparison_filter | comparison_filter OR comparison_filter
;
comparison_filter ::= _ > expression | _ < expression | _ == expression | _ >= expression | _ <= expression | _ != expression
;
expression_list ::= expression | expression , expression_list
;
expression: term | expression + term | expression - term
;
term: factor | term * factor | term / factor 
;
factor: ID | INT_LITERAL | REAL_LITERAL | STRING_LITERAL | ( expression ) | filter
;

我们现在必须编写函数来创建抽象语法树的节点。在底层，“filterc”函数只不过是一堆“IF”来验证每个表达式是否与条件匹配，只是现在表达式将被放置在下划线所在的位置。所以它会是这样的:(表达式)(比较运算符)(条件)

问题是，实际的 FILTERC 语句是“向后”读取的:首先读取表达式，然后与条件进行比较。但是程序是按顺序读取的:在找到实际表达式之前读取下划线。所以我们真的很困惑如何构建这棵树。

我不会添加我们用来创建树的节点和叶子的所有代码，否则这将是一团糟。但基本上，有一个函数可以创建具有 2 个子节点(左和右)的节点，当不应该有任何子节点时，这些指针被设置为 null。我们使用的基本结构是将运算符放在根节点，操作数作为子节点(例如:在“if”语句中，“if”关键字应该是根节点，条件是左子节点和代码如果 true 是正确的 child ，则阻止执行)。像这样:

IF condition THEN block {thenPtr = blockPtr;} ENDIF {createNode("if", conditionPtr, thenPtr);}

(“条件”和“块”在别处定义，在那里创建它们的指针)。

我们能够成功地为表达式正则表达式和语言中的所有其他规则创建树，但是这个“过滤器”函数确实令人困惑。

Answer 1

确实，当解析器读取一段表达式(例如，“>”)时，它没有足够的东西来为表达式构建树。这同样适用于您语言中的任何概念(“非终结符”)。从这个角度来看，我认为你可能会感到困惑。

显然你不了解像 Bison 这样的 LR 解析器是如何工作的。假设我们有规则 R1, R2, ... 规则有右手边，例如， Rn = T1 T2 T3 ；每个规则的右手边长度为 L(Rn)。

您需要的关键思想是，LR 解析器从输入流中从左到右收集(“堆栈”，是的，它确实使用了一堆 token ) token 。这些步骤称为“转变”。解析器反复转换，不断寻找表明已经读取了足够的标记(例如，T1、T2、然后 T3)以满足某些语法规则 Rn 的右侧的情况。解析器生成器的神奇之处和它生成的 LR 表允许解析器一次有效地跟踪所有“实时”规则，我们不打算在这里进一步讨论。

在此时已识别出右侧的点处，LR 解析器执行“减少”操作并用非终结符 Rn 替换与规则主体匹配的堆叠标记(“弹出堆栈 L( Rn) 次然后插入 Rn")。在返回到从输入流中收集终端 token 之前，它会尽可能多地减少。在一个非常小的语法上手工模拟这个过程是值得的。 [一个微妙的细节:一些规则的右手边是空的，例如，L(Rn)==0)；在这种情况下，当发生减少时，发生零爆音，是的，这听起来很有趣，但它是致命的正确]。

在解析器执行reduce 操作的每一点上，它都为您(解析器程序员)提供了做一些额外工作的机会。额外的工作几乎总是“造树”。显然，构成规则 Rn 的记号都已经看到了，所以如果记号都是终端，就可以构建一棵代表 Rn 的树。事实上，如果已经看到了 Rn 的所有标记，并且 Rn 包含一些非终结符，那么一定有 reduce Action 来产生每个非终结符。如果它们中的每一个都生成了代表自己的树，那么当包含非终结符的规则减少时，已经为其他非终结符生成了树，并且可以将这些树组合起来为当前规则生成树。

像 Bison 这样的 LR 解析器生成器工具可以帮助您，通常通过提供您可以在 reduce-action 中调用的树构建操作符来帮助您。它还有助于使已处理的非终结符树可用于您的缩减操作，因此它可以将它们组合起来为缩减操作生成树。 (它通过在与 token 堆栈平行的堆栈中跟踪生成的树来做到这一点。)在任何时候它都不会尝试减少，或者您是否尝试过生成一棵树，其中您没有所需的所有子树.

我认为您需要仔细阅读 Bison，当您尝试实现解析器和缩减时，所有这些都会变得清晰；该手册有很好的例子。很明显你没有这样做(害怕不知道如何处理树木？)，因为 a) 你表达的规则被打破了；无法生成术语，并且 b) 您没有任何嵌入的 reduce 操作。