Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: antispam@math.uni.wroc.pl Newsgroups: comp.compilers Subject: Re: Who first invented dotted-item notation? Date: Sat, 28 May 2022 04:51:45 -0000 (UTC) Organization: Aioe.org NNTP Server Lines: 45 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <22-05-052@comp.compilers> References: <22-05-046@comp.compilers> <22-05-049@comp.compilers> <22-05-050@comp.compilers> Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="42119"; mail-complaints-to="abuse@iecc.com" Keywords: parse, history, comment Posted-Date: 28 May 2022 15:35:46 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:3024 Christopher F Clark 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]