Re: Who first invented dotted-item notation?

Christopher F Clark <christopher.f.clark@compiler-resources.com> wrote:
> 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.


This idea is in paper by Floyd "A Descriptive Language for Symbol
Manipulation" where he descibes system of rules for parsing.
Instead of dot he uses a triangle as a marker, and his rules
are different than context-free rules.


I think that to have definite answer you need to be very precise
what you ask. Marking positions is very old technique. Implicitely
it appears in math works on Tue systems and word problems.
In a sense position of head in Turing machine is doing the
same work.


Dot is used in Earley paper from 1967. Knuth 1965 paper seem to
be hidden by paywalls, so I can not see what is in it, but
reasonable guess is that Knuth used dot. Knuth ideas are
innovative enough that if you specify your question to parsing
using set of items of context-free grammars, then I believe
he is the first. OTOH in more general setting marker tokens
for "current position" were crucial for proof that systems
of substitutions (rewrites) are Turing complete and this
seem to be done in early fifties.


--
                                                            Waldek Hebisch
[Knuth didn't use dots. You can find a copy of the paper at
https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.361.8867
Click the "cached" link at the upper right. -John]

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