Lilypond BNF

classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

Lilypond BNF

Carl Sorensen-4
Almost a year ago, Pedro Kroger was working on a bnf description of
lilypond. (see  http://lists.gnu.org/archive/html/lilypond-
devel/2004-10/msg00074.html).  Han-Wen suggested hacking Bison so that
it would produce the BNF directly from the .yy file.

I went a different direction, and produced a python script that ignores
all the C++ stuff in parser.yy, resulting in a BNF description of
lilypond that is generated directly from the parser.

I've attached the script (yy2bnf.py), along with the result of running
the script on the current CVS version of parser.yy (lilypond.bnf).

I'd like to suggest that lilypond.bnf be added to the documentation, to
be automatically generated as part of the make process, using yy2bnf.py.

Thanks,

Carl Sorensen
--
Carl Sorensen <[hidden email]>

_______________________________________________
lilypond-devel mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/lilypond-devel

yy2bnf.py (2K) Download Attachment
lilypond.bnf (12K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Lilypond BNF

Nicolas Sceaux
Carl Sorensen <[hidden email]> writes:

> Almost a year ago, Pedro Kroger was working on a bnf description of
> lilypond. (see  http://lists.gnu.org/archive/html/lilypond-
> devel/2004-10/msg00074.html).  Han-Wen suggested hacking Bison so that
> it would produce the BNF directly from the .yy file.
>
> I went a different direction, and produced a python script that ignores
> all the C++ stuff in parser.yy, resulting in a BNF description of
> lilypond that is generated directly from the parser.
>
> I've attached the script (yy2bnf.py), along with the result of running
> the script on the current CVS version of parser.yy (lilypond.bnf).
>
> I'd like to suggest that lilypond.bnf be added to the documentation, to
> be automatically generated as part of the make process, using yy2bnf.py.
>
> Thanks,
>
> Carl Sorensen

It might be a good idea to process the output of `bison -v parser.yy`:
parser.output contains the rules, and lists terminals and non-terminals,
with references to the rules where they appear (and some more
informations).

nicolas


_______________________________________________
lilypond-devel mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Lilypond BNF

Han-Wen Nienhuys
In reply to this post by Carl Sorensen-4
Carl Sorensen wrote:

> Almost a year ago, Pedro Kroger was working on a bnf description of
> lilypond. (see  http://lists.gnu.org/archive/html/lilypond-
> devel/2004-10/msg00074.html).  Han-Wen suggested hacking Bison so that
> it would produce the BNF directly from the .yy file.
>
> I went a different direction, and produced a python script that ignores
> all the C++ stuff in parser.yy, resulting in a BNF description of
> lilypond that is generated directly from the parser.
>
> I've attached the script (yy2bnf.py), along with the result of running
> the script on the current CVS version of parser.yy (lilypond.bnf).
>
> I'd like to suggest that lilypond.bnf be added to the documentation, to
> be automatically generated as part of the make process, using yy2bnf.py.
>

That would be cool,  but just dumping a BNF somewhere is a bit
half-baked. Wouldn't it be better to make a "literate Yacc", where we
intersperse explanations of the grammar (in texinfo format, so it can be
integrated with the program reference manual) with the BNF itself? Also,
a couple of nitpicks

  * BNF usually uses a slightly different syntax

   <nonterminal> ::=  <nt1> <nt2>

I believe. But frankly, I don't care about

  * The current script doesn't strip /* */ comments.


--
  Han-Wen Nienhuys - [hidden email] - http://www.xs4all.nl/~hanwen


_______________________________________________
lilypond-devel mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Lilypond BNF

Carl Sorensen-4
In reply to this post by Nicolas Sceaux
On Tue, 2005-07-26 at 21:30 +0200, Nicolas Sceaux wrote:

>
> It might be a good idea to process the output of `bison -v parser.yy`:
> parser.output contains the rules, and lists terminals and non-terminals,
> with references to the rules where they appear (and some more
> informations).

Thanks for the idea, Nicolas.  parser.output has nicer output (in most
cases) than I produced with my python script.  It does look like a
better place to start.  I'll see what I can do with it.

Thanks,

Carl
--
Carl Sorensen <[hidden email]>



_______________________________________________
lilypond-devel mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Lilypond BNF

Carl Sorensen-4
In reply to this post by Han-Wen Nienhuys

>
> That would be cool,  but just dumping a BNF somewhere is a bit
> half-baked. Wouldn't it be better to make a "literate Yacc", where we
> intersperse explanations of the grammar (in texinfo format, so it can be
> integrated with the program reference manual) with the BNF itself?

Yes, this would be better.  But it would require more development time
for me than I want to put into the project.  I'd like to use my limited
development time to get a FretDiagram context into lilypond.  That's why
I used python to make a hack that was quick and dirty.

Just out of curiousity, what kind of texinfo information would you like
to put in a Yacc/Bison source file by way of grammar explanation?

>  Also,
> a couple of nitpicks
>
>   * BNF usually uses a slightly different syntax
>
>    <nonterminal> ::=  <nt1> <nt2>
>
> I believe. But frankly, I don't care about

I realize that Yacc syntax isn't standard BNF syntax.  I wasn't too
concerned about getting it into standard BNF.  I just wanted to get
something that would allow me to see what goes where in a lilypond input
file.  This means that when I have a question, I can do something other
than just search out an example, and hope that my modifications to it
work.  Perhaps I should have called it a simplified Yacc syntax (or
code-free Yacc syntax) rather than a BNF format.

>
>   * The current script doesn't strip /* */ comments.
>

That was a conscious decision on my part (but maybe not the best
decision).  I'll be happy to change the script to strip the /* */
comments, if you think it's useful for lilypond.  If not, I'll just use
it for my benefit.

Thanks,

Carl
--
Carl Sorensen <[hidden email]>



_______________________________________________
lilypond-devel mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Lilypond BNF

Han-Wen Nienhuys
Carl Sorensen wrote:

>>That would be cool,  but just dumping a BNF somewhere is a bit
>>half-baked. Wouldn't it be better to make a "literate Yacc", where we
>>intersperse explanations of the grammar (in texinfo format, so it can be
>>integrated with the program reference manual) with the BNF itself?
>
>
> Yes, this would be better.  But it would require more development time
> for me than I want to put into the project.  I'd like to use my limited
> development time to get a FretDiagram context into lilypond.  That's why
> I used python to make a hack that was quick and dirty.
>
> Just out of curiousity, what kind of texinfo information would you like
> to put in a Yacc/Bison source file by way of grammar explanation?

some background information. For example, it could be used to give some
examples for

  MUSIC_FUNCTION_SCM


>>  * The current script doesn't strip /* */ comments.
>>
>
>
> That was a conscious decision on my part (but maybe not the best
> decision).  I'll be happy to change the script to strip the /* */
> comments, if you think it's useful for lilypond.  If not, I'll just use
> it for my benefit.
>

I think I misunderstood you. I interpreted your hack as an offer to put
the BNF  into the manual, which is a good idea, but most of the comments
aren't meant as documentation.



--
  Han-Wen Nienhuys - [hidden email] - http://www.xs4all.nl/~hanwen


_______________________________________________
lilypond-devel mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Lilypond BNF

Carl Sorensen-4
On Wed, 2005-07-27 at 02:12 +0200, Han-Wen Nienhuys wrote:
> Carl Sorensen wrote:

>
> >>  * The current script doesn't strip /* */ comments.
> >>
> >
> >
> > That was a conscious decision on my part (but maybe not the best
> > decision).  I'll be happy to change the script to strip the /* */
> > comments, if you think it's useful for lilypond.  If not, I'll just use
> > it for my benefit.
> >
>
> I think I misunderstood you. I interpreted your hack as an offer to put
> the BNF  into the manual, which is a good idea, but most of the comments
> aren't meant as documentation.
>

I did intend the hack to be a way to put BNF in the manual, even if it
is just the stripped-down Yacc syntax.  I can see that the comments
probably don't belong.

I'll hack a bit on Nicolas' idea of using the output file from Bison as
a source for the stripped-down Yacc syntax.  When I'm done, I'll submit
another try.

Thanks,

Carl

--
Carl Sorensen <[hidden email]>



_______________________________________________
lilypond-devel mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Lilypond BNF

Carl Sorensen-4
On Tue, 2005-07-26 at 19:22 -0600, Carl Sorensen wrote:

>
> I'll hack a bit on Nicolas' idea of using the output file from Bison as
> a source for the stripped-down Yacc syntax.  When I'm done, I'll submit
> another try.
>

I've now hacked on a Python script to clean up the output file.  The new
file lilypond.grammar has a cleaned up description of the grammar, and
indexes to both terminals and non-terminals.

This still isn't the intelligent Yacc output, but I think it's slightly
less half-baked than my previous hack, and could profitably be included
in the manual.

Comments?

Carl
--
Carl Sorensen <[hidden email]>

_______________________________________________
lilypond-devel mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/lilypond-devel

lilypond.grammar (27K) Download Attachment
yyout2grammar.py (3K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Lilypond BNF

Juergen Reuter

Hi,

FYI: I just googled for "syntax diagrams" and "generate" and found this
page:

http://www.research.philips.com/technologies/syst_softw/elegant/

They offer a GPL'd tool for automatically generating syntax diagrams (in
PostScript format) for a given (E)BNF.  There is a paper that documents
this tool:
http://www.research.philips.com/technologies/syst_softw/elegant/downloads/Diagrams.pdf

Greetings,
Juergen


_______________________________________________
lilypond-devel mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Lilypond BNF

Carl Sorensen-4
On Wed, 2005-07-27 at 11:56 +0200, Juergen Reuter wrote:

> Hi,
>
> FYI: I just googled for "syntax diagrams" and "generate" and found this
> page:
>
> http://www.research.philips.com/technologies/syst_softw/elegant/
>
> They offer a GPL'd tool for automatically generating syntax diagrams (in
> PostScript format) for a given (E)BNF.  There is a paper that documents
> this tool:
> http://www.research.philips.com/technologies/syst_softw/elegant/downloads/Diagrams.pdf
>
> Greetings,
> Juergen

This is a cool tool!  I apparently didn't find it in my googling because
I was searching for Yacc, or Bison.

As I looked at the Elegant pages, it appears to me that Elegant is not
syntactically compatible with Yacc/Bison.  Therefore, switching to
Elegant would require a complete rewrite of the parser.  This is a
bigger job than I am personally up for.

The benefits of this tool include being able to automatically generate
both "true" BNF and graphical syntax diagrams.  However, I didn't see in
my relatively quick perusal any facility for including comments in the
BNF output.

Thanks,

Carl
--
Carl Sorensen <[hidden email]>



_______________________________________________
lilypond-devel mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Lilypond BNF

Pedro Kröger
In reply to this post by Carl Sorensen-4
Carl Sorensen <[hidden email]> writes:

> Almost a year ago, Pedro Kroger was working on a bnf description of
> lilypond. (see  http://lists.gnu.org/archive/html/lilypond-
> devel/2004-10/msg00074.html).  Han-Wen suggested hacking Bison so that
> it would produce the BNF directly from the .yy file.

I was trying to make an ebnf description, which is more compact and easy
to read, IMHO. Han-Wen's suggestion is good for generating bnf
descriptions, but to generate ebnf would require much more work.

Pedro



_______________________________________________
lilypond-devel mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Lilypond BNF

Carl Sorensen-4
On Wed, 2005-07-27 at 09:35 -0300, Pedro Kr�ger wrote:

> I was trying to make an ebnf description, which is more compact and easy
> to read, IMHO. Han-Wen's suggestion is good for generating bnf
> descriptions, but to generate ebnf would require much more work.

Not understanding the differences between bnf and ebnf, I raced off to
google and found this article:
http://www.garshol.priv.no/download/text/bnf.html#id1.

Aha -- now I see why you want to use ebnf instead of bnf -- you get each
definition down to a single line.  Given the index/cross reference
available in the parser.output file, it may be possible to automatically
generate an ebnf automatically.  I'll put it in the hopper to think
about, but won't promise to do anything about it.

Carl
--
Carl Sorensen <[hidden email]>



_______________________________________________
lilypond-devel mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Lilypond BNF

Nicolas Sceaux
In reply to this post by Carl Sorensen-4
Carl Sorensen <[hidden email]> writes:

> I'll hack a bit on Nicolas' idea of using the output file from Bison as
> a source for the stripped-down Yacc syntax.  When I'm done, I'll submit
> another try.

However, if the idea is to put @comments in parser.yy, it would be
better to process parser.yy directly with its comments, rather than
parser.output.


_______________________________________________
lilypond-devel mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Lilypond BNF

Pedro Kröger
In reply to this post by Carl Sorensen-4

Carl Sorensen <[hidden email]> writes:

> Aha -- now I see why you want to use ebnf instead of bnf -- you get each
> definition down to a single line.

that's right. the article in the link you posted doesn't say, but (I bet
you've figured) you can also use curly braces { and square brackets [
for grouping as in regular expressions.

here are a few more pointers you may want to see:

http://en.wikipedia.org/wiki/Extended_Backus-Naur_form
http://www.augustana.ab.ca/~mohrj/courses/2000.fall/csc370/lecture_notes/ebnf.html

> available in the parser.output file, it may be possible to automatically
> generate an ebnf automatically.

that would be really nice.

Pedro


_______________________________________________
lilypond-devel mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/lilypond-devel
Reply | Threaded
Open this post in threaded view
|

Re: Lilypond BNF

Carl Sorensen-4
In reply to this post by Nicolas Sceaux
On Wed, 2005-07-27 at 19:28 +0200, Nicolas Sceaux wrote:
> Carl Sorensen <[hidden email]> writes:
>
> > I'll hack a bit on Nicolas' idea of using the output file from Bison as
> > a source for the stripped-down Yacc syntax.  When I'm done, I'll submit
> > another try.
>
> However, if the idea is to put @comments in parser.yy, it would be
> better to process parser.yy directly with its comments, rather than
> parser.output.

I agree, but Yacc/Bison as written don't have a direct facility for
handling @comments.  They could be included in a /* */ comment block,
but that seems like more deviation than it's worth.

It seems to me that unless/until Yacc/Bison gets expanded to allow for
@comments, I get the best results from parsing parser.output.

Carl

--
Carl Sorensen <[hidden email]>



_______________________________________________
lilypond-devel mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/lilypond-devel