Regexy II
=========

## Backtracking ##

('a' x 999) ~~ rx{^(aa|aaaa)*$}         <-- exponenciální
('a' x 9) ~~ rx{^(a|aa)(aa)*$}          <-- backtrackuje přes volby v |
('a' x 9) ~~ rx{^(a|aa):(aa)*$}         <-- zákaz BT => selže (podobně :r)

('a' x 9) ~~ rx{^(a+)([aa]+)$}          <-- backtrackuje přes "+
('a' x 9) ~~ rx:r{^(a+)([aa]+)$}        <-- zákaz BT => selže
('a' x 9) ~~ rx:r{^(a+!)([aa]+)$}       <-- pro konkrétní "+" povolím BT

## Longest token match (co doopravdy dělá A|B) ##

Vítězí nejdelší "čistokrevný prefix":
  * patří do něj vše vyhodnotitelne bez side-efektů
  * zalézá se i do podregexů, ale nikoliv rekurzivně
  * idiom {} pro ukončení prefixu
-> Perl6 si odvozuje vlastní tokenizer

## Příslovce ##

Při deklaraci regexu (mohou být i kdekoliv uvnitř):
  :i :ignorecase    <-- nerozlišovat velká/malá písmena
  :r :ratchet       <-- zákaz backtrackingu
  :s :sigspace      <-- signifikantní whitespace (volá <ws>, kdekoliv se
                        v regexu objeví mezery)

			Defaultní <ws> pravidlo ekvivalentní /<!ww>\s*/
			-- tedy mezi dvěma znaky slova povinné mezery,
			jinde volitelné.

			Např.:
			"my   sub"  ~~ rx:s/my sub/
			"mysub"    !~~ rx:s/my sub/
			"1+  1"	    ~~ rx:s/\d+  "+"  \d+/

Při matchování:
  :c(N) :continue(N)  <-- pokračuje od dané pozice
  :c :continue      <-- pokračuje od $/.to, je-li $/ definováno (jinak 0)
  :p(N) :pos(N)     <-- vyžaduje výskyt začínající na dané pozici
  :g :global        <-- hledá všechny nepřekrývající se výskyty, $/=list
  :e :exhaustive    <-- ... i ty překrývající se
  :o :overlap       <-- pro každou pozici nejdelší výskyt

Gramatiky
---------

Skupina pojmenovaných regexů, které se na sebe odkazují, dohromady obvykle
parsuje nějaký jazyk. Ve skutečnosti třída, regexy=metody.

Regexové deklarátory:
  * regex { ... }
  * token { ... } <---> regex { :r ... }     # zakazuje backtrackování
  * rule  { ... } <---> regex { :r :s ... }  # + sigspace

grammar SimpleJSON {
    token string-char { <-[\\\"]> | '\u' <[0..9]>**4 | \\<["/\\bfnrt]> }
    token string      { '"' <.string-char>*? '"' }
    token integer     { '-'? <[0..9]>+ }
    rule value        { <string> | <integer> | <list>  }
    rule list         { '[' <value> * % ',' ']' }
    rule TOP          { \s* <value> \s* } # na krajích sigspace nezabere
}

Gramatika má metodu parse, která matchuje pravidlo TOP a vrací Match objekt.
Díky automatickému zachytávání <...> výsledek je syntaktický strom.

> say SimpleJSON.parse(q{  [42, "hroch", [1, 2]]  })
'[42, "hroch", [1, 2]]'
 value => '[42, "hroch", [1, 2]]'
  list => '[42, "hroch", [1, 2]]'
   value => '42'
    integer => '42'
   value => '"hroch"'
    string => '"hroch"'
   value => '[1, 2]'
    list => '[1, 2]'
     value => '1'
      integer => '1'
     value => '2'
      integer => '2'

## Dědičnost ##

Gramatiky jsou třídy, dají se dědit. Jednotlivá pravidla jsou interně
metody: dají se předefinovat a můžete se odkázat na zděděnou (přímo,
zatím moc nefungují callwith a spol). Platí běžná pravidla dědičnosti
a MRO, můžete používat role.

grammar BetterJSON is SimpleJSON {
    rule object { '{' <field> * % ',' '}' }
    rule field { <key=.string> ':' <value> }
    rule value { <SimpleJSON::value> | <object> } # odkaz na zděděné pravidlo
}

## AST ##

Umožňuje jednotlivých uzlům gramatického stromu přiřazovat sémantické
hodnoty.

grammar AST-JSON {
    token string-char {   (<-[\\\"]>)	     {make ~$0}
                        | '\u' (<[0..9]>**4) {make "0x$0".chr}
                        | \\<["/\\bfnrt]>    {#`[TODO]}
		      }
    token string      { '"' <string-char>*? '"'
			    {make $<string-char>>>.ast.join("")} }
    token integer     { ('-'? <[0..9]>+)	{make +$0} }
    rule value        { [<v=string> | <v=integer> | <v=list>] {make $<v>.ast} }
    rule list         { '[' <value> * % ',' ']' {make $<value>>>.ast} }
    rule TOP          { \s* <value> \s*		{make $<value>.ast} }
}

> say AST-JSON.parse(q{[42, "hroch", [1, 2]]  }).ast.perl;
[42, "hroch", [1, 2]]

Vysvětlení:
{ kód }	    <-- spustí zadaný kód pokud zpracování regexu dojde na dané místo,
		má přístup k učiněným captures (jako <?{}>)
make ...    <-- nastaví AST hodnotu aktuálního submatche
$match.ast  <-- vytáhne AST z hotového match objektu (nebo $match.made)

## Další ##

Modul Grammar::Tracer umí ukázat průběh parsování gramatikou:

use Grammar::Tracer;
grammar SimpleJSON { ... }
SimpleJSON.parse('["xy", 42, c]')

## Protoregexy ###

Hezký způsob, jak psát rozšiřitelné gramatiky pomocí multi-dispatche:
*Nefunkční* příklad:

grammar Expr {
    rule TOP { <expr> }
    proto rule expr {*}
    rule expr:sym<num> { <num> }
    rule expr:sym<add> { <expr> '+' <num> }
    rule expr:sym<sub> { <expr> '-' <num> }
    token num { \d+ }
}

Co je špatně?

  - levá rekurze se zacyklí => nutno prohodit na <num> '+' <expr>
  - proto rule se nechová jako implicitní OR, backtrackuje se
    přes něj podivně (možná bug?)
  - potřebujeme, aby se zvolil longest prefix, ale implicitní <.ws>
    přeruší prefix

Opraveno:

grammar Expr {
    rule TOP { <expr> }
    proto token expr {*}
    token expr:sym<num> { <num> }
    token expr:sym<add> { <num> <.s> '+' <.s> <expr> }
    token expr:sym<sub> { <num> <.s> '-' <.s> <expr> }
    token num { \d+ }
    token s { \s* }
}

Balíčky a moduly
================

## Balíčky (namespacy) ##

package P {
    my sub my-func {}	    <-- lexikální metoda, není vidět zvenku
    sub func {}		    <-- taktéž ('my' je default)
    our sub our-func {}     <-- tahle je veřejná (je v tabulce symbolů balíčku)

    our $var;		    <-- stejně pro proměnné
}

P::our-func	<-- volání metody z balíčku
$P::var		<-- přístup k proměnné z balíčku

package P { our sub f {} }
package P { our sub g {} }  <-- balíček lze později doplnit
class X { our sub f {} }    <-- třída je také balíček

# Vnořené balíčky

package P {
    package Q {		<-- vnořený balíček (ušetří úroveň závorek / odsazení)
	our sub foo {}
    }
    sub bar {
	Q::foo;		<-- relativní odkaz
	P::Q::foo;	<-- absolutní odkaz
    }
}
package P::Q {		<-- jiný zápis téhož (lze kombinovat)
    our sub zz {}
}

unit package P::Q::R;	<-- celý zbytek souboru patří do balíčku
our sub { ... }		    (ušetří se jedna úroveň závorek/odsazení)

## Hierarchická jména ##

MFF::SIS             <-- samotný balíček
$MFF::SIS::delay     <-- skalární proměnná uvnitř balíčku
MFF::SIS::<$delay>   <-- jiná syntaxe pro totéž
$wait                <-- zkusíme lexikálně lokální, pak aktuální balíček
$MFF::($system)::x   <-- interpolace části názvu
$::($name)           <-- interpolované lokální jméno

Standardní pořadí hledání (a příslušné pseudo-balíčky):

  * aktuální lexikální scope (MY::)
  * nadřazené lexikální scopes
  * lexikální scope kompilační jednotky (souboru, UNIT::)
  * vnější lexikální scope (standardní součášti jazyka, CORE::)
  * aktuální balíček (OUR::)
    [balíček ale najde své proměnné definované pomocí our
    dřív díky lexikálním aliasům]

Další pseudo-balíčky:

  * GLOBAL     <-- globální pro interpret (zde bydlí hlavní program)
  * PROCESS    <-- globální pro proces (zde je třeba $*IN)
  * DYNAMIC    <-- lexikální scope můj nebo kohokoliv z volajících

Balíček lze používat jako heš:

  * PROCESS::{'PERL'}  <-- totéž jako PROCESS::PERL nebo $*PERL
  * CORE::.keys

## Moduly ##

Část programu zapsaná v samostatném souboru (či více souborech),
typicky obsahuje jednu či více packages.

need MFF::SIS;    <-- načte a přeloží daný modul
use MFF::SIS;     <-- ... a navíc importuje symboly (vytvoří lexikální aliasy)

unit module MFF::SIS;

sub something($x) is export { ... }

  - is export(:some-tag)  ... pak funguje use Module :tag;
  - tag DEFAULT   <-- neuvedeme-li při import tag
  - tag MANDATORY <-- importuje se vždy nezávisle na tagách

Co se děje uvnitř:

  * Export přidá symbol do package UNIT::EXPORT::tag
  * Introspekce: dd URI::Escape::EXPORT::DEFAULT::.keys;