NetNews Usenet Archive 1992 #20/NN_1992_20.iso/spool/comp/theory/1902

Text File | 1992-09-09 | 1.7 KB | 34 lines

Newsgroups: comp.theory
Path: sparky!uunet!secapl!Cookie!frank
From: [e-mail] (Frank Adams)
Subject: Re: What kind of an automaton is this?
Message-ID: <[e-mail]>
Date: Wed, 09 Sep 1992 17:25:53 GMT
References: <[e-mail]>
Organization: Security APL, Inc.
Lines: 23

In article <[e-mail]> [e-mail] writes:
>We've been discussing on comp.compilers the kind of parsing automaton that is described in
>DeRemer[CACM 71] as being an SLR-Parser. It is not the kind of PDA I
>learned about when I studied Automata Theory with the next state and the
>output being determined by the current state, the top of the stack, and
>the current symbol in the input. In this "strange" automaton the lhs of
>the production being reduced is returned to the input after the stack
>has been popped. This is not just backing up over input, but non-terminals
>can be built up on the input, perhaps with a number of epsilon productions.
>Some people have said "oh yes, we like that and have a hack to use it"
>but it is unclear what exactly the computational complexity of this
>automaton is. LR parsing is clearly a subset of what this automaton can
>do - just don't do any of the strange reductions.

Such automata are in fact Turing-complete.  Regard the concatenation of the
items on the stack and the "input" as a Turing-machine tape.  The machine
can move forward by shifting symbols, and backward by special singleton
reductions.  New tape can be added by epsilon-productions.  (This is just an
outline of the construction, but it works.)

If you don't permit epsilon productions, you have the equivalent of a Turing
machine with a bounded tape; hence exactly the context-sensitive languages
can be recognized.