Definite clause grammars have been around a long time and are included in logic languages such as Prolog.

They can be translated into (are just syntactic sugar for) Prolog programs and are therefore I assume turing complete (unless I have missed an important limitation of DCGs relative to full Prolog).

Prolog is a logic programming language and of course supports the Boolean operators.

Boolean grammars were introduced much more recently and are typically described as an advance on previous approaches. It is not immediately obvious why they might be more expressive than DCGs.

Don't both DCGs and Boolean grammars come down to expressing linguistic rewrite rules as:

  LHS(attributes...) -> RHS1(attributes...) [<boolean operator> RHS2(attributes)]*


  S -> NP VP | 
       S V O | 
       foo & bar & not Z

What are the limitations of DCGs?

How do Boolean grammars differ?

I think Boolean grammars don't make use of attributes. That ought to make them less expressive rather than more. I see no reason why you shouldn't use attributes with Boolean grammars in principle however.

I should clarify what I mean by expressive. I mean it in both senses:

  • Is the set of languages that can be parsed using one bigger or different than the other &

  • Does the written formalism express a language more compactly and intuitively

Though those are really different questions.



Your Answer

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

Browse other questions tagged or ask your own question.