4 ms·
Does this parser combinator implementation handle left-recursive grammars?
by davexunit 10y ago
Does this parser combinator implementation handle left-recursive grammars?
- lihaoyi 10y agoNope; you need to left-factor them unfortunately. Other parser combinators may have different implementation algorithms, but this one is naive PEG/recursive-descent so you need to help it out manually otherwise it'll just infinite-recurse
- davexunit 10y agoYeah, it's much easier to write a parser combinator implementation that doesn't support it. Thanks for answering. For those interested, here is an article about a parser combinator implementation in Racket that supports left-recursive grammars: https://epsil.github.io/gll/ https://epsil.github.io/gll/
- bd82 10y agoIs it possible to detect and warn about the left recursion? Assuming a data structure representing the grammar is built at runtime to be interpreted. Won't it be possible to detect the left recursion instead of going into an infinite loop?