Building a Lexer Framework Part 3 - Executing the state machine
I keep pressing keys until I have a fully functional lexer. I wonder, how will it perform against a professional one like ANTLR4? 🤔
Abstract Syntax Seed
A blog about parsing and in-depth explanations of whatever I'm learning at the moment
Latest posts
Building a Lexer Framework Part 2 - The state machine
Using the black magic we developed for the regex engine we can easily create a state machine for any set of lexer rules.
Building a Lexer Framework Part 1 - Introduction
On the journey to reinvent the wheel yet again while learning formal languages, it is time to build a lexer to generate old-school non-AI tokens
The complex art of writing simple code for a business
Working as a software engineer is much more than writing code. There is complexity every area of the job, and that is why we need to keep the code as simple as possible. But that is not an easy job.
Defining ASTs with dynamic classes in Javascript
Defining the classes of an AST can be cumbersone due to the high amount of nodes and redundant code. Dynamic classes in JS can make this process much easier.
Building an Autocomplete Library for ANTLR4 Part 5 - Improving the error recovery
The error recovery PoC works, but it's both underperforming and has a big flaw: It doesn't work with repetitions
Building an Autocomplete Library for ANTLR4 Part 4 - Experimenting with error recovery
Autocompletion has a fatal flaw. If there is a syntax error somewhere before the cursor, the machine will fail and never reach it, even if it has more than enough context to guess the next tokens. But what if we could define recovery rules? A way for it to reset when it fails and keep going.
Building an Autocomplete Library for ANTLR4 Part 3 - Rules
At first glance, rules might seem like a odd and complex mechanism, specially since they allow recursion. But once looked in detail, it's just like any other type of transition, with a few quirks.
Building an Autocomplete Library for ANTLR4 Part 2 - Writing the core
The autocompleter works by traversing the ATN, which is ANTLR4's state machine. To do so, we begin by focusing on the three most common types of transitions: Epsilon, Atomic and Set.
Building an Autocomplete Library for ANTLR4 Part 1 - Introduction
ANTLR4 grammars are commonly used to build parsers and syntax analyzers. However, if you dive deeper you'll find out they also be used to predict what the user is going to type next.
Defining languages with sets - A horrible yet correct alternative to grammars
Grammars define a language, and a language is a set of strings... So is it possible to define a language by directly defining the set? Somehow it is
NFA vs DFA - Building a Regex Engine Part 10
With all the features of the engine finished the only question left is, what would have changed if instead of a NFA engine we had made a DFA engine?
Backreferences - Building a Regex Engine Part 9
Backreferences match the same text captured by a previous capturing group. To implement them, we need to evolve the concept of matchers/transitions.
Atomic groups - Building a Regex Engine Part 8
Atomic groups can be used to avoid unnecessary backtracking and optimize regex. In this post we explain them in detail and add them to the engine
Finding multiple matches - Building a Regex Engine Part 7
We finally modernize the interface of the regex to allow searching for multiple matches
Anchors and multiline mode - Building a Regex Engine Part 6
The start and end of string anchors (^$) allow to check that a string starts or ends in some way. We'll implement this and in the process add the first regex mode: multiline
Character classes and escape characters - Building a Regex Engine Part 5
With character classes you can test if a character is inside a certain set of symbols. This makes regex simpler and more expressive
Adding capturing groups - Building a Regex Engine Part 4
A formal regex engine is cool but kind of useless. The first step to improve it is to implement capturing groups
Creating a NFA from a regex - Building a Regex Engine Part 3
We complete the engine for formal regex by translating a regex engine to a NFA
Implementing a NFA - Building a Regex Engine Part 2
Let's talk about exacly what's a finite automata, its two types (DFA and NFA), and how to implement a NFA
Building a Regex Engine Part 1 - Introduction
Just enough information about formal language theory to answer "What is really a regex?" and "How are they executed?"