|
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数组中
阅读(1939) | 评论(0) | 转发(0) |
