| /** |
| * The MIT License (MIT) |
| * Copyright (c) 2017-present Dmitry Soshnikov <dmitry.soshnikov@gmail.com> |
| */ |
| |
| 'use strict'; |
| |
| var NFA = require('./nfa'); |
| var NFAState = require('./nfa-state'); |
| |
| var _require = require('../special-symbols'), |
| EPSILON = _require.EPSILON; |
| |
| // ----------------------------------------------------------------------------- |
| // Char NFA fragment: `c` |
| |
| /** |
| * Char factory. |
| * |
| * Creates an NFA fragment for a single char. |
| * |
| * [in] --c--> [out] |
| */ |
| |
| |
| function char(c) { |
| var inState = new NFAState(); |
| var outState = new NFAState({ |
| accepting: true |
| }); |
| |
| return new NFA(inState.addTransition(c, outState), outState); |
| } |
| |
| // ----------------------------------------------------------------------------- |
| // Epsilon NFA fragment |
| |
| /** |
| * Epsilon factory. |
| * |
| * Creates an NFA fragment for ε (recognizes an empty string). |
| * |
| * [in] --ε--> [out] |
| */ |
| function e() { |
| return char(EPSILON); |
| } |
| |
| // ----------------------------------------------------------------------------- |
| // Alteration NFA fragment: `abc` |
| |
| /** |
| * Creates a connection between two NFA fragments on epsilon transition. |
| * |
| * [in-a] --a--> [out-a] --ε--> [in-b] --b--> [out-b] |
| */ |
| function altPair(first, second) { |
| first.out.accepting = false; |
| second.out.accepting = true; |
| |
| first.out.addTransition(EPSILON, second.in); |
| |
| return new NFA(first.in, second.out); |
| } |
| |
| /** |
| * Alteration factory. |
| * |
| * Creates a alteration NFA for (at least) two NFA-fragments. |
| */ |
| function alt(first) { |
| for (var _len = arguments.length, fragments = Array(_len > 1 ? _len - 1 : 0), _key = 1; _key < _len; _key++) { |
| fragments[_key - 1] = arguments[_key]; |
| } |
| |
| var _iteratorNormalCompletion = true; |
| var _didIteratorError = false; |
| var _iteratorError = undefined; |
| |
| try { |
| for (var _iterator = fragments[Symbol.iterator](), _step; !(_iteratorNormalCompletion = (_step = _iterator.next()).done); _iteratorNormalCompletion = true) { |
| var fragment = _step.value; |
| |
| first = altPair(first, fragment); |
| } |
| } catch (err) { |
| _didIteratorError = true; |
| _iteratorError = err; |
| } finally { |
| try { |
| if (!_iteratorNormalCompletion && _iterator.return) { |
| _iterator.return(); |
| } |
| } finally { |
| if (_didIteratorError) { |
| throw _iteratorError; |
| } |
| } |
| } |
| |
| return first; |
| } |
| |
| // ----------------------------------------------------------------------------- |
| // Disjunction NFA fragment: `a|b` |
| |
| /** |
| * Creates a disjunction choice between two fragments. |
| */ |
| function orPair(first, second) { |
| var inState = new NFAState(); |
| var outState = new NFAState(); |
| |
| inState.addTransition(EPSILON, first.in); |
| inState.addTransition(EPSILON, second.in); |
| |
| outState.accepting = true; |
| first.out.accepting = false; |
| second.out.accepting = false; |
| |
| first.out.addTransition(EPSILON, outState); |
| second.out.addTransition(EPSILON, outState); |
| |
| return new NFA(inState, outState); |
| } |
| |
| /** |
| * Disjunction factory. |
| * |
| * Creates a disjunction NFA for (at least) two NFA-fragments. |
| */ |
| function or(first) { |
| for (var _len2 = arguments.length, fragments = Array(_len2 > 1 ? _len2 - 1 : 0), _key2 = 1; _key2 < _len2; _key2++) { |
| fragments[_key2 - 1] = arguments[_key2]; |
| } |
| |
| var _iteratorNormalCompletion2 = true; |
| var _didIteratorError2 = false; |
| var _iteratorError2 = undefined; |
| |
| try { |
| for (var _iterator2 = fragments[Symbol.iterator](), _step2; !(_iteratorNormalCompletion2 = (_step2 = _iterator2.next()).done); _iteratorNormalCompletion2 = true) { |
| var fragment = _step2.value; |
| |
| first = orPair(first, fragment); |
| } |
| } catch (err) { |
| _didIteratorError2 = true; |
| _iteratorError2 = err; |
| } finally { |
| try { |
| if (!_iteratorNormalCompletion2 && _iterator2.return) { |
| _iterator2.return(); |
| } |
| } finally { |
| if (_didIteratorError2) { |
| throw _iteratorError2; |
| } |
| } |
| } |
| |
| return first; |
| } |
| |
| // ----------------------------------------------------------------------------- |
| // Kleene-closure |
| |
| /** |
| * Kleene star/closure. |
| * |
| * a* |
| */ |
| function repExplicit(fragment) { |
| var inState = new NFAState(); |
| var outState = new NFAState({ |
| accepting: true |
| }); |
| |
| // 0 or more. |
| inState.addTransition(EPSILON, fragment.in); |
| inState.addTransition(EPSILON, outState); |
| |
| fragment.out.accepting = false; |
| fragment.out.addTransition(EPSILON, outState); |
| outState.addTransition(EPSILON, fragment.in); |
| |
| return new NFA(inState, outState); |
| } |
| |
| /** |
| * Optimized Kleene-star: just adds ε-transitions from |
| * input to the output, and back. |
| */ |
| function rep(fragment) { |
| fragment.in.addTransition(EPSILON, fragment.out); |
| fragment.out.addTransition(EPSILON, fragment.in); |
| return fragment; |
| } |
| |
| /** |
| * Optimized Plus: just adds ε-transitions from |
| * the output to the input. |
| */ |
| function plusRep(fragment) { |
| fragment.out.addTransition(EPSILON, fragment.in); |
| return fragment; |
| } |
| |
| /** |
| * Optimized ? repetition: just adds ε-transitions from |
| * the input to the output. |
| */ |
| function questionRep(fragment) { |
| fragment.in.addTransition(EPSILON, fragment.out); |
| return fragment; |
| } |
| |
| module.exports = { |
| alt: alt, |
| char: char, |
| e: e, |
| or: or, |
| rep: rep, |
| repExplicit: repExplicit, |
| plusRep: plusRep, |
| questionRep: questionRep |
| }; |