bison - Lex 和 Yacc 可以对自己进行 lex 和解析吗？

Question

Lex 和 Yacc 可以同时对 Lex 和 Yacc 进行 lex 和解析吗？

换句话说，是否可以编写一个自托管的 Lex/Yacc 组合，生成自己的解析器？

编辑:我并不是说组合需要完全解析输入的 C 部分。特别是，它不需要处理 typedef-name/identifier 冲突，或构建一个完整的符号表(尽管我相信两者都可以在词法分析器和解析器中用 C 代码处理) .这是因为 C 代码被逐字复制到输出。

编辑 2:基本上，Lex 和 Yacc(语言，而不是程序)有 LALR(1) 语法吗？

Answer 1

好吧，答案实际上比第一个答案报告的要复杂。我声称，不，YACC 无法解析 YACC，但细节决定成败。

YACC 的自然语法包括:

gram: %empty | gram rule
rule: ID ":" rhs
rhs: %empty | rhs ID

(使用类似 Bison 的约定:":" 是无值标记，ID 是标识符标记，%empty 强调RHS 为空的规则)。

不难看出这个文法不是LR(1)。作为 LR(1) 大致意味着当您的光标前进时，您只需查看下一个标记就知道您在哪个规则中。然后考虑以下(有效)输入:

ID : ID ID
ID : ID
ID :

您能否轻易地辨别出一条规则何时开始以及下一条规则何时开始？好吧，这种方式太简单了，试着找出 YACC 会看到的:

ID : ID ID ID : ID ID :

您如何知道第一条规则何时完成？将光标的位置视为下面的 .:

ID : ID . ID ID : ID ID :

第一条规则完成了吗？当然不是。下一步呢？

ID : ID ID . ID : ID ID :

第一条规则完成了吗？是的，很明显。但是在这两种情况下，下一个标记(也称为“先行”)都是 ID；以下标记有助于确定当前规则是否完成(“:”)或未完成(ID)。换句话说，1 次前瞻是不够的，这个文法不是 LR(1)，因此也不是 LALR(1)(这是 YACC 接受的文法类别)。显然是LR(2)。

如果我们接受更改语言并要求终止 ; 规则，那么使此语法成为 LR(1) 将非常容易:

ID : ID ID ; ID : ID ; ID : ;

不幸的是，为时已晚，POSIX 并未决定强制使用此分号，因此 YACC 的实现必须处理此 LR(2) 语法。

在 Bison 的情况下，它使用整洁/肮脏(取决于您的观点)技巧来处理它:扫描器被教导区分“常规”标识符(ID ) 和一个标识符后跟一个冒号 (ID_COLON)。然后 token 流读

ID_COLON ID ID ID_COLON ID ID_COLON

这显然是 LR(1)。

那么为什么从 YACC 开始就不需要分号呢？好吧，由于明显的引导原因，YACC 不能首先在 YACC 中编写，所以我猜 S. Johnson 从未意识到他手工编写的解析器实际上接受了比 LR(1) 更难的语法。 Bison 和 byacc 来自一个普通的克隆，其解析器也是手写的。 Bison 自己的解析器是在 2002 年启动的(commit e9955c83734d0a545d7822a1feb9c4a8038a62cb)。

我写的很多内容都可以根据您的看法进行辩论。我声称“自然”语法不是 LR(1)，但我认为不能在这里定义“自然”。所以是的，别人可能会说YACC的文法是LR(1)。但最后，我们没问题，因为如果一种语言是 LR(k)，那么它就是 LR(1)(即 LR(k) 文法可以变成 LR(1) 怪兽文法，即证明使用类似的肮脏/整洁的技巧)。

Wrt Flex，嗯，是的，它是自举的，但这样说也有点不真实:它的整体语法非常简单，很容易用正则表达式描述。然而，正则表达式本身逃脱了纯粹的常规语言的领域:有括号!所以在 Lex/Flex 内部的某个地方，必须有一个真正的解析器，无论是生成的还是手写的，来解析正则表达式。

询问 Lex 是否自举类似于询问 C 预处理器是否自举:是的，我确定那里有 #include:)