Proper separation between lexing and parsing

Question

I am currently writing a parser which, given a source file, turns it into an AST of some language, respecting the idiomatic process of lexing and then parsing using well-known parser generators (think lex and yacc). However, I am unsure as how to properly distinguish which steps should happen during lexing and which during parsing.

Consider the statement int x = 0xFFFFFFFF;. I am unsure as how to correctly lex the value. Should I convert it to an integer at lex time, therefore lexing INT[-1] or let the parser deal with this, lexing something akin to HEX_INT[0xF..]?

Alternatively, consider the statement char c = '\u0048'. Should the parser convert this to the properly UTF-8 encoded sequence or pass the encoded character along?

Any guidelines or recommmendation on correctly drawing the line between parsing and lexing would prove very helpful.

Answer 1

The distinction between lexing and parsing is just a matter of convenience. As such, do whatever is convenient for your problem.

In particular, it is never necessary to use a lexer. In principle, a parser could just as well work on a per-character basis instead of a per-token basis. There are languages that can't be parsed with an ordinary lexer (e.g. anything with contextual keywords), but if you can use one, the memory usage of the parser tends to be lower (since there are fewer tokens than characters), and the grammar tends to be simpler (since the token grammar is handled by the lexer, and comments, insignificant whitespace, etc. are usually eliminated by the lexer).

Regarding conversion of literals, this depends on the language. There are languages where literals don't have an inherent type (e.g. in Haskell 2 can be any numeric type, depending on context). There are languages with user-defined literal parsing (e.g. C++). There are languages where strings can contain interpolated code or locale-sensitive casing operators. All of these are problems that can't be solved by the lexer, and will have to be handled at another stage of the parser.

For a simple C-like language, all of those issues don't exist, and a lexer could convert the values directly. But should we?

A token is usually a tuple or record (type, location, value), where the value is the corresponding lexed string. The value may be empty where the string is useless, e.g. for keywords or operators. If the value is a string for some token-types and an integer for other token-types, juggling these different types can become awkward and error-prone, especially if your parser is implemented in a language like C (you'd have to use unions!). It would then be better to convert the values in the parser, immediately before AST construction. This is of course not an issue when the host language uses dynamic typing, or if the token-types are represented as distinct types in the host language.

Another consideration is the quality of error messages. Imagine that, for some reason, a user writes 0.5E3. During parsing you encounter a problem, like floating point numbers not being allowed in that syntactic context. Would your error message report the offending token as 0.5E3 or 500.0? Similar with numbers in hex, octal, or binary. Also very important when strings/characters contain non-printable characters, soft hyphens, or Unicode lookalikes (homographs). By converting the literals early, you are throwing information about the exact formatting away, but this information may be very helpful to a confused user. This is not a huge issue (especially when your error message quotes the line containing the error and points out the exact error location), but it's something to consider. Ideally you can show both – the original formatting and a normalized form.

Answer 2

For the first point - it is a tradeoff between simplicity and power. In most languages, a hex integer literal and a decimal integer literal are exactly equivalent, so translating both into a general integer token at the lexing stage allows you to keep the numbers of tokens down, and simplify the grammar.

On the other hand, a fancy IDE might show hex versus decimal literals with different coloring, and have options like "convert decimal into hex" and vice versa. This requires the distinction to be present in the AST, so you have to keep them as distinct token types.

For the second point, it will depend on the language, since there are different ways of handling escapes. In Java unicode escapes (whether inside or outside strings) must be resolved before tokenization, so

int\u0020x 

should be parsed the same way as:

 int x 

But in say JavaScript, they must be resolved after tokenization (and they are only allowed inside string literals).

In some languages, the meaning of characters inside a string depends on the quoting used. Eg. Python r"\n" is a different string than "\n". Since the quotes themselves are not part of the string you pass on, the easiest solution is to resolve the escapes at the lexing step where you know the quotes used, so you only need a single string token type. But again, you might want keep the distinction in the AST for tool support.

Answer 3

I would not say it is as arbitrary a distinction as the accepted answer says.

Lexing or tokenizing does not recognize semantics or relations. It just lays out all the items (tokens) for you, for easy access, filtering out irrelevant things. In a computer language the irrekevant things could be whitespace or the difference in casing or the choice for one of a series of statements that are equivalent. It recognizes keywords and constructs but does not validate.

You can lex in parallel, each file independent from the next. You can not parse in parallel, you would have to know where to start and recognize dependencies. When you parse you should know where you are and what you are doing.

Tokenization could succeed, finding only valid constructs and then your parser could find it is all bogus.

Lexing collects, parsing interprets.