|Compiler books for beginners? firstname.lastname@example.org (2002-05-27)|
|Re: Compiler books for beginners? email@example.com (Ralph Boland) (2002-05-27)|
|Re: parsing extended CFGs, was Compiler books for beginners? firstname.lastname@example.org (Chris F Clark) (2002-05-31)|
|Re: parsing extended CFGs, was Compiler books for beginners? email@example.com (Joachim Durchholz) (2002-05-31)|
|From:||"Joachim Durchholz" <firstname.lastname@example.org>|
|Date:||31 May 2002 23:03:58 -0400|
|Posted-Date:||31 May 2002 23:03:58 EDT|
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
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.
Return to the
Search the comp.compilers archives again.