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.

  • $\begingroup$ 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? $\endgroup$ – D.W. Dec 13 '19 at 20:58
  • $\begingroup$ 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 :) $\endgroup$ – B3nTek Dec 13 '19 at 21:29

Yes, you can use context-free grammars to describe data structures, but only if the data structure is linear (e.g., a linked list of integers). Context-free grammars are not well-suited for trees or graphs (for those, you need something more powerful).

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

| cite | improve this answer | |
  • $\begingroup$ ...but a tree can be view as a list of lists... and a graph... a list of double lists? (inbound and outbound?) $\endgroup$ – B3nTek Dec 13 '19 at 23:27
  • $\begingroup$ @B3nTek, I'm aware. You might notice that I wrote "a linked list of integers"... $\endgroup$ – D.W. Dec 13 '19 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.