how to use parsing expressing grammar

how to use parsing expressing grammar

[Xah Lee]

There are 2 parsing expression grammars in elisp.

    * http://www.emacswiki.org/cgi-bin/wiki/ParserCompiler, (2008) by
Mike Mattie.
    * http://www.emacswiki.org/emacs/ParsingExpressionGrammars (2008)
by Helmut Eller.

The second one seems simpler, and i'm trying to learn it as a regex
replacement, but don't know how to use it.

Could anyone give concrete example in the following scenario?

For example, on my website i have things like:

 <hr>
 <p>Related essays:</p>
 <ul>
 <li><a href="someFilePath1">SomeTitleString2</a> someSring1</li>
 <li><a href="someFilePath2">SomeTitleString2</a> someSring2</li>
 ...
 </ul>

Suppose i want to change them to:

 <hr>
 <p>See also:</p>
 <p>
 <a href="someFilePath1">SomeTitleString1</a> someSring1<br>
 <a href="someFilePath2">SomeTitleString2</a> someSring2<br>
 ...
 </p>

How do i do it?

Thanks.

  Xah
∑ http://xahlee.org/

☄

Re: how to use parsing expressing grammar

[Kevin Rodgers]

Xah Lee wrote:
> There are 2 parsing expression grammars in elisp.
> 
>     * http://www.emacswiki.org/cgi-bin/wiki/ParserCompiler, (2008) by
> Mike Mattie.
>     * http://www.emacswiki.org/emacs/ParsingExpressionGrammars (2008)
> by Helmut Eller.
> 
> The second one seems simpler, and i'm trying to learn it as a regex
> replacement, but don't know how to use it.
> 
> Could anyone give concrete example in the following scenario?
> 
> For example, on my website i have things like:
> 
>  <hr>
>  <p>Related essays:</p>
>  <ul>
>  <li><a href="someFilePath1">SomeTitleString2</a> someSring1</li>
>  <li><a href="someFilePath2">SomeTitleString2</a> someSring2</li>
>  ...
>  </ul>
> 
> Suppose i want to change them to:
> 
>  <hr>
>  <p>See also:</p>
>  <p>
>  <a href="someFilePath1">SomeTitleString1</a> someSring1<br>
>  <a href="someFilePath2">SomeTitleString2</a> someSring2<br>
>  ...
>  </p>
> 
> How do i do it?

Choose the right tool for the job:

sed -e 's|^<p>Related essays:</p>$|<p>See also:</p>|' -e 
'/^<ul>$/,/^<\/ul>/{s|^<\(/*\)ul>$|<\1p>|;s|^<li>||;s|</li>$|<br>|;}'

And since this is help-gnu-emacs@gnu.org:

C-x h
C-u M-| sed -e ...

-- 
Kevin Rodgers
Denver, Colorado, USA

Re: how to use parsing expressing grammar

[Xah Lee]

On Dec 17, 7:43 pm, Kevin Rodgers <kevin.d.rodg...@gmail.com> wrote:
> Xah Lee wrote:
> > There are 2 parsing expression grammars in elisp.
>
> >     *http://www.emacswiki.org/cgi-bin/wiki/ParserCompiler, (2008) by
> > Mike Mattie.
> >     *http://www.emacswiki.org/emacs/ParsingExpressionGrammars(2008)
> > by Helmut Eller.
>
> > The second one seems simpler, and i'm trying to learn it as a regex
> > replacement, but don't know how to use it.
>
> > Could anyone give concrete example in the following scenario?
>
> > For example, on my website i have things like:
>
> >  <hr>
> >  <p>Related essays:</p>
> >  <ul>
> >  <li><a href="someFilePath1">SomeTitleString2</a> someSring1</li>
> >  <li><a href="someFilePath2">SomeTitleString2</a> someSring2</li>
> >  ...
> >  </ul>
>
> > Suppose i want to change them to:
>
> >  <hr>
> >  <p>See also:</p>
> >  <p>
> >  <a href="someFilePath1">SomeTitleString1</a> someSring1<br>
> >  <a href="someFilePath2">SomeTitleString2</a> someSring2<br>
> >  ...
> >  </p>
>
> > How do i do it?
>
> Choose the right tool for the job:
>
> sed -e 's|^<p>Related essays:</p>$|<p>See also:</p>|' -e
> '/^<ul>$/,/^<\/ul>/{s|^<\(/*\)ul>$|<\1p>|;s|^<li>||;s|</li>$|<br>|;}'
>
> And since this is help-gnu-em...@gnu.org:
>
> C-x h
> C-u M-| sed -e ...

I'm mainly interested in learning about parsing expression grammar,
because its power is a order of magnitude higher than regex. In
practice, this just means it's the next generation of regex.

the sed code won't work in general... because as soon as you have some
other chars or slight variation, it stops working. You'll need to code
up a lot variations than conditional expressions. All the ~4000 html
pages on my website are valid html4. Even at the level of strictness
of valid xml, regex simply can't work.

if i wanted to, could've used Perl, which i'm a master, which is far
more powerful than sed. Even though emacs regex is less powerful than
perl, but in my opinion, the fact that you can move cursor about
freely due to elisp's buffer datatype, its power as a text processing
lang beats Perl despite Perl's more powerful regex. But still, they
all inferior to parsing expression grammar.

i think parsing expression grammar is so important that it should be
core of emacs soon, perhaps coded in C.

PS for those interested in PEG, Helmut Eller has given answer in
comp.emacs, here:
http://groups.google.com/group/comp.emacs/browse_frm/thread/acb19cb47f2e632f

See also:

• Text Processing: Elisp vs Perl
  http://xahlee.org/emacs/elisp_text_processing_lang.html

• Pattern Matching vs Lexical Grammar Specification
  http://xahlee.org/cmaci/notation/pattern_matching_vs_pattern_spec.html

  Xah
∑ http://xahlee.org/

☄

Re: how to use parsing expressing grammar

[Xah Lee]

more questions on parsing expression grammar.

let's say i want to change tags of the form

“<img src="archimedesspiral.png">”

into

“<img src="★">”

I tried the following:

(defun doMyReplace ()
(interactive)
  (peg-parse
   (start imgTag)
  (imgTag "<img" whitespace "src=" "\"" (replace filePath "★") "\""
">")
  (whitespace [" "])
  (filePath [a-z "."])
   )
)

then placed my cursor at the beginning of the tag, then call
doMyReplace. It doesn't seems to work, except moving cursor to after
the “a”.

I spent about 20 min but couldn't see what's wrong with my code?

----------------

in general, i wanted to use PEG to do transformation from html 4
transitional to html 4 strict. I have maybe 3 hundred files to do
this. One of the primary change from html 4 trans to html 4 strict is
that any image tag now needs to be wrapped with “div”.

So basically,

<img ...>

needs to become

<div><img ...></div>

The first job i tried to do to as a simplification, is to try to write
a img tag matcher to test with. here's my code:

(defun doMyReplace ()
(interactive)
  (peg-parse
  (imgTag "<img" whitespace
 "src=" "\"" filePath "\"" whitespace
 "alt=" "\"" (replace altStr "★") "\"" whitespace
 "height=" "\"" digits "\"" whitespace
 "width=" "\"" digits "\""
 ">")
  (whitespace ["\n "])
  (digits [0-9])
  (filePath [A-Z a-z "./_"])
  (altStr [A-Z a-z "./ '"])
   )
)

but then couldn't get it to work.

Any help appreciated.

Btw, would you be interested in starting a mailing list on PEG in
emacs? e.g. yasnippet has one thru google, nxml has one in yahoo
group, ljupdate has one in livejournal. I think it'd be helpful.

  Xah
∑ http://xahlee.org/

☄

On Dec 19, 3:27 pm, Xah Lee <xah...@gmail.com> wrote:
> On Dec 17, 10:22 am, Helmut Eller <eller.hel...@gmail.com> wrote:
>
>
>
> > * Helmut Eller [2008-12-17 16:21+0100] writes:
>
> > > Recording positions in this manner is obviously tedious and it just
> > > shows that the package hasn't received much battle testing.  As a little
> > > improvement we could define a custom "region" operator which acts
> > > similarly as the *list operator, but instead of collecting a list we
> > > push the start and end positions.  E.g.:
>
> > I released a new version of peg.el and added a replace operator.
> > We can now match and replace without helper function:
>
> > (defun parse3 ()
> >   (peg-parse
> >    (start _ "<hr>" _ title _ ul)
> >    (title "<p>" (replace (* (not "</p>") (any)) "See also:") "</p>")
> >    (ul (replace "<ul>" "<p>") _ (*list li _) (replace "</ul>" "</p>"))
> >    (li (replace "<li>" "") (* (not "</li>") (any)) (replace "</li>" "<br>"))
> >    (_ (* (or whitespace comment)))
> >    (whitespace ["\n\t "])
> >    (comment "<-- " (* (not "-->") (any)) "-->")))
>
> > Helmut.
>
> Holy cow. This worked! LOL!
>
> Thanks!
>
>   Xah
> ∑http://xahlee.org/
>
> ☄

Re: how to use parsing expressing grammar

[Helmut Eller]

* Xah Lee [2008-12-20 09:42+0100] writes:

> I tried the following:
>
> (defun doMyReplace ()
> (interactive)
>   (peg-parse
>    (start imgTag)
>   (imgTag "<img" whitespace "src=" "\"" (replace filePath "★") "\""
> ">")
>   (whitespace [" "])
>   (filePath [a-z "."])
>    )
> )
>
> then placed my cursor at the beginning of the tag, then call
> doMyReplace. It doesn't seems to work, except moving cursor to after
> the “a”.

The filePath rule only matches the first character.  You probably
want to write (+ [a-z "."]).  Same issue for whitespace.

> The first job i tried to do to as a simplification, is to try to write
> a img tag matcher to test with. here's my code:
>
> (defun doMyReplace ()
> (interactive)
>   (peg-parse
>   (imgTag "<img" whitespace
>  "src=" "\"" filePath "\"" whitespace
>  "alt=" "\"" (replace altStr "★") "\"" whitespace
>  "height=" "\"" digits "\"" whitespace
>  "width=" "\"" digits "\""
>  ">")
>   (whitespace ["\n "])
>   (digits [0-9])
>   (filePath [A-Z a-z "./_"])
>   (altStr [A-Z a-z "./ '"])
>    )
> )

Same problem here.  

If the basics work you can try to generalize this a bit.  E.g.

(imgTag "<img" whitespace (* attribute whitespace) ">")
(attribute (or src height width alt))
(src "src" whitespace "=" whitespace "\"" filePath \"\"")

etc.

> Btw, would you be interested in starting a mailing list on PEG in
> emacs? e.g. yasnippet has one thru google, nxml has one in yahoo
> group, ljupdate has one in livejournal. I think it'd be helpful.

So far only 2 people asked questions.  If there are some more we can set
up a mailing list.

Helmut.

Re: how to use parsing expressing grammar

[Xah Lee]

Xah Lee wrote:
> let's say i want to change tags of the form
> “<img src="archimedesspiral.png">”
> into
> “<img src="★">”
> I tried the following:
> (defun doMyReplace ()
> (interactive)
>   (peg-parse
>    (start imgTag)
>   (imgTag "<img" whitespace "src=" "\"" (replace filePath "★") "\"" ">")
>   (whitespace [" "])
>   (filePath [a-z "."])
>    )
> )

Helmut Eller wrote:
> The filePath rule only matches the first character.  You probably
> want to write (+ [a-z "."]).  Same issue for whitespace.

Thanks a lot! It worked out great!

I have another question, hopefully this one is not a dumb one.

In summary, if i have

   (imgTag "<img" whitespace (+ attributes whitespace) ">")

how to tell PEG that if a attribute is the last item, then the
whitespace following it is optional?

For example, the above will match
<A B C >
but won't match
<A B C>

Here's my code:

(defun doMyReplace ()
(interactive)
  (peg-parse
   (imgTag "<img" _ (+ attributes _) ">")
   (attributes (or src alt width height))
   (src "src" _* "=" _* "\"" filePath "\"")
   (filePath (+ [A-Z a-z "./_-"]))
   (alt "alt" _* "=" _* "\"" altStr "\"")
   (altStr (* [A-Z a-z "./ '_"]))
   (width "width" _* "=" _* "\"" digits "\"")
   (height "height" _* "=" _* "\"" digits "\"")
   (_* (* ["\n \t"])) ; 0 or more white space
   (_ (+ ["\n \t"])) ; 1 or more white space
   (digits (+ [0-9]))
   )
)

here's a sample text to be matched:
<img src="archimedes_spiral_k.png" alt="archimedean spiral"
width="288" height="115">

if i add a space to the ending “>”, it matches.

Thanks again.

> > Btw, would you be interested in starting a mailing list on PEG in
> > emacs? e.g. yasnippet has one thru google, nxml has one in yahoo
> > group, ljupdate has one in livejournal. I think it'd be helpful.
>
> So far only 2 people asked questions.  If there are some more we can set
> up a mailing list.

I'm pretty sure if you create it, more and more people will join it.
I'm very interested in PEG and think it is of critical importance. If
say emacs 24 has it built in as C code, with all its regex functions
such as search-forward-regexp, query-replace-regexp etc having PEG
version, it would make emacs a killer app.

From Wikipedia, it appears that people have already wrote PEG lib for
most major langs. There is already a C lib for PEG. The problem with
them is that most comes with a background of computer lang parsing, as
opposed to practical use for text processing like regex. (note: regex
itself came from computer science background as a way to determine
languages with “regular” grammar, but today it is far removed from
theoretical parsing. The process of this transmutation took i think 10
years, and it took another 10 or so years until it become a widely
popular tool in langs, starting with Perl in the 1990s) I don't forsee
that in the next 10 years that practicing programers will all know
about computer science of parsing or that major langs will all have
formal grammar spec. I'm pretty certain people are already seeing the
potential of PEG as regex replacement and working towards creatings
such practical goal.

  Xah
∑ http://xahlee.org/

☄

Re: how to use parsing expressing grammar

[Helmut Eller]

* Xah Lee [2008-12-20 22:41+0100] writes:

> I have another question, hopefully this one is not a dumb one.
>
> In summary, if i have
>
>    (imgTag "<img" whitespace (+ attributes whitespace) ">")
>
> how to tell PEG that if a attribute is the last item, then the
> whitespace following it is optional?

Hmm, good question.  Perhaps something like

(imgTag "<img" (+ whitespace attribute) (opt whitespace) ">")

This does a bit of backtracking, but easy to read.

>> So far only 2 people asked questions.  If there are some more we can set
>> up a mailing list.
>
> I'm pretty sure if you create it, more and more people will join it.
> I'm very interested in PEG and think it is of critical importance. 

I'll try to set up project at savannah.

> If say emacs 24 has it built in as C code, with all its regex
> functions such as search-forward-regexp, query-replace-regexp etc
> having PEG version, it would make emacs a killer app.

I don't think that PEGs are easy to use interactively, like
query-replace-regexp.  Regexps have a more concise notation, which is
crucial when used interactively.

> From Wikipedia, it appears that people have already wrote PEG lib for
> most major langs. There is already a C lib for PEG. The problem with
> them is that most comes with a background of computer lang parsing, as
> opposed to practical use for text processing like regex. (note: regex
> itself came from computer science background as a way to determine
> languages with “regular” grammar, but today it is far
> removed from theoretical parsing. The process of this transmutation
> took i think 10 years, and it took another 10 or so years until it
> become a widely popular tool in langs, starting with Perl in the
> 1990s) I don't forsee that in the next 10 years that practicing
> programers will all know about computer science of parsing or that
> major langs will all have formal grammar spec. I'm pretty certain
> people are already seeing the potential of PEG as regex replacement
> and working towards creatings such practical goal.

I think that the Lua language uses PEGs for text processing and
apparently implements it's regexp library on top of PEGs.

Helmut.

Re: how to use parsing expressing grammar

[Leo]

On 2008-12-21 09:49 +0000, Helmut Eller wrote:
>> I'm pretty sure if you create it, more and more people will join it.
>> I'm very interested in PEG and think it is of critical importance.
>
> I'll try to set up project at savannah.

I have seen the project on
http://savannah.nongnu.org/projects/emacs-peg. I wonder it might be a
good idea to make a newsgroup on gmane to link to the mailing list. It
will make more Emacs users subscribe to it.

Best wishes,
-- 
.:  Leo  :.  [ sdl.web AT gmail.com ]  .: I use Emacs :.

Re: how to use parsing expressing grammar

[Mike Mattie]

On Tue, 03 Mar 2009 17:34:41 +0000
Leo <sdl.web@gmail.com> wrote:

> On 2008-12-21 09:49 +0000, Helmut Eller wrote:
> >> I'm pretty sure if you create it, more and more people will join
> >> it. I'm very interested in PEG and think it is of critical
> >> importance.
> >
> > I'll try to set up project at savannah.
> 
> I have seen the project on
> http://savannah.nongnu.org/projects/emacs-peg. I wonder it might be a
> good idea to make a newsgroup on gmane to link to the mailing list. It
> will make more Emacs users subscribe to it.
> 
> Best wishes,

I was working on a PEG/CFG parser compiler:
http://www.emacswiki.org/cgi-bin/wiki/ParserCompiler

I will be resuming the development soon. Please keep me in the loop on such efforts.

Cheers,
Mike Mattie

Re: how to use parsing expressing grammar

[Xah Lee]

On Mar 3, 9:59 am, Mike Mattie <codermat...@gmail.com> wrote:
> On Tue, 03 Mar 2009 17:34:41 +0000
>
> Leo <sdl....@gmail.com> wrote:
> > On 2008-12-21 09:49 +0000, Helmut Eller wrote:
> > >> I'm pretty sure if you create it, more and more people will join
> > >> it. I'm very interested in PEG and think it is of critical
> > >> importance.
>
> > > I'll try to set up project at savannah.
>
> > I have seen the project on
> >http://savannah.nongnu.org/projects/emacs-peg. I wonder it might be a
> > good idea to make a newsgroup on gmane to link to the mailing list. It
> > will make more Emacs users subscribe to it.
>
> > Best wishes,
>
> I was working on a PEG/CFG parser compiler:http://www.emacswiki.org/cgi-bin/wiki/ParserCompiler
>
> I will be resuming the development soon. Please keep me in the loop on such efforts.

Folks,

when you create a PEG parser, please please make it user oriented one,
so that any user of emacs familiar with regex find-replace will be
able to use PEG for find-replace. In particular, when doing find-
replace on nested text such as XML.

regex is powerful, but it doesn't do nested text. PEG comes to the
rescue. However, it needs to be regex-like, in the sense that the
program interface will be a simple source text and replacement text.
e.g. a function peg-replace that takes 2 args, pattern text, and text
source. The pattern text can be the region, buffer, or a filename, the
text source to work on can be similar. (thus, maybe peg-replace-
region, peg-replace-buffer, peg-replace-file etc.)

last time i was looking at PEG, i opted to try Helmut Eller's version
because it seems simpler. (mike's version is far more compiler geeking
incomprehensible) But still problematic to use. I got busy in other
things so i didn't continue on studying it, so i dropped out of this
thread (havn't read Helmut's last message in detail). Rather, i simply
want just to use it. Last in this thread, he mentioned about stacks
and i went huh... and just didn't have time to go further.

Regex is practically extremely useful, a tool every programer uses
today. However, regex cannot work with nested text such as XML/HTML,
which is used extensively, probably more so than any programing lang
or text. So, brigining regex power to html/xml will be a major impact
on not just emacs, but the whole programing industry. PEG, practically
speaking, is basically just the next generation of so-called regex.
Emacs can be the first to have such a feature. (existing PEG
implementations in various lang,  at this point, as far as i know, are
all tech geeking toys, done by geekers interested in language parsing
and so on.)

Personally, i have huge need for regex that can work on html.
PEG is of course not just a regex replacement, but a BNF replacement
in the sense it is actually for machines to read. For these reasons
that's how i got heavily interested in PEG. (see:
• Pattern Matching vs Lexical Grammar Specification
  http://xahlee.org/cmaci/notation/pattern_matching_vs_pattern_spec.html
)

Please make your PEG in emacs with a regex-like API. Something any
emacs user familiar with regex will be able to use brainlessly. This
will be huge...

i had plans to open a mailing list and stuff... but got busy with
other things. I'll come back to this. But i hope you are convienced
about making PEG usable as a text-editing tool, as opposed to a tool
for computer scientist or compiler/parser writers.

Also, Mike & Helmut, please consider putting your code in goode code.
Google Code is very popular, probably today the most popular code
building service, and extremely easy to use, and from my studies
Google's products and services are all extremely high quality. It
would help a lot in your software at least in the marketing aspect if
you use Google Code. Also, open a google group is very useful and
popular. (yasnippet is a successful example for a emacs project on
google code. There are several others, including e.g. js2, ejacs, the
erlang one, etc.) Going into Savana or anything on FSF services tend
to be a dead end. (yeah, controversy, but whatever.)

  Xah
∑ http://xahlee.org/

☄

Re: how to use parsing expressing grammar

[W Dan Meyer]

Xah Lee <xahlee@gmail.com> writes:

> On Mar 3, 9:59 am, Mike Mattie <codermat...@gmail.com> wrote:
>> On Tue, 03 Mar 2009 17:34:41 +0000
>>
>> Leo <sdl....@gmail.com> wrote:
>> > On 2008-12-21 09:49 +0000, Helmut Eller wrote:
>> > >> I'm pretty sure if you create it, more and more people will join
>> > >> it. I'm very interested in PEG and think it is of critical
>> > >> importance.
>>
>> > > I'll try to set up project at savannah.
>>
>> > I have seen the project on
>> >http://savannah.nongnu.org/projects/emacs-peg. I wonder it might be a
>> > good idea to make a newsgroup on gmane to link to the mailing list. It
>> > will make more Emacs users subscribe to it.
>>
>> > Best wishes,
>>
>> I was working on a PEG/CFG parser compiler:http://www.emacswiki.org/cgi-bin/wiki/ParserCompiler
>>
>> I will be resuming the development soon. Please keep me in the loop on such efforts.

Are we talking about memoising PEG (e.g Packrat) in elisp?  There might
be more people interested.  I do realise that Emacs doesn't have decent
parsing facility and it makes it's regular expression based engine in
more complex areas useless (mentioned nested tags). Since it's automata
based you cannot go beyond simple patterns.  That means also that
everybody is reinventing a wheel with implanting all those recursive
decent parsers when it comes to analyse, pretty print, syntax highlight
of such modes like Haskell one.  Packrat parser is the best option out
there currently because it recognises much complex grammar then LALR(1),
and it has no ambiguities with expressing these grammars. Works well
also as a standalone combinator based solution rather then a parser
generator, plus it is lex-less e.g allow to recognise several different
languages in _one_go_ and one context without marking them explicitly!
cheers Dan W

Re: how to use parsing expressing grammar

[Miles Bader]

W Dan Meyer <specuu@gmail.com> writes:
> Are we talking about memoising PEG (e.g Packrat) in elisp? ...
> Packrat parser is the best option out there currently because it
> recognises much complex grammar then LALR(1), and it has no
> ambiguities with expressing these grammars.

You also might be interested in Roberto Ierusalimschy's paper on the
implemenation of LPEG, which is a PEG implementation for Lua:

   http://www.inf.puc-rio.br/~roberto/docs/peg.pdf


Note that LPEG does _not_ use the packrat algorithm, as apparently it
presents some serious practical problems for common uses of parsing
tools:

      In 2002, Ford proposed Packrat [5], an adaptation of the original
   algorithm that uses lazy evaluation to avoid that inefficiency.

      Even with this improvement, however, the space complexity of the
   algorithm is still linear on the subject size (with a somewhat big
   constant), even in the best case. As its author himself recognizes,
   this makes the algorithm not befitting for parsing “large amounts of
   relatively flat” data ([5], p. 57). However, unlike parsing tools,
   regular-expression tools aim exactly at large amounts of relatively
   flat data.

      To avoid these difficulties, we did not use the Packrat algorithm
   for LPEG. To implement LPEG we created a virtual parsing machine, not
   unlike Knuth’s parsing machine [15], where each pattern is
   represented as a program for the machine. The program is somewhat
   similar to a recursive-descendent parser (with limited backtracking)
   for the pattern, but it uses an explicit stack instead of recursion.


The general LPEG page is here:

   http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html


-Miles

-- 
Justice, n. A commodity which in a more or less adulterated condition the
State sells to the citizen as a reward for his allegiance, taxes and personal
service.

Re: how to use parsing expressing grammar

[Mike Mattie]

On Wed, 04 Mar 2009 09:35:00 +0900
Miles Bader <miles@gnu.org> wrote:

> W Dan Meyer <specuu@gmail.com> writes:
> > Are we talking about memoising PEG (e.g Packrat) in elisp? ...
> > Packrat parser is the best option out there currently because it
> > recognises much complex grammar then LALR(1), and it has no
> > ambiguities with expressing these grammars.
> 
> You also might be interested in Roberto Ierusalimschy's paper on the
> implemenation of LPEG, which is a PEG implementation for Lua:
> 
>    http://www.inf.puc-rio.br/~roberto/docs/peg.pdf
> 
> 
> Note that LPEG does _not_ use the packrat algorithm, as apparently it
> presents some serious practical problems for common uses of parsing
> tools:
> 
>       In 2002, Ford proposed Packrat [5], an adaptation of the
> original algorithm that uses lazy evaluation to avoid that
> inefficiency.
> 
>       Even with this improvement, however, the space complexity of the
>    algorithm is still linear on the subject size (with a somewhat big
>    constant), even in the best case. As its author himself recognizes,
>    this makes the algorithm not befitting for parsing “large amounts
> of relatively flat” data ([5], p. 57). However, unlike parsing tools,
>    regular-expression tools aim exactly at large amounts of relatively
>    flat data.
> 
>       To avoid these difficulties, we did not use the Packrat
> algorithm for LPEG. To implement LPEG we created a virtual parsing
> machine, not unlike Knuth’s parsing machine [15], where each pattern
> is represented as a program for the machine. The program is somewhat
>    similar to a recursive-descendent parser (with limited
> backtracking) for the pattern, but it uses an explicit stack instead
> of recursion.
> 
> 
> The general LPEG page is here:
> 
>    http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html
> 
> 
> -Miles
> 

It seems there is a convergence :) I implemented the same thing in my
parser compiler, with a different intent.The PEG operators decompose
down to an internal instruction set translated by the core into
elisp functions.

The VM is a co-routine of two functions. A compiler which generates
code from a valid instruction set, and a "union" function which
determines the validity of a given instruction sequence. The union
essentially attempts to pack as many instructions as possible into
a matching function. When adding an instruction produces an invalid set
it kicks the set to the compile function and starts a fresh matching 
function.

My goal was to allow the creation of custom operators for the ugly parts
of practical grammars that can be mixed with standard operators
in a consistent fashion. If the compiler is flexible enough then maybe
the AST can move inside the parser so the user does not have to re-invent
the wheel from the match hooks -> AST.

It's probably getting a bit to parser specific for emacs-help, but if you
want to compare notes feel free to e-mail me.

Cheers,
Mike Mattie

Re: how to use parsing expressing grammar

[Mike Mattie]

[-- Attachment #1: Type: text/plain, Size: 3246 bytes --]

On Tue, 03 Mar 2009 23:52:25 +0000
W Dan Meyer <specuu@gmail.com> wrote:

> Xah Lee <xahlee@gmail.com> writes:
> 
> > On Mar 3, 9:59 am, Mike Mattie <codermat...@gmail.com> wrote:
> >> On Tue, 03 Mar 2009 17:34:41 +0000
> >>
> >> Leo <sdl....@gmail.com> wrote:
> >> > On 2008-12-21 09:49 +0000, Helmut Eller wrote:
> >> > >> I'm pretty sure if you create it, more and more people will
> >> > >> join it. I'm very interested in PEG and think it is of
> >> > >> critical importance.
> >>
> >> > > I'll try to set up project at savannah.
> >>
> >> > I have seen the project on
> >> >http://savannah.nongnu.org/projects/emacs-peg. I wonder it might
> >> >be a
> >> > good idea to make a newsgroup on gmane to link to the mailing
> >> > list. It will make more Emacs users subscribe to it.
> >>
> >> > Best wishes,
> >>
> >> I was working on a PEG/CFG parser
> >> compiler:http://www.emacswiki.org/cgi-bin/wiki/ParserCompiler
> >>
> >> I will be resuming the development soon. Please keep me in the
> >> loop on such efforts.
> 
> Are we talking about memoising PEG (e.g Packrat) in elisp?  There
> might be more people interested.  I do realise that Emacs doesn't
> have decent parsing facility and it makes it's regular expression
> based engine in more complex areas useless (mentioned nested tags).
> Since it's automata based you cannot go beyond simple patterns.  That
> means also that everybody is reinventing a wheel with implanting all
> those recursive decent parsers when it comes to analyse, pretty
> print, syntax highlight of such modes like Haskell one.  Packrat
> parser is the best option out there currently because it recognises
> much complex grammar then LALR(1), and it has no ambiguities with
> expressing these grammars. Works well also as a standalone combinator
> based solution rather then a parser generator, plus it is lex-less
> e.g allow to recognise several different languages in _one_go_ and
> one context without marking them explicitly! cheers Dan W

Yes, packrat PEG. I am currently working on the left recursion, and the memoization.
The code generator is done. It is still very alpha, and a vehicle for experimenting, but
it is also the third iteration.

I want to make it useful first, which requires a number of features, and then try some more
exotic things.

The design goal is to produce a parser compiler that is easy to use. There are many tasks, or
good projects in Emacs that would be far easier to solve with a parser. 

It is implemented as a macro so that you can go from from grammer to parser is a single eval. 
There is a direct correlation between the grammar and the AST produced in simple
grammars. With these two features you can quickly put together a parser to glue various
jobs together. It will be complete too so you aren't handicapped in complex grammars.

Beyond that I want to implement more before I venture on where the design can go.

What I don't expect is parsing large volumes of data such as the linux kernel tree
at reasonable speed. Maybe it will, For that I would expect
to port it outside of elisp.

I won't give timelines, but I have more time than before (0) to work on it now.

Cheers,
Mike Mattie


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 197 bytes --]

Re: how to use parsing expressing grammar

[Mike Mattie]

On Tue, 3 Mar 2009 14:05:39 -0800 (PST)
Xah Lee <xahlee@gmail.com> wrote:

> On Mar 3, 9:59 am, Mike Mattie <codermat...@gmail.com> wrote:
> > On Tue, 03 Mar 2009 17:34:41 +0000
> >
> > Leo <sdl....@gmail.com> wrote:
> > > On 2008-12-21 09:49 +0000, Helmut Eller wrote:
> > > >> I'm pretty sure if you create it, more and more people will
> > > >> join it. I'm very interested in PEG and think it is of critical
> > > >> importance.
> >
> > > > I'll try to set up project at savannah.
> >
> > > I have seen the project on
> > >http://savannah.nongnu.org/projects/emacs-peg. I wonder it might
> > >be a
> > > good idea to make a newsgroup on gmane to link to the mailing
> > > list. It will make more Emacs users subscribe to it.
> >
> > > Best wishes,
> >
> > I was working on a PEG/CFG parser
> > compiler:http://www.emacswiki.org/cgi-bin/wiki/ParserCompiler
> >
> > I will be resuming the development soon. Please keep me in the loop
> > on such efforts.
> 
> Folks,
> 
> when you create a PEG parser, please please make it user oriented one,
> so that any user of emacs familiar with regex find-replace will be
> able to use PEG for find-replace. In particular, when doing find-
> replace on nested text such as XML.
> 
> regex is powerful, but it doesn't do nested text. PEG comes to the
> rescue. However, it needs to be regex-like, in the sense that the
> program interface will be a simple source text and replacement text.
> e.g. a function peg-replace that takes 2 args, pattern text, and text
> source. The pattern text can be the region, buffer, or a filename, the
> text source to work on can be similar. (thus, maybe peg-replace-
> region, peg-replace-buffer, peg-replace-file etc.)
> 
> last time i was looking at PEG, i opted to try Helmut Eller's version
> because it seems simpler. (mike's version is far more compiler geeking
> incomprehensible) But still problematic to use. I got busy in other
> things so i didn't continue on studying it, so i dropped out of this
> thread (havn't read Helmut's last message in detail). Rather, i simply
> want just to use it. Last in this thread, he mentioned about stacks
> and i went huh... and just didn't have time to go further.
> 
> Regex is practically extremely useful, a tool every programer uses
> today. However, regex cannot work with nested text such as XML/HTML,
> which is used extensively, probably more so than any programing lang
> or text. So, brigining regex power to html/xml will be a major impact
> on not just emacs, but the whole programing industry. PEG, practically
> speaking, is basically just the next generation of so-called regex.
> Emacs can be the first to have such a feature. (existing PEG
> implementations in various lang,  at this point, as far as i know, are
> all tech geeking toys, done by geekers interested in language parsing
> and so on.)
> 
> Personally, i have huge need for regex that can work on html.
> PEG is of course not just a regex replacement, but a BNF replacement
> in the sense it is actually for machines to read. For these reasons
> that's how i got heavily interested in PEG. (see:
> • Pattern Matching vs Lexical Grammar Specification
>   http://xahlee.org/cmaci/notation/pattern_matching_vs_pattern_spec.html
> )
> 
> Please make your PEG in emacs with a regex-like API. Something any
> emacs user familiar with regex will be able to use brainlessly. This
> will be huge...
> 
> i had plans to open a mailing list and stuff... but got busy with
> other things. I'll come back to this. But i hope you are convienced
> about making PEG usable as a text-editing tool, as opposed to a tool
> for computer scientist or compiler/parser writers.
> 
> Also, Mike & Helmut, please consider putting your code in goode code.
> Google Code is very popular, probably today the most popular code
> building service, and extremely easy to use, and from my studies
> Google's products and services are all extremely high quality. It
> would help a lot in your software at least in the marketing aspect if
> you use Google Code. Also, open a google group is very useful and
> popular. (yasnippet is a successful example for a emacs project on
> google code. There are several others, including e.g. js2, ejacs, the
> erlang one, etc.) Going into Savana or anything on FSF services tend
> to be a dead end. (yeah, controversy, but whatever.)
> 
>   Xah
> ∑ http://xahlee.org/
> 
> ☄

Making it simple to use is possible, and a goal. My project is not there
yet. There are still some thorny issues to work out. Until then it will
be very geeky :)

Overcoming the use issue will IMHO require good documentation with *alot*
of examples. When I am writing that I will let you know.

Cheers,
Mike Mattie

Re: how to use parsing expressing grammar

[Helmut Eller]

* Xah Lee [2009-03-03 23:05+0100] writes:

> Please make your PEG in emacs with a regex-like API. Something any
> emacs user familiar with regex will be able to use brainlessly. This
> will be huge...

Emacs's regexp API is stateful which isn't always great.  match-string
and friends refer to the last match which makes save-match-data
necessary and is hardly elegant.  It's also very easy to forget
save-match-data in timers, process-filters, etc.  I clearly prefer APIs
which minimize global side-effects.

The regexp approach to specify submatches "counting parens" is also hard
to use because those indices need to be adjusted when the regexp
changes.  Parens in regexps are used for two purposes: to override
precedence and to specify submatches.  This double function is IMO
confusing and rarely useful.

No, the Emacs regexp API is not the best example to imitate.  

> Also, Mike & Helmut, please consider putting your code in goode code.
> Google Code is very popular, probably today the most popular code
> building service, and extremely easy to use, and from my studies
> Google's products and services are all extremely high quality. It
> would help a lot in your software at least in the marketing aspect if
> you use Google Code. Also, open a google group is very useful and
> popular. (yasnippet is a successful example for a emacs project on
> google code. There are several others, including e.g. js2, ejacs, the
> erlang one, etc.) Going into Savana or anything on FSF services tend
> to be a dead end. (yeah, controversy, but whatever.)

Like it or not, Emacs is an FSF project and anything that wants to have
some influence in the Emacs world better follows FSF standards.

Google doesn't offer mailing lists, only web interfaces.  AFAIK, it's
not possible to read Google Groups from within Emacs which rules it out
for me.

Helmut.

Re: how to use parsing expressing grammar

[Xah Lee]

Hi Helmut,

another question i have is, how do i capture text as in regex's “\(...
\)”, “\1”?

I know in your elisp header file it mentions

;;  (action FORM)          ; evaluate FORM
;;  `(VAR... -- FORM...)   ; stack action

how do i capture match using that?

e.g. to match

<img src="some.png" alt="pretty" width="33" height="33" >

(defun doMyReplace ()
(interactive)
  (peg-parse
   (imgTag "<img" _ (+ attributes _) ">")
   (attributes (or src alt width height))
   (src "src" _* "=" _* "\"" filePath "\"")
   (filePath (+ [A-Z a-z "./_-"]))
   (alt "alt" _* "=" _* "\"" altStr "\"")
   (altStr (* [A-Z a-z "./ '_"]))
   (width "width" _* "=" _* "\"" digits "\"")
   (height "height" _* "=" _* "\"" digits "\"")
   (_* (* ["\n \t"])) ; 0 or more white space
   (_ (+ ["\n \t"])) ; 1 or more white space
   (digits (+ [0-9]))
   )
)

suppose i want to swap the src and alt text and have

<img src="pretty" alt="some.png" width="33" height="33" >

Thanks.

  Xah
∑ http://xahlee.org/

☄

Re: how to use parsing expressing grammar

[Helmut Eller]

* Xah Lee [2008-12-20 23:27+0100] writes:

> Hi Helmut,
>
> another question i have is, how do i capture text as in regex's “\(...
> \)”, “\1”?
>
> I know in your elisp header file it mentions
>
> ;;  (action FORM)          ; evaluate FORM
> ;;  `(VAR... -- FORM...)   ; stack action
>
> how do i capture match using that?

Basically there are 2 phases.  The first phase parses, i.e., decides
which rules match, and the second phase executes actions.  Actions are
executed at the point of match.  The action can do whatever is needed.

The peg stack can be use to pass values between actions.  You don't have
to use the stack, you could also use global variables or whatever is
convenient.

[...]
> suppose i want to swap the src and alt text and have
>
> <img src="pretty" alt="some.png" width="33" height="33" >

That's a bit complicated, but I think it's also a bit complicated to swap
to submatches with regexps.  Let's assume that we have a helper function
to swap two regions:

(defun swap-regions (start1 end1 start2 end2)
  (if (< start2 start1) 
      (swap-regions start2 end2 start1 end1)
    (let ((string1 (buffer-substring start1 end1))
	  (string2 (buffer-substring start2 end2)))
      (delete-region start2 end2)
      (goto-char start2)
      (insert string1)
      (delete-region start1 end1)
      (goto-char start1)
      (insert string2))))

Then this should work:

(defun doMyReplace ()
  (interactive)
  (let (src-start src-end alt-start alt-end)
    (peg-parse
     (imgTag "<img" _ (+ attributes _) ">")
     (attributes (or src alt width height))
     (src "src" = 
	  (action (setq src-start (point)))
	  "\"" filePath "\""
	  (action (setq src-end (point))))
     (filePath (+ [A-Z a-z "./_-"]))
     (alt "alt" = 
	  (action (setq alt-start (point)))
	  "\"" altStr "\"" 
	  (action (setq alt-end (point))))
     (altStr (* [A-Z a-z "./ '_"]))
     (width "width" =  "\"" digits "\"")
     (height "height" = "\"" digits "\"")
     (= _* "=" _*)
     (_* (* ["\n \t"])) ; 0 or more white space
     (_ (+ ["\n \t"])) ; 1 or more white space
     (digits (+ [0-9])))
    (swap-regions alt-start alt-end src-start src-end)))


I guess a mechanism to give matched regions a name would be useful.
E.g.  (capture E NAME) would match E and store the matched region with
NAME in a hashtable.  Actions could than easily refer to that region by
looking in the hashtable.  Auxiliary functions like (capture-string NAME)
or (capture-beginning NAME) to lookup the matched string resp. start
position in the hypothetical capture table could be implemented on top
of that.  Also something like replace-capture would then be easy to add.

Helmut.

Re: how to use parsing expressing grammar

[ashishnkadakia]

Sorry for the pointer to different language here.

If it doesn't matter which language you want to use, use Perl.
It has decent parsing modules, that can do job wonderfully.


On Dec 20, 3:42 am, Xah Lee <xah...@gmail.com> wrote:
> more questions on parsing expression grammar.
>
> let's say i want to change tags of the form
>
> “<img src="archimedesspiral.png">”
>
> into
>
> “<img src="★">”
>
> I tried the following:
>
> (defun doMyReplace ()
> (interactive)
>   (peg-parse
>    (start imgTag)
>   (imgTag "<img" whitespace "src=" "\"" (replace filePath "★") "\""
> ">")
>   (whitespace [" "])
>   (filePath [a-z "."])
>    )
> )
>
> then placed my cursor at the beginning of the tag, then call
> doMyReplace. It doesn't seems to work, except moving cursor to after
> the “a”.
>
> I spent about 20 min but couldn't see what's wrong with my code?
>
> ----------------
>
> in general, i wanted to use PEG to do transformation from html 4
> transitional to html 4 strict. I have maybe 3 hundred files to do
> this. One of the primary change from html 4 trans to html 4 strict is
> that any image tag now needs to be wrapped with “div”.
>
> So basically,
>
> <img ...>
>
> needs to become
>
> <div><img ...></div>
>
> The first job i tried to do to as a simplification, is to try to write
> a img tag matcher to test with. here's my code:
>
> (defun doMyReplace ()
> (interactive)
>   (peg-parse
>   (imgTag "<img" whitespace
>  "src=" "\"" filePath "\"" whitespace
>  "alt=" "\"" (replace altStr "★") "\"" whitespace
>  "height=" "\"" digits "\"" whitespace
>  "width=" "\"" digits "\""
>  ">")
>   (whitespace ["\n "])
>   (digits [0-9])
>   (filePath [A-Z a-z "./_"])
>   (altStr [A-Z a-z "./ '"])
>    )
> )
>
> but then couldn't get it to work.
>
> Any help appreciated.
>
> Btw, would you be interested in starting a mailing list on PEG in
> emacs? e.g. yasnippet has one thru google, nxml has one in yahoo
> group, ljupdate has one in livejournal. I think it'd be helpful.
>
>   Xah
> ∑http://xahlee.org/
>
> ☄
>
> On Dec 19, 3:27 pm, Xah Lee <xah...@gmail.com> wrote:
>
> > On Dec 17, 10:22 am, Helmut Eller <eller.hel...@gmail.com> wrote:
>
> > > * Helmut Eller [2008-12-17 16:21+0100] writes:
>
> > > > Recording positions in this manner is obviously tedious and it just
> > > > shows that the package hasn't received much battle testing.  As a little
> > > > improvement we could define a custom "region" operator which acts
> > > > similarly as the *list operator, but instead of collecting a list we
> > > > push the start and end positions.  E.g.:
>
> > > I released a new version of peg.el and added a replace operator.
> > > We can now match and replace without helper function:
>
> > > (defun parse3 ()
> > >   (peg-parse
> > >    (start _ "<hr>" _ title _ ul)
> > >    (title "<p>" (replace (* (not "</p>") (any)) "See also:") "</p>")
> > >    (ul (replace "<ul>" "<p>") _ (*list li _) (replace "</ul>" "</p>"))
> > >    (li (replace "<li>" "") (* (not "</li>") (any)) (replace "</li>" "<br>"))
> > >    (_ (* (or whitespace comment)))
> > >    (whitespace ["\n\t "])
> > >    (comment "<-- " (* (not "-->") (any)) "-->")))
>
> > > Helmut.
>
> > Holy cow. This worked! LOL!
>
> > Thanks!
>
> >   Xah
> > ∑http://xahlee.org/
>
> > ☄