Derk Gwen <>
23 Aug 2003 23:05:39 -0400

          From comp.compilers

Related articles
Re: Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! (Bob Foster) (2003-08-20)
Re: Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! (Derk Gwen) (2003-08-23)
| List of all articles for this month |

From: Derk Gwen <>
Newsgroups: comp.compilers
Date: 23 Aug 2003 23:05:39 -0400
Organization: Quick STOP Groceries
References: 03-08-060
Keywords: parse, theory
Posted-Date: 23 Aug 2003 23:05:39 EDT

# These restrictions are commonly met by parenthesis languages, which
# observe the sufficient but not necessary condition that entrance to
# and exit from recursive rules are bracketed by tokens that are not
# otherwise used in the rule(s). Thus, many parenthesis languages can be
# parsed using regular language techniques, e.g., by derivatives
# augmented in one way or the other by a simple stack.

In an LR(k) state machine, these regions show up as strongly connected
components. If you backtrack from a reduction to every state that can
shift that reduced token, and only one reduction backtrack goes into
such an SCC, the rest crossing over the loop, then you have this
situation. You can then replace the normal stack operations with an
integer count of how often you've looped around the SCC.

Derk Gwen
Quit killing people. That's high profile.

Post a followup to this message

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