Skip to content

Instantly share code, notes, and snippets.

@DmitrySoshnikov
DmitrySoshnikov / LL1-parser-first-follow-sets.js
Last active March 27, 2024 07:24
LL(1) Parser. Parsing table, part 1: First and Follow sets.
/**
* LL(1) parser. Building parsing table, part 1: First and Follow sets.
*
* NOTICE: see full implementation in the Syntax tool, here:
* https://github.com/DmitrySoshnikov/syntax/blob/master/src/sets-generator.js
*
* by Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
* MIT Style License
*
* An LL(1)-parser is a top-down, fast predictive non-recursive parser,
@DmitrySoshnikov
DmitrySoshnikov / infix-to-postfix-regexp.js
Created September 24, 2011 20:14
Infix to postfix notation RegExp converter
/**
* Infix to postfix notation RegExp converter
*
* To implement RegExp machine (NFA, DFA) we need
* to transform first RegExp string to postfix notation
* for more convinient work with the stack. This function
* does exactly this.
*
* See: http://swtch.com/~rsc/regexp/regexp1.html
*
@hilukasz
hilukasz / Selected_layers-PS.jsx
Last active July 12, 2023 15:52
get array of selected layers in photoshop via extendscript
var docRef = app.activeDocument;
cTID = function(s) { return app.charIDToTypeID(s); };
sTID = function(s) { return app.stringIDToTypeID(s); };
function newGroupFromLayers(doc) {
var desc = new ActionDescriptor();
var ref = new ActionReference();
ref.putClass( sTID('layerSection') );
@DmitrySoshnikov
DmitrySoshnikov / lr0-items.js
Last active February 15, 2023 14:56
LR Parsing: Canonical collection of LR(0) items
/**
* LR-parsing.
*
* Canonical collection of LR(0) items.
*
* by Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
* MIT Style License (C) 2015
*
* See this "rock-painting" to get the picture of what we're building here:
*
@DmitrySoshnikov
DmitrySoshnikov / LL1-parsing-table.js
Last active February 15, 2023 14:55
LL(1) Parser. Parsing table, part 2: building the table from First and Follow sets.
/**
* Building LL(1) parsing table from First and Follow sets.
*
* by Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
* MIT Style License
*
* This diff is a continuation of what we started in the previous two diffs:
*
* Dependencies:
*
@DmitrySoshnikov
DmitrySoshnikov / LL-parser.js
Last active February 15, 2023 14:54
LL-parser
/**
* = LL parser =
*
* by Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
* MIT Style license
*
* Often one can see manually written LL parsers implemented as
* recursive descent. Approach in this diff is a classical parse table
* state machine.
*
@DmitrySoshnikov
DmitrySoshnikov / stack-vm.js
Last active January 20, 2023 17:33
Educational Stack-based Virtual Machine
/**
* Educational Stack-based VM.
*
* See also:
* - More complex example with recursion: https://gist.github.com/DmitrySoshnikov/afda459222e96e6002ac
* - Register-based VM example: https://gist.github.com/DmitrySoshnikov/6407781
*
* by Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
* http://dmitrysoshnikov.com
* MIT Stye License (C) 2015
/**
* NFA (Non-deterministic finite automata)
*
* A formalism for regular grammars (to recognize strings based on regular
* expressions).
*
* Regexp parser to transform AST to NFA:
* https://www.npmjs.com/package/regexp-tree
*
* NFA/DFA fragment examples:
@DmitrySoshnikov
DmitrySoshnikov / NFA-DFA-RegExp.js
Last active May 21, 2021 08:41
Classic RegExp implementation (NFA, DFA)
/**
* Classic RegExp implementation (NFA, DFA).
*
* by Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
* MIT License, 2017
*/
/**
* Epsilon.
*/
@luchy0120
luchy0120 / thompson_nfa.c
Last active August 21, 2019 03:54
NFA Thompson Construction by Russ Cox
/*
* Regular expression implementation.
* Supports only ( | ) * + ?. No escapes.
* Compiles to NFA and then simulates NFA
* using Thompson's algorithm.
*
* See also http://swtch.com/~rsc/regexp/ and
* Thompson, Ken. Regular Expression Search Algorithm,
* Communications of the ACM 11(6) (June 1968), pp. 419-422.
*