How to evaluate a Kleene's Closure through CFG and attribute grammars For a CFG with the production rules that can represent a regular expression. How can one calculate all the set of strings that regular expression would produce.
For T = {a, b,*,(,)}
and an arbitrary production rule I created to represent a simple regular expression
S-&gt;SS | S* | (S) | a | b | ∅
What would be an attribute grammar which can calculate the set of all strings that the regex can evaluate.
For example if we generate b(a)*
Then the output generated by regular expression would be a set of infinte strings {b,baa,ba,baaa......}
using set valued expression in the attribute grammar.
I am not sure how to represent set valued concatenation and Kleene closure.
Any &quot;interesting&quot; regular expression (i.e., one that includes Kleene star) represents an infinite set. Thus to &quot;calculate the set of all strings&quot; won't work so well. In a sense, the regular expression is a compact description of the language. What other kind of description do you expect to construct?
It is rather easy to construct regular expressions that represent very complex languages, that the reader needs to descypher to make sense of it.