Even in the regular case it can be non-terminating by using left-recursive rules. E.g. consider parsing a*: as --> as, [a]. as --> []. Prolog will rec

Even in the regular case it can be non-terminating by using left-recursive rules. E.g. consider parsing a*: as --> as, [a]. as --> []. Prolog will recurse infinitely on the first rule.