How to prevent duplications when generating strings from context free grammar

Solution 1:

The Wikipedia entry on BFS says: (emphasis added)

Breadth-first search can be generalized to graphs, when the start node (sometimes referred to as a 'search key') is explicitly given, and precautions are taken against following a vertex twice.

and the pseudocode implementation includes such a precaution (see lines 10 and 11 reproduced below):

  9  for all edges from v to w in G.adjacentEdges(v) do
  10   if w is not labeled as explored then
  11     label w as explored
  12     Q.enqueue(w)

It does not mention how to "label w as explored"; two common strategies are to use an additional data structure which maps nodes to a Boolean (either a dictionary or an array, depending on how nodes are identified) or to augment the node data structure with an additional Boolean field.

That will work for any grammar, but it is not necessary fo unambiguous grammars. Since it is trivial to find an unambiguous grammar for a Dyck language, you could save some time by using it instead of rejecting duplicate results. But I would suggest writing the graph-oriented BFS any way, because the overhead is slight and it allows a wider range of possible grammars.