7

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.

4
  • Both of your examples are pure C code. If you are doing this for personal education, to learn about parsing, translation, and compiling, you might want to consider parsing a language that is easier to parse than C. PASCAL (and its successors) were specifically designed to be both robust and easy to parse in one pass with minimal lookahead and backtracking. If you are doing this for others to use, you might want to ask yourself if the world needs Yet Another Weird C-Like Language. May 3, 2017 at 15:47
  • @JohnR.Strohm The actual language I am parsing is a LISP-derivative with few builtins and a rather simple grammar, the C code was just the quickest way to exemplify my problem.
    – ThreeFx
    May 3, 2017 at 16:22
  • 1
    @ThreeFx For a Lisp dialect, a hand-written parser is probably going to be much simpler than using a lexer+parser generator.
    – amon
    May 3, 2017 at 16:29
  • @ThreeFx, if you're parsing a LISP-like language, you're crazy if you do it by any means other than embedding it in LISP. May 3, 2017 at 19:12

3 Answers 3

10

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.

3
  • 1
    Actually, your error message handler should display the actual text of the line where the problem apparently occurred, maybe with traceback text lines, with an up-arrow and a note that "the error occurred HERE ^^^^^". Of course, this is the PASCAL way of doing things, which is by definition anathema to C fans. May 3, 2017 at 15:49
  • @JohnR.Strohm Agreed, and many languages/compilers do provide such user-friendly error messages. I try to imitate Rust's message style for any parsers I write. But many tools I use are far behind, notably GCC and Perl.
    – amon
    May 3, 2017 at 15:56
  • that would seem to suggest that PASCAL was far ahead of its time, as it had that error message style from the beginning, back around 1972 (or even earlier). May 3, 2017 at 19:10
3

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.

2

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.