0

When writing a lexer/parser, why/when would an advised developer chose to define the tokens' types through an enumeration field/type hierarchy?

Image: Left: a Token class using a TokenType enumeration, right: an abstract Token class and its derivatives.


The closest question I've found here so far was Lexing: One token per operator, or one universal operator token? by Jeroen Bollen, but it seems to be more about the ideal deepth of the token type hierarchy.

As for my personal experience I've used Newtonsoft.Json's reader, which uses an enumeration, and I've read about C#'s Expression types, which seem to use a hierarchy, but also seem to be more than just tokens.

1

An enumeration is the classic/C-ish way to define tokens, but that doesn't make it extraordinarily good – precisely because it is difficult to keep track of associated values. A token might contain the value of a literal (e.g. number or string), and might also contain metadata such as character stream offsets, line number and column, ….

A sum type as in ML languages is vastly preferable: as compact as an enumeration + data field, but with proper type safety. Unfortunately C#, C++, and Java do not support proper sum types, so that we have to resort to a class hierarchy. This is not ideal (higher memory overhead, the class hierarchy can't be sealed), but it's usually better than the dynamic typing route where the token has a field for a nullable object.

Note that in the context of a token hierarchy of a parser, it is okay to downcast to specific token types. Alternatively, you can use the Visitor Pattern to match specific token types in a type-safe manner.

Nevertheless, I would generally advise against a deep token class hierarchy. Instead of introducing an abstract Break class, you might want to instead add methods/properties to the base Token type like IsBreak => false (and override in the subclasses). I'd possibly diverge from this in two cases:

  • for keyword tokens, as in this design each keyword will be its own class. It's much more comfortable if these keyword classes can have nearly empty bodies and just inherit any defaults from their base.
  • for binary/unary operators, since a parser is often only interested in whether a token is a binary operator rather than deciding which binary operator it is, e.g. when doing operator precedence parsing.

One alternative I want to mention for completeness is scannerless parsing where you don't have explicit tokens at all. Instead, lexing/tokenization would be directly integrated into the parser. While many parser generators require the tokens to be parsed in advance, e.g. PEG, Marpa, or ad-hoc techniques like Recursive Descent do not.

  • By "sum type", you mean Swift's enumerations with value/Kotlin's sealed classes? – Odepax Nov 7 '18 at 17:45
  • @Odepax Yes, exactly. Sum type, tagged union, variant record etc. all refer to the same concept, although Kotlin and Scala try to fit it into the class hierarchy concept (which is actually quite convenient!). Sum types were popularized by the ML language family, and are slowly becoming more mainstream (e.g. in Swift or Rust). – amon Nov 7 '18 at 17:51
  • "[...] enumeration is the classic/C-ish way [...]" Would the choice between the enumeration field and the hierarchy pathways be generally shifting from one to the other, like a new best practice? Or are there deeper reasons why one would go for putting "metadata" in the Token Reader (like what Newtonsoft.Json does) v.s. in individual Token objects? – Odepax Nov 7 '18 at 19:10
  • @Odepax Swift-style enumerations are strictly better than the other alternatives. The choice between a C-style enum or a class hierarchy depends on how those tookens will be used. If I'm feeding them into an existing parser, that parser is probably only interested in the token type, and enums are fine for that. If I'm using the tokens in my own code I'd prefer the class hierarchy because I can add convenience methods. I'd also prefer proper classes if the associated data differs a lot between token types. – amon Nov 7 '18 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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