RE: Who first invented dotted-item notation?

From	Christopher F Clark <christopher.f.clark@compiler-resources.com>
Newsgroups	comp.compilers
Subject	RE: Who first invented dotted-item notation?
Date	2022-05-24 11:27 +0300
Organization	Compilers Central
Message-ID	<22-05-050@comp.compilers> (permalink)
References	<22-05-046@comp.compilers> <22-05-049@comp.compilers>

Show all headers | View raw

Our wise moderator wrote:
> I believe Chris is asking about the specific use of a dot to show the
> position in a partially parsed BNF rule.

Yes, exactly.

It gives a kind of "operational semantics" to BNF/Regexes.  "I am
here.  This is what I expect to see next.  Or this, or this."

The way many kids learn to write stories with "This happened.  And
then this.  And then this. And then this."  It's considered bad style.
However, it gives a very simple semantics.

Someone must have invented the idea of specifically marking the
rule/regular expression with an indication on where you are in it.  It
may be an obvious thing, but someone had to realize that it should be
made explicit and one can reason from it.

Glushkov NFAs have fewer states and epsilon transitions than Thompson
NFAs although both represent the same regular expressions.

It's something I think anyone interested in automata or parsing should
learn.  I actually started writing about it in a blog/book I was
thinking of writing on the topic to explain some things like what we
did at Intel making hardware accelerators or how we did ELR parsing
(LR + regular expressions) in Yacc++.  Or even how one should look at
PEG grammars or GLR or Okhotin's work.  It's a basic foundation and
too many people don't seem to know it.  But someone must have first
thought of expressing it that way.

Kind regards,
Chris

--
******************************************************************************
Chris Clark                  email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc.  Web Site: http://world.std.com/~compres
23 Bailey Rd                 voice: (508) 435-5016
Berlin, MA  01503 USA      twitter: @intel_chris
------------------------------------------------------------------------------

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

Thread

Who first invented dotted-item notation? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-05-22 12:32 +0300
  Re: Who first invented dotted-item notation? Kaz Kylheku <480-992-1380@kylheku.com> - 2022-05-22 18:29 +0000
    RE: Who first invented dotted-item notation? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-05-23 13:23 +0300
  Re: Who first invented dotted-item notation? gah4 <gah4@u.washington.edu> - 2022-05-23 18:31 -0700
    RE: Who first invented dotted-item notation? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-05-24 11:27 +0300
      Re: Who first invented dotted-item notation? antispam@math.uni.wroc.pl - 2022-05-28 04:51 +0000

csiph-web