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 1 of 2  [1] 2  Next page →

#2154 — Best language for implementing compilers?

Hello Compiler Experts!

The book [1] that I started reading says this:

	ML is well suited to many applications,
	but compiler implementation in particular
	seems to hit all of its strong points and
	few of its weaknesses. Implementing a
	compiler in ML is quite a pleasant task.

What is it about ML that makes it such a good language for implementing
compilers?

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

/Roger

[1] "Modern Compiler Implementation in ML" by Andrew W. Appel
(https://www.cs.princeton.edu/~appel/modern/basic/ml/extract.pdf)

[toc] | [next] | [standalone]

#2155

The book you are referring to is "the Tiger book" which has 3 version:
Java, C and ML.
I have C version and I love it. However ML has many features to save
your time on implementing data structures.
In addition, the modern Scheme which contains pattern matching and
record-type is as good as ML in my opinion.

Best regards.

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

#2156

On Fri, 8 Feb 2019 12:20:18 +0000, "Costello, Roger L."
<costello@mitre.org> wrote:

>What is it about ML that makes it such a good language for implementing
>compilers?

Compiling involves a lot of pattern matching, and pattern matching is
a native feature of ML.

I can recall papers from that same era advocating writing compilers in
Prolog, or similar declarative languages, in which essentially all
programming is done with pattern matching.


Lisp and Lisp-like languages - Scheme, Racket, etc. - are also nice to
work with for compiler writing. These languages don't natively include
pattern matching, but they are extensible [using metaprogramming] and
there are good pattern match libaries available for most popular
implementations.

Racket, in particular, is a "batteries included" Scheme derivative
that includes ML-like pattern matching in its basic distribution.


George

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

#2158

On 08/02/2019 23:36, George Neuner wrote:
> On Fri, 8 Feb 2019 12:20:18 +0000, "Costello, Roger L."
> <costello@mitre.org> wrote:
>
>> What is it about ML that makes it such a good language for implementing
>> compilers?
>
> Compiling involves a lot of pattern matching, and pattern matching is
> a native feature of ML.

You mean for tokenising and parsing? That would be a small part of
compilation (the easy bit, in my view), although it seems to be a
preoccupation of this group.

But don't people (not me) tend to use external tools for that?

I would say that no special language features at all are required for
writing a compiler, even if parsing is directly coded in the language.

In fact it is one of the least demanding kinds of programs as usually it
will take one or more files as input, and write one or more files as output.

It doesn't even need flexible strings, as suggested in another post, as
most strings once encountered will be a fixed size. (Although
first-class string handling is useful if generating another source code
as output.)

--
bart
[If a language doesn't have some sort of data structures, pointers, and
dynamic memory allocation, writing a compiler in it will be painful. -John]

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

#2160

 > I would say that no special language features at all are required for
 > writing a compiler, even if parsing is directly coded in the language.

People wrote compilers in Fortran '66, so that's clearly true.
On the other hand, how easy were they to understand, maintain, extend?

De
[If you're thinking of Fortran H, it used some private extensions
that provided pointers and structures.  I thought I saw the source
code online somewhere but can't find it now. -John]

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

#2164

 > [If you're thinking of Fortran H, it used some private extensions
 > that provided pointers and structures.  I thought I saw the source
 > code online somewhere but can't find it now. -John]

No, I was thinking of things like Intel's PL/M compiler and the
Software Tools ratfor stuff.

De
[As I recall, Ratfor was bootstrapped using primitive versions of
itself.  That used to be pretty common. -John]

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

#2166

In article <19-02-012@comp.compilers>,
Our esteemed moderator wrote:
>[As I recall, Ratfor was bootstrapped using primitive versions of
>itself.  That used to be pretty common. -John]

The first ratfor was done in C using yacc and maybe lex. I suspect
that that was then used to write the ratfor-in-ratfor presented in
"Software Tools".
--
Aharon (Arnold) Robbins 		arnold AT skeeve DOT com

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

#2161

On 2019-02-11, Bart <bc@freeuk.com> wrote:
> On 08/02/2019 23:36, George Neuner wrote:
>> On Fri, 8 Feb 2019 12:20:18 +0000, "Costello, Roger L."
>> <costello@mitre.org> wrote:
>>
>>> What is it about ML that makes it such a good language for implementing
>>> compilers?
>>
>> Compiling involves a lot of pattern matching, and pattern matching is
>> a native feature of ML.
>
> You mean for tokenising and parsing? That would be a small part of
> compilation (the easy bit, in my view), although it seems to be a
> preoccupation of this group.

I think George is talking about structural pattern matching:
expressing the handling of cases of various shapes of data using
a notation which resembles those shapes.

Opportunities for pattern-matching occur pretty much in any compiler
pass: various tree-to-tree transformations use pattern matching.
Target code generation, peephole optimizations and such can use it.

E.g. suppose we want to check whether we have an expression that is
the binary product of two binary sums, as in (* (+ a b) (+ c d)).

Without pattern matching:

 (when (and (eq (car expr) '*)  ;; starts with *
            (consp (cdr expr))  ;; has an argument
            (consp (cddr expr)) ;; has another argument
            (null (cdddr expr)) ;; then the list ends
            (consp (cadr expr)) ;; first arg is a compound
            (eq (cadr expr) '+) ;; ... starting with a +
            ... ;; etc
   (do-whatever ...))

With very rudimentary pattern matching (simple destructuring):

 (destructuring-when (op1 (op2 a b) (op3 c d)) expr
   (when (equal (list op1 op2 op3) '(* + +))
     (do-whatever ...)))

With pattern matching:

 (when-match expr (* (+ ?a ?b) (+ ?c ?d))
   (do-whatever ...) ;; ?a ?b ... are in scope bound to subtrees
   ...)

Pattern matching can typically handle objects other than just lists.
Vectors, data structures, tuples, dictionaries ...

Some pattern matchers have support for arbitrary Boolean predicates,
like matching only when the third element of the list in foo.bar is an
even integer.

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

#2168

On 2019-02-12 15:43:46 UTC+1 Bart wrote:
> On 08/02/2019 23:36, George Neuner wrote:
> > On Fri, 8 Feb 2019 12:20:18 +0000, "Costello, Roger L."
> > <cost...@mitre.org> wrote:
> >
> >> What is it about ML that makes it such a good language for implementing
> >> compilers?
> >
> > Compiling involves a lot of pattern matching, and pattern matching is
> > a native feature of ML.
>
> You mean for tokenising and parsing? That would be a small part of
> compilation (the easy bit, in my view), although it seems to be a
> preoccupation of this group.

Agree. Pattern matching might help a little during tokenising,
but I have doubts that it leads to a fast tokenizing function.

For parsing I don't think that pattern matching leads to correct
results in all cases. I have seen too much buggy attempts to do
parsing with pattern matching. Even for such simple things as
lines with key=value I saw "solutions" with pattern matching, that
triggered bugs when the line was not simple. A good approach for
parsing is LL(1), which has nothing to do with pattern matching.
With pattern matching you are in danger, to get something that
just works when the weather is good. Good compilers just don't
use pattern matching for parsing.

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] | [next] | [standalone]

#2169

Am 09.03.2019 um 07:47 schrieb mertesthomas@gmail.com:

> For parsing I don't think that pattern matching leads to correct
> results in all cases. I have seen too much buggy attempts to do
> parsing with pattern matching. Even for such simple things as
> lines with key=value I saw "solutions" with pattern matching, that
> triggered bugs when the line was not simple. A good approach for
> parsing is LL(1), which has nothing to do with pattern matching.

IMO bottom-up parsers (LR) do pattern matching, in contrast to top-down
parsers (LL). Where bottom-up parsers can suffer from shift/reduce
conflicts.

DoDi

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

#2171

On Sat, 9 Mar 2019 10:14:01 +0100, Hans-Peter Diettrich
<DrDiettrich1@netscape.net> wrote:

>IMO bottom-up parsers (LR) do pattern matching, in contrast to top-down
>parsers (LL). Where bottom-up parsers can suffer from shift/reduce
>conflicts.

And top-down parsers suffer from common prefixes and backtracking.

George

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

#2173

On 2019-03-09, Hans-Peter Diettrich <DrDiettrich1@netscape.net> wrote:
> Am 09.03.2019 um 07:47 schrieb mertesthomas@gmail.com:
>
>> For parsing I don't think that pattern matching leads to correct
>> results in all cases. I have seen too much buggy attempts to do
>> parsing with pattern matching. Even for such simple things as
>> lines with key=value I saw "solutions" with pattern matching, that
>> triggered bugs when the line was not simple. A good approach for
>> parsing is LL(1), which has nothing to do with pattern matching.
>
> IMO bottom-up parsers (LR) do pattern matching, in contrast to top-down
> parsers (LL). Where bottom-up parsers can suffer from shift/reduce
> conflicts.

Top-down is still pattern matching!

Match this, then match that, then peek at the next symbol, and choose
among five different functions, each of which match this, match that ...

There is no unravelling of nested syntax without pattern matching
in some shape or form.

LL(1) matching is still a combination of matching a regular language,
with a push-down automaton.

Just because you hand-translate that into recursive-descent code doesn't
mean it ceases to be a regex recognizer with push-down

--
TXR Programming Lanuage: http://nongnu.org/txr
Music DIY Mailing List:  http://www.kylheku.com/diy
ADA MP-1 Mailing List:   http://www.kylheku.com/mp1

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

#2170

On 09/03/2019 06:47, mertesthomas@gmail.com wrote:
> On 2019-02-12 15:43:46 UTC+1 Bart wrote:
>> On 08/02/2019 23:36, George Neuner wrote:
>>> On Fri, 8 Feb 2019 12:20:18 +0000, "Costello, Roger L."
>>> <cost...@mitre.org> wrote:
>>>
>>>> What is it about ML that makes it such a good language for implementing
>>>> compilers?
>>>
>>> Compiling involves a lot of pattern matching, and pattern matching is
>>> a native feature of ML.
>>
>> You mean for tokenising and parsing? That would be a small part of
>> compilation (the easy bit, in my view), although it seems to be a
>> preoccupation of this group.
>
> Agree. Pattern matching might help a little during tokenising,
> but I have doubts that it leads to a fast tokenizing function.

In one exchange on comp.lang.python a few years ago, I posted a highly
un-Pythonic and generally derided tokeniser program.

However it turned out to be faster than someone else's more elegant
tokeniser based on regular expressions.

And that was despite the regular expression library being implemented (I
would presume) in compiled native code. Mine would have been mostly
byte-code.
[Python's REs are not particularly fast.  Perl's seem about twice as fast. -John]

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

#2172

On Sat, 9 Mar 2019 01:47:38 -0500 (EST), mertesthomas@gmail.com wrote:

>For parsing I don't think that pattern matching leads to correct
>results in all cases. I have seen too much buggy attempts to do
>parsing with pattern matching.

You have seen the approach of bad patterns - you have not seen that
patterns are a bad approach.

I also have seen some poor attempts made using pattern matching - when
the patterns are too general, or don't cover 100% the intended cases -
there will be unintended matches.  Pattern matching is only as
exacting as you make it.  It doesn't necessarily save you any time or
code ... what it does do is make the code more manageable and easier
to verify.

George

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

#2174

On 2019-03-10, George Neuner <gneuner2@comcast.net> wrote:
> On Sat, 9 Mar 2019 01:47:38 -0500 (EST), mertesthomas@gmail.com wrote:
>
>>For parsing I don't think that pattern matching leads to correct
>>results in all cases. I have seen too much buggy attempts to do
>>parsing with pattern matching.
>
> You have seen the approach of bad patterns - you have not seen that
> patterns are a bad approach.
>
> I also have seen some poor attempts made using pattern matching - when
> the patterns are too general, or don't cover 100% the intended cases -
> there will be unintended matches.  Pattern matching is only as

Sometimes unintended matches are better; you can deal with the
over-match easily later in the pipeline.

Lisp is a good example: any possible tree shape, containing any symbols,
can be scanned into a tree. Then macros and operators check for invalid
syntax.

In C, any combination of type specifiers and qualifiers can occur in a
declaration. For instance the simple grammar will match
"long char unsigned short int double".

Enforcing the permissible combinations is a constraint check.

The valid combinations can occur in any order: unsigned long int, int
long unsigned, ...

It would be a fool's errand to write phrase structure rules to match the
valid combinations and not match invalid ones.

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

#2175

On Tuesday, February 12, 2019 at 9:43:46 AM UTC-5, Bart wrote:
> On 08/02/2019 23:36, George Neuner wrote:
> > On Fri, 8 Feb 2019 12:20:18 +0000, "Costello, Roger L."
> > <costello@mitre.org> wrote:
> >
> >> What is it about ML that makes it such a good language for implementing
> >> compilers?
> >
> > Compiling involves a lot of pattern matching, and pattern matching is
> > a native feature of ML.
>
> You mean for tokenising and parsing? That would be a small part of
> compilation (the easy bit, in my view), although it seems to be a
> preoccupation of this group.

This thread has gone down a rabbit hole.  The pattern matching in ML is not
used for tokenizing and parsing.  Unfortunately the term "pattern matching" is
used for a wide variety of things.  Tokenizing and parsing being one of them.
It is also used in AI and Machine Learning circles to mean something
different.  The network security folks have still a third use of the term.
However, in this context that's not what ML style pattern matching is used for
(and it is yet a fourth variation on what pattern matching means).  There are
probably many other uses of the term I'm not aware of, but I know those four
and see how they overlap but are not the same.  Each different form attacks a
different problem and uses a different meaning of the word pattern.

If you want really fast tokenizing and parsing, you turn it into a DFA (PDA
for a parser) and implement the engine for doing so in assembly
language/machine code.  Tom Pennelo wrote an excellent paper on how to do
that.  BTW, the code for an LL parser is slightly faster than the code for an
LR one, because it is less general and doesn't push as much stuff on the
stack.  You pay for that speed with a slightly less general grammar formalism,
but in practice it doesn't matter.  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 you want to get faster, you have to find a way of dealing with
multiple characters at a time.  There are papers on how to do that (mostly in
the context of network security), but for the lexing case it is a challenge to
do and I've never seen it used in general practice.)

Ok, having dispensed with that.  Let's talk about ML style pattern matching
and where it is used and what it is used for.

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.

The technique 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.

I think you see a similar approach in Ira Baxter's Semantic Design tool.

Notice, that I am not talking about the source code and lexing and parsing
here.  I'm talking about what you do afterwards.  That's where the bulk of the
work is done.  You have structured data, but you want it in a different
structure.  That's the problem that ML pattern matching helps you solve.  It
isn't about lexing and parsing at all.

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

#2176

On 10/03/2019 11:13, Christopher F Clark wrote:
> On Tuesday, February 12, 2019 at 9:43:46 AM UTC-5, Bart wrote:
>> On 08/02/2019 23:36, George Neuner wrote:
>>> On Fri, 8 Feb 2019 12:20:18 +0000, "Costello, Roger L."
>>> <costello@mitre.org> wrote:
>>>
>>>> What is it about ML that makes it such a good language for implementing
>>>> compilers?
>>>
>>> Compiling involves a lot of pattern matching, and pattern matching is
>>> a native feature of ML.
>>
>> You mean for tokenising and parsing? That would be a small part of
>> compilation (the easy bit, in my view), although it seems to be a
>> preoccupation of this group.
>
> This thread has gone down a rabbit hole.  The pattern matching in ML is not
> used for tokenizing and parsing.
....

> If you want really fast tokenizing and parsing, you turn it into a DFA (PDA
> for a parser) and implement the engine for doing so in assembly
> language/machine code.

How fast are we talking about?

Using traditional methods on my not very fast PC, I can get up to 10
million lines per second for basic tokenising, 5Mlps with symbol table
lookups for identifiers (user names or keywords), and up to 2Mlps with
full parsing (building the symbol table and syntax tree on the way).

Which comes to an insignificant amount of the runtime of most compilers.

Parsing needs to recognise keywords in order to do its job; I can see
that tokenising and parsing could be combined into a single pass that
works a character at a time, but requiring machine generated parsing
code as it would otherwise be impractical. But what sort of speed-ups
could that give?

> 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.

On the same machine that I can parse sqlite3.c (a 210Kloc test +
windows.h) in about 0.14 seconds, a full 'gcc -O0 -c' compile takes 8.8
seconds. -O3 takes 54 seconds, nearly 400 times as long as parsing. (And
being C that includes dealing with macro expansion in the tokeniser,
include files, conditional code etc.)

[This test uses windows.h, and gcc uses a much more elaborate version
than my test. But a standalone compile of windows.h by gcc is 1.3
seconds with either -O0 or -O3, so is not too significant]

See the table here:

   https://github.com/sal55/qx/blob/master/compilertest.txt

This compares compilers when given 20K-2000K lines of the same input.
(Not realistic code, but still interesting to see how they managed.)

All you have to do is look at the difference between gcc 8.1.0
(unoptimised), and TinyC.

Both have exactly the same job to do in terms of parsing input, yet one
timing shows 16.5 seconds for gcc, and 0.2 seconds for Tiny C. That
means the job of parsing cannot have taken more than 0.2 seconds.

This is why I suggested it is not significant for most compilers. (It
might be for Tiny C, but getting that even faster can hardly be a
priority...)

(BTW my own compilers on that chart are 'bcc', 'MM', and 'QC', which are
mostly just behind Tiny C.)

>
> Notice, that I am not talking about the source code and lexing and parsing
> here.

That's why I asked the question.


> I'm talking about what you do afterwards.  That's where the bulk of the
> work is done.

OK. Clearly my compilers work differently, or at least that aspect of it
is in a very crude form, as I don't recall needing to do any such
pattern matching.

Is this associated with optimising?

--
bart

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

#2181

On Sunday, March 10, 2019 at 9:07:41 PM UTC-4, Bart wrote:
> On 10/03/2019 11:13, Christopher F Clark wrote:
> > On Tuesday, February 12, 2019 at 9:43:46 AM UTC-5, Bart wrote:
> >> On 08/02/2019 23:36, George Neuner wrote:
> >>> On Fri, 8 Feb 2019 12:20:18 +0000, "Costello, Roger L."
> >>> <costello@mitre.org> wrote:
> >>>
> >>>> What is it about ML that makes it such a good language for
implementing
> >>>> compilers?
> >>>
> >>> Compiling involves a lot of pattern matching, and pattern matching is
> >>> a native feature of ML.
> >>
> >> You mean for tokenising and parsing? That would be a small part of
> >> compilation (the easy bit, in my view), although it seems to be a
> >> preoccupation of this group.
> >
> > This thread has gone down a rabbit hole.  The pattern matching in ML is
not
> > used for tokenizing and parsing.
> ....
>
> > If you want really fast tokenizing and parsing, you turn it into a DFA
(PDA
> > for a parser) and implement the engine for doing so in assembly
> > language/machine code.
>
> How fast are we talking about?

I haven't measured in a long time, so I can't quote any numbers.  However, as
I recall, you can lex a buffer in roughly the same time you can access it via
getc rather than reading with fread if your lexer code is tight.  In fact, the
fetching of the characters is often a significant factor in the lexing time.
The other significant factors are the time spent in calls (to either the I/O
library or passing a token back to the parser.  So, really fast lexers
actually often concentrate on that, minimizing both (e.g. reading large
buffers and batching up a whole set of tokens to pass to the parser rather
than one at a time).

> Which comes to an insignificant amount of the runtime of most compilers.

That probably depends upon the complexity of the other parts. The last time I
benchmarked lexer and parser times was for a compiler that dealt with a
language for industrial automation.  In that compiler, before tweaking, the
lexer and parser took up about a third of the total compilation time.
Admittedly the language was very simple.  After tweaking we got it down to
around 10% of the time.  The only other bit of code in the compiler took up
10% in our profiling runs was the writing out of the resulting compiled file.


> Parsing needs to recognise keywords in order to do its job

I consider recognizing keywords and hashing identifiers both to be part of the
lexer's responsibility, but don't necessarily mean you should do them in the
DFA.

> > I'm talking about what you do afterwards.  That's where the bulk of the
> > work is done.
>
> OK. Clearly my compilers work differently, or at least that aspect of it
> is in a very crude form, as I don't recall needing to do any such
> pattern matching.

You probably aren't trying to support multiple front ends and back ends with
the same compiler.  You probably aren't attempting much optimization either.
If neither of those applies, you can often make your IR (intermediate
representation) fairly close to the source language AST (abstract syntax
tree).  Then, you don't need pattern matching to do rewrites.

That said, see the response that describes how to do code generation as
rewrites.  People have been doing that since the 1970s at least.  It can make
specifying a code generator easy.

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

#2182

Am 11.03.2019 um 18:49 schrieb Christopher F Clark:
> On Sunday, March 10, 2019 at 9:07:41 PM UTC-4, Bart wrote:

>> How fast are we talking about?
>
> I haven't measured in a long time, so I can't quote any numbers.  However, as
> I recall, you can lex a buffer in roughly the same time you can access it via
> getc rather than reading with fread if your lexer code is tight.  In fact, the
> fetching of the characters is often a significant factor in the lexing time.
> The other significant factors are the time spent in calls (to either the I/O
> library or passing a token back to the parser.  So, really fast lexers
> actually often concentrate on that, minimizing both (e.g. reading large
> buffers and batching up a whole set of tokens to pass to the parser rather
> than one at a time).

In the age of multi-core processors and threads some parallel work can
reduce the overall processing time. Then the longest running part of
the compiler determines the total run time, not the sum of all times.

With sufficiently large memory it's possible to read (or map) entire
files into RAM, so that library function calls for reading characters
are not required any more.

With all the caches used by nowadays OSs it's hard to reproduce
benchmark times. And that's not always really required or desireable!
Imagine a fast compiler that is invoked after every single change to
the source code, which will benefit from OS caches, whereas a slow
compiler invoked once per hour or day will suffer even more from the
lack of cached files and directories. A clever IDE can do such caching
itself, and can remember which *parts* of a source file have not been
touched since the last compile, much bettter than the OS file
modification date.  And it can compile updates in the background, so
that a final compilation of an entire project may run as fast as the
compilation summary is presented to the user :-)

DoDi

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

#2184

On 12/03/2019 05:54, Hans-Peter Diettrich wrote:
> Am 11.03.2019 um 18:49 schrieb Christopher F Clark:

>> I haven't measured in a long time, so I can't quote any numbers.
>> However, as
>> I recall, you can lex a buffer in roughly the same time you can access
>> it via
>> getc rather than reading with fread if your lexer code is tight.  In
>> fact, the
>> fetching of the characters is often a significant factor in the lexing
>> time.
>> The other significant factors are the time spent in calls (to either
>> the I/O
>> library or passing a token back to the parser.  So, really fast lexers
>> actually often concentrate on that, minimizing both (e.g. reading large
>> buffers and batching up a whole set of tokens to pass to the parser
>> rather
>> than one at a time).
>
> In the age of multi-core processors and threads some parallel work can
> reduce the overall processing time. Then the longest running part of
> the compiler determines the total run time, not the sum of all times.
>
> With sufficiently large memory it's possible to read (or map) entire
> files into RAM, so that library function calls for reading characters
> are not required any more.

That's been the case for a very long time. My sqlite3.c test file, a
large 210K line file is 8MB; my PC has 8000MB of RAM. So loading such a
large file occupies 0.1% of the memory.

Loading that file takes 9ms on my machine, although thanks to file
caching. (Without caching, then it's up to how efficiently the OS can
fetch files into memory, but that's outside the scope of the compiler,
and not something it can do much about.)

Anyway, once in memory, scanning the characters involves traversing the
source by incrementing a byte pointer. That part of my lexers usuaily
looks like this (this one designed for C source):

    doswitch lxsptr++^             # (looping switch)
    when 'A'..'Z','a'..'z','$','_' then
       .... start of identifier
    when '1'..'9' then
       .... start of decimal number

> With all the caches used by nowadays OSs it's hard to reproduce
> benchmark times. And that's not always really required or desireable!

I would dispute that file load times should be considered part of
compilation time, at least when comparing performance.

Imagine a compiler accessed via a library API, where you pass it a
string as the input source, and it returns the output as another string.
File i/o doesn't come into it. Or maybe the input was synthesised or
generated from another program.

> Imagine a fast compiler that is invoked after every single change to
> the source code,

Both of my own languages do have whole program compilers that /must/
process all modules on every change. However, my projects are small
enough (20-40K lines over a few dozen modules), that it might take 0.2
to 0.3 seconds total elapsed time. (There is some scope for further
improvement, but I don't need it at the moment.)

(Actually, lexing and parsing probably /is/ about 30% of my compile
times, but only because the compilers are generally quite fast. The
byte-code compiler has touched on a million lines per second, on a
older, somewhat faster machine.

But at that level it becomes difficult to test compiler speed on real
programs because the actual timing gets lost in the noise; just printing
a few more lines of output might take as long!

One older compiler was written in a dynamic language which had to be
compiled to byte-code. The performance of that compiler was indifferent,
but the one used to generate the byte-code was blazing fast. In fact,
for a while it was set up so that every time I ran this compiler, it was
compiled from scratch (some 24Kloc).

I didn't notice, since it only took some tens of milliseconds. That;s
not something you can attempt with gcc (rebuilding it every time it's run).)

  which will benefit from OS caches, whereas a slow
> compiler invoked once per hour or day will suffer even more from the
> lack of cached files and directories. A clever IDE can do such caching
> itself, and can remember which *parts* of a source file have not been
> touched since the last compile, much bettter than the OS file
> modification date.  And it can compile updates in the background, so
> that a final compilation of an entire project may run as fast as the
> compilation summary is presented to the user :-)

Yeah, but that would be misleading the user as to the real compiler
performance...

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

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.compilers

csiph-web