State of the Art

Hi all,

I havn't worked in compiler construction and programming languages for
some years, but now I have a chance to return to this area. I would
like to find out what happened while I was absent.

So, let me ask the following questions:
- In your opinion, what are the greatest advances in compiler
construction in the last ten years?
- What are the most important current trends?

I know, these a pretty general question, but I believe the answers are
not only of interest for me.

Thanks in advance, Peter

From my limited experience I'd say that one advancement is the LL(*)
algorithm which allows arbitrary scan ahead of tokens (compared to
e.g. LL(5) which allows only to check the next 5). It is implemented
in ANTLR 3.x and available on www.antlr.org . There is also a book
from the author which does not only explain the use of ANTLR but also
the algorithm in deeper detail.

Best regards,
Johannes

Johannes schrieb:

> From my limited experience I'd say that one advancement is the LL(*)
> algorithm which allows arbitrary scan ahead of tokens (compared to
> e.g. LL(5) which allows only to check the next 5).

I'd prefer PEG, which also establishes a defined order for ambiguous cases.

DoDi

On 21 Jul., 08:31, Hans-Peter Diettrich <DrDiettri...@aol.com> wrote:
> Johannes schrieb:
>
> > From my limited experience I'd say that one advancement is the LL(*)
> > algorithm which allows arbitrary scan ahead of tokens (compared to
> > e.g. LL(5) which allows only to check the next 5).
>
> I'd prefer PEG, which also establishes a defined order for ambiguous cases.
>
> DoDi

Hi all,

thanks for the answers so far. To keep track, here's a nice list of
compiler generator tools: http://en.wikipedia.org/wiki/Compari...ser_generators.

PEG is classified as a "recursive decent" parser generator. A quick
scan of the reference http://pdos.csail.mit.edu/~baford/packrat/popl04/
has given me the info that this type of parsers is capable of
accepting non-contextfree languages.

Cheers, Peter

> > I'd prefer PEG, which also establishes a defined order for
> ambiguous cases.
> >
> > DoDi
>
> Hi all,
>
> thanks for the answers so far. To keep track, here's a nice list of
> compiler generator tools:
> http://en.wikipedia.org/wiki/Compari...ser_generators.
>
> PEG is classified as a "recursive decent" parser generator. A quick
> scan of the reference http://pdos.csail.mit.edu/~baford/packrat/popl04/
> has given me the info that this type of parsers is capable of
> accepting non-contextfree languages.


Peter's original question was:

> - In your opinion, what are the greatest advances in compiler
> construction in the last ten years?

First - the disclaimer: I'm a parser generator author who has developed a
proprietary parsing algorithm, so my opinion may be biased.

Any parser generator notation that allows for the intersection of lexemes
can recognize a subset of Type 1 languages. PEGs also recognize a subset of
Type 1 languages without intersection (predicates). (q.v.
http://compilers.iecc.com/comparch/article/05-09-108). IMO, the major
contribution of PEGs is not the context-sensitive possibilities it allows
for, but the re-introduction of memoization into parsing algorithms and the
subsequent avoidance of backtracking and its consequences on complexity. I
say this after some consideration, but my reasoning won't fit** in the
margin here.

For other interesting work, you might look into Okhotin's
Boolean/Conjunctive grammars. They also allow for context sensitivity,
and IMO, in a more orderly fashion than PEGs. Okhotin is a meticulous
mathematician before all else, and the practical results he has
obtained are quite thoroughly examined in terms of the theory behind
them.

My personal favorite ... adaptive grammars and parsers. This
particular area has come a long way in the last 10 years.

Relevant links in that area:

http://en.wikipedia.org/wiki/Adaptive_grammar
http://www.pcs.usp.br/~lta/union/index.php?cp=4

Using adaptive techniques, I've yet to come up against a
context-sensitive language that isn't in practice recognizable in less
than O(n^3) time, with some very interesting results (such as
pseudoknots) being linear.

In terms of compiler construction practice, in my opinion, the most
important trend has been the move toward virtual machine
backends. This started with Java and has been going strong with the
CLR of the .NET family of languages. As it stands, my cell phone is
powered by Java ... in 5 years, my toaster may be powered by C#. I see
this trend as being important because certain practice in compiler
construction will have more impact than previously. For instance, new
optimization techniques will benefit a wider range of applications.

Others' mileage will likely vary.

Cheers,

--
Quinn Tyler Jackson

** But two for instances: I believe Ford's PEGs led to the introduction of
memoization into ANTLR, and since ANTLR is used in a non-laboratory sense,
the impact there is on actual practice. It also led to the introduction of
memoization into the Meta-S parsing engine.

Hi all,

The replies almost exclusively go about parser algorithms. But many
people still use old good yacc-based, or manually written recursive
descent parsers. Perhaps this is because they do the job as well.

On the other hand everyone (at least this is my layman impression)
seems to use such things as SSA-based redundancy elimination, graph
coloring register allocation. But these algorithms are not new.

Is there anything relatively new (say not described by Muchnik) that
became or going to become widely used? Something that clearly wins
over older algorithms.

Regards,
Aleksey

Hans-Peter Diettrich <DrDiettrich1@aol.com> writes:

> Johannes schrieb:
>
>> From my limited experience I'd say that one advancement is the LL(*)
>> algorithm which allows arbitrary scan ahead of tokens (compared to
>> e.g. LL(5) which allows only to check the next 5).
>
> I'd prefer PEG, which also establishes a defined order for ambiguous cases.

The most recent versions for ANTLR can use the PEG ordering for
ambiguous cases if I read the documentation correctly. This should
give the best of both worlds, warnings when you have an ambiguous (or
atleast a non-LL) grammar, and well-defined PEG rules for resolving
those ambiguities, so that you can still write grammars for those
cases.

In either case, the PEG work builds on Terence's LL(k) and predicated
grammar work, so those have to be considered fundamental to it. One
can argue that there would be no PEG grammars if we hadn't had
predicated LL(k) grammars first.

Just my opinions,
-Chris

************************************************** ****************************
Chris Clark Internet: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. or: compres@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)

Peter <peter.deussen@fokus.fraunhofer.de> writes:

> I havn't worked in compiler construction and programming languages for
> some years, but now I have a chance to return to this area. I would
> like to find out what happened while I was absent.
>
> So, let me ask the following questions:
> - In your opinion, what are the greatest advances in compiler
> construction in the last ten years?

I think the greatest advance has been exploiting the higher speed and
more memory of modern computers. This means that you can use
parser-generator tools and keep the whole syntax tree in memory and do
multiple passes over it without having to write out to a file after
each pass. This makes writing a comiler a lot easier.

JIT compilation has also had great advances in the last decade.

Otherwise, I think the advances are more in programming languages than
in compilers.

> - What are the most important current trends?

I would say the most important current trend is compiling for
multi-core CPUs (such as Cell).

Torben

"Peter" <peter.deussen@fokus.fraunhofer.de> wrote in message
> I havn't worked in compiler construction and programming languages for
> some years, but now I have a chance to return to this area. I would
> like to find out what happened while I was absent.
>
> So, let me ask the following questions:
> - In your opinion, what are the greatest advances in compiler
> construction in the last ten years?

Yes there's been quite alot in terms of grammar recognition, Tomita's
GLR, and a number of extensions and speedups of the originally tainted
algorithm. Then PEG and PackRat parsing which are more natural to use
than LR grammars.

Then for backends there's LLVM :-

http://llvm.org

And Microsoft Research'es Pheonix :-

http://research.microsoft.com/phoenix/?0sr=a

There's a weath of papers on CiteSeer that are worth looking at too :-

http://citeseer.ist.psu.edu/

Good luck and have fun,

Aaron

torbenm@pc-003.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen) wrote:
>
>JIT compilation has also had great advances in the last decade.

Tracing JITs are particularly interesting, since by construction they
only compile host code and do cross-method optimizations like polymorphic
inlining. And they have much less overhead than method-at-a-time JITs
based on batch compiler techniques.

Tony.
--
f.anthony.n.finch <dot@dotat.at> http://dotat.at/
BISCAY: SOUTHWESTERLY 3 OR 4, OCCASIONALLY 5 AT FIRST. MODERATE. THUNDERY
SHOWERS. MODERATE OR GOOD, OCCASIONALLY POOR.