void make_parser(void) { int i;
parser = NEW2(nstates, action *); for (i = 0; i < nstates; i++) parser[i] = parse_actions(i);
find_final_state(); remove_conflicts(); unused_rules(); if (SRtotal + RRtotal > 0) total_conflicts(); defreds(); }
|
在每个状态上,都有一个action链表来描述它可以执行什么动作
action有两种类型动作,一种是SHIFT,一种是REDUCE
一个状态可以有多个SHIFT,每个SHIFT对应一个终结符,这些终结符保存在shift_table数组中
一个状态同时可以有多个REDUCE,每个(rule号,向前看符号)对应一个
static action * add_reductions(int stateno, action *actions) { int i, j, m, n; int ruleno, tokensetsize; unsigned *rowp;
tokensetsize = WORDSIZE(ntokens); m = lookaheads[stateno]; n = lookaheads[stateno + 1];
//所有可以规约的规则 for (i = m; i < n; i++) { ruleno = LAruleno[i]; rowp = LA + i * tokensetsize;
//该规则对应的向前看符号,每个符号都有一个REDUCE for (j = ntokens - 1; j >= 0; j--) { if (BIT(rowp, j)) actions = add_reduce(actions, ruleno, j); actions } } return (actions); }
|
parser数组存每个状态对应的action链表的头,链表已经按照symbol和类型以及规则号排序
find_final_state();
该函数找出哪个状态号是接受状态, 接受状态就是从状态0接受一个goal到达的状态,如代码所示:
static void find_final_state(void) { int goal, i; Value_t *to_state2; shifts *p;
p = shift_table[0]; to_state2 = p->shift; goal = ritem[1]; for (i = p->nshifts - 1; i >= 0; --i) { final_state = to_state2[i]; if (accessing_symbol[final_state] == goal) break; } }
|
remove_conflicts();
冲突解决也是yacc中很重要的一部分,因为它直接关系到规则的语义和一些默认行为。如果用户的理解和yacc不一致,那用户写的规则可能不是用户想要表达的。
上面的actions结构无论是SHIFT还是REDUCE,都有一个符号对应,如果一个状态上有一个符号出现多次,那么就出现冲突了.
冲突可能出现在SHIFT和REDUCE之间,也可能是SHIFT和REDUCE之间,分别称为SR(移入-规约)冲突和RR(规约-规约)冲突。
static void remove_conflicts(void) { int i; int symbol; action *p, *pref = 0;
SRtotal = 0; RRtotal = 0; SRconflicts = NEW2(nstates, Value_t); RRconflicts = NEW2(nstates, Value_t); for (i = 0; i < nstates; i++) { SRcount = 0; RRcount = 0; symbol = -1; for (p = parser[i]; p; p = p->next) { /* 如果不是相同的符号,那就没有冲突 */ if (p->symbol != symbol) { pref = p; symbol = p->symbol; } else if (i == final_state && symbol == 0) { /* $end 有点特殊,如果看见goal了,前面是$end 直接就shift接受了 */ SRcount++; p->suppressed = 1; } else if (pref != 0 && pref->action_code == SHIFT) { /* SHIFT-REDUCE冲突 */ /* p必然是REDUCE类型,p->prec对应规则的优先级 */ if (pref->prec > 0 && p->prec > 0) { /* 都具有优先级 */ if (pref->prec < p->prec) { /* 终结符的优先级低, 规约, suppressed = 2;该action永远不会有效 */ pref->suppressed = 2; pref = p; } else if (pref->prec > p->prec) { /* 终结符的优先级高, 移入, 当前action(p) 失效 */ p->suppressed = 2; } else if (pref->assoc == LEFT) { /* 终结符的优先级和规则相等 * 如果终结符是左结合的,则规约 */ pref->suppressed = 2; pref = p; } else if (pref->assoc == RIGHT) { /* 终结符的优先级和规则相等 * 如果终结符是右结合的,则移入 */ p->suppressed = 2; } else { /* 没有结合性,无法解决 */ pref->suppressed = 2; p->suppressed = 2; } } else { /* 如果有至少一个没有优先级 * 则移入 */ SRcount++; p->suppressed = 1; } } else { /* REDUCE-REDUCE冲突, 选择靠前的规则 */ RRcount++; p->suppressed = 1; } } SRtotal += SRcount; RRtotal += RRcount; SRconflicts[i] = SRcount; RRconflicts[i] = RRcount; } }
|
另外可以看出,如果优先级能解决冲突,则不对冲突计数,因为这种冲突是yacc的特性之一,用户通常不希望这种情况报冲突,比如a+b*c,在遇到*时的冲突解决
suppressed 的值 1和2分别表示是否计数
比如当向前看符号没有action的时候,如果有一个REDUCE action的suppressed是0或者1,那么可以打印其它符号是规约
unused_rules();
该函数检查是否有某些规则没有有效地出现在某个REDUCE类型的action中。
defreds();
该函数判断某个状态是否可以直接规约,而不需要参考向前看符号,有两种情况符合要求:
1. 只有一个REDUCE action
2. 有若干个REDUCE action,但是规则号相同,这样,无论向前看符号是不是这些action对应的符号,都该规约
每个状态的默认规约规则号存在defred数组中
阅读(1950) | 评论(0) | 转发(0) |