什么是带有epsilon过渡的左递归LR(0)项的闭包？

Question

假设我有这个语法:

A: ?
 | B 'a'
B: ?
 | B 'b'

什么被认为是项目的关闭A: • B 'a'？
换句话说,在计算闭包时如何处理epsilon转换？

Answer 1

这非常简单.包括在关闭

    A = ... <dot> X ... ;

都是规则

    X =   <dot> R1 R2 R3 ... ;

第一个(R1)不为空.对于第一个(R1)中的每个(非空)令牌K,您需要(传递!)包含

    R1 = <dot> k ... ;

等等,但可能你已经清楚了.

你具体的问题是,如果R1可以为空,会发生什么？然后你还需要包括

    X =   R1 <dot> R2 ... ;

类似地,对于R2为空,如果R1可以为空,并且类似于Ri为空,如果R1 .. Ri-1可以为空.在极端情况下,所有Ri都可以是空的(语法中有很多可选的子句),最后你可以包括

    X =  R1 R2 ... Rn <dot> ;

注意,确定第一个(R1)"可以为空"本身就是一个传递闭包问题.

我为DMS构建的GLR解析器生成器使用Warshall的算法预先计算first_can_be_empty,然后在闭包构造中使用它.