Syntaksanalyse: Compiler Top Down & Bottom Up Parsingstyper

Syntaksanalyse i compilerdesignproces kommer efter den leksikalske analysefase. Det er også kendt som Parse Tree eller Syntax Tree. Parse Tree er udviklet ved hjælp af foruddefineret grammatik af sproget. Syntaksanalysatoren kontrollerer også, om et givet program opfylder reglerne i en kontekstfri grammatik. Hvis den opfylder, opretter parseren derefter parsetræet for det pågældende kildeprogram. Ellers vil den vise fejlmeddelelser.

Hvorfor har du brug for Syntax Analyser?

• Tjek om koden er grammatisk gyldig
• Den syntaktiske analysator hjælper dig med at anvende regler på koden
• Hjælper dig med at sikre, at hver åbningsbøjle har en tilsvarende lukkebalance
• Hver erklæring har en type, og at typen skal eksistere

Vigtig syntaksanalysatorterminologi

Vigtige terminologier brugt i syntaksanalyseprocessen:

• Dømme: En sætning er en gruppe af tegn over et eller andet alfabet.

• Leksem: Et leksem er den laveste syntaktiske enhed i et sprog (f.eks. total, start).

• Token: Et token er blot en kategori af leksemer.

• Nøgleord og reserverede ord – Det er en identifikator, der bruges som en fast del af syntaksen i et udsagn. Det er et reserveret ord, som du ikke kan bruge som variabelnavn eller identifikator.

• Støjord – Støjord er valgfrie, som indsættes i en erklæring for at forbedre sætningens læsbarhed.

• Kommentarer – Det er en meget vigtig del af dokumentationen. Det vises for det meste med /* */, eller//Blank (mellemrum)

• afgrænsere – Det er et syntaktisk element, som markerer starten eller slutningen af ​​en eller anden syntaktisk enhed. Som et udsagn eller udtryk, "begynd"..."slut" eller {}.

• Tegn sæt – ASCII, Unicode

• Identifikatorer – Det er en begrænsning af længden, som hjælper dig med at reducere sætningens læsbarhed.

• Operator symboler – + og – udfører to grundlæggende aritmetiske operationer.
• Syntaktiske elementer i sproget

Hvorfor har vi brug for parsing?

En parse kontrollerer også, at inputstrengen er velformet, og hvis ikke, afvis den.

Følgende er vigtige opgaver, som parseren udfører i compilerdesign:

• Hjælper dig med at opdage alle typer syntaksfejl
• Find den position, hvor fejlen er opstået
• Klar og præcis beskrivelse af fejlen.
• Retablering fra en fejl for at fortsætte og finde yderligere fejl i koden.
• Bør ikke påvirke kompilering af "korrekte" programmer.
• Parsen skal afvise ugyldige tekster ved at rapportere syntaksfejl

Parsing teknikker

Parsingteknikker er opdelt i to forskellige grupper:

• Top-down parsing,
• Bottom-up parsing

Top-down parsing

I den top-down parsing starter konstruktionen af ​​parsetræet ved roden og fortsætter derefter mod bladene.

To typer top-down-parsing er:

1. Forudsigende parsing:

Prediktiv parse kan forudsige, hvilken produktion der skal bruges til at erstatte den specifikke inputstreng. Den forudsigende parser bruger look-ahead point, som peger mod næste input symboler. Backtracking er ikke et problem med denne parsingteknik. Det er kendt som LL(1) Parser

2. Rekursiv descent parsing:

Denne parsing-teknik analyserer rekursivt inputtet for at lave et prasetræ. Den består af flere små funktioner, en for hver ikke-terminal i grammatikken.

Bottom-up parsing

I parsing fra bunden og op i compilerdesign starter konstruktionen af ​​parsetræet med bladet, og derefter bearbejder det mod sin rod. Det kaldes også shift-reduce parsing. Denne type parsing i compilerdesign er skabt ved hjælp af nogle softwareværktøjer.

Fejl – Gendannelsesmetoder

Almindelige fejl, der opstår i parsing i systemsoftware

• leksikalsk: Navn på en forkert indtastet identifikator
• Syntaktisk: ubalanceret parentes eller et manglende semikolon
• Semantisk: uforenelig værditildeling
• Logisk: Uendelig sløjfe og ikke tilgængelig kode

En parser skal være i stand til at opdage og rapportere enhver fejl fundet i programmet. Så hver gang der opstod en fejl, parseren. Det burde kunne håndtere det og fortsætte med at analysere det resterende input. Et program kan have følgende typer fejl i forskellige kompileringsprocesser. Der er fem almindelige fejlgendannelsesmetoder, som kan implementeres i parseren

Gendannelse af erklæringstilstand

• I det tilfælde, hvor parseren støder på en fejl, hjælper det dig med at tage korrigerende skridt. Dette tillader resten af ​​input og tilstande at parse fremad.
• For eksempel, tilføjelse af et manglende semikolon kommer i sætningstilstands gendannelsesmetode. Parse-designeren skal dog være forsigtig, mens du foretager disse ændringer, da en forkert korrektion kan føre til en uendelig løkke.

Panic-Mode gendannelse

• I det tilfælde, hvor parseren støder på en fejl, ignorerer denne tilstand resten af ​​sætningen og behandler ikke input fra forkert input til afgrænsningstegn, som et semikolon. Dette er en simpel fejlgendannelsesmetode.
• I denne type gendannelsesmetode afviser parseren inputsymboler én efter én, indtil en enkelt udpeget gruppe af synkroniseringstokens er fundet. Synkroniseringstokens bruger generelt afgrænsere som eller.

Gendannelse på sætningsniveau

• Compiler retter programmet ved at indsætte eller slette tokens. Dette giver den mulighed for at fortsætte med at parse, hvorfra den var. Den udfører korrektion på det resterende input. Det kan erstatte et præfiks for det resterende input med en streng, hvilket hjælper parseren med at fortsætte processen.

Fejlproduktioner

• Gendannelse af fejlproduktion udvider grammatikken for det sprog, som genererer de fejlagtige konstruktioner. Parseren udfører derefter fejldiagnostik om denne konstruktion.

Global korrektion

• Compileren skal foretage færre ændringer som muligt under behandling af en forkert inputstreng. Givet forkert inputstreng a og grammatik c, vil algoritmer søge efter et parsetræ for en relateret streng b. Ligesom nogle indsættelser, sletninger og modifikationer lavet af tokens, der er nødvendige for at transformere an til b, er så lidt som muligt.

Grammatik

En grammatik er et sæt af strukturelle regler, der beskriver et sprog. Grammatikker tildeler struktur til enhver sætning. Dette udtryk refererer også til studiet af disse regler, og denne fil inkluderer morfologi, fonologi og syntaks. Det er i stand til at beskrive mange, af syntaksen af programmeringssprog.

Regler for formgrammatik

• Det ikke-terminale symbol skal vises til venstre for den mindst ene produktion
• Målsymbolet bør aldrig vises til højre for::= af nogen produktion
• En regel er rekursiv, hvis LHS vises i dens RHS

Notationskonventioner

Symbol for notationskonventioner kan angives ved at omslutte elementet i firkantede parenteser. Det er en vilkårlig sekvens af forekomster af elementet, som kan angives ved at omslutte elementet i klammer efterfulgt af et stjernesymbol, { … }*.

Det er et valg af alternativet, som kan bruge symbolet inden for den enkelte regel. Det kan være omgivet af parentes ([,] ), når det er nødvendigt.

To typer notationskonventioner område Terminal og Ikke-terminaler

1. Terminaler:

• Små bogstaver i alfabetet, såsom a, b, c,
• Operator-symboler som +,-, * osv.
• Tegnsætningssymboler såsom parenteser, hash, komma
• 0, 1, …, 9 cifre
• Fed skriftstrenge som id eller if, alt hvad der repræsenterer et enkelt terminalsymbol

2. Ikke-terminaler:

• Store bogstaver som A, B, C
• Navne med små bogstaver i kursiv: udtrykket eller nogle

Kontekst gratis grammatik

En CFG er en venstre-rekursiv grammatik, der har mindst én produktion af typen. Reglerne i en kontekstfri grammatik er hovedsageligt rekursive. En syntaksanalysator kontrollerer, at det specifikke program opfylder alle reglerne for kontekstfri grammatik eller ej. Hvis den opfylder, kan disse reglersyntaksanalysatorer oprette et parsetræ for det pågældende program.

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

Grammatisk afledning

Grammatikafledning er en sekvens af grammatikregler, som omdanner startsymbolet til strengen. En afledning beviser, at strengen hører til grammatikkens sprog.

Afledning længst til venstre

Når sætningsformen for input scannes og erstattes i venstre mod højre rækkefølge, er det kendt som afledning længst til venstre. Sætningsformen, som er afledt af afledningen længst til venstre, kaldes den venstre sætningsform.

Afledning længst til højre

Afledning længst til højre scan og erstat input med produktionsregler, fra højre mod venstre, sekvens. Det er kendt som afledning længst til højre. Den sætningsform, der er afledt af den længst højre afledning, er kendt som højre sætningsform.

Syntaks vs. leksikalsk analysator

Syntaksanalysator	Leksisk analysator
Syntaksanalysatoren beskæftiger sig hovedsageligt med rekursive konstruktioner af sproget.	Den leksikalske analysator letter opgaven med syntaksanalysatoren.
Syntaksanalysatoren arbejder på tokens i et kildeprogram for at genkende meningsfulde strukturer i programmeringssproget.	Den leksikale analysator genkender tokenet i et kildeprogram.
Den modtager input i form af tokens fra leksikale analysatorer.	Den er ansvarlig for gyldigheden af ​​et token leveret af syntaksanalysatoren

Ulemper ved at bruge Syntax Analyzers

• Det vil aldrig afgøre, om et token er gyldigt eller ej
• Not hjælper dig med at afgøre, om en operation udført på en tokentype er gyldig eller ej
• Du kan ikke beslutte, at token skal erklæres og initialiseres, før det bliver brugt

Resumé

• Syntaksanalyse er en anden fase af compilerdesignprocessen, der kommer efter leksikalsk analyse
• Den syntaktiske analysator hjælper dig med at anvende regler på koden
• Sætning, Lexeme, Token, Nøgleord og reserverede ord, Støjord, Kommentarer, Afgrænsningstegn, Tegnsæt, Identifikatorer er nogle vigtige udtryk, der bruges i syntaksanalysen i compilerkonstruktion
• Parse kontrollerer, at inputstrengen er velformet, og hvis ikke, afviser den
• Parsingteknikker er opdelt i to forskellige grupper: Top-Down Parsing, Bottom-Up Parsing
• Leksikalsk, syntaktisk, semantisk og logisk er nogle almindelige fejl, der opstår under parsingmetoden
• En grammatik er et sæt af strukturelle regler, der beskriver et sprog
• Symbol for notationskonventioner kan angives ved at omslutte elementet i firkantede parenteser
• En CFG er en venstre-rekursiv grammatik, der har mindst én produktion af typen
• Grammatikafledning er en sekvens af grammatikregler, som omdanner startsymbolet til strengen
• Syntaksanalysatoren beskæftiger sig hovedsageligt med rekursive konstruktioner af sproget, mens den leksikalske analysator letter syntaksanalysatorens opgave i DBMS
• Ulempen ved Syntax-analysatormetoden er, at den aldrig vil afgøre, om et token er gyldigt eller ej