Re: parsing extended CFGs, was Compiler books for beginners?

Ralph Boland wrote:
>
> Why has LR based parser generator tools that directly support (that do
> not translate the grammar into non-extended form) regular expression
> operators so uncommon anyway; other than that they are fairly complex?


Technically, that should be simple. The "sets-of-items" construction
that's used for constructing the LR tables is essentially just a
construction of a DFA, so all extensions to DFA should be easily
applicable to LR parsing.


I'm not sure that using REs for parser rules is a good idea anyway.
General REs make it difficult to identify subnodes of a node, for
example. Without REs, I must write
      foo ::= bar baz
              | bar
              | baz
              | .
and the semantic action associated with every rule will know whether $1
is a bar or a baz. If I write
      foo ::= [bar] [baz]
this is much more compact, but the semantic actions will have to find
out whether there's a bar or not before it can access $1, something that
the parser could have done for it.
I know there are ways to handle such cases - but this is just a little
example. The full power of regular expressions is definitely overkill
for parsing. REs are tailored towards classifying strings of tokens
without retaining information on their internal structure, while parsers
are tailored towards identifying parts of strings and putting them into
relation with each other.


Regards,
Joachim

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