c - 您如何解析上下文相关的 C 代码？

Question

我遇到的一个问题是 C 必须是上下文相关的，并且不能用一个前瞻标记来解析。例如

int main1;
int main() {}

这是我能想到的最简单的示例，其中函数定义和变量声明都以相同的标记类型开头。您必须一直查看左括号或分号以确定要解析的内容。

我的问题是，这是如何实现的？词法分析器是否有一些袖手旁观的技巧来进行前瞻并发出区分两者的无形标记？现代解析有很多先行标记吗？

Answer 1

您应该阅读 LR 或 shift-reduce 解析器。他们自下而上地组装解析树。对于 main 函数，它是这样的:

• 将 int 作为 TYPE 终端 token 移入堆栈
• 将 main 作为 IDENTIFIER 终端 token 移入堆栈
• 将(移入栈中
• 将)移入栈中
• 删除 ( 和 ) 并替换为 ARGLIST 非终端标记
• 将{移入栈中
• 将移入栈中
• 删除那些并替换为 STMT_BLOCK 非终端标记
• 删除 TYPE、IDENTIFIER、ARGLIST 和 STMT_BLOCK 标记，并替换为 FUNCTION_DEF 标记。

当然，每次进行替换时，它都会构建一个新的解析树片段并将其附加到新的标记上。(我编造了这些 token 名称。)

它在有限状态机的控制下工作，该状态机识别堆栈中的标记模式，并与输入的下一个(单个)标记一起决定是将下一个标记移入，还是应用其中一个语法规则将堆栈上的一组标记减少为单个标记。 FSM 由解析器生成器根据语法规则列表构建。

之所以称为 LR，是因为它从左侧读取输入标记，但从右侧应用语法规则。它不同于 LL 或递归下降，后者从左侧应用语法规则。 Pascal 是一种 LL(1) 语言。 C 不是 LL(1)，因此需要 LR(1) 解析器。例如，它允许 C 在不混淆解析器的情况下将几乎所有内容嵌入嵌套括号中。

我希望这能帮助您了解正在发生的事情。