it-swarm-eu.dev

Měl bych použít generátor syntaktického analyzátoru nebo bych měl vrátit vlastní kód lexeru a syntaktického analyzátoru?

Jaké specifické výhody a nevýhody každého způsobu práce na gramatice programovacího jazyka?

Proč/Kdy mám hodit svůj vlastní? Proč/Kdy mám použít generátor?

83
Maniero

Ve skutečnosti existují tři možnosti, všechny tři jsou vhodnější v různých situacích.

Varianta 1: generátory syntaktického analyzátoru nebo „potřebujete analyzovat nějaký jazyk a chcete, aby to fungovalo, zatraceně“

Řekněme, že jste požádáni, abyste postavili syntaktický analyzátor pro nějaký prastarý datový formát TEĎ. Nebo potřebujete, aby byl váš syntaktický analyzátor rychlý. Nebo potřebujete, aby byl váš syntaktický analyzátor snadno udržovatelný.

V těchto případech je pravděpodobně nejlepší použít generátor syntaktického analyzátoru. Nemusíte se hádat s podrobnostmi, nemusíte mít spoustu komplikovaného kódu, aby správně fungovali, stačí napsat gramatiku, kterou bude vstup dodržovat, napsat nějaký manipulační kód a testovat: okamžitý analyzátor.

Výhody jsou jasné:

  • Je (obvykle) docela snadné napsat specifikaci, zejména pokud vstupní formát není příliš divný (možnost 2 by byla lepší, pokud je).
  • Skončíte s velmi snadno udržovatelnou prací, která je snadno pochopitelná: definice gramatiky obvykle proudí mnohem přirozenější než kód.
  • Parsery generované dobrými generátory syntaktických analyzátorů jsou obvykle mnohem rychlejší než ručně psaný kód. Ručně psaný kód může být rychlejší, ale pouze pokud znáte své věci - proto nejčastěji používané kompilátory používají ručně psaný rekurzivně-sestupový analyzátor.

U syntaktických generátorů musíte být opatrní: někdy mohou gramatiky odmítnout. Pro přehled různých typů analyzátorů a toho, jak vás mohou kousnout, můžete začít zde . Zde najdete přehled mnoha implementací a typů gramatik, které přijímají.

Varianta 2: ručně psané parsery, nebo „chcete si vytvořit vlastní syntaktický analyzátor a záleží na uživatelsky přívětivém“

Generátory syntaktického analyzátoru jsou pěkné, ale nejsou příliš přátelští (koncoví uživatelé, ne vy) přátelští. Obvykle nemůžete dávat dobré chybové zprávy ani poskytovat obnovení chyb. Možná je váš jazyk velmi divný a parsery odmítají vaši gramatiku nebo potřebujete více kontroly, než vám dává generátor.

V těchto případech je pravděpodobně nejlepší použít ručně psaný rekurzivně-sestupný syntaktický analyzátor. I když to napravíte, může to být komplikované, máte úplnou kontrolu nad svým syntaktickým analyzátorem, takže můžete provádět všechny druhy pěkných věcí, které s generátory parserů nemůžete dělat, jako jsou chybové zprávy a dokonce i obnovení chyb (zkuste odstranit všechny středníky ze souboru C #) : kompilátor C # si bude stěžovat, ale i tak detekuje většinu dalších chyb bez ohledu na přítomnost středníků).

Ručně psané analyzátory také obvykle fungují lépe než generované, za předpokladu, že kvalita analyzátoru je dostatečně vysoká. Na druhou stranu, pokud se vám nepodaří napsat dobrý analyzátor - obvykle kvůli (kombinaci) nedostatku zkušeností, znalostí nebo designu - pak je výkon obvykle pomalejší. Pro lexery je však pravdou opak: obecně generované lexery používají vyhledávání v tabulkách, díky čemuž jsou rychlejší než (většina) ručně psaných.

Vzdělávání, psaní vlastního syntaktického analyzátoru vás naučí více než pomocí generátoru. Koneckonců musíte psát stále komplikovanější kód a navíc musíte přesně porozumět tomu, jak analyzujete jazyk. Na druhou stranu, pokud se chcete naučit, jak si vytvořit svůj vlastní jazyk (získejte zkušenosti s návrhem jazyků), je výhodnější možnost 1 nebo 3: pokud vyvíjíte jazyk, pravděpodobně se hodně změní, a možnost 1 a 3 vám s tím usnadní čas.

Varianta 3: ručně psané generátory syntaktického analyzátoru, nebo „snažíte se toho hodně naučit z tohoto projektu a nevadilo by vám skončit šikovným kusem kódu, který můžete znovu použít“

Toto je cesta, kterou právě procházím: píšete svůj vlastní syntaktický generátor. I když je to velmi netriviální, pravděpodobně vás to naučí nejvíce.

Abych vám dal představu, co takový projekt zahrnuje, řeknu vám o svém vlastním pokroku.

Generátor lexerů

Nejprve jsem si vytvořil vlastní generátor lexerů. Obvykle navrhuji software počínaje tím, jak bude tento kód použit, a tak jsem přemýšlel o tom, jak jsem chtěl, abych mohl svůj kód použít, a napsal tento kus kódu (je to v C #):

Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    { // This is just like a Lex specification:
      //                    regex   token
        new StringTokenPair("\\+",  CalculatorToken.Plus),
        new StringTokenPair("\\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\\d+", CalculatorToken.Number),
    });

foreach (CalculatorToken token in
             calculatorLexer.GetLexer(new StringReader("15+4*10")))
{ // This will iterate over all tokens in the string.
    Console.WriteLine(token.Value);
}

// Prints:
// 15
// +
// 4
// *
// 10

Dvojice vstupních řetězců-tokenů jsou převedeny na odpovídající rekurzivní strukturu popisující regulární výrazy, které reprezentují, pomocí myšlenek aritmetického zásobníku. Toto je pak přeměněno na NFA (nedeterministický konečný automat), který je zase převeden na DFA (deterministický konečný automat). Poté můžete porovnat struny s DFA.

Tímto způsobem získáte dobrý nápad, jak přesně lexery fungují. Kromě toho, pokud to uděláte správným způsobem, výsledky vašeho generátoru lexerů mohou být zhruba stejně rychlé jako profesionální implementace. Ve srovnání s možností 2 neztratíte ani žádnou expresivitu a ve srovnání s možností 1 moc expresivitu.

Implementoval jsem lexerový generátor do více než 1600 řádků kódu. Tento kód způsobí, že výše uvedená práce funguje, ale stále generuje lexer za běhu při každém spuštění programu: Chystám se přidat kód, abych ho v určitém okamžiku zapisoval na disk.

Pokud chcete vědět, jak napsat svůj vlastní lexer, toto je dobré místo pro začátek.

Generátor syntaktického analyzátoru

Poté napíšete generátor syntaktického analyzátoru. Odkazuji na zde znovu pro přehled o různých druzích analyzátorů - zpravidla platí, že čím více mohou analyzovat, tím pomaleji jsou.

Rychlost není pro mě problém, rozhodl jsem se implementovat Earleyho parser. Pokročilé implementace Earleyho syntaktického analyzátoru bylo ukázáno být asi dvakrát tak pomalý jako jiné typy syntaktického analyzátoru.

Na oplátku za tento rychlý zásah získáte schopnost analyzovat jakýkoli druh gramatiky, dokonce dvojznačný ty. To znamená, že se nikdy nebudete muset starat o to, zda váš analyzátor má nějaké rekurze doleva, nebo jaký je konflikt snižující posun. Můžete také definovat gramatiky snadněji pomocí nejednoznačných gramatik, pokud nezáleží na tom, který strom analýzy je výsledkem, například že nezáleží na tom, zda analyzujete 1 + 2 + 3 jako (1 + 2) +3 nebo jako 1 + (2 + 3).

Takto může vypadat část kódu pomocí generátoru syntaktického analyzátoru:

Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    {
        new StringTokenPair("\\+",  CalculatorToken.Plus),
        new StringTokenPair("\\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\\d+", CalculatorToken.Number),
    });

Grammar<IntWrapper, CalculatorToken> calculator
    = new Grammar<IntWrapper, CalculatorToken>(calculatorLexer);

// Declaring the nonterminals.
INonTerminal<IntWrapper> expr = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> term = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> factor = calculator.AddNonTerminal<IntWrapper>();

// expr will be our head nonterminal.
calculator.SetAsMainNonTerminal(expr);

// expr: term | expr Plus term;
calculator.AddProduction(expr, term.GetDefault());
calculator.AddProduction(expr,
                         expr.GetDefault(),
                         CalculatorToken.Plus.GetDefault(),
                         term.AddCode(
                         (x, r) => { x.Result.Value += r.Value; return x; }
                         ));

// term: factor | term Times factor;
calculator.AddProduction(term, factor.GetDefault());
calculator.AddProduction(term,
                         term.GetDefault(),
                         CalculatorToken.Times.GetDefault(),
                         factor.AddCode
                         (
                         (x, r) => { x.Result.Value *= r.Value; return x; }
                         ));

// factor: LeftParenthesis expr RightParenthesis
//         | Number;
calculator.AddProduction(factor,
                         CalculatorToken.LeftParenthesis.GetDefault(),
                         expr.GetDefault(),
                         CalculatorToken.RightParenthesis.GetDefault());
calculator.AddProduction(factor,
                         CalculatorToken.Number.AddCode
                         (
                         (x, s) => { x.Result = new IntWrapper(int.Parse(s));
                                     return x; }
                         ));

IntWrapper result = calculator.Parse("15+4*10");
// result == 55

(Všimněte si, že IntWrapper je prostě Int32, kromě toho, že C # vyžaduje, aby to byla třída, proto jsem musel zavést třídu wrapper)

Doufám, že uvidíte, že výše uvedený kód je velmi silný: lze analyzovat jakoukoli gramatiku, se kterou můžete přijít. Do gramatiky můžete přidat libovolné kousky kódu, které jsou schopné vykonávat spoustu úkolů. Pokud se vám to podaří, můžete výsledný kód znovu použít k provádění mnoha úkolů velmi snadno: stačí si pomocí tohoto kusu kódu vybudovat překladač příkazového řádku.

78
Alex ten Brink

Pokud jste nikdy nikdy nenapsali parsery, doporučil bych to udělat. Je to legrace a naučíte se, jak věci fungují, a naučíte se ocenit úsilí, které vám generátory syntaktického analyzátoru a lexerů ušetří před provedením příštího času, který potřebujete parser.

Navrhuji také, abyste zkusili přečíst http://compilers.iecc.com/crenshaw/ , protože má velmi dobrý přístup k tomu, jak to udělat.

22
user1249

Výhodou psaní vlastního rekurzivního syntaktického analyzátoru sestupu je, že můžete generovat vysoce kvalitní chybové zprávy o syntaktických chybách. Pomocí generátorů syntaktického analyzátoru můžete v určitých bodech provádět chyby a přidávat vlastní chybové zprávy, ale generátory syntaktických analyzátorů prostě neodpovídají možnosti úplné kontroly nad analýzou.

Další výhodou psaní vlastního je, že je snazší analyzovat jednodušší reprezentaci, která nemá korespondenci s vaší gramatikou.

Pokud je vaše gramatika pevná a chybové zprávy jsou důležité, zvažte rozmístění své vlastní nebo alespoň pomocí generátoru syntaktického analyzátoru, který vám poskytne chybové zprávy, které potřebujete. Pokud se vaše gramatika neustále mění, měli byste místo toho zvážit použití generátorů syntaktického analyzátoru.

Bjarne Stroustrup hovoří o tom, jak použil YACC pro první implementaci C++ (viz Návrh a vývoj C++ )). V tomto prvním případě si přál, aby místo toho napsal svůj vlastní rekurzivní syntaktický analyzátor sestupu!

14
Macneil

Možnost 3: Ani (Roll your own parser generátor)

Jen proto, že existuje důvod, proč nepoužívat ANTLR , bizon , Coco/R , Grammatica , JavaCC , Lemon , Parboiled , SableCC , Quex , atd. - to neznamená, že byste měli okamžitě hodit svůj vlastní syntaktický analyzátor + lexer.

Identifikujte proč všechny tyto nástroje nejsou dostatečně dobré - proč vám nedovolí dosáhnout vašeho cíle?

Pokud si nejste jisti, že zvláštnosti v gramatice, se kterou se zabýváte, jsou jedinečné, neměli byste pro to vytvořit pouze jediný vlastní syntaktický analyzátor + lexer. Místo toho vytvořte nástroj, který vytvoří to, co chcete, ale může být také použit k uspokojení budoucích potřeb, poté jej uvolněte jako svobodný software, abyste zabránili jiným lidem mít stejný problém jako vy.

10
Peter Boughton

Válcování vlastního parseru vás nutí přemýšlet přímo o složitosti vašeho jazyka. Pokud je obtížné rozebrat jazyk, bude pravděpodobně obtížné jej pochopit.

V počátečních dnech byl o generátory syntaktického analyzátoru velký zájem motivovaný vysoce komplikovanou syntaxí jazyka (někteří by řekli „mučení“). JOVIAL byl obzvláště špatný příklad: vyžadoval dva hledače symbolů v době, kdy všechno ostatní vyžadovalo nanejvýš jeden symbol. Díky tomu bylo generování syntaktického analyzátoru pro kompilátor JOVIAL obtížnější, než se očekávalo (divize General Dynamics/Fort Worth se při získávání kompilátorů JOVIAL pro program F-16 těžko naučila).

Dnes je rekurzivní generace všeobecně preferovanou metodou, protože je pro spisovatele kompilátoru snazší. Kompilátory rekurzivního sestupu silně odměňují jednoduchý, čistý jazykový design, protože je mnohem snazší napsat rekurzivně-sestupný syntaktický analyzátor pro jednoduchý, čistý jazyk než pro spletitý, chaotický jazyk.

Konečně: Uvažovali jste o vložení jazyka do LISP a nechali tlumočníka LISP, aby za vás provedl těžký trénink? AutoCAD to udělal a zjistil, že jeho život byl mnohem snazší. Tam je docela málo lehkých tlumočníků LISP, někteří embeddable.

8
John R. Strohm

Jednou jsem napsal parser pro komerční aplikaci a použil jsem yacc. Tam byl konkurenční prototyp kde vývojář psal celou věc ručně v C + + a to fungovalo asi pětkrát pomaleji.

Pokud jde o lexer pro tento parser, psal jsem to úplně ručně. Trvalo - promiňte, bylo to téměř před 10 lety, takže si to přesně nepamatuji - asi 1000 řádků v C .

Důvodem, proč jsem ručně psal lexer, byla vstupní syntaktická gramatika. Byl to požadavek, něco, co moje implementace analyzátoru musela splňovat, na rozdíl od něčeho, co jsem navrhl. (Samozřejmě bych to navrhl jinak. A lépe!) Gramatika byla silně závislá na kontextu a dokonce lexing v některých místech závisel na sémantice. Například středník může být součástí tokenu na jednom místě, ale oddělovač na jiném místě - na základě sémantické interpretace nějakého prvku, který byl dříve analyzován. Tak jsem „ručně“ pohřbil takové sémantické závislosti v ručně psaném lexeru a to mi dalo docela přímočarou [~ # ~] bnf [~ # ~] bylo snadné implementovat do yacc.

PŘIDÁNO v reakci na Macneil: yacc poskytuje velmi silnou abstrakci, která umožňuje programátorovi myslet na terminály, non-terminály, produkce a podobné věci. Také při implementaci funkce yylex() mi pomohlo soustředit se na vrácení aktuálního tokenu a nebát se toho, co bylo před nebo po něm. Programátor C++ pracoval na úrovni postav, aniž by měl výhodu takové abstrakce, a nakonec vytvořil komplikovanější a méně efektivní algoritmus. Došli jsme k závěru, že pomalejší rychlost nemá nic společného se samotným C++ nebo knihovnami. Měřili jsme čistou rychlost analýzy pomocí souborů načtených do paměti; Pokud bychom měli problém s ukládáním souborů do vyrovnávací paměti, nebyl by nástroj yacc naším řešením.

TAK CHCETE PŘIDAT: Toto není recept na psaní analyzátorů obecně, pouze příklad toho, jak to fungovalo v jedné konkrétní situaci.

6
azheglov

Záleží na tom, jaký je váš cíl.

Snažíte se naučit, jak analyzátory/kompilátory fungují? Pak napište vlastní od nuly. To je jediný způsob, jak byste se opravdu naučili ocenit všechny výhody a výstupy toho, co dělají. Posledních pár měsíců jsem psal a byl to zajímavý a cenný zážitek, zejména „ah, takže to je důvod, proč to jazyk X dělá ...“ momenty.

Potřebujete něco rychle spojit pro žádost v termínu? Pak možná použijte analyzátor.

Potřebujete něco, o čem budete chtít během následujících 10, 20, možná dokonce 30 let, expandovat? Napište svůj vlastní a udělejte si čas. Bude to dobře stát za to.

3
GrandmasterB

To záleží zcela na tom, co musíte analyzovat. Můžete hodit svůj vlastní rychleji, než byste mohli zasáhnout křivku učení lexeru? Je materiál, který má být analyzován, natolik statický, že nebudete litovat rozhodnutí později? Považujete stávající implementace za příliš složité? Pokud ano, bavte se válením vlastního, ale pouze pokud se neohýbáte křivku učení.

V poslední době jsem si opravdu oblíbil analyzátor citronů , což je pravděpodobně nejjednodušší a nejjednodušší, co jsem kdy použil. Pro snadnou údržbu věcí ji používám jen pro většinu potřeb. SQLite to používá, stejně jako některé další významné projekty.

Ale vůbec se nezajímám o lexery, kromě toho, že se mi nedostanou do cesty, když potřebuji použít jeden (odtud citron). Můžete být, a pokud ano, proč si to neudělat? Mám pocit, že se vrátíte k používání toho, který existuje, ale poškriabejte svědění, pokud musíte :)

3
Tim Post

Uvažovali jste o Martin Fowlers jazykový pracovní přístup ? Citace z článku

Nejviditelnější změnou, kterou jazykový pracovní stůl provádí v rovnici, je snadnost vytváření externích DSL. Už nemusíte psát syntaktický analyzátor. Musíte definovat abstraktní syntaxi - ale ve skutečnosti je to docela jednoduchý krok modelování dat. Navíc vaše DSL získá výkonný IDE - i když musíte strávit nějaký čas definováním tohoto editoru. Generátor je stále něco, co musíte udělat, a můj smysl je, že to není moc jednodušší, než to kdy bylo. Ale pak vytvoření generátoru pro dobrý a jednoduchý DSL je jednou z nejjednodušších částí cvičení.

Když jsem si to přečetl, řekl bych, že dny psaní vlastního analyzátoru skončily a je lepší použít jednu z dostupných knihoven. Jakmile zvládnete knihovnu, budou mít z těchto znalostí prospěch všechny DSL, které vytvoříte v budoucnu. Také se ostatní nemusí naučit váš přístup k analýze.

Upravit tak, aby obsahoval komentář (a revidovanou otázku)

Výhody válcování vlastní

  1. Budete vlastnit syntaktický analyzátor a získejte všechny krásné zážitky z myšlení prostřednictvím složité řady problémů
  2. Možná přijdete s něčím zvláštním, o čem nikdo jiný nenapadlo (nepravděpodobné, ale vypadáte jako chytrý chlap)
  3. Udrží vás to obsazeno zajímavým problémem

Stručně řečeno, měli byste se hodit sami, když se chcete opravdu proniknout hluboko do útrob vážně obtížného problému, který se cítíte silně motivováni zvládnout.

Výhody používání knihovny někoho jiného

  1. Vyhnete se znovu vynalézání kola (běžný problém v programování budete souhlasit)
  2. Můžete se soustředit na konečný výsledek (nový lesklý jazyk) a příliš si dělat starosti s tím, jak je analyzován atd
  3. Uvidíte svůj jazyk v akci mnohem rychleji (ale vaše odměna bude menší, protože to nebylo vše, co jste)

Proto, pokud chcete rychlý výsledek, použijte knihovnu někoho jiného.

Celkově jde o výběr toho, jak moc chcete problém vlastnit, a tím i řešení. Pokud to chcete všechno, pak hodte svůj vlastní.

3
Gary Rowe

Velkou výhodou při psaní vlastního textu je, že budete vědět, jak napsat svůj vlastní. Velkou výhodou použití nástroje, jako je yacc, je to, že budete vědět, jak tento nástroj používat. Jsem fanouškem treetop pro počáteční průzkum.

2
philosodad

Proč neporušit generátor syntaktického analyzátoru s otevřeným zdrojovým kódem a vytvořit si svůj vlastní? Pokud nepoužíváte generátory syntaktického analyzátoru, bude velmi obtížné udržovat kód, pokud jste provedli velké změny syntaxe vašeho jazyka.

V mých analyzátorech jsem používal regulární výrazy (myslím, Perl-styl), abych tokenizoval, a pomocí některých funkcí pro zvýšení čitelnosti kódu. Kód generovaný syntaktickým analyzátorem však může být rychlejší vytvořením stavových tabulek a dlouhých switch-cases, což může zvětšit velikost zdrojového kódu, pokud .gitignore.

Zde jsou dva příklady mých vlastních psaných analyzátorů:

https://github.com/SHiNKiROU/DesignScript - ZÁKLADNÍ dialekt, protože jsem byl příliš líný na to, abych psal lookaheads do maticové notace, obětoval jsem kvalitu chybové zprávy https: // github. com/SHiNKiROU/ExprParser - Kalkulačka vzorců. Všimněte si podivných metaprogramovacích triků

1
Ming-Tang

"Měl bych použít toto osvědčené" kolo "nebo ho znovu vynalézat?"

0
JBRWilkinson