# How to write grammar production rules to describe recursive structures?

I'm trying to describe a data structure by production rules. The structure is recursive; say a list of type $$A$$ made of elements of type $$A$$ or $$B$$.

Writing the grammar, I build this:

$$(S \rightarrow AS|ε)$$ $$(A \rightarrow AA|bA|ε)$$

where $$b$$ is a terminal representing element $$B$$ of my list.

The production $$A \rightarrow AA$$ got me a little baffled... is there something right? Thank you.

• I'm confused. You wrote the grammar that way, but you are baffled by it? Why did you write the grammar that way? What properties exactly do you need the language to have? We can't tell whether it is right without knowing what criteria it needs to satisfy to count as right. What specifically has you baffled by it? Is this an exercise, and if so, can you credit the original source where you encountered it? Can you edit the question accordingly? – D.W. Dec 13 '19 at 20:58
• What I want is to know if there is some inconsistency in using production rules to describe data structures. The baffling comes from the production A->AA because i've not seen examples like that... I need some "it's all right" to move on... and it's not an exercise, it' my work :) – B3nTek Dec 13 '19 at 21:29

There's nothing wrong with a production like $$A \to AA$$; that's a valid rule that can appear in a context-free grammar.