yacc 解析器在左递归后缀之前减少

Question

我在 yacc 中编写了一个非常简单的左递归语法，它基于一种简单的类 C 语言的数据类型。生成的yacc解析器在左递归后缀之前减少，我不知道为什么。

这里是源代码：

%%
start: type {
        printf("Reduced to start.\n");
    };

type: pointer {
        printf("Reduced pointer to type.\n");
    } 
    | char {
        printf("Reduced char to type.\n");
    };

char: KW_CHAR {
        printf("Reduced to char.\n");
    };

pointer: type ASTERISK {
        printf("Reduced to pointer.\n");
    };
%%

给定输入 char *（KW_CHAR 星号）：

Reduced to char.
Reduced char to type.
syntax error

Answer 1

您似乎并没有询问您收到的解析错误（如评论中所述，这可能是 yylex() 返回的令牌类型的问题），而是为什么解析器缩减是按照您的跟踪显示的顺序执行的。这就是我将在此处尝试解决的问题，即使它很可能是 XY problem，因为理解降序很重要。

在这种情况下，减少顺序非常简单。如果您有作品：

pointer: type ASTERISK

然后 type 必须在移动 ASTERISK 之前减少。在 LR 解析器中，当要减少的 right-hand 端恰好在最后消耗的输入标记处结束时，必须完成减少。（先行标记已被词法扫描器识别，但尚未被解析器使用。因此它不是归约的一部分，也可用于识别在同一点结束的其他归约。）

我希望制作中的原因更明显

type: char

char需要在type之前减少。在 char 被归约之前，它不能用于 type 的归约。

真的，这两个示例显示了相同的行为。缩减是 left-to-right，并且是自下而上（即首先 children）。因此，这种解析的名称。

所以你的解析器显示的缩减顺序（首先是 char，然后是 type，只有在 * 被移动之后，pointer）正是意料之中。

yacc 解析器在左递归后缀之前减少

yacc parser reduces before left recursion suffix

c

parsing

yacc

lalr