[Haskell-cafe] Re: Frisby grammars that have context

[Jan-Willem Maessen]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2425 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070530/12299116/smime.bin