parsing - 从生成的解析表中检索语法规则

Question

我有一个很古老的C公司解析器代码，它是从一个古老的Yacc生成的，并使用yyact，yypact，yypgo，yyr1，yyr2，yytoks，yyexca，yychk ，yydef表（但没有yyreds），并且原始语法源也丢失了。那段旧代码需要修改，但我无法从头开始对其进行重新编码。

是否可以通过推导解析表来机械地检索/重新生成解析规则，以重构语法？

带有一个小的表达式解析器的示例，我可以使用相同的古老Yacc处理该表达式：

yytabelem yyexca[] ={
-1, 1,
    0, -1,
    -2, 0,
-1, 21,
    261, 0,
    -2, 8,
    };
yytabelem yyact[]={

    13,     9,    10,    11,    12,    23,     8,    22,    13,     9,
    10,    11,    12,     9,    10,    11,    12,     1,     2,    11,
    12,     6,     7,     4,     3,     0,    16,     5,     0,    14,
    15,     0,     0,     0,    17,    18,    19,    20,    21,     0,
     0,    24 };
yytabelem yypact[]={

  -248, -1000,  -236,  -261,  -236,  -236, -1000, -1000,  -248,  -236,
  -236,  -236,  -236,  -236,  -253, -1000,  -263,  -245,  -245, -1000,
 -1000,  -249, -1000,  -248, -1000 };
yytabelem yypgo[]={

     0,    17,    24 };
yytabelem yyr1[]={

     0,     1,     1,     1,     2,     2,     2,     2,     2,     2,
     2,     2,     2 };
yytabelem yyr2[]={

     0,     8,    12,     0,     6,     6,     6,     6,     6,     6,
     4,     2,     2 };
yytabelem yychk[]={

 -1000,    -1,   266,    -2,   259,   263,   257,   258,   267,   262,
   263,   264,   265,   261,    -2,    -2,    -1,    -2,    -2,    -2,
    -2,    -2,   260,   268,    -1 };
yytabelem yydef[]={

     3,    -2,     0,     0,     0,     0,    11,    12,     3,     0,
     0,     0,     0,     0,     0,    10,     1,     4,     5,     6,
     7,    -2,     9,     3,     2 };

yytoktype yytoks[] =
{
    "NAME", 257,
    "NUMBER",   258,
    "LPAREN",   259,
    "RPAREN",   260,
    "EQUAL",    261,
    "PLUS", 262,
    "MINUS",    263,
    "TIMES",    264,
    "DIVIDE",   265,
    "IF",   266,
    "THEN", 267,
    "ELSE", 268,
    "LOW",  269,
    "UMINUS",   270,
    "-unknown-",    -1  /* ends search */
};

/* am getting this table in my example, 
but it is not present in the studied parser :^( */
char * yyreds[] =
{
    "-no such reduction-",
    "stmt : IF exp THEN stmt",
    "stmt : IF exp THEN stmt ELSE stmt",
    "stmt : /* empty */",
    "exp : exp PLUS exp",
    "exp : exp MINUS exp",
    "exp : exp TIMES exp",
    "exp : exp DIVIDE exp",
    "exp : exp EQUAL exp",
    "exp : LPAREN exp RPAREN",
    "exp : MINUS exp",
    "exp : NAME",
    "exp : NUMBER",
};

我正在寻找

stmt    : IF exp THEN stmt
        | IF exp THEN stmt ELSE stmt
        | /*others*/
        ;

exp     : exp PLUS exp
        | exp MINUS exp
        | exp TIMES exp
        | exp DIVIDE exp
        | exp EQUAL exp
        | LPAREN exp RPAREN
        | MINUS exp
        | NAME
        | NUMBER
        ;

编辑：为了清楚起见，我剥离了示例的生成的解析器，但是为了帮助进行分析，我发布了整个生成的代码as a gist。请不要因为某种未知原因而不在我要研究/更改的解析器中没有yyreds表。我想这不会很有趣：^ S

Answer 1

一个有趣的问题。只是将表与语法进行匹配，似乎yyr1和yyr2为您提供了规则的“轮廓”-yyr1是每个规则左侧的符号，而yyr2是2x右侧的符号数。您还可以在方便的表格中找到所有终端的名称。但是非终端的名称丢失了。

要弄清楚哪些符号出现在每个规则的rh上，您需要从表中重建状态机，这可能涉及读取和理解实际执行解析的y.tab.c文件中的代码。有些表（看起来像yypact，yychk和yydef）由状态号索引。似乎yyact被yypact[state] + token索引了。但这只是猜测。您需要查看解析代码，并了解其如何使用表来编码可能发生的移位，减少和失真。

一旦有了状态机，就可以从包含特定规则简化的状态回溯到具有该规则变化和混乱状态的状态。转换为归约状态意味着该规则的最后一个符号是令牌已转换。 goto进入还原状态意味着rhs上的最后一个符号是goto的符号。倒数第二个符号从shift / goto变为执行shift / goto到归约状态的状态，依此类推。

编辑

正如我推测的那样，yypact是一个国家的“主要行动”。如果值为YYFLAG（-1000），则这是仅还原状态（无移位）。否则，它是一个潜在的转移状态，而yyact[yypact[state] + token]为您提供转移到的潜在状态。如果yypact[state] + token超出了yyact表的范围，或者令牌与该状态的条目符号不匹配，则该令牌没有任何移位。

yychk是每个状态的进入符号-正数表示您在该令牌上转移到该状态，而负数表示您在该非终端上转到该状态。

yydef是该状态的减少量-正数表示减少该规则，而0表示不减少，而-2表示两次或更多次可能的减少。 yyexca是具有多个减少量的州的减少量表。对-1 state表示以下项是给定状态的；以下对token rule表示对于前瞻token，它应减小rule。令牌的-2是通配符（列表的末尾），规则的0意味着没有可减少的规则（取而代之为错误），而-1表示接受输入。

yypgo表是符号的注释-如果状态yyact[yypgo[sym] + state + 1]在yyact的范围内，则进入状态yyact[yypgo[sym]]，否则进入yydef的状态。

因此，要重构规则，请查看yyexca和yyr1表以查看哪些状态简化了每个规则，然后向后查看该状态如何达到。

例如，规则1。从yyr2和S1: X X X X表中，我们知道其形式为yydef-在lhs上为非终端＃1，在rhs上为4个符号。在状态16中（从yychk表中减少），状态16中的访问符号（从yyact[26]中）为-1。

S1: ?? ?? ?? S1

您从yypgo[1] == 17和yypgo[1] + 8 + 1进入状态16，这意味着goto来自状态8（26 == THEN。状态8的访问符号是267（yyact[6]），所以我们现在有了：

S1: ?? ?? THEN S1

您从yypact[state] == -261进入状态8，因此先前的状态为yychk[3] == -2，即状态3。yyact[24]，因此我们具有：

S1: ?? S2 THEN S1

您从yypgo[2] == 24和进入状态3，因此此处任何状态都可能进入3。因此，我们现在对于该规则有些困惑；为了弄清楚第一个符号是什么，我们需要从状态0（开始状态）向前发展，以重建状态机。

编辑

此代码将从上面的表格格式解码状态机，并输出每种状态下的所有shift / reduce / goto操作：

#define ALEN(A)         (sizeof(A)/sizeof(A[0]))
for (int state = 0; state < ALEN(yypact); state++) {
    printf("state %d:\n", state);
    for (int i = 0; i < ALEN(yyact); i++) {
        int sym = yychk[yyact[i]];
        if (sym > 0 && i == yypact[state] + sym)
            printf("\ttoken %d shift state %d\n", sym, yyact[i]);
        if (sym < 0 && -sym < ALEN(yypgo) && 
            (i == yypgo[-sym] || i == yypgo[-sym] + state + 1))
            printf("\tsymbol %d goto state %d\n", -sym, yyact[i]); } 
    if (yydef[state] > 0)
        printf("\tdefault reduce rule %d\n", yydef[state]);
    if (yydef[state] < 0) {
        for (int i = 0; i < ALEN(yyexca); i+= 2) {
            if (yyexca[i] == -1 && yyexca[i+1] == state) {
                for (int j = i+2; j < ALEN(yyexca) && yyexca[j] != -1; j += 2) {
                    if (yyexca[j] < 0) printf ("\tdefault ");
                    else printf("\ttoken %d ", yyexca[j]);
                    if (yyexca[j+1] < 0) printf("accept\n");
                    else if(yyexca[j+1] == 0) printf("error\n");
                    else printf("reduce rule %d\n", yyexca[j+1]); } } } } }

它将产生如下输出：

state 0:
        symbol 1 goto state 1
        token 266 shift state 2
        symbol 2 goto state 3
        default reduce rule 3
state 1:
        symbol 1 goto state 1
        symbol 2 goto state 3
        token 0 accept
        default error
state 2:
        symbol 1 goto state 1
        token 257 shift state 6
        token 258 shift state 7
        token 259 shift state 4
        symbol 2 goto state 3
        token 263 shift state 5
state 3:
        token 261 shift state 13
        token 262 shift state 9
        token 263 shift state 10
        token 264 shift state 11
        token 265 shift state 12
        token 267 shift state 8
        symbol 1 goto state 1
        symbol 2 goto state 3
..etc

这应该对重构语法有帮助。