Re: Re: DFAs,NFAs,REs,CFGs,PDAs ARGH!

# 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 http://derkgwen.250free.com/html/index.html
Quit killing people. That's high profile.

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