Syntaxisanalyse: compiler-types van top-down en bottom-up parseren

Syntaxisanalyse in compiler Het ontwerpproces komt na de lexicale analysefase. Het staat ook bekend als de parse tree of syntaxisboom. De parse tree wordt ontwikkeld met behulp van vooraf gedefinieerde grammatica van de taal. De syntaxisanalysator controleert ook of een bepaald programma voldoet aan de regels die worden geïmpliceerd door een contextvrije grammatica. Als dit het geval is, maakt de parser de parse tree van dat bronprogramma. Anders worden er foutmeldingen weergegeven.

Waarom heb je Syntax Analyser nodig?

• Controleer of de code grammaticaal geldig is
• De syntactische analysator helpt u regels op de code toe te passen
• Helpt u ervoor te zorgen dat elk openingsaccolade een overeenkomstig eindsaldo heeft
• Elke aangifte heeft een type en dat type moet bestaan

Belangrijke terminologie van de Syntax Analyzer

Belangrijke terminologieën die worden gebruikt in het syntaxisanalyseproces:

• Zin: Een zin is een groep tekens over een bepaald alfabet.

• Lexeme: Een lexeme is de syntactische eenheid op het laagste niveau van een taal (bijvoorbeeld totaal, start).

• Token: Een token is slechts een categorie lexemen.

• Trefwoorden en gereserveerde woorden – Het is een identificatie die wordt gebruikt als een vast onderdeel van de syntaxis van een instructie. Het is een gereserveerd woord dat u niet kunt gebruiken als variabelenaam of identificatie.

• Lawaaiige woorden – Ruiswoorden zijn optioneel en kunnen in een verklaring worden ingevoegd om de leesbaarheid van de zin te vergroten.

• Heb je vragen? Stel ze hier. – Het is een zeer belangrijk onderdeel van de documentatie. Het wordt meestal weergegeven met /* */, of//Blank (spaties)

• delimiters – Het is een syntactisch element dat het begin of einde van een syntactische eenheid markeert. Zoals een verklaring of uitdrukking, “begin”…end”, of {}.

• Karakterset – ASCII, Unicode

• Identifiers – Het is een beperking van de lengte die u helpt de leesbaarheid van de zin te verminderen.

• Operator symbolen – + en – voert twee basisrekenkundige bewerkingen uit.
• Syntactische elementen van de taal

Waarom hebben we parseren nodig?

Een parse controleert ook of de invoertekenreeks goed is opgemaakt en als dat niet het geval is, wordt deze afgewezen.

Hieronder staan ​​de belangrijke taken die de parser uitvoert bij het ontwerpen van een compiler:

• Helpt u bij het detecteren van alle soorten syntaxisfouten
• Zoek de positie waarop de fout is opgetreden
• Duidelijke en nauwkeurige beschrijving van de fout.
• Herstel van een fout om door te gaan en verdere fouten in de code te vinden.
• Mag de compilatie van “juiste” programma’s niet beïnvloeden.
• De parseerfunctie moet ongeldige teksten afwijzen door syntaxisfouten te rapporteren

Ontledingstechnieken

Parseertechnieken zijn onderverdeeld in twee verschillende groepen:

• Top-down parseren,
• Bottom-up parseren

Top-down parseren

Bij de top-down parseerconstructie begint de ontleedboom bij de wortel en gaat dan verder richting de bladeren.

Er zijn twee soorten top-down-parsering:

1. Voorspellende parsering:

Met voorspellende parse kan worden voorspeld welke productie moet worden gebruikt om de specifieke invoerreeks te vervangen. De voorspellende parser maakt gebruik van een vooruitkijkpunt, dat naar de volgende invoersymbolen wijst. Backtracking is geen probleem met deze parseertechniek. Het staat bekend als LL(1)-parser

2. Recursieve afdalingsparsering:

Deze parseertechniek ontleedt de invoer recursief om een ​​prase-boom te maken. Het bestaat uit verschillende kleine functies, één voor elke niet-terminal in de grammatica.

Bottom-up parseren

Bij bottom-up parsing in compiler design begint de constructie van de parse tree met het leaf, en dan gaat het naar de root. Het wordt ook wel shift-reduce parsing genoemd. Dit type parsing in compiler design wordt gemaakt met behulp van een aantal software tools.

Fout – Herstelmethoden

Veelvoorkomende fouten die optreden bij het parseren in systeemsoftware

• Lexicale: Naam van een onjuist getypte ID
• syntactisch: ongebalanceerd haakje of een ontbrekende puntkomma
• Semantisch: incompatibele waardetoewijzing
• logisch: Oneindige lus en niet bereikbare code

Een parser moet in staat zijn om elke fout die in het programma wordt gevonden te detecteren en te rapporteren. Dus wanneer er een fout optreedt, moet de parser. Deze moet in staat zijn om deze te verwerken en de resterende invoer te parsen. Een programma kan de volgende typen fouten hebben in verschillende fasen van het compilatieproces. Er zijn vijf veelvoorkomende foutherstelmethoden die in de parser kunnen worden geïmplementeerd

Herstel in instructiemodus

• In het geval dat de parser een fout tegenkomt, helpt deze u corrigerende maatregelen te nemen. Hierdoor kunnen de rest van de invoer en statussen vooruit worden geparseerd.
• Het toevoegen van een ontbrekende puntkomma gebeurt bijvoorbeeld in de herstelmethode in de instructiemodus. De parse-ontwerper moet echter voorzichtig zijn bij het aanbrengen van deze wijzigingen, aangezien één verkeerde correctie tot een oneindige lus kan leiden.

Herstel in paniekmodus

• In het geval dat de parser een fout tegenkomt, negeert deze modus de rest van de verklaring en verwerkt geen invoer van foutieve invoer naar scheidingsteken, zoals een puntkomma. Dit is een eenvoudige methode voor foutherstel.
• Bij dit type herstelmethode wijst de parser invoersymbolen één voor één af totdat er een enkele aangewezen groep synchronisatietokens is gevonden. De synchronisatietokens gebruiken over het algemeen scheidingstekens zoals of.

Herstel op zinsniveau

• Compiler corrigeert het programma door tokens in te voegen of te verwijderen. Hierdoor kan het verder gaan met parseren vanaf het punt waar het was. Het voert een correctie uit op de resterende invoer. Het kan een voorvoegsel van de resterende invoer vervangen door een tekenreeks, waardoor de parser het proces kan voortzetten.

Fout producties

• Error production recovery breidt de grammatica uit voor de taal die de foutieve constructies genereert. De parser voert vervolgens een foutdiagnose uit over die constructie.

Mondiale correctie

• De compiler moet zo min mogelijk wijzigingen aanbrengen tijdens het verwerken van een onjuiste invoerreeks. Gegeven de onjuiste invoerreeks a en grammatica c, zullen algoritmen zoeken naar een parse tree voor een gerelateerde reeks b. Zoals sommige invoegingen, verwijderingen en wijzigingen van tokens die nodig zijn om an in b te transformeren, is zo min mogelijk.

Grammatica

Een grammatica is een reeks structurele regels die een taal beschrijven. Grammatica's geven structuur aan elke zin. Deze term verwijst ook naar de studie van deze regels, en dit bestand omvat morfologie, fonologie en syntaxis. Het is in staat om veel van de syntaxis van te beschrijven programmeertalen.

Regels voor vormgrammatica

• Het niet-terminale symbool moet links van de ten minste ene productie verschijnen
• Het doelsymbool mag nooit rechts van de::= van een productielijn worden weergegeven.
• Een regel is recursief als LHS in zijn RHS voorkomt

Notationele conventies

Notatieconventies symbool kan worden aangegeven door het element tussen vierkante haken te plaatsen. Het is een willekeurige reeks instanties van het element die kan worden aangegeven door het element tussen accolades te plaatsen, gevolgd door een asterisk-symbool, { … }*.

Het is een keuze voor het alternatief waarbij het symbool binnen de enkele regel mag worden gebruikt. Het kan indien nodig tussen haakjes ([,] ) worden geplaatst.

Er zijn twee soorten notatieconventies: terminals en niet-terminals

1. Terminals:

• Kleine letters in het alfabet, zoals a, b, c,
• OperaTor-symbolen zoals +,-, *, etc.
• Leestekens zoals haakjes, hekje, komma
• 0, 1, …, 9 cijfers
• Vetgedrukte tekenreeksen zoals id of if, iets dat een enkel terminalsymbool vertegenwoordigt

2. Niet-terminals:

• Hoofdletters zoals A, B, C
• Cursieve namen in kleine letters: de uitdrukking of enkele

Contextvrije grammatica

Een CFG is een links-recursieve grammatica die ten minste één productie van het type heeft. De regels in een contextvrije grammatica zijn voornamelijk recursief. Een syntaxisanalysator controleert of een specifiek programma aan alle regels van contextvrije grammatica voldoet of niet. Als het wel voldoet, kunnen de syntaxisanalysatoren van deze regels een ontleedboom voor dat programma maken.

expression -> expression -+ term
expression -> expression – term 
expression-> term
term  -> term * factor
term -> expression/ factor
term  -> factor factor
factor ->  ( expression )
factor -> id

Grammatica-afleiding

Grammatica-afleiding is een reeks grammaticaregels die het startsymbool in de string omzet. Een afleiding bewijst dat de string tot de taal van de grammatica behoort.

Meest linkse afleiding

Wanneer de sententiële vorm van invoer wordt gescand en vervangen in de volgorde van links naar rechts, staat dit bekend als meest linkse afleiding. De zinsvorm die wordt afgeleid door de meest linkse afleiding wordt de links-sententiële vorm genoemd.

Meest rechtse afleiding

Meest rechtse afleidingsscan en vervang de invoer door productieregels, van rechts naar links, volgorde. Het staat bekend als de meest rechtse afleiding. De zinsvorm die is afgeleid van de meest rechtse afleiding staat bekend als rechts-sententiële vorm.

Syntaxis versus lexicale analysator

Syntaxisanalysator	Lexicale analysator
De syntaxisanalysator houdt zich voornamelijk bezig met recursieve constructies van de taal.	De lexicale analysator verlicht de taak van de syntaxisanalysator.
De syntaxisanalysator werkt op tokens in een bronprogramma om betekenisvolle structuren in de programmeertaal te herkennen.	De lexicale analysator herkent het token in een bronprogramma.
Het ontvangt input, in de vorm van tokens, van lexicale analysatoren.	Zij is verantwoordelijk voor de geldigheid van een token geleverd door de syntaxisanalysator

Nadelen van het gebruik van Syntax Analyzers

• Het zal nooit bepalen of een token geldig is of niet
• Het helpt u niet om te bepalen of een bewerking die op een tokentype is uitgevoerd, geldig is of niet
• U kunt niet beslissen dat het token wordt gedeclareerd en geïnitialiseerd voordat het wordt gebruikt

Samenvatting

• Syntaxisanalyse is een tweede fase van het compilerontwerpproces die volgt op lexicale analyse
• De syntactische analysator helpt u regels op de code toe te passen
• Zin, Lexeme, Token, trefwoorden en gereserveerde woorden, ruiswoorden, opmerkingen, scheidingstekens, tekenset, identificatiegegevens zijn enkele belangrijke termen die worden gebruikt in de syntaxisanalyse in de constructie van de compiler
• Parseren controleert of de invoertekenreeks goed is opgemaakt en als dit niet het geval is, wordt deze afgewezen
• Parseertechnieken zijn onderverdeeld in twee verschillende groepen: Top-Down Parsing, Bottom-Up Parsing
• Lexicaal, syntactisch, semantisch en logisch zijn enkele veelvoorkomende fouten die optreden tijdens de parseermethode
• Een grammatica is een reeks structurele regels die een taal beschrijven
• Notatieconventies kunnen worden aangegeven door het element tussen vierkante haken te plaatsen
• Een CFG is een links-recursieve grammatica die ten minste één productie van het type heeft
• Grammatica-afleiding is een reeks grammaticaregels die het startsymbool in de string omzet
• De syntaxisanalysator houdt zich voornamelijk bezig met recursieve constructies van de taal, terwijl de lexicale analysator de taak van de syntaxisanalysator vergemakkelijkt. dbms
• Het nadeel van de Syntax-analysemethode is dat deze nooit zal bepalen of een token geldig is of niet