| Re2c | |
|---|---|
| Sorts | fri och öppen källkodsprogramvara och generator för lexikalanalys [d] |
| Skrivet i | C och C++ |
| Operativ system | plattformsoberoende |
| Första upplagan | 1994 [1] |
| senaste versionen |
|
| stat | aktiva |
| Hemsida | re2c.org _ |
| Mediafiler på Wikimedia Commons | |
re2c ( r egular e xpression toc , r egular e xpression toc ode ) är ett gratis generatorverktyg för öppen källkod som genererar snabba och lätta inbäddningsbara lexers , orienterade för att arbeta med språk: C , C ++ , Go , Rust .
Verktyget skapades ursprungligen av Peter Bumbulis och beskrivs i hans artikel [3] , senare släpptes re2c till det offentliga området och har sedan dess underhållits av frivilliga [4] .
Verktyget skiljer sig från sina mer välkända analoger (som lex och flex ) genom att det har ett flexibelt interaktionsgränssnitt (den genererade koden interagerar med ett externt program med hjälp av primitiver), genererar optimerade icke-bordslexers, stöder infångningar (submatchextraktion) ) baserat på deterministiska finita automater med taggar (TDFA).
Verktyget används huvudsakligen i projekt där höghastighetsanalys av syntax krävs , såsom Ninja [5] och PHP [6] .
Huvudmålet med re2c är att generera snabba lexers [3] som är minst lika snabba som rimligt optimerade handskrivna lexers . Istället för att använda den traditionella kalkylarksmetoden kodar re2c den genererade tillståndsmaskinen direkt i form av villkor och jämförelser. Som ett resultat är programmet snabbare än dess tabellbaserade motsvarighet [3] och mycket lättare att felsöka och förstå. Dessutom leder detta tillvägagångssätt ofta till mindre lexers [3] eftersom re2c tillämpar ett antal optimeringar såsom DFA-minimering och tunnelautomatkonstruktion [7] . En annan stor egenskap hos re2c är dess flexibla gränssnitt. Istället för att använda en fast programmall tillåter re2c programmeraren att skriva det mesta av gränssnittskoden och anpassa den genererade lexern till en viss miljö. Huvudtanken är att re2c ska vara en nollkostnadsabstraktion för programmeraren, att använda verktyget bör aldrig göra att programmet körs långsammare än motsvarande handkodade implementering.
Implementeringen är baserad på "lookahead-TDFA" [10] [11] [12] algoritmen ;
Re2c-programmet kan innehålla valfritt antal /*!re2c ... */block. Varje block består av en sekvens av regler, definitioner och konfigurationer (de kan blandas, men det är vanligtvis bäst att sätta konfigurationer först, sedan definitioner och sedan regler). Reglerna har formen - REGEXP { CODE }eller REGEXP := CODE;, där REGEXPär ett reguljärt uttryck , och CODE- är ett block av C-kod. När REGEXPden matchar ingångssträngen överförs kontrollflödet till motsvarande block CODE. Det finns en specialregel: standardregeln med *istället för REGEXP, den aktiveras om inga andra regler matchar. re2c har girig matchande semantik - om flera regler matchar, är regeln som matchar det längre prefixet att föredra, om motstridiga regler matchar samma prefix, så har den tidigare regeln företräde. Definitioner har formen NAME = REGEXP;(och följaktligen NAME { REGEXP }i Flex-kompatibelt läge). Konfigurationer har formen re2c:CONFIG = VALUE;, där CONFIGär namnet på en specifik konfiguration och VALUEär antingen ett nummer eller en sträng. För mer avancerad användning, kolla in den officiella re2c-manualen [20] .
re2c använder följande syntax för reguljära uttryck:
Teckenklasser och strängliteraler kan innehålla följande escape-sekvenser: \a, \b, \f, \n, \r, \t, \v, \\, oktal \ooooch hexadecimal \xhh, \uhhhh, \Uhhhhhhhh.
Följande är ett exempel på ett enkelt re2c-program i filen example.re . Den kontrollerar att alla inmatningsargument är decimaltal. Koden för re2c är inramad i kommentarerna /*!re2c ... */[21] .
C :
// re2c $INPUT -o $OUTPUT -i --case-intervaller #inkludera <assert.h> bool lex ( const char * s ) { const char * YYCURSOR = s ; /*!re2c re2c:yyfill:enable = 0; re2c:define:YYCTYPE = char; nummer = [1-9][0-9]*; nummer { return true; } * { return false; } */ } int main () { hävda ( lex ( "1234" )); returnera 0 ; }Med tanke på att kommandot $ re2c -is -o example.c example.regenererar koden nedan ( exempel.c ). Innehållet i kommentaren /*!re2c ... */ersätts av en deterministisk finit automat kodad som villkorliga hopp och jämförelser, resten av programmet kopieras ordagrant till utdatafilen. Det finns flera alternativ för att generera kod, vanligtvis använder re2c operatorn switch, men den kan använda kapslade operatorer if(som i det här exemplet med alternativet -s) eller generera bitmappar och hoppa tabeller . Vilket alternativ som är bättre beror på C-kompilatorn , re2c-användare uppmuntras att experimentera.
/* Genererad av re2c */ // re2c $INPUT -o $OUTPUT -i --case-intervaller #inkludera <assert.h> bool lex ( const char * s ) { const char * YYCURSOR = s ; { röding yych ; yych = * YYCURSOR ; switch ( yych ) { fall '1' ... '9' : gå till åå2 ; default : goto yy1 ; } åå1 : ++ YYCURSOR ; { return false ; } åå2 : yych = *++ YYCURSOR ; switch ( yych ) { fall '0' ... '9' : gå till åå2 ; default : goto yy3 ; } åå3 : { return true ; } } } int main () { hävda ( lex ( "1234" )); returnera 0 ; }gå :
//go:generera re2go $INPUT -o $OUTPUT -i huvudpaketet _ func lex ( str string ) { var cursor int /*!re2c re2c:define:YYCTYPE = byte; re2c:define:YYPEEK = "str[markör]"; re2c:define:YYSKIP = "markör += 1"; re2c:yyfill:enable = 0; antal = [1-9][0-9]*; nummer { return } * { panik("fel!") } */ } func main () { lex ( "1234\x00" ) } // Kod genererad av re2c, REDIGERA INTE. //go:generera re2go $INPUT -o $OUTPUT -i huvudpaketet _ func lex ( str string ) { var cursor int { var yych byte yych = str [ cursor ] switch ( yych ) { fall '1' , '2' , '3' , '4' , '5' , '6' , '7' , '8' , '9' : gå åå2 standard : gå till åå1 } åå1 : markör += 1 { panik ( "fel!" ) } åå2 : markör += 1 yych = str [ cursor ] switch ( yych ) { fall '0' , '1' , '2' , '3' , '4' , '5' , '6' , '7' , '8' , '9' : gå åå2 standard : gå åå3 } åå3 : { return } } } func main () { lex ( "1234\x00" ) }Rost :
// re2rust $INPUT -o $OUTPUT fn lex ( s : & [ u8 ]) -> bool { låt mut markör = 0 ; /*!re2c re2c:define:YYCTYPE = u8; re2c:define:YYPEEK = "*s.get_unchecked(cursor)"; re2c:define:YYSKIP = "markör += 1;"; re2c:yyfill:enable = 0; nummer = [1-9][0-9]*; nummer { return true; } * { return false; } */ } fn main () { hävda! ( lex ( b"1234 \0 " )); } /* Genererad av re2c */ // re2rust $INPUT -o $OUTPUT fn lex ( s : & [ u8 ]) -> bool { låt mut markör = 0 ; { #[allow(unused_assignments)] låt mut yych : u8 = 0 ; låt mut yystate : usize = 0 ; ' yyl : loop { matcha tillstånd { 0 => { yych = osäkra { * s . get_unchecked ( cursor )}; markör += 1 ; matcha yych { 0x31 ..= 0x39 => { yystate = 2 ; fortsätt 'yyl ; } _ => { yystate = 1 ; fortsätt 'yyl ; } } } 1 => { return false ; } 2 => { yych = osäkra { * s . get_unchecked ( cursor )}; matcha yych { 0x30 .. = 0x39 _ markör += 1 ; yystate = 2 ; fortsätt 'yyl ; } _ => { yystate = 3 ; fortsätt 'yyl ; } } } 3 => { return true ; } _ => { panik! ( "internt lexer-fel" ) } } } } } fn main () { hävda! ( lex ( b"1234 \0 " )); }