Lex和Yacc lex可以解析自己吗？

Question

Lex和Yacc可以一起解析lex和Yacc吗？

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

编辑:我并不是说组合需要完全解析输入的C部分。特别是，它不需要处理typedef名称/标识符冲突，也不需要构建一个完整的符号表(尽管我认为两者都可以在lexer和解析器中处理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) )之间做出区别。然后，令牌流读取

ID_COLON ID ID ID_COLON ID ID_COLON

这显然是LR(1)。

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

我所写的大部分内容都可以根据你对事物的看法而进行辩论。我声称“自然”语法不是LR(1)，但我不认为这里可以定义“自然”。所以是的，其他人可能会说YACC的语法是LR(1)。但最后，我们还是可以的，因为如果一种语言是LR(k)，那么它就是LR(1) (即LR(k)语法可以转化为LR(1)怪物文法，这是用类似的肮脏/整洁的技巧证明的)。

Wrt，是的，是的，它是引导的，但这样说也有点不正确:它的整体语法非常简单，而且很容易被regexps描述。然而，regexp本身逃离了仅仅是常规语言的领域:有括号！因此，在Lex/Flex的某个地方，必须有一个真正的解析器，不管是生成的还是手工编写的，来解析regexp。

询问Lex是否已引导，类似于询问C预处理程序是否已引导:是的，我确信其中有#include :)

Answer 2

yacc的POSIX规范包含一个Yacc语法，用于识别Yacc的输入。因此，是的，Yacc语法可以用Yacc编写。

lex的POSIX规范不包括它识别的正则表达式的Lex规范。然而，这并不意味着不能产生这样的规范。