Design of non-recursive parser of JavaScript in C (highly memory constrained)

Question

We need to implement JavaScript parser in C, and we target very memory-constrained platforms; the most constrained part is the stack.

Currently, we have descent recursive parser, and C stack is easily overflown by reasonably complicated expressions. So, our goal is to make C stack consumption not to grow as the expressions nesting grows.

The only way that I can think of is to maintain our own stack, and our parser will be just a single huge function with lots of labels and gotos. It is rather messy and not very maintainable; we can hide some mess by macros, but anyway, it will be much more messy than usual function calls.

But then:

We can implement stack in a more efficient way (embedded compilers are often, ... not very good)
We can even use segmented stack (since huge contiguous pieces of memory are very expensive here)

Am I right that there are no other ways to implement that? I mean, other than the single function with lots of labels and gotos, and our own hand-made stack.

If I'm wrong, I'd be happy to listen for your suggestions.

very memory constrained? what size of memory are we talking about here and what code have you tried? — Mike -- No longer here
– Mike -- No longer here, Commented Oct 30, 2015 at 1:00
One way to help keep your stack small is to make your data small; e.g. compress the data into bit fields instead of larger data types. For example, in JSON a "value" type can be one of seven values: string, number, object, array, true, false, or null. This can be encoded into 3 bits. Use the other 5 bits in that byte for something else. <Edit> Oh wait, this is Javascript, not JSON :) sorry. The same technique is valid though. — sifferman
– sifferman, Commented Oct 30, 2015 at 3:34
You could always use bison. Bison-generated parsers are small, manage their own parser stacks, and execute rapidly. — rici
– rici, Commented Oct 30, 2015 at 3:39
@dmitry: and they had some evidence for this curious assertion? :-) — rici
– rici, Commented Oct 30, 2015 at 14:25

Ira Baxter · Accepted Answer · 2015-10-30 05:49:44Z

3

When you write a recursive function, you have to have stack. If the physical stack of you machine is not deep enough, you need to implement the stack another way.

As you said: "maintain our own stack, and our parser will be just a single huge function with lots of labels and gotos. It is rather messy and not very maintainable".

Well, it is maintainable if you stick to rules. Each "function" call is implemented by pushing the next program location onto your implemented psuedo-stack. If you hide all that pushing logic in a subroutine or a macro, it will be just as readable as a real function call.

answered Oct 30, 2015 at 5:49

Ira Baxter

95.9k24 gold badges188 silver badges357 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Design of non-recursive parser of JavaScript in C (highly memory constrained)

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related