Analýza syntaxe: Typy analýzy kompilátoru shora dolů a zdola nahoru

Analýza syntaxe v procesu návrhu kompilátoru následuje po fázi lexikální analýzy. Je také známý jako Parse Tree nebo Syntax Tree. Parse Tree je vyvinut s pomocí předem definované gramatiky jazyka. Analyzátor syntaxe také kontroluje, zda daný program splňuje pravidla vyplývající z bezkontextové gramatiky. Pokud vyhovuje, analyzátor poté vytvoří strom analýzy tohoto zdrojového programu. V opačném případě zobrazí chybové zprávy.

Proč potřebujete Syntax Analyser?

• Zkontrolujte, zda je kód gramaticky platný
• Syntaktický analyzátor vám pomůže aplikovat pravidla na kód
• Pomáhá vám zajistit, aby každá otevírací závorka měla odpovídající konečný zůstatek
• Každá deklarace má svůj typ a tento typ musí existovat

Důležitá terminologie analyzátoru syntaxe

Důležité terminologie používané v procesu syntaktické analýzy:

• Věta: Věta je skupina znaků v nějaké abecedě.

• lexeme: Lexém je syntaktická jednotka jazyka na nejnižší úrovni (např. total, start).

• Token: Token je jen kategorie lexémů.

• Klíčová slova a vyhrazená slova – Je to identifikátor, který se používá jako pevná součást syntaxe příkazu. Je to vyhrazené slovo, které nemůžete použít jako název proměnné nebo identifikátor.

• Hluková slova – Hlučná slova jsou nepovinná a vkládají se do prohlášení, aby se zlepšila čitelnost věty.

• Komentáře – Je to velmi důležitá součást dokumentace. Většinou se zobrazuje pomocí, /* */ nebo//Prázdné (mezery)

• Oddělovače – Je to syntaktický prvek, který označuje začátek nebo konec nějaké syntaktické jednotky. Jako příkaz nebo výraz „začátek“…“konec“ nebo {}.

• Znaková sada – ASCII, Unicode

• Identifikátory – Je to omezení délky, které vám pomáhá snížit čitelnost věty.

• Operator symboly – + a – provádí dvě základní aritmetické operace.
• Syntaktické prvky jazyka

Proč potřebujeme analýzu?

Analýza také zkontroluje, zda je vstupní řetězec správně naformátován, a pokud ne, odmítne jej.

Níže jsou uvedeny důležité úkoly, které analyzátor provádí při návrhu kompilátoru:

• Pomáhá odhalit všechny typy syntaktických chyb
• Najděte pozici, na které došlo k chybě
• Jasný a přesný popis chyby.
• Obnovení z chyby, abyste mohli pokračovat a najít další chyby v kódu.
• Nemělo by to mít vliv na kompilaci „správných“ programů.
• Analýza musí odmítnout neplatné texty nahlášením syntaktických chyb

Techniky analýzy

Techniky analýzy se dělí do dvou různých skupin:

• Analýza shora dolů,
• Analýza zdola nahoru

Analýza shora dolů

Při analýze shora dolů konstrukce stromu analýzy začíná u kořene a poté pokračuje směrem k listům.

Dva typy analýzy shora dolů jsou:

1. Prediktivní analýza:

Prediktivní analýza může předpovědět, která produkce by měla být použita k nahrazení konkrétního vstupního řetězce. Prediktivní analyzátor používá dopředný bod, který ukazuje na další vstupní symboly. Zpětné sledování není u této techniky analýzy problém. Je známý jako LL(1) Parser

2. Rekurzivní sestupová analýza:

Tato technika analýzy rekurzivně analyzuje vstup za účelem vytvoření stromu prase. Skládá se z několika malých funkcí, jedna pro každý neterminál v gramatice.

Analýza zdola nahoru

Při analýze zdola nahoru v návrhu kompilátoru začíná konstrukce stromu analýzy listem a poté se zpracovává směrem ke kořeni. Nazývá se také jako syntaktická analýza s redukcí posunu. Tento typ analýzy v designu kompilátoru je vytvořen pomocí použití některých softwarové nástroje.

Chyba – metody obnovy

Běžné chyby, ke kterým dochází při analýze v systémovém softwaru

• Lexikální: Název nesprávně zadaného identifikátoru
• Syntaktické: nevyvážená závorka nebo chybějící středník
• Sémantický: nekompatibilní přiřazení hodnoty
• logický: Nekonečná smyčka a nedosažitelný kód

Analyzátor by měl být schopen detekovat a nahlásit jakoukoli chybu nalezenou v programu. Takže kdykoli došlo k chybě, analyzátor. Mělo by to zvládnout a pokračovat v analýze zbývajícího vstupu. Program může mít následující typy chyb v různých fázích procesu kompilace. Existuje pět běžných metod obnovy chyb, které lze implementovat v analyzátoru

Obnova režimu výpisu

• V případě, že parser narazí na chybu, pomůže vám podniknout nápravné kroky. To umožňuje zbývajícím vstupům a stavům analyzovat dopředu.
• Například přidání chybějícího středníku přichází v metodě obnovení příkazového režimu. Návrhář analýzy však musí být při provádění těchto změn opatrný, protože jedna špatná oprava může vést k nekonečné smyčce.

Obnova v panickém režimu

• V případě, že analyzátor narazí na chybu, tento režim ignoruje zbytek příkazu a nezpracuje vstup z chybného vstupu do oddělovače, jako je středník. Jedná se o jednoduchou metodu obnovy chyb.
• V tomto typu metody obnovy analyzátor odmítá vstupní symboly jeden po druhém, dokud není nalezena jediná určená skupina synchronizačních tokenů. Synchronizační tokeny obecně používají oddělovače jako nebo.

Obnova na úrovni fráze

• Kompilátor opraví program vložením nebo odstraněním tokenů. To mu umožňuje pokračovat v analýze z místa, kde byl. Provede korekci na zbývajícím vstupu. Může nahradit předponu zbývajícího vstupu nějakým řetězcem, což pomůže analyzátoru pokračovat v procesu.

Error Productions

• Obnova produkce chyb rozšiřuje gramatiku jazyka, který generuje chybné konstrukce. Analyzátor pak provede diagnostiku chyb této konstrukce.

Globální korekce

• Kompilátor by měl při zpracování nesprávného vstupního řetězce provádět co nejmenší počet změn. Při nesprávném vstupním řetězci a a gramatice c budou algoritmy hledat strom analýzy pro související řetězec b. Stejně jako některé vkládání, mazání a modifikace tokenů potřebných k transformaci a na b je co nejmenší.

Gramatika

Gramatika je soubor strukturálních pravidel, která popisují jazyk. Gramatiky přiřazují strukturu libovolné větě. Tento termín také odkazuje na studium těchto pravidel a tento soubor zahrnuje morfologii, fonologii a syntaxi. Je schopen popsat mnoho ze syntaxe programovací jazyky.

Pravidla formální gramatiky

• Nekoncový symbol by se měl objevit nalevo od alespoň jedné produkce
• Symbol cíle by nikdy neměl být zobrazen napravo od::= žádné produkce
• Pravidlo je rekurzivní, pokud se v jeho RHS objeví LHS

Notační konvence

Symbol notačních konvencí může být označen tak, že prvek uzavřete do hranatých závorek. Je to libovolná posloupnost instancí prvku, kterou lze označit uzavřením prvku do složených závorek následovaných symbolem hvězdičky, { … }*.

Je to volba alternativy, která může používat symbol v rámci jediného pravidla. V případě potřeby jej lze uzavřít do závorek ([,] ).

Dva typy notačních konvencí: Terminál a Neterminál

1. Terminály:

• Malá písmena v abecedě jako a, b, c,
• Operator symboly jako +,-, * atd.
• Interpunkční znaky, jako jsou závorky, křížek, čárka
• 0, 1, …, 9 číslic
• Řetězce s tučným písmem jako id nebo if, cokoli, co představuje jeden symbol terminálu

2. Neterminály:

• Velká písmena jako A, B, C
• Názvy s malými písmeny kurzívou: výraz nebo něco

Bezkontextová gramatika

CFG je levá rekurzivní gramatika, která má alespoň jednu produkci tohoto typu. Pravidla v bezkontextové gramatice jsou převážně rekurzivní. Syntaktický analyzátor kontroluje, zda konkrétní program splňuje všechna pravidla bezkontextové gramatiky nebo ne. Pokud to splňuje, analyzátory syntaxe těchto pravidel mohou pro tento program vytvořit strom analýzy.

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

Odvozování gramatiky

Odvozování gramatiky je posloupnost gramatických pravidel, která transformuje počáteční symbol na řetězec. Odvození dokazuje, že řetězec patří do jazyka gramatiky.

Odvození nejvíce vlevo

Když je větná forma vstupu naskenována a nahrazena v pořadí zleva doprava, nazývá se derivace nejvíce vlevo. Větná forma, která je odvozena derivací nejvíce vlevo, se nazývá levá větná forma.

Odvození nejvíce vpravo

Skenování derivace úplně vpravo a nahrazení vstupu produkčními pravidly, zprava doleva, sekvence. Je známá jako nejpravější derivace. Větná forma, která je odvozena od odvození nejvíce vpravo, je známá jako pravá větná forma.

Syntax vs. Lexikální analyzátor

Syntaktický analyzátor	Lexikální analyzátor
Syntaktický analyzátor se zabývá především rekurzivními konstrukcemi jazyka.	Lexikální analyzátor usnadňuje práci syntaktického analyzátoru.
Analyzátor syntaxe pracuje na tokenech ve zdrojovém programu, aby rozpoznával smysluplné struktury v programovacím jazyce.	Lexikální analyzátor rozpozná token ve zdrojovém programu.
Přijímá vstupy ve formě tokenů od lexikálních analyzátorů.	Je odpovědný za platnost tokenu dodaného společností analyzátor syntaxe

Nevýhody použití analyzátorů syntaxe

• Nikdy nezjistí, zda je token platný nebo ne
• Not vám pomůže určit, zda je operace provedená s typem tokenu platná nebo ne
• Nemůžete se rozhodnout, že token bude deklarován a inicializován před jeho použitím

Shrnutí

• Syntaktická analýza je druhou fází procesu návrhu kompilátoru, který následuje po lexikální analýze
• Syntaktický analyzátor vám pomůže aplikovat pravidla na kód
• Věta, lexém, token, klíčová slova a vyhrazená slova, šumová slova, komentáře, oddělovače, znaková sada, identifikátory jsou některé důležité termíny používané při syntaktické analýze v konstrukci kompilátoru
• Parse zkontroluje, zda je vstupní řetězec správně naformátován, a pokud ne, odmítne jej
• Techniky analýzy se dělí do dvou různých skupin: analýza shora dolů, analýza zdola nahoru
• Lexikální, syntaktické, sémantické a logické jsou některé běžné chyby, ke kterým dochází během metody analýzy
• Gramatika je soubor strukturálních pravidel, která popisují jazyk
• Symbol notačních konvencí může být označen tak, že prvek uzavřete do hranatých závorek
• CFG je levá rekurzivní gramatika, která má alespoň jednu produkci tohoto typu
• Odvozování gramatiky je posloupnost gramatických pravidel, která transformuje počáteční symbol na řetězec
• Syntaktický analyzátor se zabývá především rekurzivními konstrukcemi jazyka, zatímco lexikální analyzátor usnadňuje práci analyzátoru syntaxe v DBMS
• Nevýhodou metody analyzátoru syntaxe je, že nikdy nezjistí, zda je token platný nebo ne