RE: Who first invented dotted-item notation?

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

Return to the comp.compilers page.
Search the comp.compilers archives again.