Re: [Haskell-cafe] Parser left recursion

You can find our experiments here: https://github.com/feuerbach/hagll But don't set your expectations high :-) Roman * Paul Callaghan [2013-03-01 06:27:46+] > Hi > > Another alternative is this Haskell library: https://github.com/paulcc/xsaiga > > This is a combinator library which is sui

Re: [Haskell-cafe] Parser left recursion

Hi Another alternative is this Haskell library: https://github.com/paulcc/xsaiga This is a combinator library which is suitable for mid-scale NLP work, so handles left recursion and (high amounts of) ambiguity to produce a packed result (which can be decoded to a list of results if required). It

Re: [Haskell-cafe] Parser left recursion

2013/2/26 Martin Drautzburg : > I wonder if I can enforce the nonNr property somehow, i.e. enforce the rule > "will not consider the same nonterminal again without having consumed any > input". You might be interested in this paper: Danielsson, Nils Anders. "Total parser combinators." ACM Sigpl

Re: [Haskell-cafe] Parser left recursion

On Sunday, 24. February 2013 16:04:11 Tillmann Rendel wrote: > Both approaches are essentially equivalent, of course: Before > considering the very same nonterminal again, we should have consumed at > least one token. I see. Thanks So for the laymen: expr ::= expr "+" expr is a problem, becaus

Re: [Haskell-cafe] Parser left recursion

On 2/24/13 7:56 AM, Kim-Ee Yeoh wrote: > On Sun, Feb 24, 2013 at 7:47 PM, Roman Cheplyaka wrote: > >> Or perhaps you meant that the production itself, when interpreted as a >> definition, is corecursive? > > I was merely thrown off by your mention of "well-founded" and the assertion > that you're

Re: [Haskell-cafe] Parser left recursion

On Sun, Feb 24, 2013 at 10:04 PM, Tillmann Rendel < ren...@informatik.uni-marburg.de> wrote: > The recursion is well-founded if (drop n1 text) is smaller then text. So > we have two cases, as Roman wrote: > > If the language defined by B contains the empty string, then n1 can be 0, > so the recurs

Re: [Haskell-cafe] Parser left recursion

Hi, Kim-Ee Yeoh wrote: Perhaps you meant /productive/ corecursion? Because the definition "A ::= B A" you gave is codata. If you write a recursive descent parser, it takes the token stream as an input and consumes some of this input. For example, the parser could return an integer that says

Re: [Haskell-cafe] Parser left recursion

On Sun, Feb 24, 2013 at 6:31 AM, Martin Drautzburg wrote: > Just a silly quick question: why isn't right-recursion a similar problem? > Very roughly: Left recursion is: let foo n = n + foo n in ... Right recursion is: let foo 1 = 1; foo n = n + foo (n - 1) in ... In short, matching the token

Re: [Haskell-cafe] Parser left recursion

On Sun, Feb 24, 2013 at 8:03 PM, Roman Cheplyaka wrote: > It may become more obvious if you try to write two recursive descent > parsers (as recursive functions) which parse a left-recursive and a > non-left-recursive grammars, and see in which case the recursion is > well-founded and why. > Whi

Re: [Haskell-cafe] Parser left recursion

* Kim-Ee Yeoh [2013-02-24 19:56:13+0700] > I was merely thrown off by your mention of "well-founded" and the assertion > that you're left with a "strictly smaller" input. I don't see any of this. It may become more obvious if you try to write two recursive descent parsers (as recursive functions)

Re: [Haskell-cafe] Parser left recursion

On Sun, Feb 24, 2013 at 7:47 PM, Roman Cheplyaka wrote: > Or perhaps you meant that the production itself, when interpreted as a > definition, is corecursive? > I was merely thrown off by your mention of "well-founded" and the assertion that you're left with a "strictly smaller" input. I don't s

Re: [Haskell-cafe] Parser left recursion

* Kim-Ee Yeoh [2013-02-24 19:22:33+0700] > On Sun, Feb 24, 2013 at 7:09 PM, Roman Cheplyaka wrote: > > > Thus, your > > recursion is well-founded — you enter the recursion with the input > > strictly smaller than you had in the beginning. > > > > Perhaps you meant /productive/ corecursion? Beca

Re: [Haskell-cafe] Parser left recursion

* Kim-Ee Yeoh [2013-02-24 19:22:33+0700] > On Sun, Feb 24, 2013 at 7:09 PM, Roman Cheplyaka wrote: > > > Thus, your > > recursion is well-founded — you enter the recursion with the input > > strictly smaller than you had in the beginning. > > > > Perhaps you meant /productive/ corecursion? > >

Re: [Haskell-cafe] Parser left recursion

On Sun, Feb 24, 2013 at 7:09 PM, Roman Cheplyaka wrote: > Thus, your > recursion is well-founded — you enter the recursion with the input > strictly smaller than you had in the beginning. > Perhaps you meant /productive/ corecursion? Because the definition "A ::= B A" you gave is codata. -- Kim

Re: [Haskell-cafe] Parser left recursion

* Martin Drautzburg [2013-02-24 12:31:37+0100] > > > Twan van Laarhoven told me that: > > >> Left-recursion is always a problem for recursive-descend parsers. > > > > Note that the left recursion is already visible in the grammar above, no > > need to convert to parser combinators. The problem is

Re: [Haskell-cafe] Parser left recursion

Hi Martin, Martin Drautzburg wrote: Note that the left recursion is already visible in the grammar above, no need to convert to parser combinators. The problem is that the nonterminal Exp occurs at the left of a rule for itself. Just a silly quick question: why isn't right-recursion a similar

Re: [Haskell-cafe] Parser left recursion

On Wednesday, 20. February 2013 09:59:47 Tillmann Rendel wrote: > > So the grammar is: > >Exp ::= Int > > | Exp "+" Exp > > > > My naive parser enters an infinite recursion, when I try to parse "1+2". > > I do understand why: > > > > "hmm, this expression could be a plus, but the

Re: [Haskell-cafe] Parser left recursion

As mentioned before, the way to handle this specific problem is to use either the pChainl or pChainr parser combinators, as e.g. found on: http://hackage.haskell.org/packages/archive/uu-parsinglib/2.7.4.1/doc/html/Text-ParserCombinators-UU-Derived.html and many similar libraries. So one can wri

Re: [Haskell-cafe] Parser left recursion

Thank you very much. To clarify: I am not in need of a parser, I just wanted to understand why left recursion is an issue (that was easy) and what techniques help to circumvent the problem. So your answer was spot-on (though I haven't implemented it yet) On Wednesday, 20. February 2013 09:59:4

Re: [Haskell-cafe] Parser left recursion

More primitively, Parsec and its predecessor Hutton-Meijer provide the chainl/chainr combinators, these automatically remove left recursion "within" the parser - i.e. you don't have to rewrite the grammar. On 20 February 2013 08:19, Dmitry Olshansky wrote: > Did you see expression parser in parse

Re: [Haskell-cafe] Parser left recursion

All, Many (but not all) of the parsing algorithms that support left recursion cannot be implemented in Haskell using the standard representation of recursion in parser combinators. The problem can be avoided in Scala because it has imperative features like referential identity and/or mutable refe

Re: [Haskell-cafe] Parser left recursion

* Tillmann Rendel [2013-02-20 12:39:35+0100] > Hi, > > Roman Cheplyaka wrote: > >Another workaround is to use memoization of some sort — see e.g. GLL > >("Generalized LL") parsing. > > Is there a GLL parser combinator library for Haskell? I know about > the gll-combinators for Scala, but havn't

Re: [Haskell-cafe] Parser left recursion

Hi, Roman Cheplyaka wrote: Another workaround is to use memoization of some sort — see e.g. GLL ("Generalized LL") parsing. Is there a GLL parser combinator library for Haskell? I know about the gll-combinators for Scala, but havn't seen anything for Haskell. Bonus points for providing the

Re: [Haskell-cafe] Parser left recursion

* Tillmann Rendel [2013-02-20 09:59:47+0100] > One way to fix this problem is to refactor the grammar in order to > avoid left recursion. So let's distinguish "expressions that can > start with expressions" and "expressions that cannot start with > expressions": > > [...] > > PS. Try adding multi

Re: [Haskell-cafe] Parser left recursion

Hi, Martin Drautzburg wrote: As an exercise I am writing a parser roughly following the expamples in Graham Hutton's book. The language contains things like: data Exp = Lit Int -- literal integer | Plus Exp Exp So the grammar is: Exp ::= Int | Exp "+" Exp My naive parse

Re: [Haskell-cafe] Parser left recursion

Did you see expression parser in parsec package? Is it not enough? 2013/2/20 Martin Drautzburg > Hello all, > > this was previously asked on haskell-beginners, but only partially > answered. > > As an exerc

Re: [Haskell-cafe] Parser left recursion

* Martin Drautzburg [2013-02-20 08:13:16+0100] > I do know for sure, that it is possible to parse "(1+2)+3" (ghci does it just > fine). But I seem to be missing a trick. > > Can anyone shed some light on this? The trick in this case is that ghci doesn't use a recursive descent parser — it uses

[Haskell-cafe] Parser left recursion

Hello all, this was previously asked on haskell-beginners, but only partially answered. As an exercise I am writing a parser roughly following the expamples in Graham Hutton's book. The language contains things like: data Exp = Lit Int -- literal integer | Plus Exp Exp My naive parser