Parsingmetoder

Parsingmetoder är tekniker för att analysera en sekvens av tecken eller token enligt en formell grammatik med målet att producera en strukturell representation, oftast ett parse-träd eller en abstrakt syntaktisk träd (AST). Indata hämtas vanligen från en lexer eller tokenisering. Parsing används i kompilatorer, tolkar och verktyg för dataformat. Genom analysen avgörs om indata följer grammatiken och vilken struktur den har, vilket ligger till grund för vidare semantisk bearbetning.

De största indelningarna av parsingmetoder är top-down och bottom-up. Top-down omfattar rekursiv nedstigning och andra LL-parsare som ofta är enkla att implementera men har begränsningar vid vänsterrekursion och komplexa grammatikstrukturer. Bottom-up inkluderar shift-reduce-parsare samt LR-familyn (LR, SLR, LALR) som generellt klarar bredare grammatiktyper men är mer komplexa och resurskrävande. Andra alternativ är GLR-parsare som hanterar icke-determinism och Parsing Expression Grammars (PEGs) som ger ett deterministiskt alternativ där bakspårning inte används i samma utsträckning. Pratt-parsning används ofta för uttryck där operatorprecedens implementeras explicit.

Val av metod beror på grammatikens egenskaper, önskat felrapportering, prestandakrav och målplattform. Top-down-metoder är oftast enklare att implementera och ger bra felmeddelanden, men kan kräva omstrukturering av vänsterrekursion. Bottom-up-parsare är kraftfullare och ger mer robust syntaktisk kontroll, men kräver mer arbete att implementera och underhålla. PEGs erbjuder ett deterministiskt alternativ där bakspårning inte används i samma utsträckning. I praktiken används olika metoder beroende på språk och applikation, från små skript-tolkar till stora programmeringsspråk.