# 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->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.

• If you just want to create a recogniser using an attribute grammar (which seems to be the case based on your comments to the answers, although it is not clear from your question) then why not just implement Thompson's construction? The attribute value for each production is the head of the NFA submachine; the linked WP page shows the constructions for each operator, although I suspect you already knew them. – rici Mar 1 at 3:37

Any "interesting" regular expression (i.e., one that includes Kleene star) represents an infinite set. Thus to "calculate the set of all strings" 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.

• Yes, I understand. What I am trying to do is to create an CFG and with attribute grammars which can evaluate and find the set of all strings. Reliastically for a compiler you wouldnt evaluate an attribute grammar based parse tree for that and would simply use a DFA based system. But for this exercise I am not supposed to do that. As I said for any given regular expression I am supposed to find the set of strings it can represent using parse tree and attribute grammar. – MicroMaximus Mar 1 at 0:56

The semantic rules of the attribute grammar "compute" the value of the expression to the left in terms of the values of the expressions to the right. With a grammar for regular expressions as you propose this is straightforward, but precisely because of that this can be confusing.

For instance the meaning of the rule $$S_0\to S_1 S_2$$ is concatenation, and this operation is directly translated into that operation on languages: $$S_0.\text{val} = (S_1.\text{val}) \cdot (S_2.\text{val})$$

[I have indexed the variables of the rules for clarity.]

Similarly for the Kleene star operation, here the syntactic notation $$*$$ in the expression, and in the production rule, is translated into the semantic operation Kleene star on languages which has the intended meaning. Thus $$S_0\to S_1^*$$ with semantic rule $$S_0.\text{val} = (S_1.\text{val})^*$$

That's all.

Once however, in a compiler setting, I have seen a different approach. There the semantic value of the expression was not a language, but a finite state automaton (non-deterministic, with $$\varepsilon$$ rules). In that way the intended meaning of the expression is nicely captured in a computable fashion. The operations in the semantic rules are then the concatenation and star constructions on automata.

In that case, the operations you are looking for is Thompson's construction.

• The second approach you are talking about is the one I am interested in, do you have any sources where I can look an example of something like that. Thanks! – MicroMaximus Mar 1 at 2:44