Re: bnf to bison grammar

[Hans Aberg]

At 08:24 -0500 2002/02/16, babar haq wrote:
>never knew its so easy to get help from a mailing list:)

As long as you don't want others to do your work. :-)

>my only problem is to convert this kind of bnf to bison
>proto-version = "v=" 1*DIGIT CRLF
>The operator "*" preceding an element indicates repetition. The full form is:
>
>        <a>*<b>element
>
>where <a> and <b> are optional decimal values, indicating at least <a> and
>at most <b> occurrences of element.

The stuff you have probably refers to how to tokenize the stuff, in which
case Flex will have that built in. For example, a rule for "digits" might
in a Flex .l file look like
%%
"1"[[:digit:]]*  { return number_starting_with_one; }
...

And in a Bison .y file
%token number_starting_with_one
%token vee_equal "v="
%%
proto-version: "v=" number_starting_with_one crlf { action }

crlf: ...


But it is also possible to expand these these EBNF extensions by rewriting
them into BNF. For example:
  x ::= a [b] c. <=>  x ::= ac | abc.
  x ::= a b+ c.  <=>  x ::= ayc. y ::= b | yb.
  x ::= a b* c.  <=>  x ::= ayc. y ::= 0 | yb.
where y is a new, independent nonterminal (grammar variable), and 0 is the
empty production (often written as epsilon in texts, represented by empty
space in the Bison grammar).

I think that the Berkeley Yacc may have them implemented, if you do not
want to write them out by hand.

But if you try to put the tokenization into the Bison generated parser,
that will probably be slow.

  Hans Aberg