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

Text File | 1992-09-11 | 2.9 KB | 51 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: Fri, 11 Sep 1992 20:39:51 GMT
References: <[e-mail]> <[e-mail]>
Organization: Security APL, Inc.
Lines: 40

In article <[e-mail]> [e-mail] (Mike Hutton) writes:
>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.
>
>To disagree with the previous two responses, even if you extend to allow
>noncanonical lookahead (i.e. allow 2 stacks to go through the
>input and put nonterminals back on the input stack), you still have a
>context-free-like grammar (just with a more powerful lookahead
>ability) defining the language.  That the noncanonical parser *uses* two
>stacks doesn't imply that any language acceptable by an arbitrary
>2-stack automaton (i.e. Turing Machine) can be expressed with an appropriate
>NLR(k) or NSLR(k) grammar---you still have k-bounded lookahead, even if
>it can also include nonterminals.

This is correct as far as it goes.  However, as I noted, the machine *can*
in fact perform (almost) arbitrary stack operations on the two stacks.  (The
pushdown-machine stack cannot be left empty, but this is a detail.)  To get
full Turing-machine compatibility, you have to encode the Turing-machine
state in the symbols on top of the stacks; this gets messy, but is quite
doable.

To approach it in terms of the lookahead, you can look ahead more than k
symbols by shifting input symbols onto the stack, deciding what you want to
do, and then moving those symbols back to the input via unit productions.
What you push back may not be *exactly* what you originally read, but it can
function like what you originally read for subsequent processing.

(If k=0, the situation is quite different.  In this case, the symbol on top
of the stack after a special reduction must be a shift state, since a shift
was done in it before (unless this is an epsilon-production; but then an
infinite loop ensues).  Hence the next operation will be a shift, and you
might as well have just put the lhs on the stack in the first place.
However, 0-symbol lookahead pdm's are not very practical.)