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

If it were just plain JavaScript, the variables would evaluate to this:

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 + 10 and y = x, then make a be 5 more 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 + 10 and y = x, then make a be 5 more 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".

  • My guess is that you're trying to use a LL parser for something requiring an LR parser. See here for a good explanation between the two. – Neil Jul 27 '18 at 8:00
  • 5
    I don't see what this has to do with parsing at all, to be honest. Your rule seems to be a semantic rule, not a syntactic one, so it would only be relevant during evaluation, not parsing. In fact, you specifically use the word "evaluate" in your question. – Jörg W Mittag Jul 27 '18 at 11:20
  • 1
    Can you describe in a bit more detail the actual, real-world problem you're trying to solve? – Robert Harvey Jul 27 '18 at 14:38
  • 1
    Agree with Jörg's comment. Parsing is about matching input to a language grammar with the goal to identify the grammatical constructs in the input. Some languages have ambiguous grammars and then rules that resolve these, usually by prioritizing one grammatical construct over the other. What you're describing is not ambiguity in the grammar, but rather an interpretation of the meaning of the language (of language constructs), post parsing. So, you should look further down the line in the phases of translation for how this would be accomplished. – Erik Eidt Jul 27 '18 at 14:51

In this case, I'd look for something like project Roslyn from Microsoft for inspiration Wikipedia

The steps you want to take all come down to static analysis of the code with the rules that are in place. Roslyn uses multiple stages to do this analysis and I suggest you would do the same. First, tokenize all the code into an object structure. In your case, you want to make sure you have a construct where you have variables and values after this stage, but you should also be able to find out if certain expressions exist in the code.

Next, you'd apply the rules by using these two features of your objects. In order to do this, you could include another feature in your objects that allow you to set one variable and have everything after it re-evaluated.

Then, you might want to optimize all the code.

And finally, you'd emit the completed code to whatever output is suitable.


A typical approach I have seen is to process your more complex 'context rules' as a preprocessor, which outputs straight forward code (like the upper example), and then to process this code with a simpler standard process.

This is how C and C++ preprocessing is done, and also how early C++ compilers were built - they read the new 'fancier' syntax elements, and generated (ugly and verbose, but correct) C code; then the C compiler ran on that.


This is likely a naive approach but given the context given it could work quite nicely; Simple start with a "light parse" as you have put it, looking only for the expressions considered for your rule, keeping note of the parts of those rules that youve already found and then actually going through the code to evaluate once the "anywhere in the code" rules have been evaluated.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.