Re2c - Re2c

re2c
Původní autořiPeter Bumbulis
První vydáníkolem roku 1994; Před 26 lety (1994)[1]
Stabilní uvolnění
2.0 / 20. července 2020; Před 4 měsíci (2020-07-20)
Úložištěgithub.com/ skvadrik/ re2c
TypLexikální analyzátor generátor
LicenceVeřejná doména
webová stránkare2c.org

re2c je zdarma a open-source generátor lexeru pro C, C ++ a Jít. Kompiluje deklarativní specifikace regulárního výrazu do deterministické konečné automaty. Původně napsal Peter Bumbulis a popsal ve své práci,[1] byl vložen re2c veřejná doména a od té doby ji udržují dobrovolníci.[2] Jedná se o generátor lexerů přijímaný projekty, jako je PHP,[3] SpamAssassin,[4] Ninja build system[5] a další. Spolu s Citrón generátor analyzátoru, re2c se používá v BRL-CAD.[6] Tato kombinace se také používá s STEPcode, implementací ISO 10303 Standard.[7]

Filozofie

Hlavním cílem re2c je generování rychle lexers:[1]alespoň tak rychle, jak je rozumně optimalizováno C lexery kódované ručně. Namísto použití tradičního přístupu řízeného tabulkou re2cencodes generuje generované konečný stavový stroj přímo ve formě podmíněných skoků a srovnání. Výsledný program je rychlejší než jeho protějšek řízený tabulkou[1]a mnohem snazší ladit a porozumět. Navíc tento přístup často vede k menším lexerům,[1]protože re2c používá řadu optimalizací, jako je Minimalizace DFA a výstavba tunelový automat.[8]Další charakteristickou vlastností re2c je jeho flexibilní rozhraní: namísto předpokladu pevné šablony programu umožňuje program re2c programátorovi napsat většinu kódu rozhraní a přizpůsobit vygenerovaný lexer konkrétnímu prostředí. Hlavní myšlenkou je, že re2c by měl být nulové náklady abstrakce pro programátora: jeho použití by nikdy nemělo vést k pomalejšímu programu než odpovídající ručně kódovaná implementace.

Funkce

  • Extrakce dílčího zápasu:[9] re2c podporuje jak zachytávací skupiny vyhovující POSIX, tak samostatné značky [10] (s chamtivou disambiguací zcela vlevo a volitelným zpracováním opakovaného dílčího zápasu). Implementace je založena na algoritmu lookahead-TDFA. [11]
  • Podpora kódování:[12] re2c podporuje ASCII, UTF-8, UTF-16, UTF-32, UCS-2 a EBCDIC.
  • Flexibilní uživatelské rozhraní:[13] generovaný kód používá několik primitivních operací k propojení s prostředím (čtení vstupních znaků, postup na další vstupní pozici atd.); uživatelé mohou tyto primitivy předefinovat na cokoli potřebují.
  • Skladovatelný stav:[14] re2c podporuje obojí pull-model lexery (když lexer běží bez přerušení a podle potřeby přitáhne více vstupů) a push-model lexers (když je lexer pravidelně zastavován a obnovován, aby analyzoval nové bloky vstupu).
  • Podmínky zahájení:[15] re2c může generovat více vzájemně propojených lexerů, kde každý lexer je spouštěn určitým stav v programu.
  • Vlastní ověření:[16] re2c má speciální režim, ve kterém ignoruje veškerý použitý definovaný kód rozhraní a generuje samostatný kostra program. Re2c navíc generuje dva soubory: jeden se vstupními řetězci odvozenými z běžné gramatiky a druhý s komprimovanými výsledky shody, které se používají k ověření chování lexeru na všech vstupech. Vstupní řetězce jsou generovány tak, aby značně pokrývaly přechody a cesty DFA. Ke generování dat dochází hned po konstrukci DFA a před jakoukoli optimalizací, ale samotný lexer je plně optimalizován, takže kostrové programy jsou schopné odhalit jakékoli chyby v optimalizacích a generování kódu.
  • Varování:[17] re2c provádí statickou analýzu programu a varuje uživatele před možnými nedostatky nebo chybami, jako je nedefinovaný tok řízení, nedosažitelný kód, špatně vytvořené únikové symboly a potenciální zneužití primitiv rozhraní.
  • Ladění. Kromě generování lexerů čitelných člověkem má re2c řadu možností, které vypouštějí různé mezilehlé reprezentace generovaného lexeru, například NFA, více fází DFA a výsledný programový graf v DOT formát.[18]

Syntax

Program re2c může obsahovat libovolný počet / *! re2c ... * / bloky. Každý blok se skládá ze sekvence pravidla, definice a konfigurace(mohou být smíchány, ale obecně je lepší dát nejdříve konfigurace, pak definice a pak pravidla). Pravidla mají formu REGEXP {CODE} nebo REGEXP: = KÓD; kde REGEXP je regulární výraz a KÓD je blok kódu C. Když REGEXP odpovídá vstupnímu řetězci, řídicí tok se přenese do přidruženého KÓD. Existuje jedno zvláštní pravidlo: výchozí pravidlo s * namísto REGEXP; spustí se, pokud se neshodují žádná jiná pravidla. re2c má chamtivý odpovídající sémantika: pokud se shoduje více pravidel, upřednostňuje se pravidlo, které odpovídá delší předponě; pokud se konfliktní pravidla shodují se stejnou předponou, má přednost dřívější pravidlo. Definice mají formu JMÉNO = REGEXP; (a také JMÉNO {REGEXP} v Flex režim kompatibility). Konfigurace mají formu re2c: CONFIG = HODNOTA; kde KONFIG je název konkrétní konfigurace a HODNOTA je číslo nebo řetězec. Pokročilejší použití najdete v oficiální příručce re2c.[19]

Regulární výrazy

re2c používá následující syntaxi pro regulární výrazy:

  • "foo" řetězec citlivý na velká a malá písmena
  • 'foo' řetězcový literál bez rozlišení malých a velkých písmen
  • [a-xyz], [^ a-xyz] třída znaků (možná negovaná)
  • . jakýkoli znak kromě nového řádku
  • R S rozdíl tříd postav
  • R * nula nebo více výskytů R
  • R + jeden nebo více výskytů R
  • R? volitelný R
  • R {n} opakování R přesně n krát
  • R {n,} opakování R alespoň n krát
  • R {n, m} opakování R z n na m krát
  • (R) prostě R; závorky se používají k přepsání priority nebo k podmnožině stylu POSIX
  • R S zřetězení: R následován S
  • R | S alternativní: R nebo S
  • R / S dívat se dopředu: R následován S, ale S není spotřebován
  • název regulární výraz definovaný jako název (kromě v Flex Režim kompatibility)
  • @jelen an jelen: uloží poslední vstupní pozici, na které @jelen odpovídá proměnné s názvem jelen
  • #mtag an m-tag: uloží všechny vstupní pozice, na kterých #mtag odpovídá proměnné s názvem mtag

Třídy znaků a řetězcové literály mohou obsahovat následující řídicí sekvence: A, b, F, n, r, t, proti, \\, osmičkové úniky ooo a hexadecimální úniky xhh, uhhhh a Uhhhhhhhh.

Příklad

Zde je velmi jednoduchý program v re2c (example.re). Kontroluje, zda jsou všechny vstupní argumenty hexadecimální čísla. Kód pro re2c je uzavřen v komentářích / *! re2c ... * /, zbytek je prostý C Složitější příklady najdete na oficiálním webu re2c[20].

#zahrnout <stdio.h>statický int lex(konst char *YYCURSOR){    konst char *YYMARKER;    / *! re2c        re2c: define: YYCTYPE = char;        re2c: yyfill: enable = 0;        end = " x00";        hex = "0x" [0-9a-fA-F] +;        * {printf ("err  n"); návrat 1; }        šestihranný konec {printf ("hex  n"); návrat 0; }    */}int hlavní(int argc, char **argv){    pro (int i = 1; i < argc; ++i) {        lex(argv[i]);    }    vrátit se 0;}

Vzhledem k tomu, re2c -is -o example.c example.re generuje níže uvedený kód (example.c). Obsah komentáře / *! re2c ... * / jsou nahrazeny a deterministický konečný automat zakódováno ve formě podmíněných skoků a srovnání; zbytek programu je doslovně zkopírován do výstupního souboru. Existuje několik možností generování kódu; běžně používá re2c přepínač příkazy, ale lze použít vnořené -li příkazy (jako v tomto příkladu s -s nebo generovat bitmapy a přeskakovat tabulky. Která možnost je lepší, záleží na kompilátoru C; uživatelům re2c se doporučuje experimentovat.

/ * Generováno programem re2c 1.2.1 dne Pá 23. srpna 21:59:00 2019 * /#zahrnout <stdio.h>statický int lex(konst char *YYCURSOR){    konst char *YYMARKER;    {	char yych;	yych = *YYCURSOR;	-li (yych == '0') jít do yy4;	++YYCURSOR;yy3:	{ printf("chybovat n"); vrátit se 1; }yy4:	yych = *(YYMARKER = ++YYCURSOR);	-li (yych != 'X') jít do yy3;	yych = *++YYCURSOR;	-li (yych >= 0x01) jít do yy8;yy6:	YYCURSOR = YYMARKER;	jít do yy3;yy7:	yych = *++YYCURSOR;yy8:	-li (yych <= '@') {		-li (yych <= 0x00) jít do yy9;		-li (yych <= '/') jít do yy6;		-li (yych <= '9') jít do yy7;		jít do yy6;	} jiný {		-li (yych <= 'F') jít do yy7;		-li (yych <= '`') jít do yy6;		-li (yych <= 'F') jít do yy7;		jít do yy6;	}yy9:	++YYCURSOR;	{ printf(„hex n"); vrátit se 0; }}}int hlavní(int argc, char **argv){    pro (int i = 1; i < argc; ++i) {        lex(argv[i]);    }    vrátit se 0;}

Viz také

Reference

  1. ^ A b C d E Bumbulis, Peter; Donald D., Cowan (březen – prosinec 1993). „RE2C: univerzálnější generátor skeneru“. Dopisy ACM o programovacích jazycích a systémech. 2 (1–4).
  2. ^ „Autoři, dokumentace re2c“.
  3. ^ „Vytváření PHP“. Interní kniha PHP. Citováno 2020-07-20.
  4. ^ „SpamAssassin (sa-kompilace)“.
  5. ^ "Ninja: build.ninja". Ninja. Citováno 2020-07-20.
  6. ^ „BRL-CAD (tools: re2c)“.
  7. ^ http://stepcode.github.io/docs/build_process/
  8. ^ Joseph, Grosch (1989). "Efektivní generování stolních skenerů". Softwarová praxe a zkušenosti 19: 1089–1103.
  9. ^ „Extrakce dílčího zápasu, dokumentace re2c“.
  10. ^ Ville, Laurikari (2000). „NFA s označenými přechody, jejich převod na deterministické automaty a aplikace na regulární výrazy“ (PDF). Sedmé mezinárodní sympozium o zpracování řetězců a vyhledávání informací, 2000. SPIRE 2000. Sborník.
  11. ^ Ulya, Trofimovich (2017). "Označeno deterministické konečné automaty s Lookahead". arXiv:1907.08837 [cs.FL ].
  12. ^ „Kódování, dokumentace re2c“.
  13. ^ "Programové rozhraní, dokumentace re2c".
  14. ^ "Skladovatelný stav, dokumentace re2c".
  15. ^ „Podmínky spuštění, dokumentace re2c“.
  16. ^ „Skeleton, dokumentace re2c“.
  17. ^ „Varování, dokumentace re2c“.
  18. ^ „Vizualizace, dokumentace re2c“.
  19. ^ "Uživatelská příručka (C), dokumentace re2c".
  20. ^ „Oficiální web“.

externí odkazy