Re: PDAs and regular expressions (Andrew Bromage)
24 Oct 1998 01:47:10 -0400

          From comp.compilers

Related articles
PDAs and regular expressions (pseale) (1998-10-22)
Re: PDAs and regular expressions (1998-10-24)
Re: PDAs and regular expressions (1998-10-24)
| List of all articles for this month |

From: (Andrew Bromage)
Newsgroups: comp.compilers
Date: 24 Oct 1998 01:47:10 -0400
Organization: Computer Science, The University of Melbourne
References: 98-10-141
Keywords: parse, theory

G'day all.

"pseale" <> writes:

> Given a pushdown automaton, I wonder:
> - what the weakest grammatical model is that can describe the possible
>contents of the pushdown tape in any given state (for instance, a regular
>expression) and

It intuitively seems regular, since the contents of an LR(k) parser's
stack is at the most regular. However the weakest grammatical model
that I can think of is the regular language over stack _operations_ (as
opposed to stack _symbols_).


0 means "empty set"
1 means "null string"
+ means "union"
<i| means "push symbol i"
|i> means "pop symbol i"

The algebra of stack operations is a spinor algebra:

a <i| = <i| a
a |i> = |i> a

<i| |j> = 1, if i = j
= 0, otherwise

\Sum_{i is a stack symbol} |i> <i| = 1

For example, a^n b^n is equivalent to the regular expression:

<0| (a <1|)* (a |1>)* |0>

(The stack symbol 0 corresponds to the bottom of the stack.)

Tha language of stack symbols for this stack is the set of finite-
length prefixes of this expression:

<0| <1|* |1>* |0>

(i.e. the above expression with the terminal symbols removed.)

This set of prefixes is certainly regular in the algebra of stack

> - if so, has anyone developed an algorithm to compute this.

Working with the language of stack operations may give you a start.
You may like to try finding a way to convert a regular expression
over stack operations into a regular expression over stack symbols.

Andrew Bromage

Post a followup to this message

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