| Re2c | |
|---|---|
| Typ | bezplatný a open source software a generátor lexikálního analyzátoru [d] |
| Zapsáno v | C a C++ |
| Operační systém | multiplatformní |
| První vydání | 1994 [1] |
| Nejnovější verze | |
| Stát | aktivní |
| webová stránka | re2c.org _ |
| Mediální soubory na Wikimedia Commons | |
re2c ( r egular e xpression t o c , r egular e xpression t o kod ) je bezplatný open source generátorový nástroj , který generuje rychlé a snadno vložitelné lexery orientované na práci s jazyky: C , C++ , Go , Rust .
Nástroj byl původně vytvořen Peterem Bumbulisem a popsán ve svém článku [3] , později byl re2c uvolněn do veřejné domény a od té doby je spravován dobrovolníky [4] .
Nástroj se liší od svých známějších analogů (jako je lex a flex ) v tom, že má flexibilní interakční rozhraní (vygenerovaný kód interaguje s externím programem pomocí primitiv), generuje optimalizované netabulkové lexery, podporuje capture (extrakce submatch ) založené na deterministických konečných automatech s tagy (TDFA).
Nástroj se používá hlavně v projektech, kde je vyžadována vysoká rychlost syntaxe , jako je Ninja [5] a PHP [6] .
Hlavním cílem re2c je generovat rychlé lexery [3] , které jsou alespoň tak rychlé jako rozumně optimalizované ručně psané C lexery . Namísto použití tradičního tabulkového přístupu kóduje re2c vygenerovaný stavový stroj přímo ve formě podmínek a srovnání. Výsledkem je, že program je rychlejší než jeho tabulkový protějšek [3] a mnohem snadněji se ladí a rozumí. Navíc tento přístup často vede k menším lexerům [3] , protože re2c používá řadu optimalizací, jako je minimalizace DFA a konstrukce tunelových automatů [7] . Další skvělou vlastností re2c je jeho flexibilní rozhraní. Namísto použití fixní šablony programu umožňuje re2c programátorovi napsat většinu kódu rozhraní a přizpůsobit vygenerovaný lexer libovolnému danému prostředí. Hlavní myšlenkou je, že re2c by mělo být pro programátora abstrakcí s nulovými náklady a použití nástroje by nikdy nemělo způsobit pomalejší běh programu než odpovídající ručně kódovaná implementace.
Implementace je založena na algoritmu "lookahead-TDFA" [10] [11] [12] ;
Program re2c může obsahovat libovolný počet /*!re2c ... */bloků. Každý blok se skládá z posloupnosti pravidel, definic a konfigurací (lze je kombinovat, ale obvykle je nejlepší dát nejprve konfigurace, pak definice a pak pravidla). Pravidla mají tvar - REGEXP { CODE }nebo REGEXP := CODE;, kde REGEXPje regulární výraz a CODE- je blok kódu C. Když REGEXPse shoduje se vstupním řetězcem, řídicí tok se přenese do odpovídajícího bloku CODE. Existuje jedno speciální pravidlo: výchozí pravidlo s *namísto REGEXP, spustí se, pokud žádná jiná pravidla neodpovídají. re2c má sémantiku chamtivé shody – pokud se shoduje více pravidel, upřednostňuje se pravidlo odpovídající delší předponě, pokud konfliktní pravidla odpovídají stejné předponě, pak má přednost dřívější pravidlo. Definice mají formu NAME = REGEXP;(a podle toho NAME { REGEXP }v režimu kompatibilním s Flex). Konfigurace mají tvar re2c:CONFIG = VALUE;, kde CONFIGje název konkrétní konfigurace a VALUEje to buď číslo nebo řetězec. Pro pokročilejší použití nahlédněte do oficiálního manuálu re2c [20] .
re2c používá pro regulární výrazy následující syntaxi:
Třídy znaků a řetězcové literály mohou obsahovat následující sekvence escape: \a, \b, \f, \n, \r, \t, \v, \\, osmičkové \oooa šestnáctkové \xhh, \uhhhh, \Uhhhhhhhh.
Následuje příklad jednoduchého programu re2c v souboru example.re . Kontroluje, že všechny vstupní argumenty jsou desetinná čísla. Kód pro re2c je zarámován v komentářích /*!re2c ... */[21] .
C :
// re2c $INPUT -o $OUTPUT -i --case-ranges #include <assert.h> bool lex ( const char * s ) { const char * YYCURSOR = s ; /*!re2c re2c:yyfill:enable = 0; re2c:define:YYCTYPE = char; číslo = [1-9][0-9]*; číslo { return true; } * { return false; } */ } int main () { tvrdit ( lex ( "1234" )); návrat 0 ; }Vzhledem k tomu, že příkaz $ re2c -is -o example.c example.regeneruje níže uvedený kód ( example.c ). Obsah komentáře /*!re2c ... */je nahrazen deterministickým konečným automatem zakódovaným jako podmíněné skoky a porovnání, zbytek programu je doslovně zkopírován do výstupního souboru. Existuje několik možností pro generování kódu, obvykle re2c používá operátor switch, ale může používat vnořené operátory if(jako v tomto příkladu s volbou -s) nebo generovat bitmapy a tabulky skoků . Která možnost je lepší závisí na kompilátoru C , uživatelům re2c se doporučuje experimentovat.
/* Generováno re2c */ // re2c $INPUT -o $OUTPUT -i --case-ranges #include <assert.h> bool lex ( const char * s ) { const char * YYCURSOR = s ; { char yych ; yych = * YYCURSOR ; přepínač ( yych ) { případ '1' ... '9' : goto yy2 ; výchozí : goto yy1 ; } yy1 : ++ YYCURSOR ; { return false ; } yy2 : yych = *++ YYCURSOR ; přepínač ( yych ) { případ '0' ... '9' : goto yy2 ; výchozí : goto yy3 ; } yy3 : { return true ; } } } int main () { tvrdit ( lex ( "1234" )); návrat 0 ; }jít :
//go:generate re2go $INPUT -o $OUTPUT -i hlavní balíček func lex ( str řetězec ) { var kurzor int /*!re2c re2c:define:YYCTYPE = byte; re2c:define:YYPEEK = "str[kurzor]"; re2c:define:YYSKIP = "kurzor += 1"; re2c:yyfill:enable = 0; číslo = [1-9][0-9]*; číslo { vrátit } * { panika("chyba!") } */ } func main () { lex ( "1234\x00" ) } // Kód vygenerovaný re2c, NEUPRAVUJTE. //go:generate re2go $INPUT -o $OUTPUT -i hlavní balíček func lex ( str řetězec ) { var kurzor int { var yych byte yych = str [ kurzor ] přepínač ( yych ) { velikost písmen '1' , '2' , '3' , '4' , '5' , '6' , '7' , '8' , '9' : goto yy2 výchozí : goto yy1 } yy1 : kurzor += 1 { panika ( "chyba!" ) } yy2 : kurzor += 1 yych = str [ kurzor ] přepínač ( yych ) { velikost písmen '0' , '1' , '2' , '3' , '4' , '5' , '6' , '7' , '8' , '9' : goto yy2 výchozí : goto yy3 } yy3 : { vrátit } } } func main () { lex ( "1234\x00" ) }Rez :
// re2rust $INPUT -o $OUTPUT fn lex ( s : & [ u8 ]) -> bool { nech mut kurzor = 0 ; /*!re2c re2c:define:YYCTYPE = u8; re2c:define:YYPEEK = "*s.get_unchecked(kurzor)"; re2c:define:YYSKIP = "kurzor += 1;"; re2c:yyfill:enable = 0; číslo = [1-9][0-9]*; číslo { return true; } * { return false; } */ } fn main () { tvrdit! ( lex ( b"1234 \0 " )); } /* Generováno re2c */ // re2rust $INPUT -o $OUTPUT fn lex ( s : & [ u8 ]) -> bool { nech mut kurzor = 0 ; { #[allow(unused_assignments)] nech mut yych : u8 = 0 ; let mut yystate : useize = 0 ; ' yyl : smyčka { stav shody { 0 => { yych = nebezpečné { * s . get_unchecked ( kurzor )}; kurzor += 1 ; odpovídat yych { 0x31 ..= 0x39 => { yystate = 2 ; pokračovat 'yyl ; } _ => { yystate = 1 ; pokračovat 'yyl ; } } } 1 => { return false ; } 2 => { yych = nebezpečné { * s . get_unchecked ( kurzor )}; odpovídat yych { 0x30 .. = 0x39 _ kurzor += 1 ; yystate = 2 ; pokračovat 'yyl ; } _ => { yystate = 3 ; pokračovat 'yyl ; } } } 3 => { return true ; } _ => { panika! ( "interní chyba lexera" ) } } } } } fn main () { tvrdit! ( lex ( b"1234 \0 " )); }