Re: Preview in grammar

"Ulrich Frank" <franku@fmi.uni-passau.de> writes:


> I need a preview which token comes next in an uncomplete input
> string.


Yacc++ generated parsers have a function (that you can customize)
called "display_expected" which will list the tokens (and/or
non-terminals) allowed at its current parsing point. We have
traditionally used it to display what token would have been legal when
an error is encountered, but we had one client (that we know of) who
used it just as you suggest to list tokens about to be entered. For
example, you might want to do that if you are using the parser with a
menu system where you want to gray-out illegal options.


Such a function can be added to any kind of LR parser if you
understand how the tables are laid out. For an LR parser, "all you
have to do", is find out which table entries are error entries.


If the tables are unpacked, it's easier. When the tables are packed,
you have to unpack them and you may have to disentangle which entries
are for which state.


Once you know the entries for a specific state, you can evaluate the
entries. If the entry is a "shift" entry, then it is not an error
entry. The same is true for "accept" entries. They are also not
error entries. Entries which are specificially error entries are, of
course, error entries. The hardest ones to deal with are reduce
entries. One can treat reduce entries as non-error entries. However,
in many LR based parsers, you will get reduce entries to states where
they are then error entries. So, it is better if you trace back the
LR stack and process the reduce entry in the "goto" state, and you may
have to do that recursively until you get to a state where you don't
reduce on the token as lookahead.


That's the basic algorithm, if your parser generator has additional
features, such as predicates or GLR parsing, there are more wrinkles,
but they all can be worked out.


You can do a similar thing with LL parsers. In fact, table driven LL
parsers are even easier than LR ones. Recursive descent parsers are
harder because the actions are encoded in the generated code and not
in a table that one can read.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

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