Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2323 > unrolled thread

Regular expressions in lexing and parsing

Back to article view | Back to comp.compilers

Contents

  Regular expressions in lexing and parsing Ed Davis <ed_davis2@yahoo.com.dmarc.email> - 2019-05-17 13:18 +0000
    Regular expressions in lexing and parsing Ben Hanson <jamin.hanson@googlemail.com> - 2019-05-18 13:24 +0100
    Re: Regular expressions in lexing and parsing Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-05-21 07:14 +0200
      Re: Regular expressions in lexing and parsing Fortran steve kargl <sgk@troutmask.apl.washington.edu> - 2019-05-22 04:12 +0000
      Re: Regular expressions in lexing and parsing "Ev. Drikos" <drikosev@gmail.com> - 2019-05-23 18:42 +0300

#2323 — Regular expressions in lexing and parsing

This is a blog post from Rob Pike, of Plan-9 and Go fame - I found it pretty
interesting.

Regular expressions in lexing and parsing
August 22, 2011

Comments extracted from a code review. I've been asked to disseminate them
more widely.

I should say something about regular expressions in lexing and parsing.
Regular expressions are hard to write, hard to write well, and can be
expensive relative to other technologies. (Even when they are implemented
correctly in N*M time, they have significant overheads, especially if they
must capture the output.) Lexers, on the other hand, are fairly easy to write
correctly (if not as compactly), and very easy to test. Consider finding
alphanumeric identifiers. It's not too hard to write the regexp (something
like "[a-ZA-Z_][a-ZA-Z_0-9]*"), but really not much harder to write as a
simple loop. The performance of the loop, though, will be much higher and will
involve much less code under the covers. A regular expression library is a big
thing. Using one to parse identifiers is like using a Mack truck to go to the
store for milk. And when we want to adjust our lexer to admit other character
types, such as Unicode identifiers, and handle normalization, and so on, the
hand-written loop can cope easily but the regexp approach will break down.

A similar argument applies to parsing. Using regular expressions to explore
the parse state to find the way forward is expensive, overkill, and
error-prone. Standard lexing and parsing techniques are so easy to write, so
general, and so adaptable there's no reason to use regular expressions. They
also result in much faster, safer, and compact implementations.

Another way to look at it is that lexers and parsing are matching
statically-defined patterns, but regular expressions' strength is that they
provide a way to express patterns dynamically. They're great in text editors
and search tools, but when you know at compile time what all the things are
you're looking for, regular expressions bring far more generality and
flexibility than you need.

Finally, on the point about writing well. Regular expressions are, in my
experience, widely misunderstood and abused. When I do code reviews involving
regular expressions, I fix up a far higher fraction of the regular expressions
in the code than I do regular statements. This is a sign of misuse: most
programmers (no finger pointing here, just observing a generality) simply
don't know what they are or how to use them correctly. Encouraging regular
expressions as a panacea for all text processing problems is not only lazy and
poor engineering, it also reinforces their use by people who shouldn't be
using them at all.

So don't write lexers and parsers with regular expressions as the starting
point. Your code will be faster, cleaner, and much easier to understand and to
maintain.
--

[Orignally here https://commandcenter.blogspot.com/2011/08/regular-expressions-in-lexing-and.html

It took me a minute to figure out what he was saying, since the patterns in a lexer are regular
expressions.  I believe the point is not to use general purpose regex libraries but rather to
use something like flex or re2c which will take a set of expressions and actions and
precompile them. -John]

[toc] | [next] | [standalone]

#2325

 >[Orignally here
https://commandcenter.blogspot.com/2011/08/regular-expressions-in-lexing-and.html

 >It took me a minute to figure out what he was saying, since the patterns in a lexer are regular
 >expressions. I believe the point is not to use general purpose regex libraries but rather to
 >use something like flex or re2c which will take a set of expressions and actions and
 >precompile them. -John]

I have my doubts due to:

 >Consider finding
 >alphanumeric identifiers. It's not too hard to write the regexp (something
 >like "[a-ZA-Z_][a-ZA-Z_0-9]*"), but really not much harder to write as a
 >simple loop. The performance of the loop, though, will be much higher and will
 >involve much less code under the covers.

and

 >And when we want to adjust our lexer to admit other character
 >types, such as Unicode identifiers, and handle normalization, and so on, the
 >hand-written loop can cope easily but the regexp approach will break down.

It doesn't help that flex *still* doesn't support Unicode, but according
to http://re2c.org/manual/features/encodings/encodings.html re2c does.

My view is that just as regex libraries have been embraced by most
languages (even C++ has std::regex now), the same should happen for
lexer and parser generators. This is the approach I have taken with
lexertl and parsertl. Hana Dusíková is doing interesting work in the
compile time regex space with
https://github.com/hanickadot/compile-time-regular-expressions .
Apparently she is working on a DFA version this year which will be
presented at cppnow - http://cppnow.org/history/2019/schedule/ . I'm
hoping that this new version can be used as a lexer generator and then I
can switch to it for a lot of my lexing needs.

Regards,

Ben
[I agree that once you have some way to embed precompiled DFAs in your
code, it doesn't much matter whether the rest is  pattern-action like
in flex or something else. -John]

[toc] | [prev] | [next] | [standalone]

#2326

Am 17.05.2019 um 15:18 schrieb Ed Davis:

> So don't write lexers and parsers with regular expressions as the starting
> point. Your code will be faster, cleaner, and much easier to understand and to
> maintain.

I think that regular expressions are primarily usable in *formal* token
grammars. In contrast to parsers I'm missing *complete* formal grammars
for the tokens, including whitespace, comments, strings and other
special language elements, and how these fit together.

Here regular expressions are easier to understand and maintain than DFA
or NFA code for all those token types. The equivalent lexer
*implementation* finally is up to the compiler writer.

OTOH I wonder how a formal (regex?) FORTRAN lexer grammar could look like?

DoDi
[I've written Fortran 77 parsers.  It was quite context sensitive, particularly
deciding whether a statement was an assignment or something else. e.g.

 FORMAT(I4) = 42
 DO 10 I = 1.23   (oops)

Modern Fortran no longer ignores spaces which makes lexing a lot easier. -John]

[toc] | [prev] | [next] | [standalone]

#2327 — Re: Regular expressions in lexing and parsing Fortran

Hans-Peter Diettrich wrote:

> OTOH I wonder how a formal (regex?) FORTRAN lexer grammar could look like?
>
> [I've written Fortran 77 parsers.  It was quite context sensitive, particularly
> deciding whether a statement was an assignment or something else. e.g.
>
>  FORMAT(I4) = 42
>  DO 10 I = 1.23   (oops)
>
> Modern Fortran no longer ignores spaces which makes lexing a lot easier. -John]

Fortran supports two forms.  Fixed source form is what might be called
the legacy form, where spaces are ignored.  Spaces are significant for
free source form.  See Section 6.3 of the Fortran 2018 standard (ie,
N2146.pdf).

So, yes, a Fortran compiler has two lexer/parsers.

--
steve

[toc] | [prev] | [next] | [standalone]

#2328

On 21/05/2019 8:14 AM, Hans-Peter Diettrich wrote:
> ...
> OTOH I wonder how a formal (regex?) FORTRAN lexer grammar could look like?
>
> DoDi

IMHO, statement classification with a DFA isn't technically feasible
in fixed form due to the labeled DO statements. In all other cases I
think that a ")=" or "]=" outside a literal character constant implies
an assignment statement, which can be matched by a DFA.

In addition, fixed form requires some filtering for spaces and each
form distinct filtering for continuation patterns. Of course, there are
more details. That explained see ie the file OMP_Fortran_Scanner.txt at:
https://github.com/drikosev/Fortran

Ev. Drikos

-----------------------------------------------------------------------
PS: still, the generated tool fails ie to parse the following code:

$ cat doi.f
        do 10  J =(((((1))))),2
        do 10 (I)=1,2
10        print *, "hello world"
        end



> [I've written Fortran 77 parsers.  It was quite context sensitive,
> particularly
> deciding whether a statement was an assignment or something else. e.g.
>
> FORMAT(I4) = 42
   Still, we've the hard to parse optional commas in format items.

> DO 10 I = 1.23   (oops)
>
> Modern Fortran no longer ignores spaces which makes lexing a lot easier.
> -John]

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web