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

Wat is syntaxisanalyse?

Syntaxisanalyse is een tweede fase van het compilerontwerpproces waarin de gegeven invoerstring wordt gecontroleerd op de bevestiging van regels en structuur van de formele grammatica. Het analyseert de syntactische structuur en controleert of de gegeven invoer in de juiste syntaxis van de programmeertaal staat of niet.

Syntaxisanalyse in het Compiler Design-proces komt na de lexicale analysefase. Het is ook bekend als de Parse Tree of Syntax Tree. De Parse Tree is 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 het voldoet, maakt de parser vervolgens de ontleedboom van dat bronprogramma. Anderwise, worden foutmeldingen weergegeven.

Syntaxisanalyse
Syntaxisanalysatorproces

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 rekenkundige basisbewerkingen uit.
  • Syntactische elementen van de taal

Waarom hebben we parseren nodig?

Parsing

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

Parsing

Following zijn belangrijke taken die door de parser worden uitgevoerd bij het ontwerp van de 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

  1. 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 het bottom-up parseren in het compilerontwerp begint de constructie van de ontleedboom met het verlof, en vervolgens wordt deze verwerkt naar de root. Het wordt ook wel shift-reduce-parsing genoemd. Dit type parseren in het compilerontwerp wordt gemaakt met behulp van enkele 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 eventuele fouten in het programma kunnen detecteren en rapporteren. Dus telkens wanneer er een fout optrad, werd de parser. Het zou het moeten kunnen verwerken en doorgaan met het parseren van de resterende invoer. Een programma kan following soorten fouten in verschillende stadia van het compilatieproces. Er zijn vijf algemene 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 instructie en wordt de invoer van de fout niet verwerkt.neoons invoer voor scheidingsteken, zoals een puntkomma. Dit is een eenvoudige methode voor foutherstel.
  • Bij dit type herstelmethode weigert de parser invoersymbolen één voor één totdat er een enkele aangewezen groep is syncEr zijn ronisatietokens gevonden. De syncHet roniseren van tokens maakt meestal gebruik van 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

  • Foutproductieherstel breidt de grammatica uit voor de taal die de fout genereertneoons construeert. De parser voert vervolgens een foutdiagnose uit over dat construct.

Mondiale correctie

  • De compiler moet zo weinig mogelijk wijzigingen aanbrengen tijdens het verwerken van een onjuiste invoerreeks. Gegeven onjuiste invoertekenreeks a en grammatica c, zullen algoritmen zoeken naar een ontleedboom voor een gerelateerde tekenreeks b. Zoals sommige invoegingen, verwijderingen en wijzigingen aan tokens die nodig zijn om an in b te transformeren, is dit 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 productie worden weergegeven
  • Een regel is recursief als LHS in zijn RHS voorkomt

Notationele conventies

Het symbool voor notatieconventies kan worden aangegeven door het element in een vierkant te omsluiten brackets. Het is een willekeurige reeks exemplaren 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,
  • Operatorsymbolen 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
  • Niet helpt u bepalen of een bewerking die op een tokentype wordt uitgevoerd, geldig is of niet
  • U kunt niet beslissen dat het token wordt gedeclareerd en geïnitialiseerd voordat het wordt gebruikt

Samengevat

  • 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
  • Het symbool voor notatieconventies kan worden aangegeven door het element in een vierkant te omsluiten brackets
  • 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