<p>If <a href="https://chat.stackexchange.com/transcript/136286?m=64551901#64551901">Sandwich</a>'s AST generator finds that the first token is an identifier, one of two cases can be true:</p>
<ol>
<li>Function call</li>
<li>Variable assignment</li>
</ol>
<p>It stores the identifier and checks if the next token is a = in which case it's a variable assignment and it goes to the token after the = then assigns the identifier to that value. However you could in theory wait until the = token and then look behind to grab the identifier, looking behind is something I have never thought of until now.</p>
<p><strong>Is lookbehind useful in parsing?</strong></p>

<language-design><implementation><parsing><abstract-syntax-tree>
Look behind in parsers
CC BY-SA 4.0
2023-10-22T17:16:55.750Z
Generally speaking, moving forward across various tokens should change the state of the parser, so you don't need to look behind — what's behind has been captured in state.
Erik Eidt
CC BY-SA 4.0
2023-10-22T17:20:00.657Z
@ErikEidt Oh that was quick. What if something captured can be useful in some cases but isn't always, now the tokens are there in the AST so all you do is just make a new variable with a token from the AST but making multiple variables for the same token when it's pointless can be inefficient.
192927376337929292283737373773
CC BY-SA 4.0
2023-10-22T17:40:46.517Z
This seems like multiple different questions. Could you split them up? Also, a more general definition of what lookbehind is might help, but I don't think the bit about your language's interpreter's specifics is necessary.
user
CC BY-SA 4.0
2023-10-22T17:51:52.780Z
@user The questions are related and I do not want to spam the site. I think some background information could help.
192927376337929292283737373773
CC BY-SA 4.0
2023-10-22T17:53:20.920Z
*making multiple variables for the same token* — I don't know why you would do that.  What kind of parser are you doing?
Erik Eidt
CC BY-SA 4.0
2023-10-22T18:46:45.970Z
@ErikEidt If I have an identifier I will store it in a variable like "identifier" for access later quickly instead of having to get the index and use the index to get it.
192927376337929292283737373773
CC BY-SA 4.0
2023-10-22T20:49:20.973Z
'storing it in a variable' is making it part of the state of the parser -- so seems to be the opposite of "lookbehind", which would be looking backwards in the input stream (I would think)
Chris Dodd
CC BY-SA 4.0
2023-10-23T06:35:34.567Z
@ChrisDodd This is the same thing, we look backward in the input to grab something and then store that in a variable.
192927376337929292283737373773
CC BY-SA 4.0
2023-10-23T22:51:55.643Z
@The_AH: no you're not "looking backwards" -- you're remembering something you've seen previously.  Not at all the same thing.
Chris Dodd
CC BY-SA 4.0
2023-10-24T07:33:46.593Z
@ChrisDodd That is very similar to looking backwards.
192927376337929292283737373773
CC BY-SA 4.0
2023-10-24T21:24:22.407Z
@The_AH: the point is that there's no cost/limit associated with how far previously you've seen it.  With "lookahead" there's a cost (more lookahead is generally more expensive/slower), while with state, the cost is associated with the size of the state, not how long ago it was set.  So calling state "lookbehind" is not useful.
Chris Dodd
<p>Yes, and it is called parser stack.
A parser is usually an instance of <a href="https://en.wikipedia.org/wiki/Deterministic_pushdown_automaton" rel="nofollow noreferrer">deterministic pushdown automaton</a>. The most common form is LL(1) parsers, but there are others. An uncommon, but still used in practice, form is nondeterministic pushdown automata. Another uncommon form are turing-complete parsers, but this is not relevant wrt. to the question.</p>
<p>Your idea of lookbehind is implemented in practice by pushing a symbol onto the stack that influences processing of other symbols. This process is commonly referred to as parse rule.
Wrt. to the question, a <em>function assignment</em> or <em>variable assignment</em> would be realized by different parse rules.</p>
<p>An example common to most modern languages is <code>{</code> <code>}</code> which can enclose a function body or a block inside a function body - two completely unrelated things wrt. to compilation.</p>

CC BY-SA 4.0
2023-10-23T14:50:57.817Z
2024-01-20T18:52:19.903Z
2024-01-20T18:52:19.903Z
feldentm
CC BY-SA 4.0
2023-10-23T15:11:50.037Z
Could you elaborate on this? One-sentence answers aren't useful.
rydwolf
CC BY-SA 4.0
2023-10-23T17:36:34.743Z
@RydwolfPrograms hope you like the answer more, now. I'm honestly surprised that the question hasn't been closed.
feldentm
CC BY-SA 4.0
2023-10-23T18:08:35.863Z
It was closed, then reopened, and now it's in the queue again
rydwolf
CC BY-SA 4.0
2023-10-24T19:59:23.903Z
@RydwolfPrograms I provided the answer because I thought that the answer had been edited and reopened and was therefore considered acceptable by others. I don't know if there should be a "too fundamental" close vote, TBH.
feldentm
CC BY-SA 4.0
2023-10-24T20:00:30.683Z
@feldentm FWIW I reversed my downvote to an upvote; not sure the reason for the DV
rydwolf
# Look behind in parsers
Posted by: username_0 on 2023-10-22
If [Sandwich](https://chat.stackexchange.com/transcript/136286?m=64551901#64551901)'s AST generator finds that the first token is an identifier, one of two cases can be true:

1. Function call
2. Variable assignment

It stores the identifier and checks if the next token is a = in which case it's a variable assignment and it goes to the token after the = then assigns the identifier to that value. However you could in theory wait until the = token and then look behind to grab the identifier, looking behind is something I have never thought of until now.

**Is lookbehind useful in parsing?**
**Tags:** language-design implementation parsing abstract-syntax-tree
> **Comments:**
> **username_1**: Generally speaking, moving forward across various tokens should change the state of the parser, so you don't need to look behind — what's behind has been captured in state.  
> **username_0**: @ErikEidt Oh that was quick. What if something captured can be useful in some cases but isn't always, now the tokens are there in the AST so all you do is just make a new variable with a token from the AST but making multiple variables for the same token when it's pointless can be inefficient.  
> **username_2**: This seems like multiple different questions. Could you split them up? Also, a more general definition of what lookbehind is might help, but I don't think the bit about your language's interpreter's specifics is necessary.  
> **username_0**: @user The questions are related and I do not want to spam the site. I think some background information could help.  
> **username_1**: *making multiple variables for the same token* — I don't know why you would do that.  What kind of parser are you doing?  
> **username_0**: @ErikEidt If I have an identifier I will store it in a variable like "identifier" for access later quickly instead of having to get the index and use the index to get it.  
> **username_3**: 'storing it in a variable' is making it part of the state of the parser -- so seems to be the opposite of "lookbehind", which would be looking backwards in the input stream (I would think)  
> **username_0**: @ChrisDodd This is the same thing, we look backward in the input to grab something and then store that in a variable.  
> **username_3**: @The_AH: no you're not "looking backwards" -- you're remembering something you've seen previously.  Not at all the same thing.  
> **username_0**: @ChrisDodd That is very similar to looking backwards.  
> **username_3**: @The_AH: the point is that there's no cost/limit associated with how far previously you've seen it.  With "lookahead" there's a cost (more lookahead is generally more expensive/slower), while with state, the cost is associated with the size of the state, not how long ago it was set.  So calling state "lookbehind" is not useful.  
---
## 1 answers
### Answer by username_4 on 2023-10-23. Score: 1 | Accepted answer
Yes, and it is called parser stack.
A parser is usually an instance of [deterministic pushdown automaton](https://en.wikipedia.org/wiki/Deterministic_pushdown_automaton). The most common form is LL(1) parsers, but there are others. An uncommon, but still used in practice, form is nondeterministic pushdown automata. Another uncommon form are turing-complete parsers, but this is not relevant wrt. to the question.

Your idea of lookbehind is implemented in practice by pushing a symbol onto the stack that influences processing of other symbols. This process is commonly referred to as parse rule.
Wrt. to the question, a *function assignment* or *variable assignment* would be realized by different parse rules.

An example common to most modern languages is `{` `}` which can enclose a function body or a block inside a function body - two completely unrelated things wrt. to compilation.
> **Comments:**
> **username_5** (2023-10-23): Could you elaborate on this? One-sentence answers aren't useful.  
> **username_4** (2023-10-23): @RydwolfPrograms hope you like the answer more, now. I'm honestly surprised that the question hasn't been closed.  
> **username_5** (2023-10-23): It was closed, then reopened, and now it's in the queue again  
> **username_4** (2023-10-24): @RydwolfPrograms I provided the answer because I thought that the answer had been edited and reopened and was therefore considered acceptable by others. I don't know if there should be a "too fundamental" close vote, TBH.  
> **username_5** (2023-10-24): @feldentm FWIW I reversed my downvote to an upvote; not sure the reason for the DV  
---
