5

我最近一直在为基于 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 */
}

我们必须介绍一些新的产品，其中变量/函数名称可以是IDENTIFIERor 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

4

1 回答 1

2

我不能说具体的代码。

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

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

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

如果您无法从其他标识符中区分 typedef，这整个技巧就是绕过解析歧义。如果您的解析器可以容忍歧义，那么您根本不需要这个 hack；只需解析，并使用两个（子）解析构建 AST。获取 AST 后，树遍历可以找到类型信息并消除不一致的子解析。我们使用 GLR 为 C 和 C++ 执行此操作，它很好地将解析与名称解析分开。

于 2013-06-20T10:00:43.687 回答