1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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. ♦
    Commented Dec 13, 2019 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
    Commented Dec 13, 2019 at 21:29

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Dec 13, 2019 at 23:27
  • $\begingroup$ @B3nTek, I'm aware. You might notice that I wrote "a linked list of integers"... $\endgroup$
    – D.W. ♦
    Commented Dec 13, 2019 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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