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.
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:
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:
Whereas Greibach Normal Form allows a single terminal followed by any number of nonterminals: 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
[2] https://en.wikipedia.org/wiki/Greibach_normal_form