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

Groups > comp.compilers > #3020

RE: Who first invented dotted-item notation?

Show all headers | View raw

Let me explain a little further.

Dotted-items are useful in translating (and visualizing) state
machines as translations of regular expressions or grammar rules.

In Glushkov's construction one takes a regular expression /ab*(cb)+a/
and makes copies of it with a dot before each "symbol" (character you
can recognize) and one at the end.  Thus, 6 dotted-items:
/.ab*(cb)+a/
/a.b*(cb)+a/
/ab*(.cb)+a/
/ab*(c.b)+a/
/ab*(cb)+.a/
/ab*(cb)+a./

Each state in a Glushkov NFA is a subset of the powerset of these
items: (see below)

state 0:
/.ab*(cb)+a/

state 1:
/a.b*(cb)+a/
/ab*(.cb)+a/

state 2:
/ab*(c.b)+a/

state 3:
/ab*(.cb)+a/
/ab*(cb)+.a/

state 4:
/ab*(cb)+a./

The algorithm explains how to calculate what the states and their
transitions are.

Yielding something like this:

state 0:
/.ab*(cb)+a/ -> state 1

state 1:
/a.b*(cb)+a/ -> state 1
/ab*(.cb)+a/ -> state 2

state 2:
/ab*(c.b)+a/ -> state 3

state 3:
/ab*(.cb)+a/ -> state 2
/ab*(cb)+.a/ -> state 4

state 4:
/ab*(cb)+a./ -> accept

Below: Actually, in a Gluskov NFA the 6 dotted-items might be the
states, and those subsets might be how you change it to a DFA (the
subset construction algorithm).  In my mind, those things have gotten
merged, but that might be an error on my part.

Anyway, when building the LR(0) machine, you build similar-dotted
items (and subsets) to define the states of the LR(0) DFA. And, the
Earley construction adds some context information to the doffed-items.

It's how I think about state machines.  It's how they are documented
in Yacc++ with the debug option.  Yacc (and Bison) does something
similar using _ instead of dot if I recall correctly.

But, someone must have introduced the idea first.  My question is who?
 Did Backus use dotted-items?  Or did Knuth or Glushkov invent them?
Or maybe Naur.  Or someone else, maybe one unfamiliar to me? Maybe it
goes all the way back to Kleene.  Is the question lost to time?

That's my question....

Again, thanks,
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
------------------------------------------------------------------------------
[BNF was descriptive, don't think Backus ever did anything with formal parsers.
I looked at Knuth's 1965 LR parsing paper which has a lot of notation but no
dots. -John]

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