Regular Expression Compiler

This project provides a simple regular expression compiler implemented in TypeScript. The compiler includes modules for generating non-deterministic finite automata (NFA) from regular expressions, tokenizing regular expressions, and parsing abstract syntax trees (AST) for regular expressions.

While the SRegex class serves as a unified interface, each component within it is modular and can be utilized independently.

Getting Started

First, run the development server:

npm install
npm run dev

Open http://localhost:3000 with your browser to see the result.

You can start editing the page by modifying app/page.tsx. The page auto-updates as you edit the file.

Files

nfa.ts

This file contains TypeScript code for defining non-deterministic finite automata (NFA) and various operations on NFAs, such as concatenation, disjunction, and repetition. It also includes functions for testing strings against an NFA and generating strings that match an NFA.

compiler.ts

The compiler.ts file implements a compiler that translates an abstract syntax tree (AST) of a regular expression into an NFA. It uses the AST generated by the parser to create the corresponding NFA.

parser.ts

The parser.ts file defines a parser for regular expressions. It tokenizes a regular expression string and generates an AST representing the syntactic structure of the regular expression.

regex.ts

This file exports a SRegex class that encapsulates the entire regular expression compilation process. It takes a regular expression string as input, parses it, and compiles it into an NFA.

token.ts

The token.ts file defines constants, an enum, and functions related to tokenizing regular expressions. It includes an array of operators, a token type enum, and a function for creating tokens.

ast.ts

The ast.ts file defines the abstract syntax tree (AST) structure for representing regular expressions. It includes types for different nodes in the AST, such as character nodes, group nodes, disjunction nodes, and the root node.

lexer.ts

The lexer.ts file provides a lexer that tokenizes regular expression strings using the constants and functions defined in token.ts.

Usage

To use the regular expression compiler, import the necessary classes and functions from the provided modules and create an instance of the Regex class. You can then compile regular expressions into NFAs, test strings against the generated NFAs, and perform other operations related to regular expressions.

// Import the SRegex class from the "regex" module
import { SRegex } from "./regex";

// Create an instance of the SRegex class with the regular expression "a(b+c)*d"
const regex = new SRegex("a(b+c)*d");

// Get the abstract syntax tree (AST) of the compiled regular expression
const ast = regex.getAST();

// Get the tokens generated during the parsing of the regular expression
const tokens = regex.getTokens();

// Generate an array of strings that match the regular expression
const generatedStrings = regex.generateStrings();

// Test if a specific string is valid according to the compiled regular expression
const isStringValid = regex.testString("abbbd");

// Output the AST, tokens, generated strings, and the result of testing a string
console.log("Abstract Syntax Tree (AST):", ast);
console.log("Tokens:", tokens);
console.log("Generated Strings:", generatedStrings);
console.log("Is 'abbbd' a valid string?", isStringValid);

License

Distributed under the MIT License. See LICENSE.txt for more information.