lalr是yacc最难理解的地方，在分析源码的时候一直以为使用的是龙书上的算法
byacc和bison是一样的算法，据说是同一作者写的，只是gnu的选项多，后来byacc也加了一些选项，参考bison
在byacc的ACKNOWLEDEMENTS中写到
Berkeley Yacc is based on the excellent algorithm for computing LALR(1)
lookaheads developed by Tom Pennello and Frank DeRemer. The algorithm is
described in their almost impenetrable article in TOPLAS 4,4.
这篇文章就是<
>
该论文用形式语言描述了LALR1
从这篇文章的题目，就可以看出lalr1要做什么： 计算向前看符号
void
lalr(void)
{
tokensetsize = WORDSIZE(ntokens);
set_state_table();
set_accessing_symbol();
set_shift_table();
set_reduction_table();
set_maxrhs();
initialize_LA();
set_goto_map();
initialize_F();
build_relations();
compute_FOLLOWS();
compute_lookaheads();
}
|
set_state_table();
set_accessing_symbol();
set_shift_table();
set_reduction_table();
这4个函数把相应的数据结构放入相应的数组中
set_maxrhs();
该函数计算所有产生式右边最多文法符号的个数
initialize_LA();
该函数初始化向前看符号集
static void
initialize_LA(void)
{
int i, j, k;
reductions *rp;
lookaheads = NEW2(nstates + 1, Value_t);
/* 每个状态都可能可以执行规约动作，某个状态可能可以对若干个规则进行规约
* 所以每个规则都需要一个向前看符号集
* lookaheads数组给每个状态保留对应可规约规则数n对应的空槽数
* 每个空槽对应于一个向前看符号集
*/
k = 0;
for (i = 0; i < nstates; i++)
{
lookaheads[i] = (Value_t) k;
rp = reduction_table[i];
if (rp)
k += rp->nreds; /* nreds即可规约的规则数 */
}
lookaheads[nstates] = (Value_t) k;
/* LA: 一共k个向前看符号集 */
LA = NEW2(k * tokensetsize, unsigned);
LAruleno = NEW2(k, Value_t);
lookback = NEW2(k, shorts *);
k = 0;
for (i = 0; i < nstates; i++)
{
rp = reduction_table[i];
if (rp)
{
for (j = 0; j < rp->nreds; j++)
{
/* lookaheads指针指向LAruleno */
LAruleno[k] = rp->rules[j];
k++;
}
}
}
}
|
set_goto_map();
static void
set_goto_map(void)
{
shifts *sp;
int i;
int symbol;
int k;
Value_t *temp_map;
Value_t state2;
Value_t state1;
goto_map = NEW2(nvars + 1, Value_t) - ntokens;
temp_map = NEW2(nvars + 1, Value_t) - ntokens;
ngotos = 0;
for (sp = first_shift; sp; sp = sp->next)
{
for (i = sp->nshifts - 1; i >= 0; i--)
{
/* shift 数组存有移入之后的状态, 每个状态有相应的symbol */
symbol = accessing_symbol[sp->shift[i]];
/* append_states 已经对nshifts个可移入符号排序, 非终结符在后 */
if (ISTOKEN(symbol))
break;
if (ngotos == MAXSHORT)
fatal("too many gotos");
ngotos++;
goto_map[symbol]++;
}
}
k = 0;
for (i = ntokens; i < nsyms; i++)
{
temp_map[i] = (Value_t) k;
k += goto_map[i];
}
for (i = ntokens; i < nsyms; i++)
goto_map[i] = temp_map[i];
goto_map[nsyms] = (Value_t) ngotos;
temp_map[nsyms] = (Value_t) ngotos;
from_state = NEW2(ngotos, Value_t);
to_state = NEW2(ngotos, Value_t);
for (sp = first_shift; sp; sp = sp->next)
{
state1 = sp->number;
for (i = sp->nshifts - 1; i >= 0; i--)
{
state2 = sp->shift[i];
symbol = accessing_symbol[state2];
if (ISTOKEN(symbol))
break;
k = temp_map[symbol]++;
from_state[k] = state1;
to_state[k] = state2;
}
}
FREE(temp_map + ntokens);
}
|
对每个非终结符A，都可能在某个状态S1上有项目 X:Y .A; 移入A可以使得S1跳转到S2；
goto_map数组对每个非终结符计数
相应的S1和S2记录在from_state和to_state中
initialize_F();
每个goto 前一个动作肯定是规约，该规则对应于goto symbol相应的某条规则
1. 如果状态S1执行goto之后到S2，S2在向前符号上有一个shift，那么该goto是可行的
换句话说，如果当前向前看符号是S2中可以shift的某个符号，那么规约并进入S1是可以的
2. 如果不是S2中某个可以shift的符号，那么是不是就一定不行?可以看到，不是
如果S1 +A -> S2, S2上可能可以进一步规约... S2->S3,如果向前看符号在S3上有个转移
那么当时对A进行规约是可行的，不断的 S3->S4也可能继续...
每个goto有一个直接的向前看符号集, 但是某个goto之间可能有一定的关系
如果
* goto1: S1 + A-> S2 (LA: a, b)
* goto2: S2 + B(nullable) -> S3 (LA: c, d)
那么goto2的向前看符号集是goto1的子集
比如如果状态S的时候有个规约A->X，而且此时向前看符号是c
那么可以规约并进入S1，然后S1 + A进入S2
此时简单的把B规约为空，就可以对c进行shift，即状态机还可以继续
goto之间的这种关系被称为reads关系
initialize_F函数计算直接向前看符号， 计算reads关系，调用digraph函数深度优先遍历reads关系图，完善每个goto对应的向前看符号集
build_relations();
向前看符号除了上面这部分，还有一部分，称为includes关系
当A: BCX 看到C而到达状态S1时，如果X能空; 进而可以对A进行规约
那么规约后的Sa + A对应的向前看符号集就是 S1状态之前那个状态S(S + C->S1)向前看符号集的子集
因为对C进行规约，可能向前看符号并不能进行shift, 但是一旦把X推导为空进而规约A之后该向前看符号可能就能进行shift
build_relations计算includes关系，和reads关系类似，进一步扩大向前看符号集
compute_FOLLOWS()函数遍历includes关系图
另外，在initialize_LA函数中，为LA分配了内存，每个reduction的规则对应一个向前看符号集
LA是最终lalr的目标
规约之后肯定跟随goto
什么时候一个规则可以规约，取决于规约完之后的goto对应的向前看符号集是否包含当前向前看符号
这个lookback在遍历每个goto就能得到，比如 p + A, 遍历所有A对应的规则右端，就能得到所有的(q,A->w)
compute_lookaheads();
上面得到每个q, A->w对应的goto（p, A）,把它对应的前看符号集复制就可以
这里不同的goto可能会有相同的符号，这时候就是冲突解决的内容了
阅读(2372) | 评论(0) | 转发(0) |
