3 ms·

How can you use DCG in a productive way? If haven't found a good way when there is left recursion. Memonization(tabbling) only sometimes helps and refactoring t

How can you use DCG in a productive way? If haven't found a good way when there is left recursion. Memonization(tabbling) only sometimes helps and refactoring the grammar into non-left-recursive takes a lot of time and is error prone. What's your solution?

Karrot_Kream 10y ago
I typically wrap up a left recursive rule as another rule, and then have this rule choose between the base case and the recursive case. This is a pretty standard technique to break down left recursive rules though, and has nothing to do with Prolog, and everything to do with writing parsers.
YeGoblynQueenne 10y ago
To complement Karrot_Kream's answer, there's another two things you can do if you're having DCG left-recursion troubles: The first thing is to use a different parsing strategy. For instance, the Earley parser [1] used to be a typical example of (advanced ish) Prolog and wikipedia says that it performs particularly well with left-recursive languages. The disadvantage of course is that you're giving up the simplicity of having a built-in grammar-and-parser capability in your language. But in some cases that's probably a very small price to pay. The other thing you can do, which is in a sense the exact opposite of changing parsers, is to eliminate the possibility of left-recursion from your DCGs by choosing a grammar formalism that precludes it. It boils down to keeping all your rules looking like this: P --> [a₁, a₂, ..., aₙ], A₁, A₂, .... Aₘ. Where each Aᵢ is a terminal or nonterminal and each [aₖ] a terminal. In other words, expand every nonterminal first to one or more terminals, then any mix of terminals and nonterminals. That way you'll always accept a terminal before expanding a nonterminal and there's no chance of left-recursion. You can write a short syntax checker to enforce this rule in a post-processing step, or just do it by hand. You can be a little bit more rigorous and stick to more strict forms, particularly right-regular grammars, or Greibach Normal Form [2], if your grammars are context-free. Right regular grammars allow a single nonterminal on the right-hand side: A --> [a], B. Whereas Greibach Normal Form allows a single terminal followed by any number of nonterminals: P --> [a], A₁, A₂, .... Aₙ. The benefit of GNF is that any context-free grammar can be transformed into a grammar in GNF, so you can first write your grammars in a loose form, then convert them to GNF to remove left-recursions. If you want I can probably dig up a reference to how to do the conversion. ___________ [1] https://en.wikipedia.org/wiki/Earley_parser https://en.wikipedia.org/wiki/Earley_parser [2] https://en.wikipedia.org/wiki/Greibach_normal_form https://en.wikipedia.org/wiki/Greibach_normal_form

Karrot_Kream 10y ago

I typically wrap up a left recursive rule as another rule, and then have this rule choose between the base case and the recursive case. This is a pretty standard technique to break down left recursive rules though, and has nothing to do with Prolog, and everything to do with writing parsers.

YeGoblynQueenne 10y ago

To complement Karrot_Kream's answer, there's another two things you can do if you're having DCG left-recursion troubles: The first thing is to use a different parsing strategy. For instance, the Earley parser [1] used to be a typical example of (advanced ish) Prolog and wikipedia says that it performs particularly well with left-recursive languages. The disadvantage of course is that you're giving up the simplicity of having a built-in grammar-and-parser capability in your language. But in some cases that's probably a very small price to pay. The other thing you can do, which is in a sense the exact opposite of changing parsers, is to eliminate the possibility of left-recursion from your DCGs by choosing a grammar formalism that precludes it. It boils down to keeping all your rules looking like this: P --> [a₁, a₂, ..., aₙ], A₁, A₂, .... Aₘ. Where each Aᵢ is a terminal or nonterminal and each [aₖ] a terminal. In other words, expand every nonterminal first to one or more terminals, then any mix of terminals and nonterminals. That way you'll always accept a terminal before expanding a nonterminal and there's no chance of left-recursion. You can write a short syntax checker to enforce this rule in a post-processing step, or just do it by hand. You can be a little bit more rigorous and stick to more strict forms, particularly right-regular grammars, or Greibach Normal Form [2], if your grammars are context-free. Right regular grammars allow a single nonterminal on the right-hand side: A --> [a], B. Whereas Greibach Normal Form allows a single terminal followed by any number of nonterminals: P --> [a], A₁, A₂, .... Aₙ. The benefit of GNF is that any context-free grammar can be transformed into a grammar in GNF, so you can first write your grammars in a loose form, then convert them to GNF to remove left-recursions. If you want I can probably dig up a reference to how to do the conversion. ___________ [1] https://en.wikipedia.org/wiki/Earley_parser https://en.wikipedia.org/wiki/Earley_parser [2] https://en.wikipedia.org/wiki/Greibach_normal_form https://en.wikipedia.org/wiki/Greibach_normal_form