Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2154 > unrolled thread

Best language for implementing compilers?

Back to article view | Back to comp.compilers

Contents

  Best language for implementing compilers? "Costello, Roger L." <costello@mitre.org> - 2019-02-08 12:20 +0000
    Re: Best language for implementing compilers? Nala Ginrut <nalaginrut@gmail.com> - 2019-02-09 00:27 +0800
    Re: Best language for implementing compilers? George Neuner <gneuner2@comcast.net> - 2019-02-08 18:36 -0500
      Re: Best language for implementing compilers? Bart <bc@freeuk.com> - 2019-02-11 12:59 +0000
        Re: Best language for implementing compilers? drb@ihatespam.msu.edu (Dennis Boone) - 2019-02-12 09:38 -0600
          Re: Best language for implementing compilers? drb@ihatespam.msu.edu (Dennis Boone) - 2019-02-19 11:22 -0500
            Re: Best language for implementing compilers? arnold@skeeve.com (Aharon Robbins) - 2019-02-20 11:48 +0000
        Re: Best language for implementing compilers? Kaz Kylheku <157-073-9834@kylheku.com> - 2019-02-12 16:45 +0000
        Re: Best language for implementing compilers? mertesthomas@gmail.com - 2019-03-09 01:47 -0500
          Re: Best language for implementing compilers? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-03-09 10:14 +0100
            Re: Best language for implementing compilers? George Neuner <gneuner2@comcast.net> - 2019-03-09 22:47 -0500
            Re: Best language for implementing compilers? Kaz Kylheku <157-073-9834@kylheku.com> - 2019-03-10 05:40 +0000
          Re: Best language for implementing compilers? Bart <bc@freeuk.com> - 2019-03-09 12:34 +0000
          Re: Best language for implementing compilers? George Neuner <gneuner2@comcast.net> - 2019-03-09 22:57 -0500
            Re: Best language for implementing compilers? Kaz Kylheku <157-073-9834@kylheku.com> - 2019-03-10 05:48 +0000
        Re: Best language for implementing compilers? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2019-03-10 04:13 -0700
          Re: Best language for implementing compilers? Bart <bc@freeuk.com> - 2019-03-10 15:33 +0000
            Re: Best language for implementing compilers? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2019-03-11 10:49 -0700
              Re: Best language for implementing compilers? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-03-12 06:54 +0100
                Re: Best language for implementing compilers? Bart <bc@freeuk.com> - 2019-03-13 01:50 +0000
          Re: Best language for implementing compilers? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-03-10 16:13 +0100
            Re: Best language for implementing compilers? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2019-03-11 10:06 -0700
          Re: Best language for implementing compilers? George Neuner <gneuner2@comcast.net> - 2019-03-10 18:23 -0400
          Re: Best language for implementing compilers? George Neuner <gneuner2@comcast.net> - 2019-03-10 18:58 -0400
    Re: Best language for implementing compilers? "Robin Vowels" <robin51@dodo.com.au> - 2019-02-09 19:58 +1100
    Best language for implementing compilers? David Lovemore <davidlovemore@gmail.com> - 2019-02-12 03:28 -0800
    Re: Best language for implementing compilers? mertesthomas@gmail.com - 2019-03-12 10:40 -0700

Page 2 of 2 — ← Prev page 1 [2]

#2177

Am 10.03.2019 um 12:13 schrieb Christopher F Clark:

> All that said, the output of any decent
> C/C++ lexer and parser generator is often more than fast enough.  That's
> despite lexing and parsing often taking upto a third of the compilation time.
> BTW, lexing (because it looks at every character) is the dominant factor in
> that.

If so, then lexing were the dominant factor for *all* parsers with a
lexer, not only for C/C++.

My experience and the existence of specific workarounds identify two C
specific properties as most time consuming, the preprocessor and the
lack of a multi-module (project) compilation. None of these is related
to a *lexer in the strict sense* (tokenizer), because it all happens in
between the tokenizer and parser.

DoDi

[toc] | [prev] | [next] | [standalone]

#2180

On Sunday, March 10, 2019 at 9:08:12 PM UTC-4, Hans-Peter Diettrich wrote:
> Am 10.03.2019 um 12:13 schrieb Christopher F Clark:
>
> > All that said, the output of any decent
> > C/C++ lexer and parser generator is often more than fast enough.  That's
> > despite lexing and parsing often taking upto a third of the compilation
time.
> > BTW, lexing (because it looks at every character) is the dominant factor
in
> > that.
>
> If so, then lexing were the dominant factor for *all* parsers with a
> lexer, not only for C/C++.
>
> My experience and the existence of specific workarounds identify two C
> specific properties as most time consuming, the preprocessor and the
> lack of a multi-module (project) compilation. None of these is related
> to a *lexer in the strict sense* (tokenizer), because it all happens in
> between the tokenizer and parser.
>
> DoDi

Sorry for the confusion.  By C/C++ lexer and parser, I meant one written in
those languages, not compiling those languages.  To be more precise, I mean
ones where a program has generated the parsing and lexing tables and the code
that interprets those tables is in C/C++.  You can get pretty close to the
optimal code sequence using C code.  I suspect with jit'ed Java code or
similar you can probably get similar performance and code sequences.

Moreover, I was talking raw lexing and parsing speed of reading source code.
If you don't "read" the source code at all, e.g. precompiled headers, you can
go much faster.  However, in that case, you probably have to "read" but not
lex or parse the predigested code from a file.

Your point about the C preprocessor is also valid. Depending upon the
implementation, you might have to lex the code twice.  Once to get
preprocessor tokens and again to get the kind of tokens the parser consumes.
Of course, a clever design can probably find ways to use mostly the same
tokens for both purposes and skip the 2nd tokenizing except when features like
token pasting are used.  On the other hand, a naive implementation might
actually write out the pre-processed file and re-read it.  As you can imagine
the performance difference between the two implementations will likely be
noticable.
[I've seen systems that cache tokenized header files which should help.  It's a
little tricky due to token pasting, but it's not that hard. -John]

[toc] | [prev] | [next] | [standalone]

#2178

On Sun, 10 Mar 2019 04:13:47 -0700 (PDT), Christopher F Clark
<christopher.f.clark@compiler-resources.com> wrote:

>[tree matching] is so good (i.e. easy to use and understand) that Terence Parr
>built a whole tool (Sorcerer) to do just that to go along with his tool PCCTS
>(aka ANTLR) so that you could do it in Java.  I believe in modern versions, he
>has merged both into one tool.

ANTLR did subsume the Sorceror tree parsing tool that was provided
separately with PCCTS.  ANTLR also included lexer generation which
also was a separate tool in PCCTS, (and originally was not included in
the toolkit).

So ANTLR can generate lexers, LL parsers, and tree parsers all using
the same tool - and it can generate code in multiple target languages:
only the ANTLR tool itself requires Java.  PCCTS only targeted C.


But ANTLR is quite different from PCCTS - their grammars are not
compatible, so it can't be said that ANTLR is just a "newer" version.
In addition, PCCTS is LL(k) and the programmer must specify required
lookahead - the tool will fail to generate a parser (or the parser it
generates won't work) if the specified lookahead is insufficient.

ANTLR uses Parr's newer LL(*) algorithm which - in the absense of an
explicit LL(k) specification - tries to  automatically determine the
lookahead required.  This generally works as advertised, but there are
cases where the analysis can take exponential time and/or memory, and
in some cases the generated parser is slower than when lookahead is
specified.
[Creating a good grammar still is an art form 8-)]

George

[toc] | [prev] | [next] | [standalone]

#2179

Very nice post!

On Sun, 10 Mar 2019 04:13:47 -0700 (PDT), Christopher F Clark
<christopher.f.clark@compiler-resources.com> wrote:

>Unless you have written a one-pass compiler, the output of your lexer/parser
>combination is usually some form of syntax tree (either a parse tree or an
>AST).  That may or may not be a convenient intermediate representation (IR).
>If it's not you need to "rewrite" it into one.  Usually making one of more
>passes over the tree to do so.
>
>This is where ML style pattern matching shines.  You have a tree (DAG, graph,
>some sort of data structure that has links in it) and you want to modify it.
>The ML pattern match allows you to specify the shape of the tree you want to
>match and extract the relevant parts into convenient local variables.  You can
>then use those variables to construct a new tree that has the parts
>reconnected (rewritten) into the shape you desire in your IR.

It also can be useful to use tree matching for code generation: the
basic idea being to map the IR onto the instructions of the target
machine (where a target "instruction" might be a sequence of native
instructions).

You create tree patterns that correspond to target "instructions",
treat those patterns as tiles and try to cover the IR tree using a
minimum "weight" of tiles [where the tile "weight" could be cycles
consumed, registers needed, energy used, etc. ... whatever is useful
for the given task].

This works with any ISA, but it is particularly useful for CISC
machines that often provide more than one way to perform the same
operation.  The minimum weight tiling will correspond to an optimal
program [for some definition of "optimal"].

George

[toc] | [prev] | [next] | [standalone]

#2157

From: "Costello, Roger L." <costello@mitre.org>
Sent: Friday, February 08, 2019 11:20 PM

> The book was written in the 90's. Are there new languages that are even better
> than ML as a compiler implementation language?

PL/I is a very good language; being general purpose, it has
everything you'd need.

Another langage is XPL, which was specially designed for
writing compilers.  It has special features for string-handling
that make it fast for parsing text. (There's a text, "A compiler
Generator" by McKeeman et al, with the tools to implement
a language translator).

[I wouldn't use PL/I for writing a compiler.  Its pointer handling and
strings are by modern standards pretty klunky.  XPL is pretty cool for
a language designed over 50 years ago (really) but its main
improvement over PL/I, other than taking out most of the complication
not useful for system programming, was variable length strings in a
garbage collected heap.  These days everything from java to python
to C++ does that for you. -John]

[toc] | [prev] | [next] | [standalone]

#2159

One of the things that makes ML good is that it is pretty hard to make
an error that get past the type checker.

It is not only the matching, which allows easy testing and unpacking
of compound data types, but its insistance that every case is checked
that is useful.

Also functional purity has many advantages.

To answer your question though, Haskell is a language you should be looking at.

[toc] | [prev] | [next] | [standalone]

#2183

Am Freitag, 8. Februar 2019 16:55:48 UTC+1 schrieb Costello, Roger L.:
> Best language for implementing compilers?

There are language features, which make programming easier.
This is independent of the type of program.

Compilers are big programs. Compilation speed and/or run-time
performance of the generated program can be a goal. But also the
effort (time) to write a compiler must be taken into account.  The
cost to maintain a compiler is also an important factor.  Therefore
the decision for a compiler language is not so easy.

I have written scanners and parsers in C, C++, Java and Seed7.  I have
used C for the scanner and parser of the Seed7 interpreter.  I have
also written scanner, parser and preprocessor for C in Seed7.  The
code generator of the Seed7 compiler is written in Seed7.  My Basic
interpreter, which tokenizes Basic lines, is written is Seed7.

So I have some experience in writing compiler parts in higher (Seed7)
and lower (C) level languages.

Higher level features like memory management help a lot. E.g.: The
Seed7 compiler generates C code. All this C code snippets are held in
strings. The are concatenated and assigned several times, before they
are written out. Doing this in C with manual memory management would
have been a hard task.

So if you want to create a compiler in a reasonable time I suggest you
prefer a higher level language.

If compilation speed is the criteria number one you will probably need
to use C (to squeze every cycle out of the machine). This is what I
did, when implementing the front end of the Seed7 interpreter.

I designed some language features of Seed7, to support scanning and
parsing. E.g.: Every file in Seed7 has a bufferChar. A bufferChar is
just a single character attached to the file.  If you use LL(1)
parsing for tokens you read a character and assign it to the
bufferChar. Then, depending on the bufferChar, you decide what to do
next. If the bufferChar is a digit you will read a number. If the
bufferChar is a letter you will read an identifier. Etc. Examples of
such scanner functions can be found in the library scanfile.s7i.

Regards,
Thomas Mertes

--
Seed7 Homepage:  http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.compilers

csiph-web