gmane.comp.lang.lua.general

Wesley Smith | 6 Sep 21:03

lpeg and terminology

Hi list,
I'm brushing up on LPEG, trying some things out and wrapping my head
around this whole thing.  I'm currently going through the docs and "A
Text Pattern-Matching Tool based on Parsing Expression Grammars"
paper.  What's tripping me up is some of the terminology that's
currently a bit fuzzy to me.  If there's a good resource for getting a
handle on the basic, terminology-wise, I'd love to know about it.

Specifically, what does a phrase like "blind greedy repetition" mean?
I understand greedy to mean look for a mach until there are no more,
but blind is a bit of mystery.  Any info appreciated.
thanks,
wes

headers

Mark Meijer | 7 Sep 14:15

Re: lpeg and terminology

I've found Roberto's presentation about this to be very informative
(he also explains blind greedy etc). Check out the video:
http://lua-users.org/lists/lua-l/2008-08/msg00129.html

2008/9/6 Wesley Smith <wesley.hoke <at> gmail.com>:
> Hi list,
> I'm brushing up on LPEG, trying some things out and wrapping my head
> around this whole thing.  I'm currently going through the docs and "A
> Text Pattern-Matching Tool based on Parsing Expression Grammars"
> paper.  What's tripping me up is some of the terminology that's
> currently a bit fuzzy to me.  If there's a good resource for getting a
> handle on the basic, terminology-wise, I'd love to know about it.
>
> Specifically, what does a phrase like "blind greedy repetition" mean?
> I understand greedy to mean look for a mach until there are no more,
> but blind is a bit of mystery.  Any info appreciated.
> thanks,
> wes
>

headers

Mark Meijer | 7 Sep 14:30

Re: lpeg and terminology

Alternative page with same video (found via reply to the message I
linked in my previous post):
http://v.poly.edu/node/52

And here you can find the slides used in the presentation:
http://www.lua.org/wshop08.html#ierusalimschy

2008/9/7 Mark Meijer <meijer78 <at> gmail.com>:
> I've found Roberto's presentation about this to be very informative
> (he also explains blind greedy etc). Check out the video:
> http://lua-users.org/lists/lua-l/2008-08/msg00129.html
>
>
> 2008/9/6 Wesley Smith <wesley.hoke <at> gmail.com>:
>> Hi list,
>> I'm brushing up on LPEG, trying some things out and wrapping my head
>> around this whole thing.  I'm currently going through the docs and "A
>> Text Pattern-Matching Tool based on Parsing Expression Grammars"
>> paper.  What's tripping me up is some of the terminology that's
>> currently a bit fuzzy to me.  If there's a good resource for getting a
>> handle on the basic, terminology-wise, I'd love to know about it.
>>
>> Specifically, what does a phrase like "blind greedy repetition" mean?
>> I understand greedy to mean look for a mach until there are no more,
>> but blind is a bit of mystery.  Any info appreciated.
>> thanks,
>> wes
>>
>

(Continue reading)

headers

Roberto Ierusalimschy | 8 Sep 17:45

Re: lpeg and terminology

> Specifically, what does a phrase like "blind greedy repetition" mean?
> I understand greedy to mean look for a mach until there are no more,
> but blind is a bit of mystery.  Any info appreciated.

Unfortunately, the use of the term "greedy" regarding pattern
matching is not very precise with respect with its common use in
algorithms. Usually "greedy" in that context does not mean "until there
are no more", but "as much as possible". (Whether these two definitions
are equivalent depends on your definition of "possible" :)  So, the usual
repetition operators '*' and '+' are frequently called greedy.

I used the term "greedy" with the above meaning, of "as much as
possible".  "Blind", in that context, changes the meaning of what
it is "possible". It is explained on page 3 of the paper ("A Text
Pattern-Matching Tool..."):

  A blind greedy repetition [...] always matches the maximum possible span
  (therefore greedy), disregarding what comes afterwards (therefore blind).

  [...]
  A non-blind greedy repetition is one that repeats as many times as
  possible (therefore greedy), as long as the rest of the pattern
  matches (therefore non-blind).

-- Roberto