你如何解析上下文敏感的C代码？

Question

我遇到的一个问题是C必须是上下文敏感的,并且无法使用一个前瞻标记进行解析.例如

int main1;
int main() {}

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

我的问题是,这是如何实现的？词法分析器是否有一些技巧可以进行前瞻,并发出一个区分两者的隐形标记？现代解析有很多前瞻性的标记吗？

Answer 1

您应该阅读LR或shift-reduce解析器.他们自下而上组装解析树.在main功能的情况下,它像:

• 移int进栈作为TYPE终端令牌
• 移main进栈作为标识符终端令牌
• 转移(到堆栈
• 转移)到堆栈
• 去除(和),并用ARGLIST非末端取代令牌
• 转移{到堆栈
• 转移}到堆栈
• 删除它们并替换为STMT_BLOCK非终端令牌
• 删除TYPE,IDENTIFIER,ARGLIST和STMT_BLOCK标记,并替换为FUNCTION_DEF标记.

当然,每次进行替换时,它都会构建一个新的解析树片段并将其附加到新令牌上.(我编写了这些令牌名称.)

它在有限状态机的控制下工作,该有状态机识别堆栈上的令牌模式,并与下一个(单个)输入令牌一起决定是否移动下一个令牌,或者应用其中一个语法规则来减少堆栈上的令牌组成一个单一的.FSM由解析器生成器根据语法规则列表构建.

它被称为LR,因为它从左侧读取输入令牌,但从右侧应用语法规则.它不同于LL或递归下降,它从左侧应用语法规则.Pascal是一种LL(1)语言.C不是LL(1),因此需要LR(1)解析器.例如,它允许C在嵌套括号中嵌入几乎任何东西而不会混淆解析器.

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