<p>Do parsers typically operate on the entire array/list of tokens available in memory, or are the tokens often streamed one by one as they are recognized? What influences the decision?</p>

<implementation><parsing><tokens>
Do parsers typically need access to all tokens?
CC BY-SA 4.0
2023-11-28T23:16:32.903Z
Just as another data point, Edinburgh Prolog is notorious for requiring infinite lookahead. (ISO Prolog does not.)
Pseudonym
CC BY-SA 4.0
2024-01-10T04:55:07.410Z
Fun fact, since generics were added to C# 2, the parser requires unbounded lookahead to figure out how expressions of the form `A(B<C, D>(E))` should parse. Is that a call to `A` with arguments `B<C` and `D>(E)`, or a single argument that is a call to generic method `B<C, D>` with argument `E`? The heuristic which disambiguates these can require looking ahead arbitrarily many tokens past the initial `<`.
Eric Lippert
<blockquote>
<p>What influences the decision?</p>
</blockquote>
<p>Some languages cannot be lexed without also being parsed (or in the notable case of <a href="https://tex.stackexchange.com/a/151037">TeX</a>, cannot be lexed without also being <em>executed</em>). In this case, the only option is to lex lazily, because knowing where the next token boundary lies depends on feedback from the parser.</p>
<p>Generally this occurs when the tokenisation of a source text fragment depends on either the syntactic or semantic context in which it occurs. One example of this in conventional languages is determining whether the source fragment <code>&gt;&gt;</code> should be tokenised as a right-shift operator (in an expression) vs. two close-angle-brackets (in a generic type). There are multiple approaches to disambiguating this case, but one is to lex lazily and have the parser tell the lexer whether the current context is an expression or a type (see <a href="https://langdev.stackexchange.com/a/3027/89">here</a>).</p>

CC BY-SA 4.0
2023-11-22T18:37:20.560Z
2023-11-22T19:05:06.560Z
2023-11-22T19:05:06.560Z
kaya3
CC BY-SA 4.0
2023-11-24T09:07:18.463Z
TeX is an example of a language that was developed when the theory of scanning and parsing was much less developed. Shells or Tcl would be another one. The idea that you could almost completely redefine the language (using \active in TeX for example) and using macro expansion is from that time. Languages today use typically a more phased approach.
Christian Lindig
CC BY-SA 4.0
2023-11-24T18:40:31.160Z
@ChristianLindig I'm not convinced that your first sentence is very accurate... LR parsing (and in particular, LR(1) and LALR) was invented in the '60s. In fact, LR parsing was invented in the '60s by the creator of TeX, Donald Knuth. Also, potentially related to the discussion, Lisp-style macros go back to the '60s as well. On the other hand, TeX was created in the late '70s.
David Young
<p>There are handwritten LL(1) parsers that execute a tokenizer, deriving a single offending token, keeping track of the previous offending token and disambiguate ambiguous constructs such as ECMA 262 (the ECMAScript language) left side destructuring in arrow functions based on the AST.</p>
<pre class="lang-js prettyprint-override"><code>({}) =&gt; {};
({});
</code></pre>
<p>Typed dialects allow type annotations within the arrow function's signature, and these are converted to parameter bindings properly.</p>
<p>For complex qualified identifiers, a leftmost derivation, may need to be reinterpreted as another construct depending on production ambiguities. A conflicting postfix operator for instance also requires combining the parsing of different syntactic productions.</p>
<p>Here are ActionScript 3's qualified identifiers:</p>
<pre><code>*
q::x
(e)::x
q::[k]
protected::x
@x
o.(condition)
o.(e)::x
</code></pre>
<p>The conclusion is that languages like Java, JavaScript, TypeScript, and Lua do not need a collection of preprocessed tokens, but single token streaming, possibly with a track of the previous token.</p>

CC BY-SA 4.0
2023-11-22T23:42:20.957Z
2023-11-24T12:30:58.593Z
2023-11-24T12:30:58.593Z
Hydroper
<p>It depends on what language is being parsed and what tools are being used. Most parser generators implement popular algorithms (like LL(1) or LALR(1)) that require a grammar to need at most 1 token of lookahead, but add extensions (like precedence rules) that allow for parsing grammars that, strictly speaking, require more lookahead. But recursive descent parsers with backtracking allow for arbitrary lookahead. While people generally try to design grammars that only need 1 token of lookahead, many grammars require more (for instance, <a href="https://en.wikipedia.org/wiki/Parsing#/media/File:Parsing_a_C_program_that_needs_2_token_lookahead.svg" rel="nofollow noreferrer">C</a>). So I'm not sure what the typical parser does.</p>

CC BY-SA 4.0
2023-12-14T22:43:45.023Z
2023-12-14T22:43:45.023Z
Tsvi Benschar
<p>The &quot;lookahead&quot; is the number of tokens a parser needs to recognize a production. This number is a property of the grammar. Typical grammars for programming languages have a lookahead of one. The parser requests the next token from the scanner as it parses the input. In that sense, the parser does not operate on the sequence of all tokens but a much more limited context. The tokens already consumed are represented in the parser as the AST (abstract syntax tree) or whatever else the parser uses to represent the input.</p>
<p>Some grammars are ambiguous or parsers rely on backtracking. A popular example are Parsing Expression Grammars - here the parser needs to maintain  more tokens for backtracking. However, this is typically done by the parser and not the scanner. The scanner would still maintain the current position into the input and deliver the next token upon request.</p>

CC BY-SA 4.0
2023-11-22T09:25:24.163Z
2023-11-28T21:36:55.387Z
2023-11-28T21:36:55.387Z
Christian Lindig
CC BY-SA 4.0
2023-11-22T16:23:31.680Z
"Typical grammars" is maybe ambiguous here, as it may be understood as asserting that most programming languages have a grammar that requires no look-ahead, when in fact... look-ahead is quite common, at least absent grammar tricks/complex parsers.
Matthieu M.
CC BY-SA 4.0
2023-11-22T20:59:32.213Z
I wrote that a lookahead of one is common in programming languages; this is reflected in Yacc generating an LARL(1) parser.
Christian Lindig
CC BY-SA 4.0
2023-11-23T08:26:18.373Z
And how common is Yacc use in the mainstream? C and C++ requires a symbol table as far as I know. [C# requires backtracking](https://stackoverflow.com/questions/16928725/is-cs-lambda-expression-grammar-lalr1/16929127#16929127). I think Java, JavaScript & Python may be able to be parsed so? So far that's 3 out of 6, though, so I wouldn't say it's _common_....
Matthieu M.
CC BY-SA 4.0
2023-11-23T09:22:26.007Z
My argument is the other way round: Yacc implements LALR(1) parsers, as they are useful for programming languages https://en.wikipedia.org/wiki/Yacc. Clearly you can implement parsers not using Yacc. Name languages that need more lookahead, not languages that are not using Yacc. C is commonly parsed with a Yacc generated parser; the context sensitivity of typedef in C is a detail unrelated to lookahead.
Christian Lindig
CC BY-SA 4.0
2023-11-23T09:30:01.110Z
Wait, how do you parse C without a symbol table? How do you interpret `x * y` for example: it's a multiplication if `x` is a variable, but a variable declaration if `x` is a type! That's typically _not_ resolvable at the grammar level (though I guess it only requires look-back, not look-ahead).
Matthieu M.
CC BY-SA 4.0
2023-11-23T09:46:54.190Z
I did not claim that C can be parsed without a symbol table. I claimed C can be parsed with a Yacc-generated parser with limited lookahead: https://cil-project.github.io/cil/ parses C code using a Yacc grammar: https://sourceforge.net/p/cil/code/ci/master/tree/src/frontc/cparser.mly
Christian Lindig
CC BY-SA 4.0
2023-11-23T23:40:06.623Z
Small bit of additional context: you can convert any LL(N) parser into an LL(1) parser, for any fixed N, by converting the lookahead into "lookbehind" baked into the parser state. But if you have lookahead available, it's generally more efficient to use it, to the point that algorithms like ALL(*) often outperform LL(N). It's similar but different for LR family parsers.
CAD97
# Do parsers typically need access to all tokens?
Posted by: username_0 on 2023-11-22
Do parsers typically operate on the entire array/list of tokens available in memory, or are the tokens often streamed one by one as they are recognized? What influences the decision?
**Tags:** implementation parsing tokens
> **Comments:**
> **username_1**: Just as another data point, Edinburgh Prolog is notorious for requiring infinite lookahead. (ISO Prolog does not.)  
> **username_2**: Fun fact, since generics were added to C# 2, the parser requires unbounded lookahead to figure out how expressions of the form `A(B<C, D>(E))` should parse. Is that a call to `A` with arguments `B<C` and `D>(E)`, or a single argument that is a call to generic method `B<C, D>` with argument `E`? The heuristic which disambiguates these can require looking ahead arbitrarily many tokens past the initial `<`.  
---
## 4 answers
### Answer by username_4 on 2023-11-22. Score: 8 | Accepted answer
The "lookahead" is the number of tokens a parser needs to recognize a production. This number is a property of the grammar. Typical grammars for programming languages have a lookahead of one. The parser requests the next token from the scanner as it parses the input. In that sense, the parser does not operate on the sequence of all tokens but a much more limited context. The tokens already consumed are represented in the parser as the AST (abstract syntax tree) or whatever else the parser uses to represent the input.

Some grammars are ambiguous or parsers rely on backtracking. A popular example are Parsing Expression Grammars - here the parser needs to maintain more tokens for backtracking. However, this is typically done by the parser and not the scanner. The scanner would still maintain the current position into the input and deliver the next token upon request.
> **Comments:**
> **username_8** (2023-11-22): "Typical grammars" is maybe ambiguous here, as it may be understood as asserting that most programming languages have a grammar that requires no look-ahead, when in fact... look-ahead is quite common, at least absent grammar tricks/complex parsers.  
> **username_4** (2023-11-22): I wrote that a lookahead of one is common in programming languages; this is reflected in Yacc generating an LARL(1) parser.  
> **username_8** (2023-11-23): And how common is Yacc use in the mainstream? C and C++ requires a symbol table as far as I know. [C# requires backtracking](https://stackoverflow.com/questions/16928725/is-cs-lambda-expression-grammar-lalr1/16929127#16929127). I think Java, JavaScript & Python may be able to be parsed so? So far that's 3 out of 6, though, so I wouldn't say it's _common_....  
> **username_4** (2023-11-23): My argument is the other way round: Yacc implements LALR(1) parsers, as they are useful for programming languages https://en.wikipedia.org/wiki/Yacc. Clearly you can implement parsers not using Yacc. Name languages that need more lookahead, not languages that are not using Yacc. C is commonly parsed with a Yacc generated parser; the context sensitivity of typedef in C is a detail unrelated to lookahead.  
> **username_8** (2023-11-23): Wait, how do you parse C without a symbol table? How do you interpret `x * y` for example: it's a multiplication if `x` is a variable, but a variable declaration if `x` is a type! That's typically _not_ resolvable at the grammar level (though I guess it only requires look-back, not look-ahead).  
> **username_4** (2023-11-23): I did not claim that C can be parsed without a symbol table. I claimed C can be parsed with a Yacc-generated parser with limited lookahead: https://cil-project.github.io/cil/ parses C code using a Yacc grammar: https://sourceforge.net/p/cil/code/ci/master/tree/src/frontc/cparser.mly  
> **username_9** (2023-11-23): Small bit of additional context: you can convert any LL(N) parser into an LL(1) parser, for any fixed N, by converting the lookahead into "lookbehind" baked into the parser state. But if you have lookahead available, it's generally more efficient to use it, to the point that algorithms like ALL(*) often outperform LL(N). It's similar but different for LR family parsers.  
---
### Answer by username_3 on 2023-11-22. Score: 5
> What influences the decision?

Some languages cannot be lexed without also being parsed (or in the notable case of [TeX](https://tex.stackexchange.com/a/151037), cannot be lexed without also being *executed*). In this case, the only option is to lex lazily, because knowing where the next token boundary lies depends on feedback from the parser.

Generally this occurs when the tokenisation of a source text fragment depends on either the syntactic or semantic context in which it occurs. One example of this in conventional languages is determining whether the source fragment `>>` should be tokenised as a right-shift operator (in an expression) vs. two close-angle-brackets (in a generic type). There are multiple approaches to disambiguating this case, but one is to lex lazily and have the parser tell the lexer whether the current context is an expression or a type (see [here](https://langdev.stackexchange.com/a/3027/89)).
> **Comments:**
> **username_4** (2023-11-24): TeX is an example of a language that was developed when the theory of scanning and parsing was much less developed. Shells or Tcl would be another one. The idea that you could almost completely redefine the language (using \active in TeX for example) and using macro expansion is from that time. Languages today use typically a more phased approach.  
> **username_5** (2023-11-24): @ChristianLindig I'm not convinced that your first sentence is very accurate... LR parsing (and in particular, LR(1) and LALR) was invented in the '60s. In fact, LR parsing was invented in the '60s by the creator of TeX, Donald Knuth. Also, potentially related to the discussion, Lisp-style macros go back to the '60s as well. On the other hand, TeX was created in the late '70s.  
---
### Answer by username_6 on 2023-11-22. Score: 1
There are handwritten LL(1) parsers that execute a tokenizer, deriving a single offending token, keeping track of the previous offending token and disambiguate ambiguous constructs such as ECMA 262 (the ECMAScript language) left side destructuring in arrow functions based on the AST.
({}) => {};
({});

Typed dialects allow type annotations within the arrow function's signature, and these are converted to parameter bindings properly.
For complex qualified identifiers, a leftmost derivation, may need to be reinterpreted as another construct depending on production ambiguities. A conflicting postfix operator for instance also requires combining the parsing of different syntactic productions.
Here are ActionScript 3's qualified identifiers:
*
q::x
(e)::x
q::[k]
protected::x
@x
o.(condition)
o.(e)::x

The conclusion is that languages like Java, JavaScript, TypeScript, and Lua do not need a collection of preprocessed tokens, but single token streaming, possibly with a track of the previous token.
---
### Answer by username_7 on 2023-12-14. Score: 0
It depends on what language is being parsed and what tools are being used. Most parser generators implement popular algorithms (like LL(1) or LALR(1)) that require a grammar to need at most 1 token of lookahead, but add extensions (like precedence rules) that allow for parsing grammars that, strictly speaking, require more lookahead. But recursive descent parsers with backtracking allow for arbitrary lookahead. While people generally try to design grammars that only need 1 token of lookahead, many grammars require more (for instance, [C](https://en.wikipedia.org/wiki/Parsing#/media/File:Parsing_a_C_program_that_needs_2_token_lookahead.svg)). So I'm not sure what the typical parser does.
---
