headers
Ondřej Bílka | 4 Jan 2011 10:28
Picon
Favicon

Re: break at grammars

It turned out that we need split break as combination of what i denote cut and stop
When we encounter cut in or we skip subsequent branches so A cut B | C has semantics of A B | ~A C
A branch can be marked by stop and we exit loop if and only if we successfuly took marked branch

We can rewrite ordinary loop A* as (A | stop)

This distinction does not make much sense for PEG but for my beast 

It is nondeterministic topdown parser where we choose lexicographicaly smallest derivation 
with respect to took choices (I introduced break to add or in loop to catch greedy matching)
Condition to make it linear-time is that we limit recursion to left,rigth and inside expressions 
marked as nested. We assume that expression marked as nested is suffix-free. Semanticaly we want capture 
being enclosed by pair tags like for example nested('(' expression ')' )

On Sun, Jan 02, 2011 at 11:57:17AM +0100, Roman Redziejowski wrote:
>    This seems to be another way of writing the "repeat-until" operation.
> 
>    Apparently, version 4.0 of APG (ABNF Parser Generator)  by Lowell D.
>    Thomas
>    had this operation in the form *A!B, meaning "repeat matching A until B is
>    found."
>    It was removed in version 5.0 as being equivalent to *(!B A)B, which is
>    the same
>    as indicated by Francisco (for some reason APG writes star before
>    expressions).
>    See [1]http://www.coasttocoastresearch.com/apg/docs/doc50, section
>    3.2.3.5.
> 
>    My argument for introducing "repeat-until" would be a very concise
>    implementation
(Continue reading)

Permalink | Reply |
headers
Ondřej Bílka | 10 Jan 2011 21:36
Picon
Favicon

Re: break at grammars

NIce property that with cut operator(perhaps I should rename it as commit) you don't need to analyze
negative lookahead.
Negative lookahead ~A B is just (A cut Fail | B). 
I still use positive lookahead as double negation would obfustace istead of simplifying grammar
On Tue, Jan 04, 2011 at 10:28:05AM +0100, Ondřej Bílka wrote:
> It turned out that we need split break as combination of what i denote cut and stop
> When we encounter cut in or we skip subsequent branches so A cut B | C has semantics of A B | ~A C
> A branch can be marked by stop and we exit loop if and only if we successfuly took marked branch
> 
> We can rewrite ordinary loop A* as (A | stop)
> 
> This distinction does not make much sense for PEG but for my beast 
> 
> It is nondeterministic topdown parser where we choose lexicographicaly smallest derivation 
> with respect to took choices (I introduced break to add or in loop to catch greedy matching)
> Condition to make it linear-time is that we limit recursion to left,rigth and inside expressions 
> marked as nested. We assume that expression marked as nested is suffix-free. Semanticaly we want capture 
> being enclosed by pair tags like for example nested('(' expression ')' )
> 
> On Sun, Jan 02, 2011 at 11:57:17AM +0100, Roman Redziejowski wrote:
> >    This seems to be another way of writing the "repeat-until" operation.
> > 
> >    Apparently, version 4.0 of APG (ABNF Parser Generator)  by Lowell D.
> >    Thomas
> >    had this operation in the form *A!B, meaning "repeat matching A until B is
> >    found."
> >    It was removed in version 5.0 as being equivalent to *(!B A)B, which is
> >    the same
> >    as indicated by Francisco (for some reason APG writes star before
> >    expressions).
(Continue reading)

Permalink | Reply |
headers
Peter Cashin | 10 Jan 2011 21:53
Picon

Re: break at grammars

Hi


Cut is traditional name for that operator, from Prolog.

You may have read about Red and Green cuts... if not its well worth looking up.

Committed choice variants of Prolog had a flurry of popularity before they faded away.

If I understand your operator I think it is best named a cut operator.

Cheers,
Peter.


2011/1/11 Ondřej Bílka <neleai <at> seznam.cz>
NIce property that with cut operator(perhaps I should rename it as commit) you don't need to analyze negative lookahead.
Negative lookahead ~A B is just (A cut Fail | B).
I still use positive lookahead as double negation would obfustace istead of simplifying grammar
On Tue, Jan 04, 2011 at 10:28:05AM +0100, Ondřej Bílka wrote:
> It turned out that we need split break as combination of what i denote cut and stop
> When we encounter cut in or we skip subsequent branches so A cut B | C has semantics of A B | ~A C
> A branch can be marked by stop and we exit loop if and only if we successfuly took marked branch
>
> We can rewrite ordinary loop A* as (A | stop)
>
> This distinction does not make much sense for PEG but for my beast
>
> It is nondeterministic topdown parser where we choose lexicographicaly smallest derivation
> with respect to took choices (I introduced break to add or in loop to catch greedy matching)
> Condition to make it linear-time is that we limit recursion to left,rigth and inside expressions
> marked as nested. We assume that expression marked as nested is suffix-free. Semanticaly we want capture
> being enclosed by pair tags like for example nested('(' expression ')' )
>
> On Sun, Jan 02, 2011 at 11:57:17AM +0100, Roman Redziejowski wrote:
> >    This seems to be another way of writing the "repeat-until" operation.
> >
> >    Apparently, version 4.0 of APG (ABNF Parser Generator)  by Lowell D.
> >    Thomas
> >    had this operation in the form *A!B, meaning "repeat matching A until B is
> >    found."
> >    It was removed in version 5.0 as being equivalent to *(!B A)B, which is
> >    the same
> >    as indicated by Francisco (for some reason APG writes star before
> >    expressions).
> >    See [1]http://www.coasttocoastresearch.com/apg/docs/doc50, section
> >    3.2.3.5.
> >
> >    My argument for introducing "repeat-until" would be a very concise
> >    implementation
> >    (at least in the style I use in my "Mouse"), much shorter than that of
> >    *(!B A)B.
> >    Have been considering syntax such as A**B, but cannot make up my mind.
> >
> >    Happy New Year!
> >    Roman
> >
> >    On 2011-01-02 00:12, Francisco Mota wrote:
> >
> >      It might be convenient sometimes, but I don't think it increases the
> >      power of PEGs.
> >      You can always rewrite an expression like "(E1 break | E2)*" as "(!E1
> >      E2)* E1?"
> >      I wonder if there are any grammars that can't be expressed without
> >      break?
> >      2011/1/1 Ondřej Bílka <[2]neleai <at> seznam.cz>
> >
> >        Hello
> >        as I started to LR/RR eliminator I noticed that break is handy
> >
> >        It gave idea to introduce break statement to break iteration.
> >        For example C strings could be parsed as
> >         '"' ('"' break | '\"' | . )*
> >        whad do you think about it
> >        --
> >
> >        SCSI's too wide.
> >
> >        _______________________________________________
> >        PEG mailing list
> >        [3]PEG <at> lists.csail.mit.edu
> >        [4]https://lists.csail.mit.edu/mailman/listinfo/peg
> >
> >
> >  _______________________________________________
> >  PEG mailing list
> >  [5]PEG <at> lists.csail.mit.edu
> >  [6]https://lists.csail.mit.edu/mailman/listinfo/peg
> >
> > References
> >
> >    Visible links
> >    1. http://www.coasttocoastresearch.com/apg/docs/doc50
> >    2. mailto:neleai <at> seznam.cz
> >    3. mailto:PEG <at> lists.csail.mit.edu
> >    4. https://lists.csail.mit.edu/mailman/listinfo/peg
> >    5. mailto:PEG <at> lists.csail.mit.edu
> >    6. https://lists.csail.mit.edu/mailman/listinfo/peg
>
> > _______________________________________________
> > PEG mailing list
> > PEG <at> lists.csail.mit.edu
> > https://lists.csail.mit.edu/mailman/listinfo/peg
>
>
> --
>
> kernel panic: write-only-memory (/dev/wom0) capacity exceeded.
>
> _______________________________________________
> PEG mailing list
> PEG <at> lists.csail.mit.edu
> https://lists.csail.mit.edu/mailman/listinfo/peg

--

The vulcan-death-grip ping has been applied.

_______________________________________________
PEG mailing list
PEG <at> lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg

_______________________________________________
PEG mailing list
PEG <at> lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
Permalink | Reply |

Gmane