OT: C++ from bison/flex. - c++

"DaLoverhino" <DaLoveRhino@hotmail.com> wrote in message
news:1191279366.477114.271060@n39g2000hsh.googlegroups.com...
> Hello. I have to read about flex and bison for my co's next project.
>
> But it got me wondering: Were/are c++ compilers written using flex/
> bison? Or do you need another tool?
>
>
>
> Searching for LALR and C++, it looks like it could be possible but not
> practical. Is this true? If so, then what tools do compiler writers
> use or do they write their own. (Yikes!)

Try comp.compilers news group.

Aaron

On Mon, 01 Oct 2007 15:56:06 -0700, Noone wrote:

> Hello. I have to read about flex and bison for my co's next project.
>
> But it got me wondering: Were/are c++ compilers written using flex/
> bison? Or do you need another tool?
>
>
>
> Searching for LALR and C++, it looks like it could be possible but not
> practical. Is this true? If so, then what tools do compiler writers
> use or do they write their own. (Yikes!)


Someone writing a compiler is going to need to do lexical ****ysis and
create a parse tree for a given grammar. Therefore, lex and yacc, or flex
and bison can certainly be used.

I don't know why it would be "impractical" to use those tools for
implementing the C++ language. Remember though, those are only the first
two steps in the process. For a good compiler you still have a lot of
additional steps such as intermediate code generation, optimization, etc.

On Oct 3, 4:34 am, Me <no...@all.com> wrote:
> On Mon, 01 Oct 2007 15:56:06 -0700, Noone wrote:
> > Hello. I have to read about flex and bison for my co's next project.

> > But it got me wondering: Were/are c++ compilers written using flex/
> > bison? Or do you need another tool?

> > Searching for LALR and C++, it looks like it could be possible but not
> > practical. Is this true? If so, then what tools do compiler writers
> > use or do they write their own. (Yikes!)

> Someone writing a compiler is going to need to do lexical ****ysis and
> create a parse tree for a given grammar. Therefore, lex and yacc, or flex
> and bison can certainly be used.

> I don't know why it would be "impractical" to use those tools for
> implementing the C++ language. Remember though, those are only the first
> two steps in the process. For a good compiler you still have a lot of
> additional steps such as intermediate code generation, optimization, etc.

Yacc generates an LRLA(1) grammar; LRLA(1) grammars can only
handle certain sub-classes of context free grammars. C++ isn't
even context free much less LRLA(1); to make it acceptable to
yacc requires a lot of hacking. Flex has an extension which
allows handling ambiguous productions in parallel, only reducing
once the ambiguity has been raised. I don't know if this is
enough to allow it to handle C++, however---I've never tried.

The few C++ compilers where I know what is used use recursive
descent. Theoretically, recursive descent can handle an even
more restricted set of grammars, but in practice, it's a lot
easier to hack, and lends itself to backtracking when necessary.

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

In article <1191279366.477114.271060@n39g2000hsh.googlegroups.com>,
DaLoveRhino@hotmail.com says...
> Hello. I have to read about flex and bison for my co's next project.
>
> But it got me wondering: Were/are c++ compilers written using flex/
> bison? Or do you need another tool?

The grammar for C++ doesn't fit Bison's requirements, so writing a C++
parser with Bison requires lots of ugliness. Both cfront and older
versions of gcc were apparently written that way, but cfront is
discontiued and I believe gcc now uses a hand-written parser.

There are other parser generators that could/would probably do a better
job of coping with C++'s grammar, but I'm not sure whether anybody's
actually implemented a C++ compiler using one of them.

--
Later,
Jerry.

The universe is a figment of its own imagination.

On Oct 3, 9:28 am, Jerry Coffin <jcof...@taeus.com> wrote:
> In article <1191279366.477114.271...@n39g2000hsh.googlegroups.com>,
> DaLoveRh...@hotmail.com says...
>
> > Hello. I have to read about flex and bison for my co's next project.
>
> > But it got me wondering: Were/are c++ compilers written using flex/
> > bison? Or do you need another tool?
>
> The grammar for C++ doesn't fit Bison's requirements, so writing a C++
> parser with Bison requires lots of ugliness. Both cfront and older
> versions of gcc were apparently written that way, but cfront is
> discontiued and I believe gcc now uses a hand-written parser.
>
> There are other parser generators that could/would probably do a better
> job of coping with C++'s grammar, but I'm not sure whether anybody's
> actually implemented a C++ compiler using one of them.
>

Antlr can handle LL(k) grammers, and there is a C++ one available for
download (though I don't know its quality): http://www.antlr.org/grammar/list

REH

On Wed, 03 Oct 2007 03:30:36 -0700, Noone wrote:


> The few C++ compilers where I know what is used use recursive descent.
> Theoretically, recursive descent can handle an even more restricted set
> of grammars, but in practice, it's a lot easier to hack, and lends
> itself to backtracking when necessary.


Are you talking about hand coding a recursive descent parser or using a
parser generator that creates recursive descent parse trees? About 20
years ago (college) I wrote some recursive descent code for small grammars
to do statistical evaluation but could not fathom hand coding one for a
full scale language with a non-trival grammar. I believed an LALR type
parser generator was the de-facto standard for implementing non-trivial
projects.

And yes, it would seem that recursive descent would be easier to hack but
setting the thing up in the first place seems like a nightmare.

Anyway, tis OT but still fascinating stuff.

On Oct 4, 2:13 am, Me <no...@all.com> wrote:
> On Wed, 03 Oct 2007 03:30:36 -0700, Noone wrote:
> > The few C++ compilers where I know what is used use recursive descent.
> > Theoretically, recursive descent can handle an even more restricted set
> > of grammars, but in practice, it's a lot easier to hack, and lends
> > itself to backtracking when necessary.

> Are you talking about hand coding a recursive descent parser
> or using a parser generator that creates recursive descent
> parse trees?

The one I know most about (Sun CC) is hand coded. I think g++
is too. If you're going to use a parser generator, you might as
well use one which uses LR, rather that LL, since it will be
able to handle a larger set of grammars. The advantage of a
hand coded recursive descent parser is that it is easier to
"fudge" cases where the language doesn't fit the grammar.
(Also, typically, you get much better error messages and error
recovery. Colloquially expressed: with an LL parser, such as
recursive descent, you know what you're looking for, which helps
greatly in formulating error messages and in resynchronizing;
with an LR parser, you know what you got, but in the case of an
error, all you really know is that you cannot do anything with
it.)

> About 20
> years ago (college) I wrote some recursive descent code for small grammars
> to do statistical evaluation but could not fathom hand coding one for a
> full scale language with a non-trival grammar. I believed an LALR type
> parser generator was the de-facto standard for implementing non-trivial
> projects.

I think that the general consensus is that LALR parsers are OK
for medium sized projects---they're overkill for very small
things, and the grammar soon becomes too wieldy, especially if
you start adding error productions, for very large languages.
Recursive descent has the advantage that it modularizes very
well.

And of course, almost no real languages can be described
directly by an LR grammar. Even something as simple as Pascal
requires a few simple hacks, and C++ is almost hopeless---the
recursive descent implementations I've heard of use backtracking
(which isn't formally allowed:-)).

> And yes, it would seem that recursive descent would be easier
> to hack but setting the thing up in the first place seems like
> a nightmare.

Not really. It can be done in a very modular fashion, with each
function being fairly simple. And of course, anything that can
handle standard C++ isn't going to be simple; you need the
modularity to manage it.

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

On Oct 3, 3:28 pm, Jerry Coffin <jcof...@taeus.com> wrote:
> In article <1191279366.477114.271...@n39g2000hsh.googlegroups.com>,
> DaLoveRh...@hotmail.com says...

> > Hello. I have to read about flex and bison for my co's next project.

> > But it got me wondering: Were/are c++ compilers written using flex/
> > bison? Or do you need another tool?

> The grammar for C++ doesn't fit Bison's requirements, so writing a C++
> parser with Bison requires lots of ugliness. Both cfront and older
> versions of gcc were apparently written that way, but cfront is
> discontiued and I believe gcc now uses a hand-written parser.

Is this still true, now that Bison supports GLR parsing
(basically, parsing several alternatives in parallel until you
know which one to use)? CFront, of course, didn't use Bison,
but yacc, which still doesn't have this possibility, and I don't
know when Bison added it (but I'm pretty sure it wasn't present
in the early 1990's).

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

In article <1191488326.506780.177890@d55g2000hsg.googlegroups.com>,
james.kanze@gmail.com says...

[ ... ]

> > The grammar for C++ doesn't fit Bison's requirements, so writing a C++
> > parser with Bison requires lots of ugliness. Both cfront and older
> > versions of gcc were apparently written that way, but cfront is
> > discontiued and I believe gcc now uses a hand-written parser.
>
> Is this still true, now that Bison supports GLR parsing
> (basically, parsing several alternatives in parallel until you
> know which one to use)?

I'm honestly not certain, but it's _probably_ not true of versions of
Bison sufficiently recent to support GLR parsing.

> CFront, of course, didn't use Bison,
> but yacc, which still doesn't have this possibility, and I don't
> know when Bison added it (but I'm pretty sure it wasn't present
> in the early 1990's).

Yes -- current versions of Bison would fit much more closely in the
group that may well support C++ parsing more cleanly, but TTBOMK hasn't
actually been used to write a C++ compiler.

--
Later,
Jerry.

The universe is a figment of its own imagination.