Quantcast

Tweaking parboiled to handle ambiguous grammar

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Tweaking parboiled to handle ambiguous grammar

thomas juan
Dear Mathias,
I really like the elegant Scala API parboiled offers and hope to use it in my project.

I need a parser to return all possible parse results (parse forest) from an ambiguous grammar and use my other function to choose from the parse forest by evaluating them against user context / history and a knowledge base.

Given parboiled is designed for PEG, I am not sure whether this can be done at all? Perhaps parboiled can tell me right before it succeeds so I could store the parse tree as a good parse result and force failure somehow to let the parser try / search again for the next result? Or is there a better solution to do this?

The grammar may be left-recursive too, so I need the parser to handle it automatically or allow me to manually specify a search limit parameter to limit the number of recursive calls in applying production rules to avoid infinite loops.

Finally, "real" parse failures may indicate to me where to repair the grammar, and suggest possible solutions to the user, is it possible to maintain info or a "score" for failed parse attempts as they are tried?

Being new to Scala and parsing in general, I can't figure out how to do all the above, could you please give me some advice on it? Much appreciated!

Best regards,
Thomas Juan
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Tweaking parboiled to handle ambiguous grammar

mathias
Administrator
Thomas,

> I need a parser to return all possible parse results (parse forest) from an ambiguous grammar and use my other function to choose from the parse forest by evaluating them against user context / history and a knowledge base.

I'm afraid parboiled (and PEG parsers in general) won't help you here.
Unlike CFGs, PEGs are never ambiguous.

> The grammar may be left-recursive too, so I need the parser to handle it automatically or allow me to manually specify a search limit parameter to limit the number of recursive calls in applying production rules to avoid infinite loops.

Another "no, that won't work with parboiled".
parboiled can't handle left-recursion, you'd have to transform the grammar accordingly to make it work.

Cheers,
Mathias

---
[hidden email]
http://www.parboiled.org

On 25.04.2012, at 18:12, thomas juan [via parboiled users] wrote:

> Dear Mathias,
> I really like the elegant Scala API parboiled offers and hope to use it in my project.
>
> I need a parser to return all possible parse results (parse forest) from an ambiguous grammar and use my other function to choose from the parse forest by evaluating them against user context / history and a knowledge base.
>
> Given parboiled is designed for PEG, I am not sure whether this can be done at all? Perhaps parboiled can tell me right before it succeeds so I could store the parse tree as a good parse result and force failure somehow to let the parser try / search again for the next result? Or is there a better solution to do this?
>
> The grammar may be left-recursive too, so I need the parser to handle it automatically or allow me to manually specify a search limit parameter to limit the number of recursive calls in applying production rules to avoid infinite loops.
>
> Finally, "real" parse failures may indicate to me where to repair the grammar, and suggest possible solutions to the user, is it possible to maintain info or a "score" for failed parse attempts as they are tried?
>
> Being new to Scala and parsing in general, I can't figure out how to do all the above, could you please give me some advice on it? Much appreciated!
>
> Best regards,
> Thomas Juan
>
> If you reply to this email, your message will be added to the discussion below:
> http://users.parboiled.org/Tweaking-parboiled-to-handle-ambiguous-grammar-tp3938734p3938734.html
> To start a new topic under parboiled users, email [hidden email]
> To unsubscribe from parboiled users, click here.
> NAML

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Tweaking parboiled to handle ambiguous grammar

thomas juan
Got it.

Thank you, Mathias.
Loading...