Menu
Let's say I have this grammar:
A: ε
| B 'a'
B: ε
| B 'b'
What is considered to be the closure of the item A: • B 'a'?
In other words, how do I deal with the epsilon transitions when figuring out closures?
357
Closures. Suppose that S is a set of LR(0) items. The following rules tell how to build closure(S), the closure of S. You must add LR(0) items to S until there are no more to add. All members of S are in the closure(S).
An LR (0) item is a production G with dot at some position on the right side of the production. LR(0) items is useful to indicate that how much of the input has been scanned up to a given point in the process of parsing. In the LR (0), we place the reduce node in the entire row.
Since we can build this parsing table with no conflicts, the grammar is LL(1). To check if a grammar is LR(0) or SLR(1), we begin by building up all of the LR(0) configurating sets for the grammar. In this case, assuming that X is your start symbol, we get the following: (1) X' -> .
This is pretty straightforward. Included in the closure of
A = ... <dot> X ... ;
are all the rules
X = <dot> R1 R2 R3 ... ;
where first(R1) is not empty. For each (nonempty) token K in first(R1), you'll need to (transitively!) include
R1 = <dot> k ... ;
etc. but presumably you are already clear on this.
You specific question is what happens if R1 can be empty? Then you also need to include
X = R1 <dot> R2 ... ;
Similarly for R2 being empty, if R1 can be empty, and similarly for Ri being empty if R1 .. Ri-1 can be empty. In extreme circumstances, all the Ri can be empty (lots of optional subclauses in your grammar), and you can end up including
X = R1 R2 ... Rn <dot> ;
Note that determining that first(R1) "can be empty" is itself a transitive closure question.
The GLR parser generator that I built for DMS precomputes first_can_be_empty using Warshall's algorithm and then uses that in the closure construction.
103
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
