Parser

Van Wikipedia, de gratis encyclopedie
Spring naar navigatie Spring naar zoeken

Een parser [ ˈPɑːʁzɐ ] ( Engels om te ontleden, "analyseren", of Latijns pars, "deel"; in het Duits soms ook splitter ) is een computerprogramma dat in de informatica verantwoordelijk is voor de ontleding en conversie van een invoer in een geschikter formaat voor verdere verwerking is. Vaak worden parsers gebruikt om de semantiek van de invoer na het analyseproces te ontwikkelen en vervolgens om acties uit te voeren.

In vergelijking met een herkenner , die de invoer en uitvoer analyseert of deze correct of onjuist is in termen van specificaties, voert de parser de analyse van een invoer uit in een gewenste vorm en genereert hij ook structuurbeschrijvingen.

De syntaxisanalyse (parsing) wordt ook buiten de informatica gebruikt, b.v. B. in de studie van de structuur van natuurlijke talen . In grammatica zou de syntaxisanalyse van een zin overeenkomen met het opsplitsen van de zin in zijn grammaticale componenten ( syntaxis ). Zie ook taalkunde .

Toepassing en voorbeelden

Over het algemeen wordt een parser gebruikt om een ​​tekst te vertalen naar een nieuwe structuur, b.v. B. in een syntaxisboom , die de hiërarchie tussen de elementen uitdrukt.

  • HTML- code bestaat uit pure tekst. De parser in een webbrowser gebruikt dit om de logische structuur als een gegevensstructuur te creëren. Het uiterlijk van deze elementen wordt apart gedefinieerd via CSS .
  • RSS-parsers zetten RSS- feeds om naar een ander gegevensformaat, bijvoorbeeld voor een HTML-pagina.
  • XML-parsers analyseren XML- documenten en stellen de daarin vervatte informatie (d.w.z. elementen, attributen, enz.) beschikbaar voor verdere verwerking.
  • URI- parsers lossen schema's zoals URL's op in hun hiërarchische structuur (zie RFC 3986 ).
  • Parsers van logbestanden worden gebruikt om relevante informatie te extraheren uit logbestanden van webservers , gebeurtenislogboeken en andere informatie die is opgeslagen in logbestanden voor geautomatiseerde analyse.
  • Zoekmachines analyseren websites en crawlen relevante tekstpassages.
  • Een programmeertaal uitlezen . Een compiler kan dan machinecode of bytecode genereren uit de verkregen datastructuur.
  • Een opdrachtregelinterpreter ontleedt opdrachten en hun parameters voor de juiste uitvoering van de gebruikersinstructies (bijvoorbeeld via COMMAND.COM ).
  • In tekstavonturen wordt het personage bestuurd door opdrachten in natuurlijke taal in te voeren, b.v. B. "Ontgrendel de voordeur met de huissleutel". De parser ontsluit een database van alle manipuleerbare objecten in het spel en analyseert welke interactie met welke objecten in de spelwereld de speler bedoelde met zijn commando-invoer.

functionaliteit

Parsers gebruiken meestal een aparte lexicale scanner (ook wel een lexer genoemd ) om de tekst te analyseren. Dit splitst de invoergegevens (aanwezig als een eenvoudige tekenreeks) op in tokens (invoersymbolen of "woorden" die de parser begrijpt); omdat de tokenisatie een reguliere grammatica volgt, is de scanner meestal een eindige automaat . Deze tokens dienen als atomaire invoertekens voor de parser. Parsers die geen aparte scanner gebruiken, worden scannerloze parsers genoemd .

De eigenlijke parser als een implementatie van een abstracte machine (meestal geïmplementeerd als een pushdown-automaat ) zorgt voor contrast met de grammatica van de invoer, voert een syntaxiscontrole uit op de invoergegevens en maakt gewoonlijk van de gegevens een afleidingsboom (vergelijkbaar met de Engelse af en toe als Parse -Tree ). Dit wordt vervolgens gebruikt voor verdere verwerking van de gegevens; Typische toepassingen zijn semantische analyse , codegeneratie in een compiler of uitvoering door een interpreter .

In het geval van HTML zou een lexicale scanner het HTML-bestand opsplitsen in HTML-tags en lopende tekst en deze componenten doorgeven aan de parser - dat wil zeggen, de scanner "geeft" alleen om het uiterlijk van de syntaxiselementen ("als het is tussen punthaken, het is een HTML-Day"). De parser daarentegen verwerkt de syntactische verbindingen, dwz onderzoekt welke paren tags bij elkaar horen of hoe de tags in elkaar genest zijn; De parser is niet geïnteresseerd in de inhoud van de tags, maar wordt alleen in aanmerking genomen door de daaropvolgende verwerking.

Een parser is de software die de instructies in de brontekst van de gebruiker controleert, verwerkt en doorstuurt.

Parsertypen

Er wordt onderscheid gemaakt tussen verschillende ontledingsmethoden. De algemene procedure, d.w.z. de differentiatie volgens de volgorde waarin de knooppunten van de afleidingsboom worden gemaakt ( top-down , ook theoriegestuurde ontleding of bottom-up , ook invoergestuurde ontleding, evenals linkerhoek ), specifiek procedure (LL, LR, SLR, LALR, LC, ...) en implementatietechniek ( recursief aflopend , recursief oplopend of tafelgestuurd). Er wordt ook onderscheid gemaakt naar het type grammatica.

Contextvrije grammatica-parser

Hier zijn een paar methoden op basis van contextvrije grammatica's :

Parser voor contextgevoelige grammatica's

Het ontleden van goed gedefinieerde kunstmatige talen (zie formele talen , programmeertalen ) is minder complex dan het ontleden van vrij ontwikkelde natuurlijke talen zoals Engels of Duits, die worden gekenmerkt door een veelheid aan dubbelzinnigheden , onregelmatigheden en inconsistenties. Zie ook computationele taalkunde .

Opmerking: de term parseren moet niet worden verward met compileren . Deze laatste genereert een doelcode uit een broncode, inclusief parsing, maar er vinden ook andere acties plaats.

voorbeeld

Parsers worden vaak gebruikt om een ​​boomstructuur te maken van een reeks symbolen. Een typisch voorbeeld hiervan zijn wiskundige uitdrukkingen zoals

.

Deze uitdrukking, zoals die hier staat, bestaat in eerste instantie alleen uit een reeks symbolen. Het is de taak van een tokenizer als onderdeel van een parser om deze symbolen te identificeren en te classificeren (bijvoorbeeld van links naar rechts in leesrichting ). Het resultaat is een list_ , die hieronder als tabel wordt weergegeven en regel voor regel kan worden gelezen:

symbool categorie Uitleg
2 nummer
+ rekenkundig symbool
( Beugel open
2 nummer
+ rekenkundig symbool
2 nummer
) Klem gesloten
- rekenkundig symbool
zonde Symbool naam (hier: de sinusfunctie )
( Beugel open
π Symbool naam (hier: het cirkel getal π)
) Klem gesloten

De (verdere) taak van de parser is om de onderliggende structuur van deze symboolreeks te herkennen. Vaak gebeurt dit in de vorm van een parse tree ( abstract syntax tree ), die er in dit geval als volgt uit kan zien:

Parser-Organigram.svg

Dit is de uitvoer van een eenvoudige parser. Deze uitvoer kan nu door andere programma's worden geanalyseerd.

Zie ook

literatuur

  • AW Appel: implementatie van moderne compilers in Java. Cambridge 1998.
  • Paul Bennett: Een cursus in de grammatica van gegeneraliseerde zinsstructuren. Londen: UCL Press 1995. ISBN 1-85728-217-5 .
  • Robert D. Borsley: syntactische theorie. Een uniforme aanpak. London: Edward Arnold 1991. 2e herziene editie 1998, ISBN 0-340-70610-4 . Duitse vertaling: syntaxistheorie. Een geconsolideerde aanpak. Tübingen: Niemeyer Verlag 1997. ISBN 3-484-22055-4 .
  • Sven Naumann, Hagen Langer: ontleden. Teubner Verlag 1994.

web links

WikiWoordenboek: Parser - uitleg van betekenissen, woordoorsprong, synoniemen, vertalingen