-
Subjectively, it seems like there is not much information available about Definite Clause Grammars. It seems like something that is largely confined to Prolog circles. For instance, you will often see grammars for other languages described not in terms of DCGs but EBNF notation. As a programmer, it's always good to get an intuition for upper (and lower) limits of things so you can choose the best approach. For instance, algorithmic space and time complexity or "Big O" notation, halting problem concerns, CAP theorem, etc. So I am trying to understand what the upper limits of DCGs are. Because DCGs are capable of parsing natural language, it would be tempting to think that they are capable of parsing anything! According to the wikipedia article, Definite Clause Grammars are capable of parsing Type 1 or "Context-Sensitive Grammars" (such as C). However, I think this might be wrong in practice, because Prolog is Turing complete, "extending" DCGs with Prolog seems like it would be capable of parsing even Turing complete grammars. But why is this important? The answer is internet arguments, of course! 😆 Not really, but kind of. Given that DCGs are executable specifications, it seems to me, for instance, that programming languages should be described in terms of DCGs when possible. For instance, shouldn't there be a Prolog specification of the Prolog ISO standard? |
Beta Was this translation helpful? Give feedback.
Replies: 2 comments
-
They are able to describe Type 2 without auxiliary arguments (and without semicontext). Parsing is subject to non-termination issues (just introduce a useless but correct unproductive recursive rule to see the difference). With auxiliary arguments you get Turing completeness immediately. So it seems a very restricted form of auxiliary arguments is meant to get just Type 1. However, with semicontext and no auxiliary arguments they are Type 0.
There is an executable specification written in a (kind-of) subset of Prolog as informative Annex A, but it does not cover the full language. Most notably, the syntax of Prolog text is left out as is unification and similar undefined parts. |
Beta Was this translation helpful? Give feedback.
-
An additional peace of information (for internet arguments). If you restrict yourself to a specific subset of DCGs then they are equivalent to attribute grammars |
Beta Was this translation helpful? Give feedback.
They are able to describe Type 2 without auxiliary arguments (and without semicontext). Parsing is subject to non-termination issues (just introduce a useless but correct unproductive recursive rule to see the difference).
With auxiliary arguments you get Turing completeness immediately. So it seems a very restricted form of auxiliary arguments is meant to get just Type 1.
However, with semicontext and no auxiliary arguments they are Type 0.
There is an executable specification written in a (kind-of) subset of Prolog as informative Annex A, but it …