Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Should I use a lexer when using a parser combinator library like Parsec?

When writing a parser in a parser combinator library like Haskell's Parsec, you usually have 2 choices:

  • Write a lexer to split your String input into tokens, then perform parsing on [Token]
  • Directly write parser combinators on String

The first method often seems to make sense given that many parsing inputs can be understood as tokens separated by whitespace.

In other places, I have seen people recommend against tokenizing (or scanning or lexing, how some call it), with simplicity being quoted as the main reason.

What are general trade-offs between lexing and not doing it?

like image 892
nh2 Avatar asked Mar 05 '13 05:03

nh2


People also ask

What is the difference between a lexer and a parser?

A lexer is a software program that performs lexical analysis. ... A parser goes one level further than thelexer and takes the tokens produced by the lexer and tries to determine if proper sentences have been formed. Parsers work at the grammatical level, lexerswork at the word level.

Are parser combinators slow?

Parser combinators are generally slower than a hand-written or code-generated parser. That's somewhat innate due to the overhead of “threading” (for lack of a better word) your control flow through many function calls.

What is parser Haskell?

Parser combinators are known to be simple to use without requiring external tools or too many concepts to learn. That is, they are ordinary Haskell constructors that can easily be combined and returned with other parsers because of their nature as functions.


1 Answers

The most important difference is that lexing will translate your input domain.

A nice result of this is that

  • You do not have to think about whitespace anymore. In a direct (non-lexing) parser, you have to sprinkle space parsers in all places where whitespace is allowed to be, which is easy to forget and it clutters your code if whitespace must separate all your tokens anyway.

  • You can think about your input in a piece-by-piece manner, which is easy for humans.

However, if you do perform lexing, you get the problems that

  • You cannot use common parsers on String anymore - e.g. for parsing a number with a library Function parseFloat :: Parsec String s Float (that operates on a String input stream), you have to do something like takeNextToken :: TokenParser String and execute the parseFloat parser on it, inspecting the parse result (usually Either ErrorMessage a). This is messy to write and limits composability.

  • You have adjust all error messages. If your parser on tokens fails at the 20th token, where in the input string is that? You'll have to manually map error locations back to the input string, which is tedious (in Parsec this means to adjust all SourcePos values).

  • Error reporting is generally worse. Running string "hello" *> space *> float on wrong input like "hello4" will tell you precisely that there is expected whitespace missing after the hello, while a lexer will just claim to have found an "invalid token".

  • Many things that one would expect to be atomic units and to be separated by a lexer are actually pretty "too hard" for a lexer to identify. Take for example String literals - suddenly "hello world" are not two tokens "hello and world" anymore (but only, of course, if quotes are not escaped, like \") - while this is very natural for a parser, it means complicated rules and special cases for a lexer.

  • You cannot re-use parsers on tokens as nicely. If you define how to parse a double out of a String, export it and the rest of the world can use it; they cannot run your (specialized) tokenizer first.

  • You are stuck with it. When you are developing the language to parse, using a lexer might lead you into making early decisions, fixing things that you might want to change afterwards. For example, imagine you defined a language that contains some Float token. At some point, you want to introduce negative literals (-3.4 and - 3.4) - this might not be possible due to the lexer interpreting whitespace as token separator. Using a parser-only approach, you can stay more flexible, making changes to your language easier. This is not really surprising since a parser is a more complex tool that inherently encodes rules.

To summarize, I would recommend writing lexer-free parsers for most cases.

In the end, a lexer is just a "dumbed-down"* parser - if you need a parser anyway, combine them into one.


* From computing theory, we know that all regular languages are also context-free languages; lexers are usually regular, parsers context-free or even context-sensitve (monadic parsers like Parsec can express context-sensitiveness).

like image 66
nh2 Avatar answered Oct 19 '22 16:10

nh2