如何在 C 中解决 typedef-name - 标识符问题？

Question

我最近一直在为基于 C 的语言编写解析器。我正在使用 CUP（Java 的 Yacc）。

我想实施“词法分析器黑客”（http://eli.thegreenplace.net/2011/05/02/the-context-sensitive-of-c%E2%80%99s-grammar-revisited/ 或 https:/ /en.wikipedia.org/wiki/The_lexer_hack），以区分 typedef 名称和变量/函数名称等。要启用与之前声明的类型相同名称的变量（来自第一个链接的示例）：

typedef int AA;

void foo() {
    AA aa;       /* OK - define variable aa of type AA */
    float AA;    /* OK - define variable AA of type float */
}

我们必须引入一些新的产生式，其中变量/函数名称可以是IDENTIFIER或TYPENAME。这就是困难发生的时刻——语法冲突。

我试图不将这种凌乱的 Yacc 语法用于 gcc 3.4 ( http://yaxx.googlecode.com/svn-history/r2/trunk/gcc-3.4.0/gcc/c-parse.y )，但这次我不知道如何自己解决冲突。我看了一下 Yacc 语法：

declarator:
    after_type_declarator
    | notype_declarator
    ;

after_type_declarator:
    ...
    | TYPENAME
    ;

notype_declarator:
    ...
    | IDENTIFIER
    ;

fndef:
    declspecs_ts setspecs declarator
    // some action code
    // the rest of production
...

setspecs: /* empty */
    // some action code

declspecs_ts 表示声明说明符，其中“是否已看到类型说明符；在类型说明符之后，typedef 名称是要重新声明的标识符（_ts 或 _nots）。”

从 declspecs_ts 我们可以达到

typespec_nonreserved_nonattr:
    TYPENAME
    ...
    ;

乍一看，我简直不敢相信 shift/reduce 冲突怎么没有出现！ setspecs是空的，所以我们declspecs_ts跟着declarator，这样我们就可以预期解析器应该混淆TYPENAME是 fromdeclspecs_ts还是 from declarator。

任何人都可以简要（甚至准确地）解释这一点。提前致谢！

编辑：有用的链接：http ://www.gnu.org/software/bison/manual/bison.html#Semantic-Tokens

Answer 1

具体代码我不敢说。

但基本技巧是 C 词法分析器检查每个 IDENTIFIER，并决定是否可能是 typedef 的名称。如果是这样，那么它将词素类型更改为 TYPEDEF 并将其交给解析器。

词法分析器如何知道哪些标识符是 typedef？解析器实际上必须通过在运行时捕获 typedef 信息来告诉它。在与声明相关的语法中的某个位置，必须有一个操作来提供此信息。我本以为它会附加到 typedef 声明的语法规则中。

你没有展示“setspec”做了什么；也许就是这个地方。LR 解析器生成器使用的一个常见技巧是引入一个右手空的语法规则 E（您的示例“setspec”？），在其他语法规则（您的示例“fndef”）中间调用，只是为了启用在处理该规则的过程中访问语义动作。

如果您无法区分 typedef 和其他标识符，这整个技巧就是为了避免解析歧义。如果你的解析器可以容忍歧义，那么你根本不需要这个 hack；只需解析，并使用两个（子）解析构建 AST。获取 AST 后，树遍历可以查找类型信息并消除不一致的子解析。我们使用 C 和 C++ 的 GLR 来实现这一点，它完美地将解析与名称解析分开。