Quantcast

FirstOf problem

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

FirstOf problem

JonathanEdwards
Hi, making great progress with Parboiled (0.11.1) for a few weeks, but have hit a problem that looks like it might be a bug. Swapping the order of two terms in a FirstOf affects whether the parse succeeds. Should that ever possibly happen?
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: FirstOf problem

mathias
Administrator
Hi Jonathan,

> Should that ever possibly happen?

Absolutely!
This is the main difference between PEGs (see http://en.wikipedia.org/wiki/Parsing_expression_grammar) and the traditional grammars written down in (E)BNF.
In PEGs the choice operator (i.e. "FirstOf") in parboiled is _ordered_. This means that the different alternatives are tried one by one, the first match wins.
That is also the reason by parboiled calls the operator FIRSTof.

As long as the different alternatives of a "FirstOf" are mutually exclusive there is no difference between BNF and PEGs (apart from runtime concerns maybe), but as soon as one alternative is a prefix on another one you can run into trouble. (see the second section of https://github.com/sirthias/parboiled/wiki/Parsing-Performance-Tuning for an example and more details).

HTH,
Mathias

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

On 21.04.2011, at 22:41, JonathanEdwards [via parboiled users] wrote:

> Hi, making great progress with Parboiled (0.11.1) for a few weeks, but have hit a problem that looks like it might be a bug. Swapping the order of two terms in a FirstOf affects whether the parse succeeds. Should that ever possibly happen?
>
> If you reply to this email, your message will be added to the discussion below:
> http://users.parboiled.org/FirstOf-problem-tp2848597p2848597.html
> To start a new topic under parboiled users, email [hidden email]
> To unsubscribe from parboiled users, click here.

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

Re: FirstOf problem

JonathanEdwards

Mathias, I understand that, but I still don't see how reordering the FirstOf can change whether the parse succeeds at all. It appears that backtracking is failing. Thx.

On Apr 22, 2011 3:01 AM, "mathias [via parboiled users]" <[hidden email]> wrote:
>
>
> Hi Jonathan,
>
>> Should that ever possibly happen?
>
> Absolutely!
> This is the main difference between PEGs (see http://en.wikipedia.org/wiki/Parsing_expression_grammar) and the traditional grammars written down in (E)BNF.
> In PEGs the choice operator (i.e. "FirstOf") in parboiled is _ordered_. This means that the different alternatives are tried one by one, the first match wins.
> That is also the reason by parboiled calls the operator FIRSTof.
>
> As long as the different alternatives of a "FirstOf" are mutually exclusive there is no difference between BNF and PEGs (apart from runtime concerns maybe), but as soon as one alternative is a prefix on another one you can run into trouble. (see the second section of https://github.com/sirthias/parboiled/wiki/Parsing-Performance-Tuning for an example and more details).
>
> HTH,
> Mathias
>
> ---
> [hidden email]
> http://www.parboiled.org
>
> On 21.04.2011, at 22:41, JonathanEdwards [via parboiled users] wrote:
>
>> Hi, making great progress with Parboiled (0.11.1) for a few weeks, but have hit a problem that looks like it might be a bug. Swapping the order of two terms in a FirstOf affects whether the parse succeeds. Should that ever possibly happen?
>>
>> If you reply to this email, your message will be added to the discussion below:
>> http://users.parboiled.org/FirstOf-problem-tp2848597p2848597.html
>> To start a new topic under parboiled users, email [hidden email]
>> To unsubscribe from parboiled users, click here.
>
>
>
> _______________________________________________
> If you reply to this email, your message will be added to the discussion below:
> http://users.parboiled.org/FirstOf-problem-tp2848597p2850603.html
>
> To unsubscribe from FirstOf problem, visit
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: FirstOf problem

JonathanEdwards
In reply to this post by mathias

Maybe you are saying there is no backtracking into a matching
Firstof. But my problem is inside the firstof. Reordering the firstof changes whether it matches.

On Apr 22, 2011 8:36 AM, "Jonathan Edwards" <[hidden email]> wrote:
> Mathias, I understand that, but I still don't see how reordering the FirstOf
> can change whether the parse succeeds at all. It appears that backtracking
> is failing. Thx.
> On Apr 22, 2011 3:01 AM, "mathias [via parboiled users]" <
> [hidden email]> wrote:
>>
>>
>> Hi Jonathan,
>>
>>> Should that ever possibly happen?
>>
>> Absolutely!
>> This is the main difference between PEGs (see
> http://en.wikipedia.org/wiki/Parsing_expression_grammar) and the traditional
> grammars written down in (E)BNF.
>> In PEGs the choice operator (i.e. "FirstOf") in parboiled is _ordered_.
> This means that the different alternatives are tried one by one, the first
> match wins.
>> That is also the reason by parboiled calls the operator FIRSTof.
>>
>> As long as the different alternatives of a "FirstOf" are mutually
> exclusive there is no difference between BNF and PEGs (apart from runtime
> concerns maybe), but as soon as one alternative is a prefix on another one
> you can run into trouble. (see the second section of
> https://github.com/sirthias/parboiled/wiki/Parsing-Performance-Tuning for an
> example and more details).
>>
>> HTH,
>> Mathias
>>
>> ---
>> [hidden email]
>> http://www.parboiled.org
>>
>> On 21.04.2011, at 22:41, JonathanEdwards [via parboiled users] wrote:
>>
>>> Hi, making great progress with Parboiled (0.11.1) for a few weeks, but
> have hit a problem that looks like it might be a bug. Swapping the order of
> two terms in a FirstOf affects whether the parse succeeds. Should that ever
> possibly happen?
>>>
>>> If you reply to this email, your message will be added to the discussion
> below:
>>> http://users.parboiled.org/FirstOf-problem-tp2848597p2848597.html
>>> To start a new topic under parboiled users, email
> [hidden email]
>>> To unsubscribe from parboiled users, click here.
>>
>>
>>
>> _______________________________________________
>> If you reply to this email, your message will be added to the discussion
> below:
>> http://users.parboiled.org/FirstOf-problem-tp2848597p2850603.html
>>
>> To unsubscribe from FirstOf problem, visit
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: FirstOf problem

mathias
Administrator
In reply to this post by JonathanEdwards
Let's take a look at the following grammar:

S = A b
A = a a a | a a

For input "aaab" rule S matches.
But what happens when you swap the order of the choice operator in A?

S = A b
A = a a | a a a

It will not match, since backtracking does retry rules that have already matched.
Backtracking means, that the parser tries different alternatives in all "currently open" choice operators, i.e. the ones the current rule lies underneath (within).
In the case above rule A has matched after two 'a's and is not open anymore.

Backtracking would work if the grammar looked like this:
S = a a a b | a a b

As you can see the two are not equivalent since the choice operator is ordered.

Hope that helps,
Mathias

---
[hidden email]
http://www.decodified.com

On 22.04.2011, at 14:36, JonathanEdwards [via parboiled users] wrote:

> Mathias, I understand that, but I still don't see how reordering the FirstOf can change whether the parse succeeds at all. It appears that backtracking is failing. Thx.
>
> On Apr 22, 2011 3:01 AM, "mathias [via parboiled users]" <[hidden email]> wrote:
> >
> >
> > Hi Jonathan,
> >
> >> Should that ever possibly happen?
> >
> > Absolutely!
> > This is the main difference between PEGs (see http://en.wikipedia.org/wiki/Parsing_expression_grammar) and the traditional grammars written down in (E)BNF.
> > In PEGs the choice operator (i.e. "FirstOf") in parboiled is _ordered_. This means that the different alternatives are tried one by one, the first match wins.
> > That is also the reason by parboiled calls the operator FIRSTof.
> >
> > As long as the different alternatives of a "FirstOf" are mutually exclusive there is no difference between BNF and PEGs (apart from runtime concerns maybe), but as soon as one alternative is a prefix on another one you can run into trouble. (see the second section of https://github.com/sirthias/parboiled/wiki/Parsing-Performance-Tuning for an example and more details).
> >
> > HTH,
> > Mathias
> >
> > ---
> > [hidden email]
> > http://www.parboiled.org
> >
> > On 21.04.2011, at 22:41, JonathanEdwards [via parboiled users] wrote:
> >
> >> Hi, making great progress with Parboiled (0.11.1) for a few weeks, but have hit a problem that looks like it might be a bug. Swapping the order of two terms in a FirstOf affects whether the parse succeeds. Should that ever possibly happen?
> >>
> >> If you reply to this email, your message will be added to the discussion below:
> >> http://users.parboiled.org/FirstOf-problem-tp2848597p2848597.html
> >> To start a new topic under parboiled users, email [hidden email]
> >> To unsubscribe from parboiled users, click here.
> >
> >
> >
> > _______________________________________________
> > If you reply to this email, your message will be added to the discussion below:
> > http://users.parboiled.org/FirstOf-problem-tp2848597p2850603.html
> >
> > To unsubscribe from FirstOf problem, visit
>
>
> If you reply to this email, your message will be added to the discussion below:
> http://users.parboiled.org/FirstOf-problem-tp2848597p2851258.html
> To start a new topic under parboiled users, email [hidden email]
> To unsubscribe from parboiled users, click here.

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

Re: FirstOf problem

JonathanEdwards
In reply to this post by mathias

Ok my bad. The firstof is actually matching, and one of the terms is a prefix of the other. Wasn't obvious. Sorry to bother you. Thx for parboiled, it has been very productive for me.

On Apr 22, 2011 3:01 AM, "mathias [via parboiled users]" <[hidden email]> wrote:
>
>
> Hi Jonathan,
>
>> Should that ever possibly happen?
>
> Absolutely!
> This is the main difference between PEGs (see http://en.wikipedia.org/wiki/Parsing_expression_grammar) and the traditional grammars written down in (E)BNF.
> In PEGs the choice operator (i.e. "FirstOf") in parboiled is _ordered_. This means that the different alternatives are tried one by one, the first match wins.
> That is also the reason by parboiled calls the operator FIRSTof.
>
> As long as the different alternatives of a "FirstOf" are mutually exclusive there is no difference between BNF and PEGs (apart from runtime concerns maybe), but as soon as one alternative is a prefix on another one you can run into trouble. (see the second section of https://github.com/sirthias/parboiled/wiki/Parsing-Performance-Tuning for an example and more details).
>
> HTH,
> Mathias
>
> ---
> [hidden email]
> http://www.parboiled.org
>
> On 21.04.2011, at 22:41, JonathanEdwards [via parboiled users] wrote:
>
>> Hi, making great progress with Parboiled (0.11.1) for a few weeks, but have hit a problem that looks like it might be a bug. Swapping the order of two terms in a FirstOf affects whether the parse succeeds. Should that ever possibly happen?
>>
>> If you reply to this email, your message will be added to the discussion below:
>> http://users.parboiled.org/FirstOf-problem-tp2848597p2848597.html
>> To start a new topic under parboiled users, email [hidden email]
>> To unsubscribe from parboiled users, click here.
>
>
>
> _______________________________________________
> If you reply to this email, your message will be added to the discussion below:
> http://users.parboiled.org/FirstOf-problem-tp2848597p2850603.html
>
> To unsubscribe from FirstOf problem, visit
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: FirstOf problem

mathias
Administrator
No worries.
Actually this exact problem has already bitten me a few times.
Sometimes it's hard to track these cases down.

Glad that you found the bug and thanks for the praise!

Cheers,
Mathias

---
[hidden email]
http://www.decodified.com

On 22.04.2011, at 15:08, JonathanEdwards [via parboiled users] wrote:

> Ok my bad. The firstof is actually matching, and one of the terms is a prefix of the other. Wasn't obvious. Sorry to bother you. Thx for parboiled, it has been very productive for me.
>
> On Apr 22, 2011 3:01 AM, "mathias [via parboiled users]" <[hidden email]> wrote:
> >
> >
> > Hi Jonathan,
> >
> >> Should that ever possibly happen?
> >
> > Absolutely!
> > This is the main difference between PEGs (see http://en.wikipedia.org/wiki/Parsing_expression_grammar) and the traditional grammars written down in (E)BNF.
> > In PEGs the choice operator (i.e. "FirstOf") in parboiled is _ordered_. This means that the different alternatives are tried one by one, the first match wins.
> > That is also the reason by parboiled calls the operator FIRSTof.
> >
> > As long as the different alternatives of a "FirstOf" are mutually exclusive there is no difference between BNF and PEGs (apart from runtime concerns maybe), but as soon as one alternative is a prefix on another one you can run into trouble. (see the second section of https://github.com/sirthias/parboiled/wiki/Parsing-Performance-Tuning for an example and more details).
> >
> > HTH,
> > Mathias
> >
> > ---
> > [hidden email]
> > http://www.parboiled.org
> >
> > On 21.04.2011, at 22:41, JonathanEdwards [via parboiled users] wrote:
> >
> >> Hi, making great progress with Parboiled (0.11.1) for a few weeks, but have hit a problem that looks like it might be a bug. Swapping the order of two terms in a FirstOf affects whether the parse succeeds. Should that ever possibly happen?
> >>
> >> If you reply to this email, your message will be added to the discussion below:
> >> http://users.parboiled.org/FirstOf-problem-tp2848597p2848597.html
> >> To start a new topic under parboiled users, email [hidden email]
> >> To unsubscribe from parboiled users, click here.
> >
> >
> >
> > _______________________________________________
> > If you reply to this email, your message will be added to the discussion below:
> > http://users.parboiled.org/FirstOf-problem-tp2848597p2850603.html
> >
> > To unsubscribe from FirstOf problem, visit
>
>
> If you reply to this email, your message will be added to the discussion below:
> http://users.parboiled.org/FirstOf-problem-tp2848597p2851326.html
> To start a new topic under parboiled users, email [hidden email]
> To unsubscribe from parboiled users, click here.

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

Re: FirstOf problem

iubito
Of course, this is important while optimizing and checking your grammar.
e.g.
FirstOf("Hello", "Hell")... and you'll never get to Hell :)
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: FirstOf problem

mathias
Administrator
Right, I think the problem of a FirstOf alternative being a prefix of another further behind and therefore shadowing it is one of the most common grammar bugs.
Actually I already thought of adding a verifier that detects these kinds of problems.
It will be by product of another optimization that could be implemented (called "cut markers").

I just added a GH issue to track this.
(https://github.com/sirthias/parboiled/issues/20)

Cheers,
Mathias

PS: Your example should be the other way around: FirstOf("Hell", "Hello")... and you'll never get to "Hello" :)

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

On 22.04.2011, at 15:26, iubito [via parboiled users] wrote:

> Of course, this is important while optimizing and checking your grammar.
> e.g.
> FirstOf("Hello", "Hell")... and you'll never get to Hell :)
>
> If you reply to this email, your message will be added to the discussion below:
> http://users.parboiled.org/FirstOf-problem-tp2848597p2851365.html
> To start a new topic under parboiled users, email [hidden email]
> To unsubscribe from parboiled users, click here.

Loading...