← Назад към блога

Regex parser

```js
class RegexEngine {
    constructor(pattern) {
        this.pattern = pattern;
        this.pos = 0;
        this.ast = this.parse();
    }

// =========================
    // PARSER
    // =========================

peek() {
        return this.pattern[this.pos];
    }

consume() {
        return this.pattern[this.pos++];
    }

parse() {
        const ast = this.parseAlternation();

if (this.pos < this.pattern.length) {
            throw new Error(
                `Unexpected character '${this.peek()}' at ${this.pos}`
            );
        }

return ast;
    }

parseAlternation() {
        const alternatives = [
            this.parseSequence()
        ];

while (this.peek() === '|') {
            this.consume();

alternatives.push(
                this.parseSequence()
            );
        }

if (alternatives.length === 1) {
            return alternatives[0];
        }

return {
            type: "Alternation",
            alternatives
        };
    }

parseSequence() {
        const elements = [];

while (
            this.pos < this.pattern.length &&
            this.peek() !== ')' &&
            this.peek() !== '|'
        ) {
            elements.push(
                this.parseTerm()
            );
        }

return {
            type: "Sequence",
            elements
        };
    }

parseTerm() {
        let node = this.parseAtom();

const char = this.peek();

if (
            char === "*" ||
            char === "+" ||
            char === "?"
        ) {
            this.consume();

let min;
            let max;

if (char === "*") {
                min = 0;
                max = Infinity;
            }

if (char === "+") {
                min = 1;
                max = Infinity;
            }

if (char === "?") {
                min = 0;
                max = 1;
            }

node = {
                type: "Quantifier",
                expression: node,
                min,
                max
            };
        }

return node;
    }

parseAtom() {
        const char = this.consume();

if (char === undefined) {
            throw new Error("Unexpected end of pattern");
        }

// Group
        if (char === "(") {
            const expression = this.parseAlternation();

if (this.peek() !== ")") {
                throw new Error("Missing ')'");
            }

this.consume();

return {
                type: "Group",
                expression
            };
        }

// Any character
        if (char === ".") {
            return {
                type: "Any"
            };
        }

// Escape
        if (char === "\\") {
            const escaped = this.consume();

if (escaped === undefined) {
                throw new Error("Incomplete escape");
            }

return {
                type: "Literal",
                value: escaped
            };
        }

// Literal
        return {
            type: "Literal",
            value: char
        };
    }

// =========================
    // MATCHER
    // =========================

match(text) {
        const results = this.matchNode(
            this.ast,
            text,
            0
        );

return results.some(
            position => position === text.length
        );
    }

matchNode(node, text, pos) {

// Literal
        if (node.type === "Literal") {
            if (text[pos] === node.value) {
                return [pos + 1];
            }

return [];
        }

// Any character
        if (node.type === "Any") {
            if (pos < text.length) {
                return [pos + 1];
            }

return [];
        }

// Sequence
        if (node.type === "Sequence") {

let positions = [pos];

for (const element of node.elements) {

const next = [];

for (const p of positions) {
                    next.push(
                        ...this.matchNode(
                            element,
                            text,
                            p
                        )
                    );
                }

positions = next;

if (positions.length === 0) {
                    break;
                }
            }

return positions;
        }

// Alternation
        if (node.type === "Alternation") {

const results = [];

for (const alternative of node.alternatives) {
                results.push(
                    ...this.matchNode(
                        alternative,
                        text,
                        pos
                    )
                );
            }

return results;
        }

// Group
        if (node.type === "Group") {
            return this.matchNode(
                node.expression,
                text,
                pos
            );
        }

// Quantifier
        if (node.type === "Quantifier") {

let positions = [pos];

let count = 0;

while (
                count < node.max
            ) {
                const next = [];

for (const p of positions) {
                    next.push(
                        ...this.matchNode(
                            node.expression,
                            text,
                            p
                        )
                    );
                }

// Nothing more can be matched
                if (next.length === 0) {
                    break;
                }

// Prevent infinite loops
                if (
                    next.every(
                        (p, i) =>
                            p === positions[i]
                    )
                ) {
                    break;
                }

positions = [
                    ...new Set(next)
                ];

count++;
            }

if (count < node.min) {
                return [];
            }

return positions;
        }

throw new Error(
            `Unknown AST node: ${node.type}`
        );
    }
}
```

# Regex Engine Examples

## 1. Basic matching

```js
const regex = new RegexEngine("a+b");
console.log(regex.match("ab"));
// true
console.log(regex.match("aaab"));
// true
console.log(regex.match("b"));
// false
```

## 2. Alternation

```js
const regex = new RegexEngine("cat|dog");
console.log(regex.match("cat"));
// true
console.log(regex.match("dog"));
// true
console.log(regex.match("bird"));
// false
```

## 3. Groups + quantifiers

```js
const regex = new RegexEngine("(ab)+");
console.log(regex.match("ab"));
// true
console.log(regex.match("abab"));
// true
console.log(regex.match("ababab"));
// true
console.log(regex.match("ac"));
// false
```

## 4. Any character .

```js
const regex = new RegexEngine("a.c");
console.log(regex.match("abc"));
// true
console.log(regex.match("axc"));
// true
console.log(regex.match("a123c"));
// false
```

## 5. Optional ?

```js
const regex = new RegexEngine("colou?r");
console.log(regex.match("color"));
// true
console.log(regex.match("colour"));
// true
console.log(regex.match("colouur"));
// false
```

## 6. Zero or more *

```js
const regex = new RegexEngine("ab*c");
console.log(regex.match("ac"));
// true
console.log(regex.match("abc"));
// true
console.log(regex.match("abbbc"));
// true
console.log(regex.match("abx"));
// false
```

## 7. One or more +

```js
const regex = new RegexEngine("ab+c");
console.log(regex.match("ac"));
// false
console.log(regex.match("abc"));
// true
console.log(regex.match("abbbc"));
// true
```