LR(0)项目

今天在宿舍自学了LR(0)项目集规范族的构造，做了一些小笔记。

首先，要知道什么是LR（0）项目：在文法G中每个产生式的右部适当位置添加一个圆点，就构成了项目。

例如，对于产生式S->aACbd，其对应六个项目：

[0]S->•aACbd

[1]S->a•ACbd

[2]S->aA•Cbd

[3]S->aAC•bd

[4]S->aACb•d

[5]S->aACbd•

一般一个产生式可对应的项目个数为其右部符号长度加一。而空产生式A->ε只有一个项目A->•，因为空产生式的长度为0。

圆点左部表示分析过程的某时刻要用该产生式归约时已经识别过的句柄部分，右部表示期待的后缀部分。

项目[0]意味着要想用S的右部归约，当前输入串中符号应该是a。项目[1]表明用该产生式归约已与第一个符号a匹配了，需分析A的右部。以此类推，直到项目[5]的右部分析完毕，则句柄形成，可以进行归约。