Re: [Haskell-cafe] Re: Frisby grammars that have context
On May 29, 2007, at 10:44 AM, apfelmus wrote: Mark T.B. Carroll wrote: I've been playing with Text.Parsers.Frisby to see how it stacks against other options and, while it's been great so far, I am finding that I can't encode a grammar where what's acceptable depends on what's already been parsed in some nontrivial way. [...] Is this supposed to not be possible in Frisby, or (quite likely) am I missing something that allows me to? It's intentionally impossible. Frisby uses a dynamic programming approach that crucially depends on the fact that the grammar in question is context-free (actually something related, but the effect is the same). You're trying to parse a context-sensitive language. Interestingly, Rats (a packrat-based parser generator for Java) permits you to insert arbitrary boolean conditions into the grammar; if the test fails, we simply record this as parsing this nonterminal failed in the memo table, I believe. So I believe it'd actually feasible to incorporate some of the checking you're looking for into Frisby. Of course, as others point out, you can always generate grammar fragments up front if you have a fixed set of things you're looking for in any given program run (something a parser tool like Rats isn't capable of---though with its parametric module system Rats can come *very* close, doing multiple compile-time instantiations of grammar fragments). Packrat parsing, by the way, has made it vastly easier to structure and maintain a grammar for a highly ambiguous, hard-to-parse language (Fortress). I recommend it. Sometimes, you can avoid context-sensitivity if there's a way to parse the token in question regardless of whether it's valid. For example, Pascal is a context-sensitive language because you may not use a variable before it has been declared: procedure Foo(x:Integer) begin y := 1; end; This not a correct Pascal program, nevertheless the parse succeeds just fine. ... I'm pretty sure predicates in the grammar would let you catch this error at parse time (if you maintained a symbol table and looked up expression occurrences in it as you parsed). That said, I wouldn't necessarily try to structure my parser that way. -Jan-Willem Maessen smime.p7s Description: S/MIME cryptographic signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Frisby grammars that have context
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Robin Green wrote: On Tue, 29 May 2007 19:28:02 -0400 Isaac Dupree [EMAIL PROTECTED] wrote: Luckily, Haskell's laziness means that doing an extra postprocessing pass doesn't necessarily yield two traversals requiring the whole file to be stored in memory, nor worse hacks. (For grammars that aren't too wild / sequential) But the suggested code fragment on the frisby homepage: -- parse complete file, returning 'Nothing' if parse fails fmap Just (myParser - eof) // unit Nothing does require one traversal of the file all by itself. Obviously, in order to know whether the file was fully parsed without error, you need to read in the whole file, before you can write out anything. Hence you end up with *some* representation of the whole file in memory. So, yes, it doesn't necessarily yield two traversals, but you need to be careful if you want to avoid two traversals. Yes, then the choices are being failable (using something like error, or whatever happens if you don't wrap your parser as suggested) or better yet, a careful lazy datatype like data ListOutput a = Nil | Cons a (ListOutput a) | Error (ErrorInfo) Isaac -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGXXryHgcxvIWYTTURAnEeAJ9PrQUQLxeoTuIhaG8GcHW5mN6T4QCeL6FT KCQeF43ye/GzLka4zFUK66s= =y7MZ -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Frisby grammars that have context
apfelmus [EMAIL PROTECTED] writes: (snip) It's intentionally impossible. Frisby uses a dynamic programming approach that crucially depends on the fact that the grammar in question is context-free (actually something related, but the effect is the same). You're trying to parse a context-sensitive language. Aha, thanks, that makes sense: I am glad that for once I wasn't missing the obvious after all. Presumably this restriction allows it to gain other benefits. I hadn't realised that the different implementations of Frisby and Parsec had such far-reaching consequences. (snip) This not a correct Pascal program, nevertheless the parse succeeds just fine. The missing declaration for y will be detected when processing the abstract syntax tree further. The key point is that the shape of the abstract syntax tree doesn't depend on whether y is declared or not. M, indeed it was a missing-declaration sort of problem I had in mind. Thanks for the example. -- Mark ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Frisby grammars that have context
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 apfelmus wrote: Mark T.B. Carroll wrote: I've been playing with Text.Parsers.Frisby to see how it stacks against other options and, while it's been great so far, I am finding that I can't encode a grammar where what's acceptable depends on what's already been parsed in some nontrivial way. [...] Is this supposed to not be possible in Frisby, or (quite likely) am I missing something that allows me to? It's intentionally impossible. Frisby uses a dynamic programming approach that crucially depends on the fact that the grammar in question is context-free (actually something related, but the effect is the same). Is that dependence crucial? What if it gained Monad operations that just weren't intended to be used very often, and maybe locally harmed performance a little where they are used? BTW: (P s) should be an instance of Applicative (which is already possible with Frisby's current code, just not there) (I prefer the aesthetics of Frisby-applicative code to many of the combinators it provides - I tried it a little sometime, not enough to send a darcs patch) Isaac -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGXFZVHgcxvIWYTTURApl+AKClt8J1m+qkEG+qNSI4RSATmZfSkACfdJN8 4gLKaM/hKS85UgMsERoItRM= =dJx9 -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Frisby grammars that have context
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 apfelmus wrote: Isaac Dupree wrote: apfelmus wrote: Mark T.B. Carroll wrote: I've been playing with Text.Parsers.Frisby to see how it stacks against other options and, while it's been great so far, I am finding that I can't encode a grammar where what's acceptable depends on what's already been parsed in some nontrivial way. [...] Is this supposed to not be possible in Frisby, or (quite likely) am I missing something that allows me to? It's intentionally impossible. Frisby uses a dynamic programming approach that crucially depends on the fact that the grammar in question is context-free (actually something related, but the effect is the same). Is that dependence crucial? What if it gained Monad operations that just weren't intended to be used very often, and maybe locally harmed performance a little where they are used? Now that you ask, I become unsure Luckily, Haskell's laziness means that doing an extra postprocessing pass doesn't necessarily yield two traversals requiring the whole file to be stored in memory, nor worse hacks. (For grammars that aren't too wild / sequential) Isaac -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGXLcBHgcxvIWYTTURArCuAJ9mR8HFqiRNT7teWjhvAtRwXYgjfwCgu7hi YEXGLGvMVHQwlZpfxTDi0FI= =b3Q7 -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Frisby grammars that have context
On Tue, 29 May 2007 19:28:02 -0400 Isaac Dupree [EMAIL PROTECTED] wrote: Luckily, Haskell's laziness means that doing an extra postprocessing pass doesn't necessarily yield two traversals requiring the whole file to be stored in memory, nor worse hacks. (For grammars that aren't too wild / sequential) But the suggested code fragment on the frisby homepage: -- parse complete file, returning 'Nothing' if parse fails fmap Just (myParser - eof) // unit Nothing does require one traversal of the file all by itself. Obviously, in order to know whether the file was fully parsed without error, you need to read in the whole file, before you can write out anything. Hence you end up with *some* representation of the whole file in memory. So, yes, it doesn't necessarily yield two traversals, but you need to be careful if you want to avoid two traversals. -- Robin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
