17
$\begingroup$

I’ve seen it said before that C and C++ cannot be lexed without resolving identifiers to an extent. A common example is (a)*b, which could be either multiplication a * b or dereference and cast static_cast<a>(*b) depending on what a is. I understand that this kind of thing cannot be parsed without resolving a, but why does the lexer need it? My understanding is that lexing is tokenization, and this is pretty unambiguously [OpenParen, Identifier("a"), CloseParen, Asterisk, Identifier("b")] either way.

Is my understanding of the situation wrong, or is this just a bad example?

$\endgroup$
2
  • 1
    $\begingroup$ It would help if you linked to or otherwise referenced a source which makes this claim. $\endgroup$
    – kaya3
    Jun 29, 2023 at 14:32
  • 1
    $\begingroup$ @kaya3-supportthestrike I found at least two accepted answers on this site that suggest as much: 1 2 $\endgroup$
    – Bbrk24
    Jun 29, 2023 at 15:24

4 Answers 4

16
$\begingroup$

The short answer is yes, you could do it all in the parser (lexers are optional), but historically it's been easier the other way. It's mostly a historical accident that this all exists at all.


This is generally known as the "lexer hack", or "typedef-name: identifier" problem. In short, given the expression (A)*B, it could mean either (A) * (B) or (A) (*B): a multiplication or a cast — noting that B could be an arbitrary expression. Similarly,

X (Y);

could be either a declaration of variable Y with type X, or a function call to X.

While your [OpenParen, Identifier("a"), CloseParen, Asterisk, Identifier("b")] classification is fine generally, the C grammar has two separate terminals "identifier" and "typedef-name", and the a token needs to be one or the other. The two can be used in different contexts and lead to different productions, and you can't know which names are types and which are ordinary identifiers without having parsed the code up to that point. There are a lot of places where this comes up, not just these cultivated brief ambiguous examples.

The usual solution to this is that the parser keeps a table of typedefs it's seen, and feeds that back to the lexer as it goes (that's the "lexer hack"). It also has to handle scopes, because you can redeclare int A; inside a function and change its class too (or, pathologically, A A = (A)*b; A x = (A)*c;; you can come up with yet worse cases). This is a well-known foible of the language, and probably not one that would be included if designed today.

The parser wants to know whether something is a type or not for a couple of reasons. One is simply that the C reference grammar is defined this way, so if you want to align with it for reliability then you want to match that. Another is the token lookahead of conventional parsers: you want the lexical class to be known and fixed so that you know definitively which production to enter. A Yacc-generated LALR parser relies on this, and that's what was used for the C compiler.

Strictly speaking, you don't need to resolve identifiers, only know which class they're in. It doesn't matter which A variable you're talking about at this stage, that only comes later.


On the other hand, though, yes, it's possible to do this all in the parser. At the very least, because you don't need a lexer at all — a scannerless parser wouldn't have this. A generalised left-recursive parser would just take both parses and subsequently discard the one that didn't work out, so the token class wouldn't matter. A context-sensitive parser would just deal with this innately.

You could also build a parser that used the lookup table internally to choose between two simulated lexical classes whenever the question came up. Production implementations of C today often use hand-written parsers that handle these issues internally, and don't necessarily use the lexer hack.

"Context-sensitive lexing" is a bit of a foggy category, since formal context-sensitivity isn't really about lexing. This is more one foundational implementation strategy leaking out. The grammar of C is context-sensitive, and so the parser-lexer combination needs to handle (a small amount of) context sensitivity. Exactly where that handling is placed is an implementation detail. Historically, it's been put on the lexer side, but it's not a hard requirement.

$\endgroup$
1
  • 3
    $\begingroup$ In the 1974 dialect of C, before the addition of typedef, if an identifier was followed by an asterisk and not preceded by the keyword struct, the asterisk couldn't be anything other than a multiplication operator. If uses of a typedef identifier had to be preceded by some reserved word, in a manner similar to struct tags being preceded by the keyword struct, that could have fixed a lot of problems with the language and parsing. $\endgroup$
    – supercat
    Jun 30, 2023 at 17:23
8
$\begingroup$

This is my best guess because I haven't looked deeply into this issue. If an expert has a better answer, go with that.

You are correct that the lexer could lex things like that and not need context.

But that has consequences for the parser.

The parser can no longer assume asterisk means multiplication. It can no longer assume an identifier is for a variable.

Losing these assumptions means that the parser becomes context-sensitive. More importantly, it means that the parser cannot have only one token of lookahead.

In fact, I think in C's case, it could be infinite lookahead, but I'm not sure.

This makes the parser more complicated, but it could also slow down the parser quite a bit. You might even get a worse Big O.

Giving the lexer access to the symbol table and letting it split out the different types of identifiers into different token types seems like a simpler solution.

$\endgroup$
5
  • 1
    $\begingroup$ Huh, I hadn't considered that. I had heard that Kotlin needs infinite lookahead to resolve generics properly, but I didn't think about the implications for compiler performance, nor did I realize that applied to C. $\endgroup$
    – Bbrk24
    Jun 29, 2023 at 12:37
  • $\begingroup$ Yeah, it wasn't obvious to me either. I had to think about it. But I could still be wrong, so don't take my word for it. $\endgroup$ Jun 29, 2023 at 13:12
  • 1
    $\begingroup$ I'd be interested to see a pathological case where you need a very long lookahead -- like a C garden-path expression, if you will. $\endgroup$
    – Bbrk24
    Jun 29, 2023 at 13:22
  • 2
    $\begingroup$ @Bbrk24 I'm not an expert, but I presume you could just chain the example you gave, like (a)*(b)*(c)*(d)*(e)... The question is: which are dereferences, which are multiplications, which are casts, and is that clustermess even valid? And that example may not be improbable in real code either because of macro expansion. $\endgroup$ Jun 29, 2023 at 13:31
  • 1
    $\begingroup$ It doesn't seem that would necessarily need long lookahead - when the parser sees [OpenParen, Identifier("a"), CloseParen] it knows whether a is a type or a variable. Normally it would feed that information to the lexer. The parser would need to keep more state to understand whether * has an operand on its left side or not, but that doesn't depend on what comes later on the line. $\endgroup$
    – jpa
    Jun 30, 2023 at 16:56
3
$\begingroup$

It all depends on what your parser needs from your lexer.

If all it wants is a stream of language tokens, you're right: the lexer doesn't need to know that stuff. If you want it to identify the types of the tokens, it needs information from the parser.

Which of those you need depends on the way you write the BNF for your parser. For BASIC-like languages, the parser doesn't need to know what kind of identifiers it's reading. For C-like languages, the parser needs to know how the identifier was used in context.

Sometimes this is solved by doing two compilation passes on each source file. The first lexes out the tokens, parses the declarations, and classifies the tokens so that in the second pass it can tell the parser what each identifier means.

That's it in general. There are too many use-cases, each depending on language design and features, to go into much more detail.

$\endgroup$
0
2
$\begingroup$

Here's one way of looking at it.

Lexer and parser generators normally take as input a list of rules, and each rule is associated with a chunk of arbitrary code that runs when the rule matches.

The program flow is:

  1. The lexer uses its magic to figure out which chunk of code to run.
  2. That code runs.
  3. The parser uses its magic to figure out which chunk of code to run.
  4. That code runs.

Neither the lexer nor the parser knows how to look up an identifier in a hash table to figure out whether it's a typedef or not. You need to do that in your own code. The point at which you need to do it is after lexing and before parsing, i.e., in step 2.

Technically, the classification of identifiers isn't part of the lexing process. The lexing process has already completed when the code in step 2 runs. That code just happens to be located in the lexer definition file.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .