Jedna z věcí, kterou člověk v reálném životě zcela jistě nebude potřebovat, jsou formální gramatiky. Je to něco podobného, jako definice group, pologroup, monoidů a jiných prkotin. Moc jsem to nikdy nepochopil a když nedávno známý sdílel na fejsbuku screen z wikipedie, tak jsem se rozhodl se podělit o naše gramatiky. Na obrázku, mimochodem, byla Teorie kategorií. Všimněte si dole souvisejícího článku Abstraktní nesmysl.

Formální gramatika se skládá z terminálů, neterminálů. Dělí se také na kontextové a bezkontextové. Tu druhou poznáte jednoduše, neterminály neobsahují žádný jiný terminál. To znamená, že gramatika generuje jazyk, jehož slova nejsou závislá na předchozím kontextu. To není náš případ. Nedávno jsme kontextovou gramatiku stavěli přímo v aplikaci.

S -> a | b | STS
T -> T | {}

Tato gramatika generuje jazyk: a, b, ab, abab, aaaa atd. v podstatě libovolnou sekvenci a a b.

Potřebovali jsme vytvořit pseudojazyk, jehož obsah by se vždy vyhodnotil a v podstatě nám řekl, co člověk chce. Ať už to napíše, jak chce a v jakémkoliv pořadí. Například takovéto požadavky:

resolved
not resolved
!resolved
resolved by martin
resolved by: martin
resolved by not martin
resolved by martin and tomas
resolved by martin, tomas
resolved by martin and not tomas
resolved by martin&&!tomas
assigned to martin
assignee martin
resolved by not martin and not resolved, order by updated
resolved by not martin and not resolved order by updated
resolved by not martin || (!tomas or jirka)
resolved by martin || (!tomas | jirka)

a mohl bych pokračovat. Na první pohled to není nic složitého, ale bez formálních gramatik je implementace něčeho takového akorát cesta do pekla. S formálními gramatikami je to v podstatě jednoduché. Konec konců, programovací jazyky jsou také více či méně formálními gramatikami. Parsování probíhá tak, že se parsuje zleva doprava stejně, jako běžně v Evropě čteme. Pravidla jsou aplikována postupně a je nutné dávat pozor, které pravidlo má vyšší priroritu, protože správně by se mělo vzít první vyhovující pravidlo a pokračovat v gramatice dále. Jakmile žádné následující pravidlo nevyhovuje, můžeme říci, že následující jazyk není generován danou gramatikou. V tom lepším případě to projde a my máme přesně zmapováno, co větou člověk chtěl říci a podle toho mu pošleme výsledky vyhledávání.