Chinaunix首页 | 论坛 | 博客
  • 博客访问: 264568
  • 博文数量: 52
  • 博客积分: 1379
  • 博客等级: 大尉
  • 技术积分: 525
  • 用 户 组: 普通用户
  • 注册时间: 2006-06-18 17:34
文章分类

全部博文(52)

文章存档

2011年(48)

2010年(4)

分类:

2010-10-16 16:33:39


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) |
给主人留下些什么吧!~~