解析C/C++源代码：在lex/yacc中如何指定标记边界/交互？

Question

我想解析一些C++代码，作为指南，我一直在查看这里的C lex/yacc定义：http://www.lysator.liu.se/c/ANSI-C-grammar-l.html和http://www.lysator.liu.se/c/ANSI-C-grammar-y.html。

我理解标记本身的规范，但不理解它们之间的交互。例如，直接在标识符后面没有中间空格就可以有一个操作符（即“foo=”），但是数字常量紧接着标识符就不行（即123foo）。然而，我没有看到这种规则的表示方式。

我错过了什么？还是这个lex/yacc在错误接受方面太自由了？

- Greencpp

---

你说“我想解析一些C++代码”，就赢得了我的心。 - j_random_hacker

Answer 1

词法分析器将字符流转换为令牌流（我认为这就是您所说的令牌规范）。语法规定了哪些令牌序列是可接受的。因此，您不会看到不允许的内容；您只能看到允许的内容。这有意义吗？

编辑

如果要使词法分析器区分序列“123foo”和序列“123 foo”的方式之一是添加“123foo”的规范。另一种方法是将空格视为重要。

编辑2

语法错误可以从词法分析器或语法制作或编译器的后期阶段（比如类型错误，它们仍然是“语法错误”）中“检测”出来。整个编译过程的哪个部分检测哪个错误在很大程度上是一个设计问题（因为它影响错误消息的质量），我想。在给定的示例中，通过将其标记化为无效标记禁止“123foo”可能比依赖于数字文字后跟标识符的制作更有意义（至少，这是gcc的行为）。

- lijie

---

我觉得我有点困惑你的问题。"123foo" 可能甚至不能作为单个标记进行词法分析（在词法规范中没有接受 123foo 的表达式）。 - lijie

但是这个想法是指定可接受的内容，而不符合规范的所有内容都是不可接受的。 - lijie

是的，我很感兴趣了解这个问题的后续情况 :-) - Greencpp

@Greencpp：为什么你希望在词法分析阶段拒绝123foo？ - Martin York

我不一定懂得所有的东西，只是试图理解它们。这次讨论对我有所帮助。谢谢大家。 - Greencpp

Answer 2

词法分析器能正确处理123foo，并将其分割为两个标记。

• 一个整数常量
• 和一个标识符。

但是请尝试找出语法中允许这两个标记并排坐在一起的部分。因此，我打赌当词法分析器看到这两个标记时会生成一个错误。

请注意，词法分析器不关心空格（除非你明确告诉它要担心）。在这种情况下，它只会扔掉空白：

[ \t\v\n\f]     { count(); } // Throw away white space without looking.

只是为了检查这是我构建的内容：

wget http://www.lysator.liu.se/c/ANSI-C-grammar-l.html > l.l
wget http://www.lysator.liu.se/c/ANSI-C-grammar-y.html > y.y

编辑文件 l.l，以防止编译器抱怨未声明的函数：

#include "y.tab.h"

// Add the following lines
int  yywrap();
void count();
void comment();
void count();
int  check_type();
// Done adding lines

%}

创建以下文件：main.c:

#include <stdio.h>

extern int yylex();

int main()
{
    int x;
    while((x = yylex()) != 0)
    {
        fprintf(stdout, "Token(%d)\n", x);
    }
}

构建它：

$ bison -d y.y
y.y: conflicts: 1 shift/reduce
$ flex l.l
$ gcc main.c lex.yy.c
$ ./a.out
123foo
123Token(259)
fooToken(258)

是的，它将其分成了两个标记。

- Martin York

---

对，我之前被空格的存在所困扰，但是实际上无论是否存在空格都是无效的。 - Greencpp

由lex生成的部分如果标记在语法上不匹配，也不会报错；而由yacc生成的部分则会报错。 - lijie

@Greencpp：什么是无效的？它是一个完全有效的标记流（因为词法分析器不关心语法）。但这是一个语法错误，因此解析器应该报错。 - Martin York

Answer 3

本质上正在发生的是每个标记类型的词法规则都是贪婪的。例如，字符序列foo=不能被解释为单个标识符，因为标识符不包含符号。另一方面，123abc实际上是一个数字常量，虽然格式不正确，因为数字常量可以以一系列用于表示数字常量类型的字母字符结尾。

- SingleNegationElimination

---

严格来说，123abc 在 C++03 中是无效的，但在 C++0x 中是有效的，因为 C++0x 具有用户自定义字面量功能（http://en.wikipedia.org/wiki/C%2B%2B0x#User-defined_literals）。 - SingleNegationElimination

我认为数字后面只允许有有限的字母，即[uUlL]...你是说规范比这更通用吗？ - Greencpp

我非常确定，链接到的词法规范实际上会将123foo标记为一个常量后跟一个标识符，而不是作为单个（格式错误的）常量。 - Laurence Gonsalves

假设在 c++03 中，我有一个源序列像 123ublabla，这可能被歧义地解释为文字 123 后跟标识符 ublabla，这很可能是意思所在，但由于词法分析器的贪婪性，它将被解释为 123u 和 blabla。基本上不可能证明这是好的，因此文字可以以类似于标识符的序列结尾，并作为单独的步骤进行验证/评估。 - SingleNegationElimination

我觉得在词法分析器中是否进行贪婪匹配是一个“故意”的选择（只是大多数语言确实会贪婪匹配）。 - lijie

看起来单独的步骤就是语法，对吗？即“常量标识符”无效，因此无论123和foo之间有没有空格，该结构都是无效的。 - Greencpp

Answer 4

你无法使用lex和yacc解析C++，因为它是一个模糊的语法。你需要更强大的方法，比如GLR或一些hackish的解决方案，可以在运行时修改词法分析器（这就是大多数当前的C++解析器正在做的事情）。

看看Elsa/Elkhound。

- SK-logic

---

Bison现在支持GLR，因此它非常适合解析C ++。 - user556210

不要将“原始解析”能力与在处理实际的C++代码上取得进展混淆。您还需要名称和类型解析以及许多其他内容。C++14标准已经发布；它是“巨大的”；祝你好运，将所有这些考虑为构建工具的一部分。（我的公司提供完整的C++11几乎C++14解析器，因此可能会被指责有偏见；请注意，我的公司已经开发了十多年。） - Ira Baxter

@IraBaxter，回答时Elsa可以被认为是一个相当完整的C++解析器和语义分析器实现。当然，现在不是了。不幸的是，它自那以后就没有得到维护。尽管如此，现在有了Clang的完全支持，这样的工具几乎没有什么需求了。 - SK-logic