Syntaksanalyse: Parsingstyper for kompilator ovenfra og ned og nedenfra opp

Syntaksanalyse i kompilatordesignprosessen kommer etter den leksikalske analysefasen. Det er også kjent som Parse Tree eller Syntax Tree. Parse Tree er utviklet ved hjelp av forhåndsdefinert grammatikk for språket. Syntaksanalysatoren sjekker også om et gitt program oppfyller reglene som følger av en kontekstfri grammatikk. Hvis den tilfredsstiller, oppretter parseren deretter analysetreet til det kildeprogrammet. Ellers vil den vise feilmeldinger.

Hvorfor trenger du Syntax Analyser?

• Sjekk om koden er grammatisk gyldig
• Den syntaktiske analysatoren hjelper deg å bruke regler på koden
• Hjelper deg å sørge for at hver åpningsbøyle har en tilsvarende sluttbalanse
• Hver deklarasjon har en type og at typen må eksistere

Viktig syntaksanalysatorterminologi

Viktige terminologier som brukes i syntaksanalyseprosessen:

• Setning: En setning er en gruppe tegn over et eller annet alfabet.

• Lekseme: Et leksem er den syntaktiske enheten på laveste nivå i et språk (f.eks. totalt, start).

• Token: Et token er bare en kategori av leksemer.

• Nøkkelord og reserverte ord – Det er en identifikator som brukes som en fast del av syntaksen til en setning. Det er et reservert ord som du ikke kan bruke som variabelnavn eller identifikator.

• Støyord – Støyord er valgfrie som settes inn i en setning for å forbedre setningens lesbarhet.

• Kommentar – Det er en veldig viktig del av dokumentasjonen. Det vises stort sett med /* */, eller//Blank (mellomrom)

• Avgrensere – Det er et syntaktisk element som markerer starten eller slutten på en eller annen syntaktisk enhet. Som et utsagn eller uttrykk, "begynn"..."slutt", eller {}.

• Karaktersett – ASCII, Unicode

• Identifikatorer – Det er en restriksjon på lengden som hjelper deg å redusere lesbarheten til setningen.

• Operator symboler – + og – utfører to grunnleggende aritmetiske operasjoner.
• Syntaktiske elementer i språket

Hvorfor trenger vi Parsing?

En parse sjekker også at inndatastrengen er velformet, og hvis ikke, avviser den.

Følgende er viktige oppgaver som utføres av parseren i kompilatordesign:

• Hjelper deg å oppdage alle typer syntaksfeil
• Finn posisjonen der feilen har oppstått
• Klar og nøyaktig beskrivelse av feilen.
• Gjenoppretting fra en feil for å fortsette og finne flere feil i koden.
• Bør ikke påvirke kompilering av "riktige" programmer.
• Parsen må avvise ugyldige tekster ved å rapportere syntaksfeil

Parsing-teknikker

Parseteknikker er delt inn i to forskjellige grupper:

• Top-down parsing,
• Bottom-up-parsing

Top-down-parsing

I den ovenfra og ned-parsing-konstruksjonen av parsetreet starter ved roten og fortsetter deretter mot bladene.

To typer topp-ned-parsing er:

1. Prediktiv parsing:

Prediktiv parse kan forutsi hvilken produksjon som skal brukes for å erstatte den spesifikke inndatastrengen. Den prediktive parseren bruker look-ahead-punkt, som peker mot neste inngangssymboler. Tilbakesporing er ikke et problem med denne analyseteknikken. Det er kjent som LL(1) Parser

2. Rekursiv nedstigningsanalyse:

Denne analyseteknikken analyserer rekursivt inndataene for å lage et prasetre. Den består av flere små funksjoner, en for hver ikke-terminal i grammatikken.

Bottom-up-parsing

I bunnen opp-parsing i kompilatordesign starter konstruksjonen av parsetreet med bladet, og deretter prosesserer det mot roten. Det kalles også shift-reduce-parsing. Denne typen parsing i kompilatordesign lages ved hjelp av noen programvareverktøy.

Feil – Gjenopprettingsmetoder

Vanlige feil som oppstår i parsing i systemprogramvare

• Leksikalsk: Navn på en feilskrevet identifikator
• Syntaktisk: ubalansert parentes eller manglende semikolon
• Semantisk: uforenlig verditilordning
• logisk: Uendelig sløyfe og ikke tilgjengelig kode

En parser skal kunne oppdage og rapportere eventuelle feil funnet i programmet. Så når det oppstod en feil, parseren. Den skal kunne håndtere det og fortsette å analysere de gjenværende inndataene. Et program kan ha følgende typer feil ved ulike kompileringsprosessstadier. Det er fem vanlige feilgjenopprettingsmetoder som kan implementeres i parseren

Gjenoppretting av erklæringsmodus

• I tilfellet når parseren støter på en feil, hjelper det deg å ta korrigerende skritt. Dette lar resten av inndata og tilstander analysere fremover.
• For eksempel, å legge til et manglende semikolon kommer i gjenopprettingsmetoden for statement-modus. Imidlertid må parsedesigneren være forsiktig når du gjør disse endringene, da en feil korreksjon kan føre til en uendelig sløyfe.

Gjenoppretting i panikkmodus

• I tilfellet når parseren støter på en feil, ignorerer denne modusen resten av setningen og behandler ikke inndata fra feil inndata til skilletegn, som et semikolon. Dette er en enkel feilgjenopprettingsmetode.
• I denne typen gjenopprettingsmetode avviser parseren inngangssymboler én etter én inntil en enkelt utpekt gruppe synkroniseringssymboler blir funnet. Synkroniseringssymbolene bruker vanligvis skilletegn som eller.

Gjenoppretting på frasenivå

• Kompilatoren korrigerer programmet ved å sette inn eller slette tokens. Dette gjør at den kan fortsette å analysere fra der den var. Den utfører korreksjon på gjenværende inngang. Den kan erstatte et prefiks for den gjenværende inngangen med en streng, dette hjelper parseren til å fortsette prosessen.

Feilproduksjoner

• Gjenoppretting av feilproduksjon utvider grammatikken for språket som genererer de feilaktige konstruksjonene. Parseren utfører deretter feildiagnostikk om den konstruksjonen.

Global korreksjon

• Kompilatoren bør gjøre mindre antall endringer som mulig mens den behandler en feil inndatastreng. Gitt feil inndatastreng a og grammatikk c, vil algoritmer søke etter et parsetre for en relatert streng b. Som noen innsettinger, slettinger og modifikasjoner laget av tokens som trengs for å transformere an til b, er så lite som mulig.

Grammatikk

En grammatikk er et sett med strukturelle regler som beskriver et språk. Grammatikk tildeler struktur til enhver setning. Dette begrepet refererer også til studiet av disse reglene, og denne filen inkluderer morfologi, fonologi og syntaks. Den er i stand til å beskrive mange, av syntaksen til programmerings språk.

Regler for formgrammatikk

• Det ikke-terminale symbolet skal vises til venstre for den minst ene produksjonen
• Målsymbolet skal aldri vises til høyre for::= av noen produksjon
• En regel er rekursiv hvis LHS vises i RHS

Notasjonskonvensjoner

Symbol for notasjonskonvensjoner kan angis ved å sette elementet i hakeparenteser. Det er en vilkårlig sekvens av forekomster av elementet som kan angis ved å omslutte elementet i klammeparenteser etterfulgt av et stjernesymbol, { … }*.

Det er et valg av alternativet som kan bruke symbolet innenfor enkeltregelen. Den kan omsluttes av parentes ([,] ) ved behov.

To typer notasjonskonvensjoner området Terminal og Non-terminals

1. Terminaler:

• Små bokstaver i alfabetet som a, b, c,
• Operator-symboler som +,-, * osv.
• Tegnsettingssymboler som parenteser, hash, komma
• 0, 1, …, 9 sifre
• Fet skriftstrenger som id eller if, alt som representerer et enkelt terminalsymbol

2. Ikke-terminaler:

• Store bokstaver som A, B, C
• Navn med små bokstaver i kursiv: uttrykket eller noen

Kontekst gratis grammatikk

En CFG er en venstrerekursiv grammatikk som har minst én produksjon av typen. Reglene i en kontekstfri grammatikk er hovedsakelig rekursive. En syntaksanalysator sjekker at et bestemt program tilfredsstiller alle reglene for kontekstfri grammatikk eller ikke. Hvis den oppfyller, kan disse regelsyntaksanalysatorene lage et parse-tre for det programmet.

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

Grammatikkavledning

Grammatikkavledning er en sekvens av grammatikkregel som forvandler startsymbolet til strengen. En avledning beviser at strengen tilhører grammatikkens språk.

Avledning lengst til venstre

Når setningsformen for input skannes og erstattes i venstre til høyre rekkefølge, er det kjent som avledning lengst til venstre. Sentensformen som er avledet av avledningen lengst til venstre kalles venstre-setningsformen.

Avledning lengst til høyre

Avledning lengst til høyre skanner og erstatt inndataene med produksjonsregler, fra høyre til venstre, sekvens. Det er kjent som avledning lengst til høyre. Sentensformen som er avledet fra avledningen lengst til høyre er kjent som høyre-setningsformen.

Syntaks vs. Lexical Analyzer

Syntaksanalysator	Leksikalsk analysator
Syntaksanalysatoren omhandler hovedsakelig rekursive konstruksjoner av språket.	Den leksikalske analysatoren letter oppgaven til syntaksanalysatoren.
Syntaksanalysatoren fungerer på tokens i et kildeprogram for å gjenkjenne meningsfulle strukturer i programmeringsspråket.	Den leksikalske analysatoren gjenkjenner token i et kildeprogram.
Den mottar inndata, i form av tokens, fra leksikale analysatorer.	Den er ansvarlig for gyldigheten av et token levert av syntaksanalysatoren

Ulemper ved å bruke Syntax Analyzers

• Det vil aldri avgjøre om et token er gyldig eller ikke
• Not hjelper deg med å avgjøre om en operasjon utført på en tokentype er gyldig eller ikke
• Du kan ikke bestemme at token skal deklareres og initialiseres før det brukes

Sammendrag

• Syntaksanalyse er en andre fase av kompilatordesignprosessen som kommer etter leksikalsk analyse
• Den syntaktiske analysatoren hjelper deg å bruke regler på koden
• Setning, Lexeme, Token, Nøkkelord og reserverte ord, Støyord, Kommentarer, Avgrensningstegn, Tegnsett, Identifikatorer er noen viktige termer som brukes i syntaksanalysen i kompilatorkonstruksjon
• Parse sjekker at inndatastrengen er godt utformet, og hvis ikke, avviser den
• Parsingteknikker er delt inn i to forskjellige grupper: Top-Down Parsing, Bottom-Up Parsing
• Leksikalsk, syntaktisk, semantisk og logisk er noen vanlige feil som oppstår under analysemetoden
• En grammatikk er et sett med strukturelle regler som beskriver et språk
• Symbol for notasjonskonvensjoner kan angis ved å sette elementet i hakeparenteser
• En CFG er en venstrerekursiv grammatikk som har minst én produksjon av typen
• Grammatikkavledning er en sekvens av grammatikkregel som forvandler startsymbolet til strengen
• Syntaksanalysatoren omhandler hovedsakelig rekursive konstruksjoner av språket, mens den leksikalske analysatoren letter oppgaven til syntaksanalysatoren i DBMS
• Ulempen med Syntax-analysatormetoden er at den aldri vil avgjøre om et token er gyldig eller ikke