Let's talk about exacly what's a finite automata, its two types (DFA and NFA), and how to implement a NFA

Implementing a NFA - Building a Regex Engine Part 2

Just enough information about formal language theory to answer "What is really a regex?" and "How are they executed?"

Building a Regex Engine Part 1 - Introduction

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.


Defining ASTs with dynamic classes in Javascript

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 5 - Improving the 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 4 - Experimenting with error recovery

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 3 - Rules

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 2 - Writing the core

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.

Building an Autocomplete Library for ANTLR4 Part 1 - Introduction

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

Defining languages with sets - A horrible yet correct alternative to grammars

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?

NFA vs DFA - Building a Regex Engine Part 10

Backreferences match the same text captured by a previous capturing group. To implement them, we need to evolve the concept of matchers/transitions.

Backreferences - Building a Regex Engine Part 9

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

Atomic groups - Building a Regex Engine Part 8

We finally modernize the interface of the regex to allow searching for multiple matches

Finding multiple matches - Building a Regex Engine Part 7

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

Anchors and multiline mode  - Building a Regex Engine Part 6

With character classes you can test if a character is inside a certain set of symbols. This makes regex simpler and more expressive

Character classes and escape characters - Building a Regex Engine Part 5

A formal regex engine is cool but kind of useless. The first step to improve it is to implement capturing groups

Adding capturing groups - Building a Regex Engine Part 4

We complete the engine for formal regex by translating a regex engine to a NFA

All Posts

Implementing a NFA - Building a Regex Engine Part 2

Building a Regex Engine Part 1 - Introduction