Syntaxanalys: Compiler Top Down & Bottom Up Parsingstyper

Syntaxanalys i kompilatordesignprocessen kommer efter den lexikaliska analysfasen. Det är också känt som Parse Tree eller Syntax Tree. Parse Tree är utvecklad med hjälp av fördefinierad grammatik för språket. Syntaxanalysatorn kontrollerar också om ett givet program uppfyller reglerna som antyds av en kontextfri grammatik. Om den uppfyller, skapar parsern sedan analysträdet för det källprogrammet. Annars kommer det att visa felmeddelanden.

Varför behöver du Syntax Analyser?

• Kontrollera om koden är grammatiskt giltig
• Den syntaktiska analysatorn hjälper dig att tillämpa regler på koden
• Hjälper dig att se till att varje öppningsstag har en motsvarande slutbalans
• Varje deklaration har en typ och att typen måste finnas

Viktig syntaxanalysatorterminologi

Viktiga terminologier som används i syntaxanalysprocesser:

• Mening: En mening är en grupp av tecken över något alfabet.

• Lexem: Ett lexem är den syntaktiska enheten på lägsta nivå i ett språk (t.ex. totalt, start).

• Token: En token är bara en kategori av lexem.

• Nyckelord och reserverade ord – Det är en identifierare som används som en fast del av syntaxen för en sats. Det är ett reserverat ord som du inte kan använda som variabelnamn eller identifierare.

• Buller ord – Brusord är valfria som infogas i ett uttalande för att förbättra meningens läsbarhet.

• Kommentarer – Det är en väldigt viktig del av dokumentationen. Det visas oftast med /* */, eller//Blank (mellanslag)

• avgränsare – Det är ett syntaktisk element som markerar början eller slutet av någon syntaktisk enhet. Som ett påstående eller uttryck, "börja"..."slut" eller {}.

• Teckenuppsättning – ASCII, Unicode

• Identifierare – Det är en begränsning av längden som hjälper dig att minska meningens läsbarhet.

• Operator symboler – + och – utför två grundläggande aritmetiska operationer.
• Syntaktiska delar av språket

Varför behöver vi Parsing?

En analys kontrollerar också att inmatningssträngen är välformad, och om inte, avvisa den.

Följande är viktiga uppgifter som utförs av parsern i kompilatordesign:

• Hjälper dig att upptäcka alla typer av syntaxfel
• Hitta den position där felet har inträffat
• Tydlig och korrekt beskrivning av felet.
• Återställning från ett fel för att fortsätta och hitta ytterligare fel i koden.
• Bör inte påverka kompileringen av "korrekta" program.
• Analysen måste avvisa ogiltiga texter genom att rapportera syntaxfel

Analystekniker

Analystekniker är indelade i två olika grupper:

• Top-down parsing,
• Bottom-Up Parsing

Top-Down Parsing

I parsningen uppifrån och ned börjar konstruktionen av parseträdet vid roten och fortsätter sedan mot löven.

Två typer av top-down-analys är:

1. Prediktiv analys:

Predictive parse kan förutsäga vilken produktion som ska användas för att ersätta den specifika indatasträngen. Den prediktiva parsern använder blick framåt-punkt, som pekar mot nästa inmatningssymboler. Backtracking är inte ett problem med denna analysteknik. Den är känd som LL(1) Parser

2. Rekursiv nedstigningsanalys:

Denna analysteknik analyserar indata rekursivt för att skapa ett praseträd. Den består av flera små funktioner, en för varje icke-terminal i grammatiken.

Bottom-Up Parsing

I parsningen underifrån och upp i kompilatordesign börjar konstruktionen av parseträdet med bladet och sedan bearbetar det mot sin rot. Det kallas också för shift-reduce parsing. Denna typ av parsning i kompilatordesign skapas med hjälp av några programverktyg.

Fel – Återställningsmetoder

Vanliga fel som uppstår vid analys i systemprogramvara

• Lexikalisk: Namn på en felaktigt skriven identifierare
• Syntaktisk: obalanserad parentes eller ett semikolon som saknas
• Semantisk: inkompatibel värdetilldelning
• logisk: Oändlig slinga och oåtkomlig kod

En parser ska kunna upptäcka och rapportera alla fel som hittas i programmet. Så, närhelst ett fel inträffade, tolken. Den borde kunna hantera det och fortsätta att analysera den återstående inmatningen. Ett program kan ha följande typer av fel vid olika kompileringsprocesser. Det finns fem vanliga felåterställningsmetoder som kan implementeras i parsern

Återställning av utlåtandeläge

• I de fall då parsern stöter på ett fel, hjälper det dig att vidta korrigerande åtgärder. Detta tillåter resten av ingångar och tillstånd att analysera framåt.
• Till exempel, att lägga till ett saknat semikolon kommer i återställningsmetoden för statement mode. Emellertid måste analysdesignern vara försiktig när du gör dessa ändringar eftersom en felaktig korrigering kan leda till en oändlig loop.

Återställning av panikläge

• I fallet när parsern stöter på ett fel, ignorerar detta läge resten av satsen och bearbetar inte indata från felaktig inmatning till avgränsare, som ett semikolon. Detta är en enkel felåterställningsmetod.
• I denna typ av återställningsmetod avvisar tolken inmatningssymboler en efter en tills en enda utsedd grupp av synkroniseringstokens hittas. Synkroniseringssymbolerna använder vanligtvis avgränsare som eller.

Återställning på frasnivå

• Kompilatorn korrigerar programmet genom att infoga eller ta bort tokens. Detta gör att den kan fortsätta att analysera från var den var. Den utför korrigering av den återstående ingången. Det kan ersätta ett prefix för den återstående inmatningen med någon sträng, vilket hjälper parsern att fortsätta processen.

Felproduktioner

• Återställning av felproduktion utökar grammatiken för språket som genererar de felaktiga konstruktionerna. Parsern utför sedan feldiagnostik om den konstruktionen.

Global korrigering

• Kompilatorn bör göra färre antal ändringar som möjligt under bearbetning av en felaktig inmatningssträng. Givet felaktig inmatningssträng a och grammatik c, kommer algoritmer att söka efter ett analysträd för en relaterad sträng b. Liksom vissa infogningar, raderingar och modifieringar gjorda av tokens som behövs för att omvandla an till b är så lite som möjligt.

Grammatik

En grammatik är en uppsättning strukturella regler som beskriver ett språk. Grammatik tilldelar struktur till vilken mening som helst. Denna term hänvisar också till studiet av dessa regler, och den här filen inkluderar morfologi, fonologi och syntax. Det är kapabelt att beskriva många, av syntaxen för programmeringsspråk.

Formregler grammatik

• Den icke-terminala symbolen ska visas till vänster om minst en produktion
• Målsymbolen ska aldrig visas till höger om::= för någon produktion
• En regel är rekursiv om LHS förekommer i dess RHS

Notationskonventioner

Symbol för notationskonventioner kan indikeras genom att elementet omges av hakparenteser. Det är en godtycklig sekvens av instanser av elementet som kan indikeras genom att omsluta elementet med klammerparenteser följt av en asterisksymbol, { … }*.

Det är ett val av alternativet som kan använda symbolen inom den enda regeln. Den kan omges av parentes ([,] ) vid behov.

Två typer av notationskonventioner området Terminal och Non-terminals

1. Terminaler:

• Små bokstäver i alfabetet som a, b, c,
• Operator-symboler som +,-, * osv.
• Skiljetecken som parenteser, hash, kommatecken
• 0, 1, …, 9 siffror
• Fet strängar som id eller if, allt som representerar en enda terminalsymbol

2. Icke-terminaler:

• Versaler som A, B, C
• Kursiva namn med små bokstäver: uttrycket eller några

Sammanhang gratis grammatik

En CFG är en vänsterrekursiv grammatik som har minst en produktion av denna typ. Reglerna i en kontextfri grammatik är huvudsakligen rekursiva. En syntaxanalysator kontrollerar att ett specifikt program uppfyller alla regler för kontextfri grammatik eller inte. Om den uppfyller, kan dessa regelsyntaxanalysatorer skapa ett analysträd för det programmet.

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

Grammatikavledning

Grammatikavledning är en sekvens av grammatikregel som omvandlar startsymbolen till strängen. En härledning bevisar att strängen tillhör grammatikens språk.

Härledning längst till vänster

När meningsformen av inmatning skannas och ersätts i sekvens från vänster till höger, kallas det för avledning längst till vänster. Den meningsform som härleds av härledningen längst till vänster kallas för den vänstra meningsformen.

Härledning längst till höger

Härledning längst till höger skannar och ersätt indata med produktionsregler, från höger till vänster, sekvens. Det är känt som härledning längst till höger. Den meningsform som är härledd från den högra härledningen är känd som höger-sententialform.

Syntax vs. Lexical Analyzer

Syntaxanalysator	Lexical Analyzer
Syntaxanalysatorn sysslar främst med rekursiva konstruktioner av språket.	Den lexikaliska analysatorn underlättar syntaxanalysatorns uppgift.
Syntaxanalysatorn arbetar på tokens i ett källprogram för att känna igen meningsfulla strukturer i programmeringsspråket.	Den lexikaliska analysatorn känner igen token i ett källprogram.
Den tar emot indata, i form av tokens, från lexikalanalysatorer.	Den ansvarar för giltigheten av en token som tillhandahålls av syntaxanalysatorn

Nackdelar med att använda Syntax Analyzers

• Det kommer aldrig att avgöra om en token är giltig eller inte
• Not hjälper dig att avgöra om en operation utförd på en tokentyp är giltig eller inte
• Du kan inte bestämma att token ska deklareras och initieras innan den används

Sammanfattning

• Syntaxanalys är en andra fas av kompilatordesignprocessen som kommer efter lexikal analys
• Den syntaktiska analysatorn hjälper dig att tillämpa regler på koden
• Mening, Lexeme, Token, Nyckelord och reserverade ord, Brusord, Kommentarer, Avgränsare, Teckenuppsättning, Identifierare är några viktiga termer som används i Syntax Analysis i kompilatorkonstruktionen
• Parse kontrollerar att inmatningssträngen är välformad, och om inte, avvisa den
• Parsingtekniker är indelade i två olika grupper: Top-Down Parsing, Bottom-Up Parsing
• Lexikal, syntaktisk, semantisk och logisk är några vanliga fel som uppstår under analysmetoden
• En grammatik är en uppsättning strukturella regler som beskriver ett språk
• Symbol för notationskonventioner kan indikeras genom att elementet omges av hakparenteser
• En CFG är en vänsterrekursiv grammatik som har minst en produktion av denna typ
• Grammatikavledning är en sekvens av grammatikregel som omvandlar startsymbolen till strängen
• Syntaxanalysatorn behandlar huvudsakligen rekursiva konstruktioner av språket medan den lexikaliska analysatorn underlättar syntaxanalysatorns uppgift i DBMS
• Nackdelen med Syntax analysatormetoden är att den aldrig kommer att avgöra om en token är giltig eller inte