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

Groups > comp.programming > #9064 > unrolled thread

Why have a separate lexer instead of parsing 'all the way down'?

Back to article view | Back to comp.programming

Contents

  Why have a separate lexer instead of parsing 'all the way down'? luser droog <mijoryx@yahoo.com> - 2018-07-28 16:11 -0700
    Re: Why have a separate lexer instead of parsing 'all the way down'? "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2018-07-29 10:06 +0200
    Re: Why have a separate lexer instead of parsing 'all the way down'? Richard Heathfield <rjh@cpax.org.uk> - 2018-07-29 12:19 +0100
      Re: Why have a separate lexer instead of parsing 'all the way down'? Chad <cdalten@gmail.com> - 2018-07-30 09:02 -0700

#9064 — Why have a separate lexer instead of parsing 'all the way down'?

I've been doing some scattered readings lately in the realm of parsing
and the two major examples I've been looking at are Meta II (and TreeMeta)
which has special handling for terminals like $ID, $ST (string), and $NUM,
ie. isolated lexical analysis functions; and parser combinators which
(in the examples I've seen) just use parsers all the way down, ie. the
lexical analysis of building tokens uses the same mechanisms as the 
syntactic analysis of the token arrangement uses.

What are the considerations for preferring to have a separate lexer or not?
It seems /parsimonious/ (!) to use parsers all the way down, but lexing is
"a simpler job" so it also makes sense to wish for a more specialized tool.
Does the difference depend upon the details of the language you wish to
parse? Is the decision different if there are 2 or 3 types of tokens vs.
30 to 40?

I'd be interested in hearing any thoughts one way or the other, hoping that
the topic is sufficiently esoteric that flame wars are unlikely and any 
strongly held opinions have at least some entertaining anecdote behind them.

[toc] | [next] | [standalone]

#9065

On 2018-07-29 01:11, luser droog wrote:
> I've been doing some scattered readings lately in the realm of parsing
> and the two major examples I've been looking at are Meta II (and TreeMeta)
> which has special handling for terminals like $ID, $ST (string), and $NUM,
> ie. isolated lexical analysis functions; and parser combinators which
> (in the examples I've seen) just use parsers all the way down, ie. the
> lexical analysis of building tokens uses the same mechanisms as the
> syntactic analysis of the token arrangement uses.
> 
> What are the considerations for preferring to have a separate lexer or not?
> It seems /parsimonious/ (!) to use parsers all the way down, but lexing is
> "a simpler job" so it also makes sense to wish for a more specialized tool.
> Does the difference depend upon the details of the language you wish to
> parse? Is the decision different if there are 2 or 3 types of tokens vs.
> 30 to 40?
> 
> I'd be interested in hearing any thoughts one way or the other, hoping that
> the topic is sufficiently esoteric that flame wars are unlikely and any
> strongly held opinions have at least some entertaining anecdote behind them.

Of course there will be flame wars. There are people who like formal 
grammars who consequently like lexers. And there are people like me who 
consider grammars useless and see no technical reason to have lexers, 
tokenizers etc, while see many good reasons not to have this mess from 
the software architecture POV.

Software techniques hugely evolved since 70's. We know how to go to the 
semantic analysis in just one hop. It is not magic not even rocket 
science anymore.

P.S. The only valid argument for formal grammars may be the issue of 
formal verification and proof. The problem with that is that the formal 
grammar language is far more complex for a human reader than any decent 
general purpose programming language. So the chance to get errors in the 
formal specification (grammar) is higher than for a hand-written 
implementation of a parser.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

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

#9066

On 29/07/18 00:11, luser droog wrote:
<snip>

> What are the considerations for preferring to have a separate lexer or not?

<snip>

> I'd be interested in hearing any thoughts one way or the other, hoping that
> the topic is sufficiently esoteric that flame wars are unlikely and any
> strongly held opinions have at least some entertaining anecdote behind them.


No anecdote, I'm afraid, and neither am I sufficiently animated about 
the topic to get all worked up by it.

But, for what it's worth, I prefer a separate lexing process on the 
rather pragmatic grounds that I find it easier to write easy code than I 
do to write difficult code. Ploughing through a stream looking for 
tokens and building them into a symbol chain for later parsing is a damn 
sight easier (for me, at least!) than trying to parse them as I go.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

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

#9067

Sometimes it's easier to build a debugger when the lexer is separated. Especially if the program has to decorate the abstract syntax tree using keywords prior to being fed into an interpreter that in turn executes the debugger.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web