Re: --- Regexps, compilers etc., prog help ---

On 14 Mar 1997 00:34:37 -0500, in comp.compilers J. Kanze wrote:


>Concerning the moderator's comment: most regular expression's I see
>these days have been extended to allow saving part of the match. I
>think that this requires back-tracking (or does anyone know of a one
>pass solution that works in all cases).
n
I'm not particularly fond of the syntax for saving part of an RE
match. Cosnider an RE that matches any identifier I followed by a
colon, followed by that same identifier:


        (I):\1 (that's \one, not \ell)


I implemented the same semantic in LPM as follows:


        [^
              <I>
        ['the_identifier'^
        [':'$
        ['the_identifier'!


Internally, a stack of offsets is used -- when the [^ is encountered,
the current offset of the intermediate match is pushed to this stack.
When the corresponding ['foobar'^ is encountered, that offset is then
used in conjunction with the second intermediate offset -- the two
values are used to construct a temporary substring, which is pushed to
a string stack and associated with the set 'foobar'.


The ['foobar'! clause matches any member in the set 'foobar'. Since
that substring stack is given precedence over permanent members of the
set 'foobar' -- the above pattern matches "apple:apple" but not
"apple:orange"


This is done at the expense of creating temporary substrings for
internal use. Would those temporary substrings be considered
backgracking?


> Even with normal regular expressions, there are a number of tradeoffs
> between memory use, execution time and flexibility.


You can't have it all. ;-) In LPM, failure to match is more 'costly'
than success in a match. Any large stream can be efficiently scanned
for almost any complexity of pattern that is somewhere in the stream
-- but the cost of determining that a pattern ISN'T in the stream is
high in version 1.0 of the engine. Version 2.0 uses "polymorphism"
and initial tests have shown that this alone speeds up things
considerably.


> Enough to make me think that there still will be occasions for
> writing your own parser.


Which is what I did. <wink>
--
email: the_artful_parser@null.net
url: http://mypage.direct.ca/q/qjackson/
--

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