<p>As a beginner in parser generators, is it memory intensive or not to retain the set of parsed tokens in a collection? Or do actual parser generators refine what was previously parsed from a structure to another structure, such as in the following ECMAScript 2018 program...?</p>
<pre class="lang-js prettyprint-override"><code>// Refines the left-hand side into an arrow signature
//
// I.e. the {a, b} literal turns into a required
// parameter binding.
//
// I.e. the rest operator turns into
// a rest parameter binding.
//
({a, b}, ...y) =&gt; {}
</code></pre>
<p>What if the language being parsed supports typed parameters with a <code>: T</code> type annotation?</p>

<parsing>
Does it make sense to track previous tokens literally in a parser generator?
CC BY-SA 4.0
2024-01-17T21:51:10.160Z
I’m afraid I have no idea what your “ECMAScript 2018 program” is intended to demonstrate. As far as I can tell, that is an expression for a function that always returns `undefined`, and I’m not sure what the comment has to do with it. Could you clarify what you mean by “refine what was previously parsed from a structure to another structure”?
Alexis King
CC BY-SA 4.0
2024-01-17T22:09:32.843Z
The left-hand side of the arrow, presuming `...` is a placeholder and not syntax, is ambiguous between a use of the `,` sequencing operator and a formal argument list until the arrow appears.
Michael Homer
CC BY-SA 4.0
2024-01-17T23:27:59.027Z
It depends on the language and how much coupling there is between the tokenizer and the parser (and other parts of the compiler/interpreter) in the implementation.
Chris Dodd
CC BY-SA 4.0
2024-01-19T00:11:27.260Z
@MichaelHomer I don't think it's a placeholder. `...y` is the JavaScript syntax for a function parameter that receives all the remaining arguments as an array. It's like `*y` in Python, and `&rest y` in Common Lisp.
Barmar
CC BY-SA 4.0
2024-01-19T00:31:03.963Z
@Barmar It certainly unambiguously isn't now, but the spread declaration forces it to parse as a function declaration immediately, rather than when the arrow appears, so it's a much less useful example for the question than an unboundedly long list of variable names would have been.
Michael Homer
CC BY-SA 4.0
2024-01-20T18:53:35.350Z
From the title, I think the question is a duplicate of the equally closed https://langdev.stackexchange.com/questions/3051/look-behind-in-parsers. However, I'd also vote to keep it closed in the current form as it is about several different things.
feldentm
<p>Good parser generators lex the input stream as they are parsing because it's more memory efficient: you don't have to store all of the input tokens at any one point in time. And once the tokens are used to parse an syntax node, there's no point in retaining them. Furthermore, a parser should be able to parse a recursive syntax node without ever storing all of its tokens at any one point in time (e.g. parse child, forget child's tokens, parse next child, ... rather than putting all tokens on a stack and only parsing children at the end), otherwise it's not recursing the correct way (left-recursive for LALR parsers, right-recursive for LL(k) and recursive-descent parsers)</p>
<p>The parser generator may store the line/column/offset numbers in every syntax node to map it to the source, but that doesn't require storing the tokens (which in most cases can be inferred anyways).</p>

CC BY-SA 4.0
2024-01-18T00:48:41.080Z
2024-01-18T00:48:41.080Z
tarzh
# Does it make sense to track previous tokens literally in a parser generator?
Posted by: username_0 on 2024-01-17
As a beginner in parser generators, is it memory intensive or not to retain the set of parsed tokens in a collection? Or do actual parser generators refine what was previously parsed from a structure to another structure, such as in the following ECMAScript 2018 program...?
// Refines the left-hand side into an arrow signature
//
// I.e. the {a, b} literal turns into a required
// parameter binding.
//
// I.e. the rest operator turns into
// a rest parameter binding.
//
({a, b}, ...y) => {}

What if the language being parsed supports typed parameters with a : T type annotation?
**Tags:** parsing
> **Comments:**
> **username_1**: I’m afraid I have no idea what your “ECMAScript 2018 program” is intended to demonstrate. As far as I can tell, that is an expression for a function that always returns `undefined`, and I’m not sure what the comment has to do with it. Could you clarify what you mean by “refine what was previously parsed from a structure to another structure”?  
> **username_2**: The left-hand side of the arrow, presuming `...` is a placeholder and not syntax, is ambiguous between a use of the `,` sequencing operator and a formal argument list until the arrow appears.  
> **username_3**: It depends on the language and how much coupling there is between the tokenizer and the parser (and other parts of the compiler/interpreter) in the implementation.  
> **username_4**: @MichaelHomer I don't think it's a placeholder. `...y` is the JavaScript syntax for a function parameter that receives all the remaining arguments as an array. It's like `*y` in Python, and `&rest y` in Common Lisp.  
> **username_2**: @Barmar It certainly unambiguously isn't now, but the spread declaration forces it to parse as a function declaration immediately, rather than when the arrow appears, so it's a much less useful example for the question than an unboundedly long list of variable names would have been.  
> **username_5**: From the title, I think the question is a duplicate of the equally closed https://langdev.stackexchange.com/questions/3051/look-behind-in-parsers. However, I'd also vote to keep it closed in the current form as it is about several different things.  
---
## 1 answers
### Answer by username_6 on 2024-01-18. Score: 2
Good parser generators lex the input stream as they are parsing because it's more memory efficient: you don't have to store all of the input tokens at any one point in time. And once the tokens are used to parse an syntax node, there's no point in retaining them. Furthermore, a parser should be able to parse a recursive syntax node without ever storing all of its tokens at any one point in time (e.g. parse child, forget child's tokens, parse next child, ... rather than putting all tokens on a stack and only parsing children at the end), otherwise it's not recursing the correct way (left-recursive for LALR parsers, right-recursive for LL(k) and recursive-descent parsers)

The parser generator may store the line/column/offset numbers in every syntax node to map it to the source, but that doesn't require storing the tokens (which in most cases can be inferred anyways).
---
