LR(1)文法

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

已知文法G[S]的表达式求文法的LR(1)的项目集和Go函数.要求使用广度优先搜索,同时按照字典序进行转换,以保证项目集的序号正确.

Input

单组输入,当输入一个@时输入结束.

注意: 在输入中以@代表空.

规定:文法S的拓广文法为$->S

Output

输出文法的项目集和Go函数,参考示例中的格式

 

Sample Input

S->rD
D->Dai
D->i
@

Sample Output

Package: 0
$->.S
S->.rD
Package: 1
$->S.
Package: 2
S->r.D
D->.Dai
D->.i
Package: 3
S->rD.
D->D.ai
Package: 4
D->i.
Package: 5
D->Da.i
Package: 6
D->Dai.
0 1 S
0 2 r
2 3 D
2 4 i
3 5 a
5 6 i

Hint

Source