More PEG

More PEG

[Noah Lavine]

Hello all,

It looks to me like the last thing needed before the peg branch can be
used is to change some of the S-expression representations of the
components. Here are the five that I think need changing, taken from
the manual, with suggested replacements.

 -- PEG Pattern: zero or more a
     Parses A as many times in a row as it can, starting each A at the
     end of the text parsed by the previous A.  Always succeeds.

     `"a*"'

     `(body lit a *)'  change to: (* a)

 -- PEG Pattern: one or more a
     Parses A as many times in a row as it can, starting each A at the
     end of the text parsed by the previous A.  Succeeds if at least
     one A was parsed.

     `"a+"'

     `(body lit a +)'  change to: (+ a)

 -- PEG Pattern: optional a
     Tries to parse A.  Succeeds if A succeeds.

     `"a?"'

     `(? a)'

     Old: `(body lit a ?)'  change to: (? a)

 -- PEG Pattern: and predicate a
     Makes sure it is possible to parse A, but does not actually parse
     it.  Succeeds if A would succeed.

     `"&a"'

     `(body & a 1)'  change to: `(followed-by a)'

 -- PEG Pattern: not predicate a
     Makes sure it is impossible to parse A, but does not actually
     parse it.  Succeeds if A would fail.

     `"!a"'

     `(body ! a 1)'  change to: `(not-followed-by a)'

The first three were chosen to match the string representation, and
because *, + and ? are standard syntaxes for those ideas. The last two
were changed to words because I think & and ! aren't standard for the
ideas of followed-by and not-followed-by, and it would be hard to
remember which S-expression corresponded to which meaning, especially
since there is an S-expression syntax 'and' which is completely
different than '&'.

There's something I'm still a little unsure about, though. It's
possible to get deeply nested S-expressions, like '(+ (and (* "a")
"b")). Since +, * and ? only ever take one argument, it is possible to
shorten such a list by letting people merge those elements into the
next item, like this: '(+ and (* "a") "b").

On the other hand, that could get confusing if you later try to extend
peg syntax to match not just strings, but arbitrary sequences (which I
have been thinking of). For instance, say you want to match at least
one copy of the literal list '("a"). Is it (+ '("a")) or (+ quote
"a")?

What do you all think?

Noah

Re: More PEG

[Ludovic Courtès]

Hi Noah,

Noah Lavine <noah.b.lavine@gmail.com> skribis:

> It looks to me like the last thing needed before the peg branch can be
> used is to change some of the S-expression representations of the
> components. Here are the five that I think need changing, taken from
> the manual, with suggested replacements.

This looks like interesting stuff!

The syntactic changes you propose all make sense to me, FWIW.

[...]

> There's something I'm still a little unsure about, though. It's
> possible to get deeply nested S-expressions, like '(+ (and (* "a")
> "b")). Since +, * and ? only ever take one argument, it is possible to
> shorten such a list by letting people merge those elements into the
> next item, like this: '(+ and (* "a") "b").

I would rather keep it simple and avoid shortcuts that may end up being
confusing.

A more general question about PEG: how do you bind a variable to the
result of a pattern?  For instance, if you want the result of (* "a") to
be bound to variable X–just like (match '(1 2 3) ((a _ ...) a)) binds A
to 1.

Thanks,
Ludo’.

Re: More PEG

[Noah Lavine]

Hello,

> The syntactic changes you propose all make sense to me, FWIW.

Great! Then I will push an implementation soon unless someone else objects.

> A more general question about PEG: how do you bind a variable to the
> result of a pattern?  For instance, if you want the result of (* "a") to
> be bound to variable X–just like (match '(1 2 3) ((a _ ...) a)) binds A
> to 1.

We currently don't have that ability. I can see that it would be very
convenient, though, so maybe we should have it.

Right now I think you could get the same thing by running match on the
output of the peg - something like

(match (peg:tree (peg-parse <pattern> <tree>))
  ((list-of-as) ...)).

Do you think that's a good enough interface, or should the binding
happen directly? I can see that it would be more efficient if we
didn't box up the results in a structure first.

Thanks,
Noah

Re: More PEG

[Ludovic Courtès]

Hi!

Noah Lavine <noah.b.lavine@gmail.com> skribis:

> Right now I think you could get the same thing by running match on the
> output of the peg - something like
>
> (match (peg:tree (peg-parse <pattern> <tree>))
>   ((list-of-as) ...)).

Can you give an example of what ‘peg-parse’ and ‘peg:tree’ return?

Ludo’.

PS: I would suggest removing the ‘peg-’ and ‘peg:’ prefixes.  Users can
    still use a renamer if the names clash.

Re: More PEG

[Noah Lavine]

Hello,

> Can you give an example of what ‘peg-parse’ and ‘peg:tree’ return?

'peg-parse' returns a match record, which contains the string that was
parsed, the substring that actually matched, and the tree structure
produced by the matching. 'peg:tree' gets the tree structure out of a
match record.

I hadn't really looked at this part of the module, but it looks to me
now like the names aren't descriptive enough. Maybe we should change
them before putting this in a release.

Noah

On Sat, Sep 10, 2011 at 5:35 PM, Ludovic Courtès <ludo@gnu.org> wrote:
> Hi!
>
> Noah Lavine <noah.b.lavine@gmail.com> skribis:
>
>> Right now I think you could get the same thing by running match on the
>> output of the peg - something like
>>
>> (match (peg:tree (peg-parse <pattern> <tree>))
>>   ((list-of-as) ...)).
>
> Can you give an example of what ‘peg-parse’ and ‘peg:tree’ return?
>
> Ludo’.
>
> PS: I would suggest removing the ‘peg-’ and ‘peg:’ prefixes.  Users can
>    still use a renamer if the names clash.
>
>
>

Re: More PEG

[Noah Lavine]

As promised, the 'wip-peg-fixed' branch now has an updated
S-expression representation for PEG grammars, and updated
documentation for it.

As I understand it, the next thing to do before merging (and possibly
the last thing!) is to think about what things should be named, so
they can be easy for people to learn and forwards-compatible with
whatever our future plans for parsing are. I will try to send an email
soon with some thoughts on that.

Noah

On Sat, Sep 17, 2011 at 9:09 PM, Noah Lavine <noah.b.lavine@gmail.com> wrote:
> Hello,
>
>> Can you give an example of what ‘peg-parse’ and ‘peg:tree’ return?
>
> 'peg-parse' returns a match record, which contains the string that was
> parsed, the substring that actually matched, and the tree structure
> produced by the matching. 'peg:tree' gets the tree structure out of a
> match record.
>
> I hadn't really looked at this part of the module, but it looks to me
> now like the names aren't descriptive enough. Maybe we should change
> them before putting this in a release.
>
> Noah
>
> On Sat, Sep 10, 2011 at 5:35 PM, Ludovic Courtès <ludo@gnu.org> wrote:
>> Hi!
>>
>> Noah Lavine <noah.b.lavine@gmail.com> skribis:
>>
>>> Right now I think you could get the same thing by running match on the
>>> output of the peg - something like
>>>
>>> (match (peg:tree (peg-parse <pattern> <tree>))
>>>   ((list-of-as) ...)).
>>
>> Can you give an example of what ‘peg-parse’ and ‘peg:tree’ return?
>>
>> Ludo’.
>>
>> PS: I would suggest removing the ‘peg-’ and ‘peg:’ prefixes.  Users can
>>    still use a renamer if the names clash.
>>
>>
>>
>