24 Oct 1998 01:47:10 -0400

Related articles |
---|

PDAs and regular expressions pseale@ix.netcom.com (pseale) (1998-10-22) |

Re: PDAs and regular expressions glenn.langemeier@gmx.net (1998-10-24) |

Re: PDAs and regular expressions bromage@cs.mu.OZ.AU (1998-10-24) |

From: | bromage@cs.mu.OZ.AU (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" <pseale@ix.netcom.com> 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_).

Notation:

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

operations.

*> - 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.

Cheers,

Andrew Bromage

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.