| Re2c | |
|---|---|
| Tip de | software gratuit și open source și generator de analizor lexical [d] |
| Scris in | C și C++ |
| Sistem de operare | multiplatformă |
| Prima editie | 1994 [1] |
| ultima versiune |
|
| Stat | activ |
| Site-ul web | re2c.org _ |
| Fișiere media la Wikimedia Commons | |
re2c ( r egular e xpression to c , r egular e xpression to c ode ) este un utilitar gratuit generator open source care generează lexeri rapid și ușor de încorporat , orientat să lucreze cu limbaje: C , C ++ , Go , Rust .
Utilitarul a fost creat inițial de Peter Bumbulis și descris în articolul său [3] , mai târziu re2c a fost eliberat în domeniul public și de atunci a fost întreținut de voluntari [4] .
Utilitarul diferă de analogii săi mai cunoscuți (cum ar fi lex și flex ) prin faptul că are o interfață de interacțiune flexibilă (codul generat interacționează cu un program extern folosind primitive), generează lexeri optimizați non-tabel, acceptă capturi (extracția submatch-urilor). ) bazat pe automate finite deterministe cu etichete (TDFA).
Utilitarul este utilizat în principal în proiecte în care este necesară analizarea de mare viteză a sintaxei , cum ar fi Ninja [5] și PHP [6] .
Scopul principal al re2c este de a genera lexeri rapidi [3] care sunt cel puțin la fel de rapid ca lexerele C scrise de mână optimizate în mod rezonabil . În loc să folosească abordarea tradițională a foii de calcul, re2c codifică mașina de stare generată direct sub formă de condiționale și comparații. Ca rezultat, programul este mai rapid decât omologul său bazat pe tabel [3] și mult mai ușor de depanat și de înțeles. Mai mult, această abordare duce adesea la lexeri mai mici [3] deoarece re2c aplică o serie de optimizări, cum ar fi minimizarea DFA și construcția automatelor de tunel [7] . O altă caracteristică excelentă a re2c este interfața sa flexibilă. În loc să folosească un șablon de program fix, re2c permite programatorului să scrie cea mai mare parte a codului de interfață și să adapteze lexerul generat la orice mediu dat. Ideea principală este că re2c ar trebui să fie o abstracție cu costuri zero pentru programator, utilizarea utilitarului nu ar trebui să facă niciodată programul să ruleze mai lent decât implementarea corespunzătoare codificată manual.
Implementarea se bazează pe algoritmul „lookahead-TDFA” [10] [11] [12] ;
Programul re2c poate conține orice număr /*!re2c ... */de blocuri. Fiecare bloc constă dintr-o secvență de reguli, definiții și configurații (pot fi amestecate, dar de obicei cel mai bine este să puneți mai întâi configurațiile, apoi definițiile, apoi regulile). Regulile sunt de forma - REGEXP { CODE }sau REGEXP := CODE;, unde REGEXPeste o expresie regulată și CODE- este un bloc de cod C. Când REGEXPse potrivește cu șirul de intrare, fluxul de control este transferat la blocul corespunzător CODE. Există o regulă specială: regula implicită cu *în loc de REGEXP, se declanșează dacă nu se potrivește alte reguli. re2c are o semantică de potrivire lacomă - dacă mai multe reguli se potrivesc, este preferată regula care se potrivește cu prefixul mai lung, dacă regulile în conflict se potrivesc cu același prefix, atunci regula anterioară are prioritate. Definițiile au forma NAME = REGEXP;(și în consecință NAME { REGEXP }în modul compatibil Flex). Configurațiile sunt de forma re2c:CONFIG = VALUE;, unde CONFIGeste numele unei anumite configurații și VALUEeste fie un număr, fie un șir. Pentru o utilizare mai avansată, consultați manualul oficial re2c [20] .
re2c folosește următoarea sintaxă pentru expresiile regulate:
Clasele de caractere și literalele șir pot conține următoarele secvențe de escape: \a, \b, \f, \n, \r, \t, \v, \\, octal \oooși hexazecimal \xhh, \uhhhh, \Uhhhhhhhh.
Următorul este un exemplu de program re2c simplu în fișierul example.re . Se verifică dacă toate argumentele de intrare sunt numere zecimale. Codul pentru re2c este încadrat în comentarii /*!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; număr = [1-9][0-9]*; număr { return true; } * { return false; } */ } int main () { afirma ( lex ( "1234" )); returnează 0 ; }Având în vedere că comanda $ re2c -is -o example.c example.regenerează codul de mai jos ( example.c ). Conținutul comentariului /*!re2c ... */este înlocuit cu un automat finit determinist codificat ca salturi și comparații condiționate, restul programului este copiat textual în fișierul de ieșire. Există mai multe opțiuni pentru generarea codului, de obicei re2c folosește operatorul ,switch dar poate folosi operatori imbricați if(ca în acest exemplu cu opțiunea -s) sau poate genera hărți de biți și tabele de salt . Ce opțiune este mai bună depinde de compilatorul C , utilizatorii re2c sunt încurajați să experimenteze.
/* Generat de re2c */ // re2c $INPUT -o $OUTPUT -i --case-ranges #include <assert.h> bool lex ( const char * s ) { const char * YYCURSOR = s ; { char yych ; yych = * YYCURSOR ; comutator ( yych ) { case '1' ... '9' : du -te la yy2 ; implicit : du- te la yy1 ; } aa1 : ++ YYCURSOR ; { return false ; } aa2 : yych = *++ YYCURSOR ; comutator ( yych ) { case '0' ... '9' : du -te la yy2 ; implicit : du- te la yy3 ; } aa3 : { return true ; } } } int main () { afirma ( lex ( "1234" )); returnează 0 ; }du-te :
//go:generate re2go $INPUT -o $OUTPUT -i pachet principal func lex ( șir de caractere ) { var cursor int /*!re2c re2c:define:YYCTYPE = octet; re2c:define:YYPEEK = "str[cursor]"; re2c:define:YYSKIP = "cursor += 1"; re2c:yyfill:enable = 0; număr = [1-9][0-9]*; număr { return } * { panică ("eroare!") } */ } func principal () { lex ( "1234\x00" ) } // Cod generat de re2c, NU EDIȚI. //go:generate re2go $INPUT -o $OUTPUT -i pachet principal func lex ( șir de caractere ) { var cursor int { var yych octet yych = str [ cursor ] comutator ( yych ) { caz „1” , „2” , „3” , „4” , „5” , „6” , „7” , „8” , „9” : du- te la yy2 implicit : du- te la yy1 } aa1 : cursorul += 1 { panică ( "eroare!" ) } aa2 : cursorul += 1 yych = str [ cursor ] comutator ( yych ) { caz „0” , „1” , „2” , „3” , „4” , „5” , „6” , „7” , „8” , „9” : du- te la yy2 implicit : du- te la yy3 } aa3 : { return } } } func principal () { lex ( "1234\x00" ) }Rugina :
// re2rust $INPUT -o $OUTPUT fn lex ( s : & [ u8 ]) -> bool { lasă mut cursorul = 0 ; /*!re2c re2c:define:YYCTYPE = u8; re2c:define:YYPEEK = "*s.get_unchecked(cursor)"; re2c:define:YYSKIP = "cursor += 1;"; re2c:yyfill:enable = 0; număr = [1-9][0-9]*; număr { return true; } * { return false; } */ } fn principal () { afirma! ( lex ( b"1234 \0 " )); } /* Generat de re2c */ // re2rust $INPUT -o $OUTPUT fn lex ( s : & [ u8 ]) -> bool { lasă mut cursorul = 0 ; { #[allow(unused_assignments)] fie mut yych : u8 = 0 ; lasă mut yystate : usize = 0 ; ' yyl : buclă { starea meciului { 0 => { yych = nesigur { * s . get_unchecked ( cursor )}; cursor += 1 ; potrivește yych { 0x31 ..= 0x39 => { yystate = 2 ; continua 'yyl ; } _ => { yystate = 1 ; continua 'yyl ; } } } 1 => { return false ; } 2 => { yych = nesigur { * s . get_unchecked ( cursor )}; potrivește yych { 0x30 .. = 0x39 _ cursor += 1 ; yystate = 2 ; continua 'yyl ; } _ => { yystate = 3 ; continua 'yyl ; } } } 3 => { returnează adevărat ; } _ => { panică! ( „eroare internă de lexer” ) } } } } } fn principal () { afirma! ( lex ( b"1234 \0 " )); }