parsingAan de slag met parseren


Opmerkingen

Parsing verwijst in het algemeen naar het analyseren van een stuk taal, zoals een zin, en het gebruiken van de grammaticaregels van die taal om de componenten te identificeren en zo de betekenis te leren. In de informatica verwijst het naar een specifiek algoritmisch proces van het herkennen van de reeks symbolen als een geldige en waarmee de betekenis (of semantiek ) van een taalconstruct kan worden bepaald, vaak in een computertaalcompiler of -tolk.

Een eenvoudige parser

De eenvoudigste manier om een parser te schrijven, is door de techniek van recursieve afdaling te gebruiken. Dit creëert een top-down parser (die formeel een LL (1) kan worden beschreven). Om het voorbeeld te starten, moeten we eerst de grammaticaregels voor onze taal vaststellen. In dit voorbeeld gebruiken we eenvoudige rekenkundige expressie-toewijzingen voor expressies die alleen de plus-operator kunnen gebruiken:

 Assignment --> Identifier := Expression
 Expression --> Expression + Term | Term
 Term --> Identifier | (Expression)
 Identifier --> x | y | z 
 

Voor elke regel van de grammatica kunnen we een procedure schrijven om de inkomende tokens voor de regel te herkennen. Voor de doeleinden van dit voorbeeld kunnen we uitgaan van een routine met de naam NextToken die een lexicale analysator oproept om het token te leveren, en een routine genaamd error die wordt gebruikt om een foutbericht uit te voeren. De gebruikte taal is gebaseerd op Pascal.

 var token:char;  (* Updated by NextToken *) 

 procedure identifier;
 begin
    if token in ['x','y','z']
    then
        NextToken
    else
        error('Identifier expected')
 end; 
 

U kunt zien dat deze code de regel implementeert voor het herkennen van een Identifier . We kunnen dan de uitvoering van de regel voor een Term op dezelfde manier:

 procedure expression forward; 

 procedure term;
 begin
     if token = '('
     then
         begin
         nextToken;
         expression;
         if token <> ')'
         then
             error(') expected')
         else NextToken
         end
     else
         identifier
 end; 
 

Als we de regel voor Expression komen implementeren, hebben we een probleem; het eerste element van de Expression regel is zelf een Expression . Dit zou ertoe leiden dat we het volgende schrijven:

procedure expression;
begin
expression;
...
end;
 

Dit is direct zelfrecursief en zou dus voor altijd doorlopen. Grammatica die wordt geparseerd door top-down algoritmen kan om deze reden niet recursief blijven. Een gemakkelijke manier om dit probleem te verhelpen, is om de recursie als iteratie op de volgende manier te herschikken:

Expression --> Term { + Term}* 
 

We kunnen de grammaticaregel nu coderen als:

 procedure expression;
 begin
     term;
     while token = '+'
         do
         begin
             NextTerm;
             term
         end
 end; 
 

We kunnen de parser nu voltooien met de resterende regel voor de toewijzing:

procedure assignment;
begin 
    identifier;
    if token <> '='
    then
        error('= expected')
    else
        begin
        NextToken;
        expression;
        end
 end; 
 

Voorbeeld van het parseren van een Engelse zin

In de zin bijvoorbeeld:

Die cake is ontzettend lekker.

De regels van de Engelse taal zouden cake tot een zelfstandig naamwoord maken , extreem een bijwoord dat het bijvoeglijk naamwoord mooi wijzigt, en door deze analyse kon de betekenis worden begrepen.

Deze analyse is echter afhankelijk van ons als we erkennen dat de gebruikte reeks symbolen woorden zijn. Als de gebruikte tekens ons niet bekend zouden zijn, zouden we dit niet kunnen doen. Als we een zin tegenkomen met een onbekende notatie, zoals Chinees, kan parseren op deze manier moeilijk zijn. Hier is een voorbeeld van een Chinese zin:

我 可以 写 一点儿 中文.

Voor iedereen die geen Chinese karakters leest, is het niet duidelijk welke symbolen gecombineerd worden om woorden te vormen. Hetzelfde zou kunnen gelden voor een computeralgoritme bij het verwerken van Engels of Chinees.

Het parseren moet dus worden uitgevoerd door een proces dat bekend staat als lexicale analyse of scannen , waarbij de afzonderlijke tekens worden gegroepeerd in herkende symbolen, die we gewoonlijk woorden kunnen noemen, maar in parsing-algoritmen tokens worden genoemd.

Wat je nodig hebt om te parseren

Bij het uitvoeren van parsing moet vóór het starten de grammatica voor de taal worden opgegeven. Een bron van tokens is ook nodig voor de parser.

De parser kan handgeschreven code zijn, of er kan een tool voor het genereren van parsers worden gebruikt. Als een parser-generator wordt gebruikt, moet dat hulpprogramma worden gedownload en geïnstalleerd als het nog niet is opgenomen in uw platform.

Grammatica definities

Een grammatica voor een parser zou normaal gesproken in een contextvrije vorm moeten worden geschreven. Hiervoor wordt vaak een notatie zoals BNF (Backus-Naur Form) of EBNF (Extended Back-Naur Form) gebruikt. Andere notaties die gewoonlijk worden gebruikt om programmeertalen te beschrijven, kunnen spoorwegdiagrammen zijn .

Lexicale analyse

Gewoonlijk worden tokens voor de parser geleverd door een lexicale analysator (of scanner) . Meer details zijn te vinden in de documentatie voor een lexical analyzer (TBC).

Parsing-technieken

Om een parser met de hand te coderen, zou een geschikt algoritme moeten worden gekozen dat past bij zowel de gepubliceerde taal als de implementatiemiddelen. Parsing-algoritmen zijn onderverdeeld in de twee soorten top-down parsing en bottom-up parsing . Een (recursieve) top-down parser is gemakkelijker voor een beginner om te leren wanneer hij begint met het schrijven van parsers.

Parser Generator Tools

De meest gebruikelijke manier om een parser te maken, is door een tool voor het genereren van parsers te gebruiken. Er zijn veel van dergelijke tools, maar enkele van de meest gebruikte zijn: