Building a Streamable Parser From Scratch
So, I built a streamable parser. And honestly? It probably won’t be useful to anyone. But hear me out — this was one of those projects where the challenge itself was the point, and I learned a ton along the way.
Over the next few articles, I’m going to walk you through how I built this thing from the ground up. We’ll dive into all the theory you need to know, and I’ll shine some light on the practical stuff too — the parts where theory meets reality and things get messy in the best possible way.
So... What’s a Streamable Parser Anyway?
Here’s the thing: most parsers you’ll see are pretty straightforward. You feed them a complete token stream, they build an abstract syntax tree (AST), and boom — you’re done. Simple, elegant, works great.
But a streamable parser? That’s a different beast entirely. It needs to be able to process tokens as they come in, one at a time, and build the parse tree incrementally. Think of it like the difference between reading an entire book before you can understand any of it, versus being able to comprehend each sentence as you read it.
Why This Is Actually Exciting (Despite Being Kinda Impractical)
The architectural challenges that the streamable part brings are fascinating. With a normal parser, you have the luxury of looking ahead, looking back, and making decisions with the full context available. But with a streaming parser, you’re working in real-time, making decisions on the fly without always knowing what’s coming next.
This means you have to think about:
- State management: How do you keep track of where you are when tokens are coming in one at a time?
- Incremental tree building: How do you construct an AST when you don’t have all the pieces at any moment?
- Error recovery: What happens when something goes wrong mid-stream? You can’t just go back and re-parse from the beginning.
- Memory constraints: You need to be smart about what you keep around and what you can safely discard.
It’s like solving a puzzle where the pieces keep arriving one by one, and you need to figure out where each piece goes before you see the next one.
The Intersection of Theory and Practice
I’m going to cover all the theory you need — parsing algorithms, grammar rules, first and follow sets, conflict resolution, all that good stuff. But I’m also going to show you where the rubber meets the road. Where the beautiful theoretical concepts run into the messy reality of implementation details, edge cases, and the occasional “wait, why doesn’t this work?” moment.
Get Viraj Agarwal’s stories in your inbox
Join Medium for free to get updates from this writer.
Because honestly, that’s where the real learning happens. It’s one thing to understand how an LL(1) parser works on paper. It’s another thing entirely to implement one that actually processes tokens in real-time without breaking.
Fair Warning
This parser is NOT production-ready. I’m still not covering all edge cases — because it’s hard to think of ALL the edge cases when you’re building something like this. But it “works”, and more importantly, it taught me a lot about how parsers actually function under the hood. And, I am now going to try to transfer that knowledge to you.
What’s Coming
In the upcoming articles, we’ll cover:
- The fundamentals of parsing theory
- Why streaming makes everything harder and more interesting
- Converting EBNF to BNF
- Computing FIRST and FOLLOW sets
- Handling conflicts and ambiguities
I hope if you follow along, you’ll appreciate both the elegance of the theory and the satisfaction of making it actually work.
So buckle up. We’re going to build a parser that probably has no practical use, but is absolutely beautiful in its own weird way.
Happy parsing!
