What is the closure of the left-recursive element LR (0) with epsilon transitions?

Question

Say I have this grammar:

A: ε | B 'a' B: ε | B 'b' 

What is considered the closure of element A: • B 'a' ?
In other words, how can I deal with epsilon transitions in determining faults?

Answer 1

It is pretty simple. Included in closing

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

- all rules

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

where at first (R1) is not empty. For each (non-empty) token K in the first (R1) you need to (transitively!) Enable

  R1 = <dot> k ... ; 

etc .. but apparently you already understood this.

What specific question arises if R1 can be empty? Then you also need to enable

  X = R1 <dot> R2 ... ; 

Similarly, for R2 to be empty if R1 can be empty, and similarly if Ri is empty if R1 .. Ri-1 can be empty. In extreme circumstances, all Ri may be empty (many additional subqueries in your grammar), and you may end up including

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

Note that determining that the first (R1) “may be empty” is itself a matter of transitive closure.

The GLR parser generator I created for DMS first computed first_can_be_empty using the Warshall algorithm, and then uses this in the closure construct.