SLR(1) Parser and epsilon involved

parsing theory grammar compiler-theory language-theory
Oscar Mederos picture Oscar Mederos · Jun 28, 2011 · Viewed 7.3k times · Source

Let's suppose I have the following grammar:

S → X  
X → a | ϵ

If that grammar wouldn't have ϵ involved, I would construct the first state like:

S' → .S
S → .X
X → .a

but what about the ϵ symbol? Should I include:

X → .ϵ

too?

If so... when creating the next states... should I do GOTO(Io,ϵ), being Io that first state?

Answer

Rose Perrone picture Rose Perrone · Apr 28, 2012

I agree with Howard. Your state in the DFA should contain the item: x → . Here's a DFA I drew for an SLR(1) parser that recognizes a grammar that uses two epsilon productions:SLR(1) DFA

Related questions

How to determine whether a language is LL(1) LR(0) SLR(1)

Is there a simple way to determine whether a grammar is LL(1), LR(0), SLR(1)... just from looking on the grammar without doing any complex analysis? For instance: To decide whether a BNF Grammar is LL(1) you have to calculate First …

Read More
How do I parse a string to a float or int?

In Python, how can I parse a numeric string like "545.2222" to its corresponding float value, 545.2222? Or parse the string "31" to an integer, 31? I just want to know how to parse a float str to a float, and (separately) an int …

Read More
Why can't Python parse this JSON data?

I have this JSON in a file: { "maps": [ { "id": "blabla", "iscategorical": "0" }, { "id": "blabla", "iscategorical": "0" } ], "masks": [ "id": "valore" ], "om_points": "value", "parameters": [ "id": "valore" ] } I wrote this script to print all of the JSON data: import json from pprint import pprint …

Read More