10
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Just as another data point, Edinburgh Prolog is notorious for requiring infinite lookahead. (ISO Prolog does not.) $\endgroup$
    – Pseudonym
    Nov 28, 2023 at 23:16
  • $\begingroup$ 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 <. $\endgroup$ Jan 10 at 4:55

4 Answers 4

8
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ "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. $\endgroup$ Nov 22, 2023 at 16:23
  • 1
    $\begingroup$ I wrote that a lookahead of one is common in programming languages; this is reflected in Yacc generating an LARL(1) parser. $\endgroup$ Nov 22, 2023 at 20:59
  • $\begingroup$ And how common is Yacc use in the mainstream? C and C++ requires a symbol table as far as I know. C# requires backtracking. 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.... $\endgroup$ Nov 23, 2023 at 8:26
  • $\begingroup$ My argument is the other way round: Yacc implements LALR(1) parsers, as they are useful for programming languages 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. $\endgroup$ Nov 23, 2023 at 9:22
  • $\begingroup$ 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). $\endgroup$ Nov 23, 2023 at 9:30
5
$\begingroup$

What influences the decision?

Some languages cannot be lexed without also being parsed (or in the notable case of TeX, 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).

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Nov 24, 2023 at 9:07
  • $\begingroup$ @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. $\endgroup$ Nov 24, 2023 at 18:40
1
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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). So I'm not sure what the typical parser does.

$\endgroup$

You must log in to answer this question.

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