I am trying to learn how to handle complex context-sensitivity in parsing. Say you have this simple example of code:
var x = 10 var y = x + 10 var z = y + 10 var a = z + 10 var b = a + 10 var c = b + 10
x == 10 y == 20 z == 30 a == 40 b == 50 c == 60
However, I want to make this much more context-sensitive by adding some arbitrary complexity to it. Say that we add the following parser rule:
If somewhere in the code there is the expression
c = b + 10and
y = x, then make
5more than whatever it is set to, as well as converting it to a string.
This would mean it would resolve to this:
x == 10 y == 20 z == 30 a == "45" b == "4510" c == "451010"
I am hoping this example doesn't have any edge-cases to make it easy to parse. What I am hoping to get at is how to efficiently parse the expressions.
From my understanding, this is context-senstivity. Let's say the parser has tokenied into words/values and spaces, so we are left with just non-space tokens. We have the rule looking for
c = b + 10 and
y = x when we get to
a. So when we get to
a, we look around. We look backwards and forwards and all around trying to find the expressions. We find that
c = b + 10 is ahead quite a few tokens, and
y = x is behind quite a few tokens. Now imagine that this file was 10,000 lines long with complex functions and such, then it would have to scan over the whole file everywhere to figure it out, once it arrived at
var a. Now imagine that we have more than 1 rule, but 100 rules, so it is constantly scanning around the whole file.
I'm wondering what sort of pattern should be used to handle this. It seems there are at least two big things you can do to help out. First is to build an understanding of the text as you go from start to the current position. So we would know the rule is there for
y = x (and
c = b + 10), so we would be looking for this every step of the way, maybe building some sort of data structure. Once we found it, then we could have some way to look it up quickly once we found
var a. But then we still don't have
c = b + 10 until the end of the file. So it's as if we have to either skip over everything somehow and "lightly" parse the remainder until we find
c = b + 10, or we fully parse it making
a = 40 and
b = 50, etc., until we finally find
c = b + 10, and then we go back to
var a and re-parse it with the new understanding. Something like that. The problem is, all of these ways seem like a lot of processing and complicated to wrap your mind around.
Wondering if one could shed some light on best approaches or techniques on how to handle this. Not necessarily any specific algorithms as I imagine it is complicated, but maybe thoughts on where to look or how to approach it.
To elaborate further, say that we then had these rules:
(1) If somewhere in the code there is the expression
c = b + 10and
y = x, then make
5more than whatever it is set to, as well as converting it to a string. (2) If
b == "4510"then make
y == 25, and propagate the rest...
It could keep going in circles sort of like a fixed point iteration thing. Until you finally arrive at the final parse. One interpretation affects the next affects the next until it settles down. It seems like there could be a system.
Wondering if there is any sort of system for this, like "fixed point iteration on top-down or bottom-up parsers with global state and context sensitivity".