Parser
Een parser (van het Engelse to parse, ontleden, en het Latijnse pars, deel) is een computerprogramma, of component van een programma, dat de grammaticale structuur van een invoer volgens een vastgelegde grammatica ontleedt (parset). Een parser zet ingevoerde tekst om in een datastructuur. Vergelijk het met het invullen van een formulier met gegevens op de voorgegeven plaats in een voorgegeven tekstformaat, zoals bloktekst.
Het resultaat van een bewerking met een parser is meestal een boomstructuur: de syntaxisboom genoemd.
Inhoud |
Een parser heeft twee taken wat betreft zijn invoer:
- Het controleren of de gegeven invoer de correcte structuur heeft, en
- het omzetten van de tekst in een gestructureerde representatie die voor de computer begrijpelijk is.
De gestructureerde representatie van een tekst die de parser oplevert wordt een concrete syntaxisboom genoemd (of: CST, van concrete syntaxtree). Deze dient vervolgens als invoer voor een ander computerprogramma (of een andere module van hetzelfde programma) voor verdere analyse en verwerking, zoals semantische analyse, of het genereren van code door een compiler.
Een parser kan ook gebruikt worden om natuurlijke talen te analyseren. Over het algemeen is dit veel moeilijker dan het analyseren van een computerbestand, omdat er behoorlijk wat inconsequentie kan zitten in natuurlijke talen.
Een voorbeeld van het parsen van een expressie:
(a + b) × 1
kan omgezet worden in de volgende boomstructuur:
[bewerken] Soorten parsers
Er zijn verschillende soorten parsers, met verschillende mogelijkheden en verschillende manier van werken.
[bewerken] Topdown-parsers
Topdown-parsers beginnen met de root van de parsetree, en bouwen de boom steeds verder op naar beneden, richting de nodes (bladeren). Ze beginnen als het ware vanuit de grammatica, en proberen (letterlijk: ze proberen de verschillende mogelijkheden één voor één uit) deze op de tekst te passen.
We onderscheiden:
[bewerken] Recursieve descent-parsers
Recursieve descent-parsers worden geïmplementeerd als een aantal functies, of procedures, die elkaar onderling recursief aanroepen. Er is een functie voor iedere nonterminal in de grammatica. Recursieve descent-parsers zijn relatief eenvoudig met de hand te programmeren, maar lenen zich niet voor automatische generatie met een parsergenerator.
[bewerken] LL-parsers (Left to right, leftmost derivation parser)
Een LL-parser selecteert telkens een nonterminal aan de onderkant van de (tot dan toe opgebouwde) parsetree en breidt deze uit: hij voegt aan de geselecteerde node elk item dat aan de rechterkant van de produktieregel voor die nonterminal voorkomt toe als kind-node. Dit proces herhaalt zich tot de parser vastloopt. In zo'n geval vindt er backtracking plaats, en wordt een andere mogelijkheid geprobeerd.
[bewerken] Bottomup-parsers
Deze worden ook vaak shift-reduce-parsers genoemd. Bottomup-parsers bouwen de parsetree vanaf de onderkant op. Ze beginnen met het maken van de nodes onderaan de boom en voegen vervolgens lagen van nonterminals toe. Bottomup-parsers werken dus als het ware vanuit de invoer, terwijl topdown-parsers werken vanuit de grammatica.
Tijdens het opbouwen van de parsetree zoekt de parser in bovenkant van de boom telkens naar een gedeelte dat overeenkomt met de rechterkant van een productieregel. Wanneer zo'n gedeelte gevonden wordt, voegt de parser de nonterminal aan de linkerkant van de produktieregel als node toe. Vervolgens worden de nodes die samen de rechterkant van de productie vormden als kinderen aan de nieuwe node verbonden. Dit proces herhaalt zich tot zich één van de volgende mogelijkheden voordoet:
- De parser komt uiteindelijk uit bij de start-produktieregel. De linkerkant van de start-productie wordt dan toegevoegd als root en de boom is af. Als alle invoer dan ook verwerkt is, is de invoer geldig volgens de gebruikte grammatica.
- Er worden geen onverwerkte nodes die samen de rechterkant van een produktieregel meer gevonden. In dit geval is de invoer niet correct en is sprake van een syntax error.
[bewerken] LR-parsers (Left to right, leftmost derivation)
Een LR-parser is een parser die zijn invoer verwerkt van links naar rechts en een omgekeerde rightmost derivation[1] oplevert.
Een LR-parser die hierbij alleen kijkt naar het volgende symbool in de invoer, en niet verder vooruit kijkt, is een LR(1)-parser. Een LR-parser die meer dan één symbool vooruit kijkt wordt een LR(k)-parser genoemd.
[bewerken] LALR-parsers (LookAhead LR-parser)
LALR-parsers zijn een gespecialiseerde vorm van LR-parsers. Een LALR-parser werkt op dezelfde manier als andere bottomup-parsers, maar wordt op een speciale manier geïmplementeerd. LALR-parsers zijn kleiner dan "gewone" LR-parsers, maar kunnen dezelfde soorten grammatica's verwerken als LR-parsers.
[bewerken] GLR-parsers (Generalized left-to-right rightmost derivation-parsers)
GLR-parsers kunnen meer soorten grammatica's verwerken dan gewone LR-parsers. Ze kunnen namelijk ook ambigue grammatica's parsen. Als de invoer volgens de gebruikte grammatica op meerdere manieren geïnterpreteerd kan worden levert een GLR-parser alle mogelijke syntaxisbomen als resultaat op.
[bewerken] Zie ook
[bewerken] Externe links
- (en) Demonstration of Parsing Algorithms Drie Java-applets die recursive-descent, LL(1) en shift-reduce-parsing demonstreren
Bronnen, noten en/of referenties:
- ↑ Een rightmost derivation (rechter afleiding) is een afleiding van een parsetree die ontstaat door telkens de meest rechtse nonterminal te verwerken
| Compiler | ||||||
|---|---|---|---|---|---|---|
|
