Given a context free grammar, both the algorithm for determining whether a given string is grammatical and the algorithm for producing a grammatical string in that language are well understood. To produce a grammatical string, just keep replacing non-terminals with one of their right-hand-side productions until you have only terminals.

The algorithm for determining whether a sentence is grammatical given a standard formulation of an attribute grammar is also well understood.

My question is: Is there a standard algorithm to produce sentences that are grammatical with respect to attribute grammars?

Edit: I am talking about attribute grammars with synthesized and inherited attributes. Thus, it is possible to generate something not in the language when the synthesized attributes and inherited attributes don't match up. This occurs, for instance, in checking that a variable is defined before use (https://web.cs.wpi.edu/~kal/courses/compilers/module4/mysa.html).

  • 1
    $\begingroup$ I guess I am missing something. Which is the standard formulation of attribute grammar you refer to? Under Wikipedia's definition, it seems to me that any sentence that is grammatical for the "underlying" context-free grammar would also be grammatical for the attribute grammar. $\endgroup$ – Vincenzo Feb 1 '19 at 23:19
  • $\begingroup$ @Vincenzo did this clear it up? $\endgroup$ – lightning Feb 3 '19 at 17:26

Your Answer

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

Browse other questions tagged or ask your own question.