13 Aug 2004 17:32:54 -0400

From: | dhalitsky@cumulativeinquiry.com (David Halitsky) |

Newsgroups: | comp.compilers |

Date: | 13 Aug 2004 17:32:54 -0400 |

Organization: | Compilers Central |

References: | 04-08-046 04-08-058 04-08-074 |

Keywords: | parse, theory |

Larry Evans wrote:

*> Is there something like an identity element for the alternative*

*> operator, |. I'm thinking that in (x e) the space is the implicit*

*> multiplication operator with identity e, but I was wondering*

*> if there were something similar for the addition (i.e. | )*

*> operator. In addition, could this be what parsers are "in theory"*

*> using when the lexer's return # (as in yacc) to signal the end of input?*

It is interesting (to me, at least) that Larry Evans (LE) should bring

up the matter of # as an end-of-input symbol.

When I first became interested in the type of right (or left) linear

derivation in which all productions save the last introduce one

terminal and the last introduces two terminals, I immediately thought

of interpreting the rightmost(leftmost) deepest terminal as a "STOP"

symbol. This is because any such right(left) linear derivation has an

automata-theoretic interpretation as a model of a finite-state

process, and it seemed natural to me to interpret the "extra" terminal

introduced by the last production in the derivation as a designated

"STOP" symbol, or "final state" symbol, just as the symbol to the left

of the rewrite arrow in the first production can be considered a

designated initial symbol of the grammar (or "initial-state" symbol.)

However, since I don't have even the slightest REAL knowledge of

finite-state automata theory nor its relation to formal language

theory, I hestitated to bring this up as a possible interpretation of

the deepest rightmost(leftmost) terminal in the class of derivations

in which I am interested.

If the language-theoretic/automata-theoretic community were to agree

that this is as legitimate and useful interpretation of the "extra"

rightmost (leftmost) and deepest terminal in the class of derivations

under consideration, then researchers now working under the auspices

of Cumulative Inquriy can say something quite interesting about how to

"double" such derivations in an intuitvely natural way which can be

expressed both algebraically and geometrically. In this regard, see

the "oDAG/POSET Problem" material and the "oDAGs invariant under a

half-turn" material at:

http://www.CumulativeInquiry.com/Problems

The upshot of the research in these two threads at the above URL is

that we can create the derivation tree of the derivation:

A -> a B

B -> b C

C -> c D

D -> d f

by starting with the derivation tree of the derivation:

C -> c D

D -> d f

and algebraically and/or geometrically "doubling" this derivation tree

in a straightforward manner by a symmetry operation suggested by the

work of Robert Jamison (Clemson) and William F. Mann (CI) on the

notion of "trees invariant under a half-turn".

This "doubling" of derivation trees, moreover, may shed some new

formal light on the applied problem of figuring out why certain

protein structures which do NOT appear to involve gene segment

duplication nonetheless converge on structures which DO appear to

involve gene segment duplication.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.