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

Groups > comp.compilers > #2335 > unrolled thread

Re: Regular expressions in lexing and parsing

Back to article view | Back to comp.compilers

Contents

  Re: Regular expressions in lexing and parsing Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2019-06-17 08:37 -0400
    Re: Regular expressions in lexing and parsing Quinn Jackson <quinn.jackson@ieee.org> - 2019-06-18 11:56 -0700
      Re: Regular expressions in lexing and parsing Quinn Jackson <quinn.jackson@ieee.org> - 2019-06-18 12:57 -0700
      Re: Regular expressions in lexing and parsing Kaz Kylheku <847-115-0292@kylheku.com> - 2019-06-18 20:01 +0000
    Re: Regular expressions in lexing and parsing Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2019-06-18 18:43 -0400

#2335 — Re: Regular expressions in lexing and parsing

Hans-Peter Diettrich <DrDiettrich1@netscape.net> wrote:

> 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.

I definitely would not discount the use of formal grammars both for
lexing (i.e. formal regexes) and parsing and the use of tools.
When we did Yacc++, we specifically made our lexer syntax look like
our parser syntax (and used LR yacc-style productions extended with
regular expressions on the right hand side) to make the notation
formal, regular, and simple.  I would call that one of our successes.

One of the advantages of having a consistent notation and using it in
a formal manner is that often grammars can be taken almost verbatim
from a standard and the parts that are missing easily inferred.  It's
amazing how much most lexers *should* look like each other. And, that
was one of our goals to standardize some of the "tricks of the trade"
(or hacks if you prefer) so that they became part of the standard
lexicon and could be reused as languages evolved.

Not everyone needs PL/I style keywords, but it turns out they are more
useful than one would think for a dead language, so standardizing how
that is done turns it into less of a hack and allows better reasoning
about it. Same argument can be made for the different forms of
comments, ones that nest and ones that don't.  Nesting comments aren't
hard if your lexer actually can do LR lexing and not just regular
expressions.  However, the point is to gather such things together and
implement them in a standardized and verifiable way, so that there is
some level of formal correctness.

And, that would be my criticism of hand written recursive descent
parsers.  You can do amazing things with them, but you also can
produce an unmaintainable mess where no one is quite sure what is
legal and what is not.  Reading the source to the compiler is not the
solution to that problem.

Anyway, I just wanted to point out, that by doing the above when I sat
down to write the front end for the Intel Vmod project.  I took the
1995 Verilog standard and almost copied it verbatim as the source of
the lexer and parser.  It took about 2 days to do so, but when I was
done, I had a roughly working parser and after a couple of weeks it
was essentially fully debugged.  That's the advantage of using a
formal style grammar and tools. You get something that actually works
for some relatively obscure edge cases quite quickly and you can be
confident of it.  And, no it isn't just me that can do that, one our
first customers implemented SGML out of the box, the same way and I
cannot recall how many times I worked with customers implementing SQL.
There are some corner cases having to do with joins that are hard to
get right.  The main point is that when you are done, you have
something reasonably readable that you can have confidence in.

So, if someone were to seriously argue against formal grammars (and
formal lexing specs too), I would challenge them to prove their
contentions.

Yes, I can see that calling libPCRE with strings that have lots of
backreferences, assertions, fiddling with greedy v. non-greedy
operators etc. is not particularly maintainable.  However, a simple
lexer, with simple regular expressions following patterns that have
been shown to work in language after language is worth striving for
(and in many cases not that difficult).

I will let someone else have the soapbox now....

--
******************************************************************************
Chris Clark                  email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc.  Web Site: http://world.std.com/~compres
23 Bailey Rd                 voice: (508) 435-5016
Berlin, MA  01503 USA      twitter: @intel_chris

[toc] | [next] | [standalone]

#2337

On Tue, Jun 18, 2019 at 10:09 AM Christopher F Clark
<christopher.f.clark@compiler-resources.com> wrote:
>
> Hans-Peter Diettrich <DrDiettrich1@netscape.net> wrote:
>
> > 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.

To which Christopher F Clark
<christopher.f.clark@compiler-resources.com> responded in part:

> I definitely would not discount the use of formal grammars both for
> lexing (i.e. formal regexes) and parsing and the use of tools.
> When we did Yacc++, we specifically made our lexer syntax look like
> our parser syntax (and used LR yacc-style productions extended with
> regular expressions on the right hand side) to make the notation
> formal, regular, and simple.  I would call that one of our successes.

When it comes to adaptive grammars, since the terminal and
non-terminal sets can have items added and removed dynamically during
a parse, it makes a lot of sense to treat lexing and parsing as one
and the same thing. I would add that even AST traversal and decoration
can be included in this family, in practice. Treating them
orthogonally is, in my experience, less useful overall. It also makes
it much simpler in practice to read such grammars at their level of
intent.

Pertinent to Hans-Peter's quote above: right down to the whitespace is
a good thing. Especially when parsing something other than a recent
computer language, such as -- oh, I don't know -- English or some
other Natural Language. (Outside the scope of the margins of this
list, however.)

> So, if someone were to seriously argue against formal grammars (and
> formal lexing specs too), I would challenge them to prove their
> contentions.

I echo Chris's challenge.

> I will let someone else have the soapbox now....

Be careful what you wish for. ;-)

--
Quinn Jackson CSci MIScT SMACM SMIEEE FRSA

LinkedIn:           http://ca.linkedin.com/in/quinnjackson/
ResearchGate: http://researchgate.net/profile/Quinn_Jackson/
[I agree with the sentiment to use formal grammars for both lex and
parse, but it always has seemed to me that running them separately as
coroutines makes it easier to deal with comments and whitespace
without having to hang them on every token definition.  I realize that
the more context sensitive the language, the more it is likely to make
sense to combine them. -John]

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

#2338

On Tue, Jun 18, 2019 at 12:23 PM John wrote:
> [I agree with the sentiment to use formal grammars for both lex and
> parse, but it always has seemed to me that running them separately as
> coroutines makes it easier to deal with comments and whitespace
> without having to hang them on every token definition.  I realize that
> the more context sensitive the language, the more it is likely to make
> sense to combine them. -John]

The Meta-S system has a way to do that automatically. The "whitespace
rule" (__ws is the reserved name for it) also has two alias sequences
that make it simple to specify optional versus required whitespace (#@
and ## respectively):

some_rule ## some_other_rule // whitespace is not optional

some_rule #? "(" #? some_other_rule #? ")" // whitespace in all
positions is optional

Moreover, the definition of the __ws can be:

__ws ::= #notree #standard_whitespace; // defined as standard C type
whitespace, and don't stick it on the AST when recognized in the input

I have found that, while sometimes verbose, this explicit handling
makes the dynamic nature of the grammars far easier to implement at
the back-end. (At the cost of the human grammar author having to think
about whitespace more often than some would prefer.)

If I recall correctly, it was Hans-Peter Dietrich (the OP) who
convinced me a number of years back to include the ability to specify
certain tokens that did not need explicit whitespace around them in
the productions that use them. (The grammar compiler itself then takes
responsibility for inserting the appropriate whitespace operators
behind the scenes during compilation when those tokens are used.)

In the long run, this hybrid approach has offered the most
versatility, without being too cumbersome. (There are bigger dragons
to fight with adaptive systems that can modify their rules in
mid-parse.....)

--
Quinn Jackson CSci MIScT SMACM SMIEEE FRSA

LinkedIn:     http://ca.linkedin.com/in/quinnjackson/
ResearchGate: http://researchgate.net/profile/Quinn_Jackson/

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

#2339

On 2019-06-18, Quinn Jackson <quinn.jackson@ieee.org> wrote:
> On Tue, Jun 18, 2019 at 10:09 AM Christopher F Clark
><christopher.f.clark@compiler-resources.com> wrote:
>>
>> Hans-Peter Diettrich <DrDiettrich1@netscape.net> wrote:
>>
>> > 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.
>
> To which Christopher F Clark
><christopher.f.clark@compiler-resources.com> responded in part:
>
>> I definitely would not discount the use of formal grammars both for
>> lexing (i.e. formal regexes) and parsing and the use of tools.
>> When we did Yacc++, we specifically made our lexer syntax look like
>> our parser syntax (and used LR yacc-style productions extended with
>> regular expressions on the right hand side) to make the notation
>> formal, regular, and simple.  I would call that one of our successes.
>
> When it comes to adaptive grammars, since the terminal and
> non-terminal sets can have items added and removed dynamically during
> a parse, it makes a lot of sense to treat lexing and parsing as one
> and the same thing. I would add that even AST traversal and decoration
> can be included in this family, in practice. Treating them
> orthogonally is, in my experience, less useful overall. It also makes
> it much simpler in practice to read such grammars at their level of
> intent.

Separation of parsing into tokens (delimited by a regular grammar) and
phrase structure levels (recursive grammar) has the benefit that both
levels use only a single symbol of lookahead.

If everything is lumped into one (let's call it "holistic parsing"),
long lookahead and/or backtracking is required.

For instance, if we are parsing C that way, after we have seen the
character "d", we don't know whether we are looking at an identifier
or the start of the "default" keyword, and we still don't know that
after we have seen "de", "def", ..., "defa".  Only when we get to
"default", and then peek at the next character can we decide.

Even if we don't care about the lookahead technicalities, tokenizing a
language before analyzing its syntax is justifiable as a good
abstraction.

For instance, Lisp tokenizes everything into a nested data structure;
and then the actual grammar of phrases is analyzed on a data structure.
When the grammar is being analyzed, symbols are objects with an
identity; that identity is the basis for their equivalence rather than
the spelling of their names isn't the basis for their equivalence or
inequality any more.

Another way to justify tokenization is that the entities which are
delimited by tokenization correspond quite precisely to entities that
appear in the final abstract syntax tree (at least when it comes to
those which do appear).  What I mean is that even if we treat "how now
brown cow" with a holistic parser, if the four chunks "how", "now",
"brown" and "cow" are then recognizable in the abstract syntax tree, we
might as well have tokenized those items in the first place, because we
have effectively done it anyway. Our language has a concept of these
tokens.

Lastly, let's look at how natural human languages have layer divisions:
phonemes, morphemes and so on. We can analyze language phonetically
without caring about higher level syntax. It would be awkward to have to
give the syntax of a sentence in terms of phonemes, rather than entities
like "VP" (verb phrase) or "COMP" (complementizer); such a view would
likely impede our understanding more than promoting it.

--
TXR Programming Lanuage: http://nongnu.org/txr
Music DIY Mailing List:  http://www.kylheku.com/diy
ADA MP-1 Mailing List:   http://www.kylheku.com/mp1
[That default example doesn't seem like lookahead to me.  While you're
scanning the characters, you're in a merged state that might end up as
a keyword or an identifier, just like in any DFA lexer.  There may
well be other places where things are messier. -John]

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

#2340

First, Kaz Kylheku attributed some ideas to me that properly belong to
Quinn Jackson, who deserves credit for them, not me.

Second, I am agnostic on the lexer/parser split issue.  There is a
point in separating concerns and in Yacc++ we kept the lexer and
parser separate at run time although you can write one file that
defines both [and that's the default way we write grammars].  However,
the scanner-less parser people have had lots of success with blurring
that distinction.

Moreover, people like Terence Parr echo the sentiment Quinn expressed
at some level.  ANTLR uses the same language for traversing ASTs as it
does for parsing to create them in the first place.  I don't know
whether ANTLR also merges lexing and parsing, but it wouldn't surprise
me if it did.

However, clearly to have one notation that works for multiple phases
makes sense to some people.  And, while our lexer and parser in Yacc++
are separate run time objects, the notation used to create them is
unified [with a few small differences, e.g.  lexer features that are
missing from the parser and vice versa], but the general shape of
productions works for both.

But as our moderator said, there are advantages to keeping them
distinct (at least conceptually).  In particular, it is nice for the
lexer to drop certain tokens on the floor without ever sending them to
the parser.  We called those discard tokens.  Whitespace and comments
are typical examples of discard tokens.  Having them as tokens means
the lexer has a precise "formal" definition of them, but immediately
dropping them means that the parser is not burdened by specifying when
they are allowed.  By the way, it is *not* built in to Yacc++ which
tokens are discarded.  The grammar writer chooses which things are
irrelevant to parsing.  The ability to specify things which are lexed
but not parser is an important concept in getting the formalism right.
The details of how it is used to simplify the specification belong in
the hands of the grammar writer.

Further, to roughly match what Quinn was mentioning, we also have the
concept of "ignored" tokens (and non-terminals).  These items are can
be used in the grammar at places where they are required, but also
will effectively be passed over by the parser when used in other
places.  (For example, if you made a newline token that was ignored,
you could use it to mark places in the grammar where things must be at
the start of a line.)  The lexer doesn't discard these and we modify
the parser tables so that they don't impact it in those places when it
isn't required.  A slightly different formalism to deal with a
slightly different problem, but the mechanism is standardized so that
it can be made rigorous.

(I don't recall whether we have away of saying where ignored tokens
are disallowed.  It certainly makes sense to add such a feature. We
probably rely on syntactic predicates currently for that issue.)

You can see the same thing occurring with ASTs.  You don't put every
token into the AST, you put only the information that is semantically
relevant.  And whether a token is semantically relevant can depend
upon context.  Still by including only the relevant information the
consumer of an AST, be it a separate phase, or a visitor pattern, only
sees the information that is relevant and is not burdened with
extraneous information.  Now, whether you code that up separately or
write it as part of one spec is a design decision, but the separation
of concerns, which is trivially enforced if the two things are
separate run time objects (passes, phases, coroutines, etc.) is
useful.  Dropping the irrelevant information is as important as
keeping the relevant bits.

In fact, you can even see that point carried farther in systems like
LLVM, which has two different IRs, one machine independent and one
machine dependent.  Again, that forces the separation of concerns.
There are things that should be done in a machine independent manner
(and thus with that IR) and other things that must be done in a
machine dependent manner (and thus with the other IR).  There are
details that the machine dependent IR carries that the independent one
is not aware of.  I suspect the inverse of that is true also.

The point being, separation of concerns is good.  Don't complicate
things with irrelevant details.  Formalism is good.  Use notation to
make things simpler to understand without reading the implementation.
And, finally, there are many ways to achieve the same goals. However,
no matter which way one chooses, building a robust infrastructure that
supports it makes it more sound and more reliable.

On Mon, Jun 17, 2019 at 8:37 AM Christopher F Clark
<christopher.f.clark@compiler-resources.com> wrote:
>
> Hans-Peter Diettrich <DrDiettrich1@netscape.net> wrote:
>
> > 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.
>
> I definitely would not discount the use of formal grammars both for
> lexing (i.e. formal regexes) and parsing and the use of tools.
> When we did Yacc++, we specifically made our lexer syntax look like
> our parser syntax (and used LR yacc-style productions extended with
> regular expressions on the right hand side) to make the notation
> formal, regular, and simple.  I would call that one of our successes.
>
> One of the advantages of having a consistent notation and using it in
> a formal manner is that often grammars can be taken almost verbatim
> from a standard and the parts that are missing easily inferred.  It's
> amazing how much most lexers *should* look like each other. And, that
> was one of our goals to standardize some of the "tricks of the trade"
> (or hacks if you prefer) so that they became part of the standard
> lexicon and could be reused as languages evolved.
>
> Not everyone needs PL/I style keywords, but it turns out they are more
> useful than one would think for a dead language, so standardizing how
> that is done turns it into less of a hack and allows better reasoning
> about it. Same argument can be made for the different forms of
> comments, ones that nest and ones that don't.  Nesting comments aren't
> hard if your lexer actually can do LR lexing and not just regular
> expressions.  However, the point is to gather such things together and
> implement them in a standardized and verifiable way, so that there is
> some level of formal correctness.
>
> And, that would be my criticism of hand written recursive descent
> parsers.  You can do amazing things with them, but you also can
> produce an unmaintainable mess where no one is quite sure what is
> legal and what is not.  Reading the source to the compiler is not the
> solution to that problem.
>
> Anyway, I just wanted to point out, that by doing the above when I sat
> down to write the front end for the Intel Vmod project.  I took the
> 1995 Verilog standard and almost copied it verbatim as the source of
> the lexer and parser.  It took about 2 days to do so, but when I was
> done, I had a roughly working parser and after a couple of weeks it
> was essentially fully debugged.  That's the advantage of using a
> formal style grammar and tools. You get something that actually works
> for some relatively obscure edge cases quite quickly and you can be
> confident of it.  And, no it isn't just me that can do that, one our
> first customers implemented SGML out of the box, the same way and I
> cannot recall how many times I worked with customers implementing SQL.
> There are some corner cases having to do with joins that are hard to
> get right.  The main point is that when you are done, you have
> something reasonably readable that you can have confidence in.
>
> So, if someone were to seriously argue against formal grammars (and
> formal lexing specs too), I would challenge them to prove their
> contentions.
> Yes, I can see that calling libPCRE with strings that have lots of
> backreferences, assertions, fiddling with greedy v. non-greedy
> operators etc. is not particularly maintainable.  However, a simple
> lexer, with simple regular expressions following patterns that have
> been shown to work in language after language is worth striving for
> (and in many cases not that difficult).
>
> I will let someone else have the soapbox now....

--
******************************************************************************
Chris Clark                  email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc.  Web Site: http://world.std.com/~compres
23 Bailey Rd                 voice: (508) 435-5016
Berlin, MA  01503 USA      twitter: @intel_chris
------------------------------------------------------------------------------

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web