byacc 笔记二 lr0

lr0函数代码

void
lr0(void)
{
    set_derives();
    set_nullable();
    generate_states();
}



lr0函数生成lr0状态机

set_derives

该函数计算各个非终结符对应哪些规则，在calc.y中如下：

set_nullable();

该函数计算文法符号是否可空
初始所有文法符号都不可空，通过ritem(如下）

就能得到所有规则的右边符号（如果有的话） ，如果右边是空，那么标记其左边符号可空
如果遍历了一遍ritem发现某个符号可空，那么还需要继续，因为可能有这种规则
A: B;
其中B在上一趟计算出来可空，而A由于计算的时候B还是非空而没有计算出来，这次可以计算出来A可空，因为A右端所有的符号都可空

不断继续，可以看出会结束
结束之后，所有可空的也都计算完了

在该例子只有list可空

done_flag = 1;
    for (i = 1; i < nitems; i++)
    {
     empty = 1;
     while ((j = ritem[i]) >= 0)
     {
        if (!nullable[j])
         empty = 0;
        ++i;
     }
     /* 右边是空，或者右边项目都可空 */
     if (empty)
     {
         /* 项目i开始的项目对应的规则的左边 */
        j = rlhs[-j];
        if (!nullable[j])
        {
            /* 以前认为规则j不能是空的，现在可以空
             * j可能存在于某个j2的右边, 所以需要重新遍历
             * 但是很明显，总能结束
             */
         nullable[j] = 1;
         done_flag = 0;
        }
     }
    }


generate_states();

分配项目空间

调用 allocate_itemsets 函数分配每个状态对应的项目集合需要用到的数据结构:

1. kernel_base 和 kernel_items

kernel_base为每个文法符号准备一个指针，它的具体位置在kernel_items中
假设文法符号X在规则右边出现了n次，那么它对应n个位置，比如$end只有一次（$accept: goal $end)
所以$end只向0号位置，并且占用一个位置，DIGIT的次数为2， 如下是calc.y规则

number:  DIGIT
         {  $$ = $1; base = ($1==0) ? 8 : 10; }
      |  number DIGIT
         {  $$ = base * $1 + $2; }
      ;
显然$accept没有出现在右边， UMINUS也没有（它只是记录优先级），所以不占位置

这种指针+数组的结构比较紧凑，byacc好多数据结构都是这种存储方式，以前也遇到过。

每个文法符号出现多少次是通过遍历数组ritem得到的，比较简单。

2. shiftset, redset, state_set

shiftset用于在某个状态上记录可以转移到哪些状态
redset用于在某个状态上记录可以有哪些规则可规约
state_set用于查找某个状态集合是否已经对应了某个状态（号）

set_first_derives

该函数首先调用set_EFF对每个非终结符A计算它相应规则右端第一个可能的非终结符是什么
以及第一个右端非终结符对应的规则第一个非终结符, ...一直传递下去
并且把该A本身也带上

比如 A: B X |D X
B: C X
D: E

那么A将计算出 BCED等符号



记录在名字为EFF的位图数组中，每个非终结符对应一个位图
位图可以涵盖所有的非终结符， 如下所示

/* nvars * nvars bits */
rowsize = WORDSIZE(nvars);
EFF = NEW2(nvars * rowsize, unsigned);


nvars就是非终结符的个数
计算EFF的方法：

首先每个终结符对应的规则在derives已经有记录
而每个规则右边第一个符号记录在rrhs中（reader）
每个符号是不是终结符跟start_symbol比较就可以了， start_symbol ~ nsyms都是非终结符
自反传递闭包由warshall算法计算
在reflexive_transitive_closure函数中

对于calc.y，如下：


直观上看，当我们期待一个expr的时候，也允许number出现

在任何非终结符A 得到 A：B X中的所有B之后，就可以计算相应的B出现在哪些规则中
把这些规则号保存在一个位图数组中，和EFF类似，只是这时位图代表规则号，而EFF代表非终结符

每个B来自哪些规则由derives给出， 所以计算比较简单，一个个终结符遍历EFF对应的位图和derives就可以了


对于calc.c：

First Derives

$accept derives
   2
   3
   4
   5

list derives
   3
   4
   5

stat derives
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17

expr derives
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17

number derives
   16
   17

把它们的值减去2之后就和如下内容可以对应

0 $accept : list $end

   1 list :
   2 | list stat '\n'
   3 | list error '\n'

   4 stat : expr
   5 | LETTER '=' expr

   6 expr : '(' expr ')'
   7 | expr '+' expr
   8 | expr '-' expr
   9 | expr '*' expr
  10 | expr '/' expr
  11 | '-' expr
  12 | LETTER
  13 | number

  14 number : DIGIT
  15 | number DIGIT

可以看出$accept 对应前4条规则，其它类似

initialize_states

在一切准备就绪之后，generate_states调用该函数生成状态0，它只包含一个核心项目
在calc.y 中，它是

$accept: . list $end

状态的意义：

语法分析的目标就是识别goal，在calc.y中它是一个list,对C语言来说它是翻译单元，然后遇到EOF就算成功。
所以刚开始的时候我们期待看到$accept，这正是构造$accept的原因

项目代表我们期望看到什么，刚开始我们希望要得到$accept, 我们期待出现一个list（而且必须有一个list）
状态0仅仅包含一个核心项目的原因也就是$accpet只有一个规则的原因。
当然由于list可以推导出其它符号，所以该状态也会包含一些非核心项目，只是这些非核心项目并不保存在状态中

/* 生成状态0, 为其它状态做准备 */
static void
initialize_states(void)
{
    unsigned i;
    short *start_derives;
    core *p;

    /* rlhs[2] = start_symbol;
     * $accept 只有规则0，其值是2
     */
    start_derives = derives[start_symbol];
    for (i = 0; start_derives[i] >= 0; ++i)
    continue;

    assert(i == 1);

    p = (core *)MALLOC(sizeof(core) + i * sizeof(short));
    NO_SPACE(p);

    p->next = 0;
    p->link = 0;
    p->number = 0; /* 状态号 */
    p->accessing_symbol = 0; /* 什么符号到达该状态 */
    p->nitems = (Value_t) i;

    for (i = 0; start_derives[i] >= 0; ++i)
    p->items[i] = rrhs[start_derives[i]];

    /* 状态0只有一个项目, 即 $accept: . goal $end */
    assert(i == 1 && ritem[p->items[0]] == start_symbol+1 /* goal */);

    first_state = last_state = this_state = p;
    nstates = 1;
}


生成其它状态

从语句     p->items[i] = rrhs[start_derives[i]]; 可以看出项目的表示就是ritem的位置

在initialize_states生成状态0后，generate_states不断的循环生成其它的状态，直到不会有更多的状态

while (this_state)
    {
    closure(this_state->items, this_state->nitems);
    save_reductions();
    new_itemsets();
    append_states();

    if (nshifts > 0)
     save_shifts();

    this_state = this_state->next;
    }


1. 求非核心状态

closure根据核心项目生成非核心项目
比如对于状态0 $accept: list $end

对任何 list推导Aabc的A在first_derives中保存着，把这些A对应规则A：X Y对应的项目A：. X Y
加入到当前状态（现在0）中，就得到所有的项目，这些项目就表示，我们接下来该看到什么：
就是这些项目中的某个符号

这些项目保存在itemset中， 这只是临时为生成状态用的，大小是nitems， itemsetend是当前状态
所有项目的结尾

2. 当前状态是否可以规约

因为itemset中保存了所有的项目，save_reductions可以知道某个项目是否是规则的结尾处：

count = 0;
    for (isp = itemset; isp < itemsetend; isp++)
    {
    item = ritem[*isp];
    if (item < 0)
    {
     redset[count++] = (Value_t) - item;
    }
    }


参考ritem，每个规则结尾存有规则号的相反数

redset就表示有哪些规则可以规约

reductions结构用来保存一个状态的规约，它记录了相应的状态号（依次递增每生成一个状态有一个号）以及有几个规约等信息

3. 移进符号产生新状态

itemset中所有不是结尾的项目 A: X . Y，移进Y后可以得到新的状态，所有的符号Y保存在shift_symbol中

这是由new_itemsets来完成的

for (i = 0; i < nsyms; i++)
    kernel_end[i] = 0;

    shiftcount = 0;
    isp = itemset;
    while (isp < itemsetend)
    {
    i = *isp++;
    symbol = ritem[i];
    if (symbol > 0)
    {
     ksp = kernel_end[symbol];
     if (!ksp)
     {
        shift_symbol[shiftcount++] = symbol;
        ksp = kernel_base[symbol];
     }

     *ksp++ = (Value_t) (i + 1);// A: X . Y Z  TO A: X Y .Z
     kernel_end[symbol] = ksp;
    }
    }


结果保存在kernel_base指向的位置中!! kernel_base 为每个符号保留了足够的位置


接下来的append_states比较简单了

for (i = 0; i < nshifts; i++)
    {
    symbol = shift_symbol[i];
    shiftset[i] = get_state(symbol);
    }


对每个shift_symbol中的symbol, 移近之后有哪些项目在kernel_base[symbol]和kernel[end]中保存着，即看到symbol之后还能看到什么，当然这些项目是核心项目

get_state比较两个状态是否等价，如果是就范围状态号，否则新建状态

和reduction类似 shifts结构保存移进信息， 由save_shifts完成

至此，由于状态数是有限的(所有项目元素集合的幂集个数)，generate_states函数的不断生成新状态的循环总会结束

所有的状态生成，规约信息和移进都有了