1
$\begingroup$

Definite clause grammars have been around for a long time but there are not the answer to every parsing problem or we would not need to invent new formalisms. Are there any languages they cannot express in principle?

Why are they not used more?

https://www3.cs.stonybrook.edu/~warren/xsbbook/node10.html partially answers the second question but not the first.

Prolog execution of the underlying deterministic machines and its use of a stack to schedule them naturally yields a recursive descent parser. And it is well known that a recursive descent parser cannot handle left-recursive grammars; it will go into an infinite loop on them. So in Prolog we must avoid left-recursive grammars.

Also a recursive descent parser can be quite inefficient on some grammars, because it may re-parse the same substring many times. In fact, there are grammars for which recursive descent parsers take time exponential in the length of the input string. When using DCGs in Prolog, the programmer must be aware of these limitations and program around them. It is for this reason that some people respond to the claim that "You get a parser for free with Prolog" with "Maybe, but it's not a parser I want to use."

Its not clear if its a fundamental limitation of DCGs themselves rather than just the Prolog implementation. I don't see why Prolog couldn't memoize common substrings like a chart parser (most Prolog implementations memoise already).

See also my related question Is there any difference in the expressiveness of boolean grammars versus definite clause grammars?

$\endgroup$

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.