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

Groups > comp.compilers > #2175

Re: Best language for implementing compilers?

Show all headers | View raw

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.

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

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

csiph-web