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

<c><lexing>
Why can C not be lexed without resolving identifiers?
CC BY-SA 4.0
2023-06-29T14:32:15.253Z
It would help if you linked to or otherwise referenced a source which makes this claim.
kaya3
CC BY-SA 4.0
2023-06-29T15:24:11.997Z
@kaya3-supportthestrike I found at least two accepted answers on this site that suggest as much: [1](https://langdev.stackexchange.com/a/1042/15) [2](https://langdev.stackexchange.com/a/1697/15)
Bbrk24
<p>This is my best guess because I haven't looked deeply into this issue. If an expert has a better answer, go with that.</p>
<p><strong>You are correct</strong> that the lexer could lex things like that and not need context.</p>
<p>But that has consequences for the parser.</p>
<p>The parser can no longer assume asterisk means multiplication. It can no longer assume an identifier is for a variable.</p>
<p>Losing these assumptions means that the <em>parser</em> becomes context-sensitive. More importantly, it means that the parser cannot have only one token of lookahead.</p>
<p>In fact, I think in C's case, it could be infinite lookahead, but I'm not sure.</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-06-29T12:20:01.327Z
2023-06-29T12:20:01.327Z
Gavin D. Howard
CC BY-SA 4.0
2023-06-29T12:37:04.170Z
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.
Bbrk24
CC BY-SA 4.0
2023-06-29T13:12:51.890Z
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.
Gavin D. Howard
CC BY-SA 4.0
2023-06-29T13:22:54.713Z
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.
Bbrk24
CC BY-SA 4.0
2023-06-29T13:31:26.210Z
@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.
Gavin D. Howard
CC BY-SA 4.0
2023-06-30T16:56:38.897Z
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.
jpa
<p>Here's one way of looking at it.</p>
<p>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.</p>
<p>The program flow is:</p>
<ol>
<li>The lexer uses its magic to figure out which chunk of code to run.</li>
<li>That code runs.</li>
<li>The parser uses its magic to figure out which chunk of code to run.</li>
<li>That code runs.</li>
</ol>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-06-30T21:47:56.730Z
2023-06-30T21:47:56.730Z
benrg
<p>It all depends on what your parser needs from your lexer.</p>
<p>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 <em>types</em> of the tokens, it needs information from the parser.</p>
<p>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.</p>
<p>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 <em>means</em>.</p>
<p>That's it in general.  There are too many use-cases, each depending on language design and features, to go into much more detail.</p>

CC BY-SA 4.0
2023-06-30T16:21:32.933Z
2023-06-30T20:40:51.240Z
2023-06-30T20:40:51.240Z
RLWatkins
<p>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.</p>
<hr />
<p>This is generally known as the &quot;<a href="https://en.wikipedia.org/wiki/Lexer_hack" rel="noreferrer">lexer hack</a>&quot;, or &quot;typedef-name: identifier&quot; problem. In short, given the expression
<code>(A)*B</code>,
it could mean either
<code>(A) * (B)</code>
or
<code>(A) (*B)</code>: a multiplication or a cast — noting that <code>B</code> could be an arbitrary expression. Similarly,</p>
<pre class="lang-c prettyprint-override"><code>X (Y);
</code></pre>
<p>could be either a declaration of variable <code>Y</code> with type <code>X</code>, or a function call to <code>X</code>.</p>
<p>While your <code>[OpenParen, Identifier(&quot;a&quot;), CloseParen, Asterisk, Identifier(&quot;b&quot;)]</code> classification is fine generally, the C grammar has two separate terminals &quot;identifier&quot; and &quot;typedef-name&quot;, and the <code>a</code> 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.</p>
<p>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 &quot;lexer hack&quot;). It also has to handle scopes, because you can redeclare <code>int A;</code> inside a function and change its class too (or, pathologically, <code>A A = (A)*b; A x = (A)*c;</code>; 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.</p>
<p>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 <em>the</em> C compiler.</p>
<p>Strictly speaking, you don't need to <em>resolve</em> identifiers, only know which class they're in. It doesn't matter which <code>A</code> variable you're talking about at this stage, that only comes later.</p>
<hr />
<p>On the other hand, though, <strong>yes, it's possible to do this all in the parser</strong>. 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.</p>
<p>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.</p>
<p>&quot;Context-sensitive lexing&quot; 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 <em>grammar</em> 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.</p>

CC BY-SA 4.0
2023-06-29T21:13:34.697Z
2023-06-29T21:42:40.093Z
2023-06-29T21:42:40.093Z
Michael Homer
CC BY-SA 4.0
2023-06-30T17:23:51.363Z
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.
supercat
# Why can C not be lexed without resolving identifiers?
Posted by: username_0 on 2023-06-29
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(*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?
**Tags:** c lexing
> **Comments:**
> **username_1**: It would help if you linked to or otherwise referenced a source which makes this claim.  
> **username_0**: @kaya3-supportthestrike I found at least two accepted answers on this site that suggest as much: [1](https://langdev.stackexchange.com/a/1042/15) [2](https://langdev.stackexchange.com/a/1697/15)  
---
## 4 answers
### Answer by username_6 on 2023-06-29. Score: 16 | Accepted answer
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.
> **Comments:**
> **username_7** (2023-06-30): 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.  
---
### Answer by username_2 on 2023-06-29. Score: 8
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.
> **Comments:**
> **username_0** (2023-06-29): 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.  
> **username_2** (2023-06-29): 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.  
> **username_0** (2023-06-29): 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.  
> **username_2** (2023-06-29): @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.  
> **username_3** (2023-06-30): 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.  
---
### Answer by username_5 on 2023-06-30. Score: 3
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.
---
### Answer by username_4 on 2023-06-30. Score: 2
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.
---
