Как я верстал форму регистрации

Однажды мне доверили реализовать
форму регистрации

После месяца дискуссий, боев и противостояний

<input type="email"/>

Проблемка...

пробелы + проверка на сервере === собственная валидация 
    
//MDN
/^[a-zA-Z0-9.!#$%&'*+\/=?^_`{|}~-]+
  @[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}
   [a-zA-Z0-9])?(?:\.[a-zA-Z0-9]
   (?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?)*
$/

QA

Открыли википедию - Email address

Valid email addresses






one-letter local-part


local domain name with no TLD, although ICANN highly discourages dotless email addresses


see the List of Internet top-level domains

space between the quotes

Invalid email addresses


no @ character
only one @ is allowed outside quotation marks
none of the special characters in this local-part are allowed outside quotation marks
quoted strings must be dot separated or the only element making up the local-part
spaces, quotes, and backslashes may only exist when within quoted strings and preceded by a backslash
even if escaped (preceded by a backslash), spaces, quotes, and backslashes must still be contained by quotes
local part is longer than 64 characters
double dot before @
double dot after @
http://emailregex.com/

General Email Regex
RFC 5322 Official Standard

(?:[a-z0-9!#$%&'*+/=?^_`{|}~-]+(?:\.[a-z0-9!#$%&'*+/=?^_`{|}~-]+)*|"(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21\x23-\x5b\x5d-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])*")@(?:(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?\.)+[a-z0-9](?:[a-z0-9-]*[a-z0-9])?|\[(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?|[a-z0-9-]*[a-z0-9]:(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21-\x5a\x53-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])+)\])

Проверяем ...

Valid

Invalid

Finite Automata
алгоритм реализации
RegExp

Набор состояний
 

Переходы между состояниями
 

Одно состояние - начальное
 

Как минимум одно
конечное состояние

Все переходы происходят при
определенном условии

Если взглянуть подробнее на регулярные выражения, то всех их можно привести к трем простым операциям

Попробуем реализовать FA для выражения a*b*c*

Попробуем реализовать FA для выражения a*b*c*

Ок, а как это запрограммировать? (DFA)

Исходное состояние

Прочитали "a" -> переход в "S1"

Прочитали "b" -> переход в "S2"

Прочитали "c" -> переход в "S3"

Код обхода графа
довольно простой.


//Матрица переходов
const TRANSITIONS = [...];

//Входная строка (например "abbbcc")
const input = ...

let i = 0
let state = 0;
while (input[i]) {
    state = TRANSITIONS[state][input[i++]]
}

Обработка ошибок также тривиальная.


//Матрица переходов
const TRANSITIONS = [...];

//Входная строка (например "abbbcc")
const input = ...

let i = 0
let state = 0;
while (input[i]) {
    state = TRANSITIONS[state][input[i++]]
}

NFA

Исходное состояние

Символ "a"

Символ "b"

Символ "c"

Пробуем в бою

Email regexp


/^[a-zA-Z0-9.!#$%&'*+\/=?^_`{|}~-]+
  @[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}
  [a-zA-Z0-9])?(?:\.[a-zA-Z0-9]
  (?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?)*$/

Очевидно, что должны быть алгоритмы автоматической конвертации
RegEx в DFA и NFA.

Thompson's construction
FSM2Regex
Automata.js

Засада!

Мы можем сказать где у нас возникла ошибка,
но не можем сказать, причину этой ошибки

Ошибка, как она есть

        ^
   Здеся ошибка

Как бы хотелось

Собака!
Мил господин,
а собачку(@) ты ведь забыл вставить!

Как бы хотелось

               ^
Все классно, только вот было бы еще хорошо добавить доменное имя. .com или .org к примеру

Lexer -> Parser -> Semantic Analysis -> Optimization -> Code gen

Контекстно-свободные грамматики

Контекстно-свободная грамматика (сокращенно КС грамматика) - формальная грамматика типа 2 в иерархии Хомски.

Контекстно-свободная грамматика \(G\) это четверка \((N,T,P,S)\):

При этом, используют такие названия:
\(N\) — множество нетерминальных символов,
\(T\) — множество терминальных символов,
\(P\) — множество правил вывода
\(S\) начальный символ.
Правила \( (\alpha ,\beta )\in P \) записывают как \(\alpha \rightarrow \beta \).
В левой части правила вывода должен находиться одна переменная (нетерминальный символ).
Формально, должен выполняться \( \alpha \in N,\beta \in (N\cup T)^{*}, де |\beta |\geq 1\).
Расширением КС-грамматик является стохастические КВ грамматики. Правилам вывода сопоставляют вероятность использования: \( \rho :P\rightarrow \mathbb {R} \) де \( \sum _{p_{r}\in P_{r}}\rho (p_{r})=1 \)

Aliens vs predator 

Exp  -> Term + Exp
      | Term

Term -> ( Exp )
      | Int * Term
      | Int

Int  -> 1 | 2 | 3 |
        4 | 5 | 6 |
        7 | 8 | 9 | 0

// Грамматика для арифметических выражений типа: 1 + 3 * ( 8 + 5 )
Стартовый символ Продукция
(production) Нетерминальные символы (non terminal) Терминальные символы (terminal) 

Exp  -> Term + Exp
      | Term

Term -> ( Exp )
      | Int * Term
      | Int

Int  -> 1 | 2 | 3 |
        4 | 5 | 6 |
        7 | 8 | 9 | 0

Превращаем это все в код


    Exp  -> Term + Exp
          | Term

    Term -> ( Exp )
          | Int * Term
          | Int

    Int  -> 1
          | 2
          | 3
          | 4
          | 5
          | 6
          | 7
          | 8
          | 9
          | 0

Каждая продукция - это функция


    const Exp  = () => {
        return Term + Exp
             | Term
    }

    const Term = () => {
        return ( Exp )
             | Int * Term
             | Int
    }

    const Int  = () => {
        return 1
              | 2
              | 3
              | 4
              | 5
              | 6
              | 7
              | 8
              | 9
              | 0
        }

Каждый нетерминальный символ - вызов функции.


    const Exp  = () => {
        return Term() + Exp()
             | Term()
    }

    const Term = () => {
        return ( Exp()  )
             | Int() * Term()
             | Int()
    }

    const Int  = () => {
        return 1
             | 2
             | 3
             | 4
             | 5
             | 6
             | 7
             | 8
             | 9
             | 0
    }

Вписываем "&&" и "||", расставляем скобки


    const Exp  = () => {
        return ( Term() && + && Exp() )
            || ( Term() )
    }

    const Term = () => {
        return ( ( && Exp() && ) )
            || ( Int() && * && Term() )
            || ( Int() )
    }

    const Int  = () => {
        return ( 1 )
            ||( 2 )
            ||( 3 )
            ||( 4 )
            ||( 5 )
            ||( 6 )
            ||( 7 )
            ||( 8 )
            ||( 9 )
            ||( 0 )
    }

Все терминальные символы используем через функцию match


    const match = (term) => {}

    const Exp  = () => {
        return ( Term() && match(+) && Exp() )
            || ( Term() )
    }

    const Term = () => {
        return ( match(() && Exp() && match()) )
            || ( Int() && match(*) && Term() )
            || ( Int() )
    }

    const Int  = () => {
        return ( match(1) )
            || ( match(2) )
            || ( match(3) )
            || ( match(4) )
            || ( match(5) )
            || ( match(6) )
            || ( match(7) )
            || ( match(8) )
            || ( match(9) )
            || ( match(0) )
    }

Добавляем работу с указателем 


    let i = 0
    const match = (term) => {}

    const Exp =  () => {
        const s = i;
        return (i = s, Term() && match("+") && Exp() )
            || (i = s, Term() )
    }

    const Term = () => {
        const s = i;
        return (i = s, match("(") && Exp && match(")") )
            || (i = s, Int() && match("*") && Term() )
            || (i = s, Int() )
    }

    const Int  = () => {
        const s = i;
        return (i = s, match("1") )
            || (i = s, match("2") )
            || (i = s, match("3") )
            || (i = s, match("4") )
            || (i = s, match("5") )
            || (i = s, match("6") )
            || (i = s, match("7") )
            || (i = s, match("8") )
            || (i = s, match("9") )
            || (i = s, match("0") )
    }

Реализуем match, и добавляем враппер


const Parser (input){
    let i = 0
    const match = (term) => term === input[i++];

    const Exp =  () => {
        const s = i;
        return (i = s, Term() && match("+") && Exp() )
            || (i = s, Term() )
    }

    const Term = () => {
        const s = i;
        return (i = s, match("(") && Exp && match(")") )
            || (i = s, Int() && match("*") && Term() )
            || (i = s, Int() )
    }

    const Int  = () => {
        const s = i;
        return (i = s, match("1") )
            || (i = s, match("2") )
            || (i = s, match("3") )
            || (i = s, match("4") )
            || (i = s, match("5") )
            || (i = s, match("6") )
            || (i = s, match("7") )
            || (i = s, match("8") )
            || (i = s, match("9") )
            || (i = s, match("0") )
    }

    return Exp()
}

Ok теперь email

Internet Message Format. Spec RFC 5322
...
3.4.1. Addr-Spec Specification
...

RFC822: Standard for ARPA Internet Text Messages

ABNF


email-address   = local "@" domain
local           = local-word *("." local-word)
domain          = 1*(sub-domain ".") top-domain
local-word      = 1*local-char
sub-domain      = 1*sub-domain-char
top-domain      = 2*6top-domain-char
local-char      = alpha / num / special
sub-domain-char = alpha / num / "-"
top-domain-char = alpha
alpha           = %d65-90 / %d97-122
num             = %d48-57
special         = %d33 / %d35 / %d36-39 / %d42-43 / %d45 / %d47
            / %d61 / %d63 / %d94-96 / %d123-126

RegEx


Irregexp, Google Chrome's New Regexp Implementation
irregex
re2
Email Address Regular Expression That 99.99% Works.
Thompson's construction
FSM2Regex
Automata.js

Контекстно свободные грамматики


Augmented Backus–Naur form
apg-js2
An Alternative to Regular Expressions: apg-exp
PEG.js
nearley.js

Благодарю за внимание :)

Доклад: Как я верстал форму регистрации

https://neformal13.github.io/parsers-presentation/

Git
https://github.com/neformal13/parsers-presentation


Мыхайло Иванкив (Mykhailo Ivankiv)

twitter:
neformal
skype:
neformal.lviv
email:
neformal.lviv@gmail.com
github:
neformal13