是否可以通过扣除解析表来机械检索/重新生成解析规则以重建语法？
我可以使用相同的古代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
一个有趣的问题.只是从表格到语法匹配,似乎yyr1和yyr2给出了规则的“轮廓” – yyr1是每个规则左侧的符号,而yyr2是右侧符号数的2倍.您还可以在方便的表格中找到所有终端的名称.但是非终端的名字丢失了.要确定每个规则的rhs上有哪些符号,您需要从表中重建状态机,这可能涉及读取和理解实际进行解析的y.tab.c文件中的代码.一些表(看起来像yypact,yychk和yydef)由州号索引.看来yyact可能是由yypact [state]标记索引的.但那些只是猜测.您需要查看解析代码并了解它如何使用表来编码可能的shift,reduce和gotos.
拥有状态机后,您可以通过具有该规则的移位和结果的状态从包含特定规则减少的状态回溯.转换到缩减状态意味着该规则的rhs上的最后一个符号是转移的标记.转到缩小状态意味着rhs上的最后一个符号是goto的符号.倒数第二个符号来自shift / goto到执行shift / goto到还原状态的状态,依此类推.
编辑
正如我猜测的那样,yypact是一个州的“主要行动”.如果值为YYFLAG(-1000),则这是仅减少状态(无移位).否则它是一个潜在的移位状态,yyact [yypact [state] token]为你提供了转移到的潜在状态.如果yypact [state]标记超出yyact表的范围,或者标记与该状态的条目符号不匹配,则该标记没有移位.
yychk是每个状态的入口符号 – 正数表示您在该令牌上切换到该状态,而负数表示您在该非终端上转到该状态.
yydef是该状态的减少 – 正数表示减少该规则,而0表示不减少,-2表示减少两个或更多. yyexca是减少一个以上的州的减少表.对-1状态表示以下条目用于给定状态;以下对令牌规则意味着对于超前令牌它应该减少规则.令牌的-2是通配符(列表的末尾),而规则的0表示没有减少的规则(代之以错误),-1表示接受输入.
yypgo表是符号的gotos – 如果yyact和yyact [yypgo [sym]]的范围在yyact [yypgo [sym]状态1],则转到yyact [yypgo [sym] state 1].
因此,要重建规则,请查看yydef和yyexca表以查看哪些状态会减少每个规则,然后返回以查看状态是如何到达的.
例如,规则#1.从yyr1和yyr2表中,我们知道它的形式为S1：X X X X – lh上的非终端#1和rhs上的4个符号.它的状态16减少(来自yydef表,状态16(来自yychk)的访问符号为-1.所以它的：
S1: ?? ?? ?? S1
你从yyact [26]进入状态16,yypgo [1] == 17,这意味着goto来自状态8(26 == yypgo [1] 8 1.状态8的访问符号是267(那么现在我们有：
S1: ?? ?? THEN S1
你从yyact [6]进入状态8,所以前面的状态有yypact [state] == -261,状态为3.yychk [3] == -2,所以我们有：
S1: ?? S2 THEN S1
你从yyact [24]进入状态3,yypgo [2] == 24所以任何州都可以在这里转到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
这应该有助于重建语法.