14 Nov 2000 13:14:17 -0500

From: | frank@gnu.de (Frank Heckenbach) |

Newsgroups: | comp.compilers |

Date: | 14 Nov 2000 13:14:17 -0500 |

Organization: | Posted via University of Erlangen |

References: | 00-11-073 00-11-080 00-11-083 |

Keywords: | lex, parse |

Posted-Date: | 14 Nov 2000 13:14:16 EST |

pcj1@my-deja.com wrote:

*> Chris, I don't think you read my post thoroughly enough. I'm not*

*> talking about deterministic pushdown automata (DPDA) though the name*

*> "deterministic pushdown finite automata" (DPDFA) is clearly very*

*> similar (by intent).*

*>*

*> A DPDA is not a DPDFA. Let me explain (excuse the formality, it's for*

*> my own good)*

*>*

*> ==================================================*

*>*

*> [...]*

*>*

*> What I'm talking about*

*>*

*> DPDFA is a system (M, K, f(m,k)) where:*

*>*

*> - M is a set of DFA's as above*

*>*

*> - K is a set of symbols called the "token" alphabet which is defined*

*> as the union of the output symbols over M (all the output*

*> symbols)*

*>*

*> - f(m,k) is a function mapping M X K to M (the mode transition*

*> function).*

*>*

*> Therefore, a DPDFA is a set of DFA's, not a single DFA. A lexer that*

*> uses a DPDFA may only be in one "mode" at a time (using one of the*

*> DFA's in M). When a token is recognized, the mode transition function*

*> is consulted to possibly move the lexer in a new "mode" (or "state").*

*> If these moves are done without a stack, you get flex. If the moves*

*> are done using a stack (and a special "pop" instruction in K), you get*

*> what I'm talking about.*

*>*

*> So while both DPDA's and DPDFA's use dfa's and stacks, they are quite*

*> different. The languages that may be derived from either are*

*> different, therefore they are not the same (though I have not proved*

*> that).*

*>*

*> Since I'm obviously in the belief that "DPDFA" is a unique animal, I'm*

*> looking for more information about it such that I don't have to spin*

*> and or re-invent wheels (general laziness).*

*> [Interesting question. It feels to me like it's equivalent to a DPDA*

*> but my comp theory isn't good enough to prove it either way. -John]*

I don't really feel like putting up a formal proof (not at this time

of night, anyway), but I think the basic idea to prove equivalence

would be to identify pairs of DPDFA states and active DFA (M x Q,

assuming for simplicity that all DFAs have the same set of states)

with DPDA states (i.e., construct a DPDA such that the transitions fit

this identification).

This is under the assumption that the choice of next DFA depends

only on the current DFA, the token and the state of the stack (i.e.,

something like f: M x K x A -> M x A where A is the (infinite) set

of stack states, and f "respects stack semantics").

If, however, the push/pop operations can be part of arbitrary C

coded rules (to use lex terminology), as in your original request,

this doesn't hold. But then, already lex with C rules is a Turing

machine, and so is anything more powerful including arbitrary C

rules...

Technical side note: You can do what you want perfectly well in lex

(at least GNU flex -- don't know about the original lex). The

argument of BEGIN is not required to be a constant, so you can use

your favourite stack implementation and call BEGIN (top of stack)

after each push and pop.

Frank

--

Frank Heckenbach, frank@[NOSPAM.REMOVE.THIS]g-n-u.de, http://fjf.gnu.de/

PGP and GPG keys: http://fjf.gnu.de/plan

Pascal code, BP CRT bugfix: http://fjf.gnu.de/programs.html

Free GNU Pascal Compiler: http://home.pages.de/~GNU-Pascal/

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.