Co je to syntaxová analýza?
Syntaxová analýza je druhou fází procesu návrhu kompilátoru, ve kterém je u daného vstupního řetězce zkontrolováno potvrzení pravidel a struktury formální gramatiky. Analyzuje syntaktickou strukturu a kontroluje, zda je daný vstup ve správné syntaxi programovacího jazyka nebo ne.
Syntaxová analýza v procesu návrhu kompilátoru přichází po fázi lexikální analýzy. Je také známý jako Parse Tree nebo Syntax Tree. Parse Tree je vyvinut pomocí předem definované gramatiky jazyka. Analyzátor syntaxe také kontroluje, zda daný program splňuje pravidla implikovaná bezkontextovou gramatikou. Pokud to vyhovuje, syntaktický analyzátor poté vytvoří strom syntaktické analýzy tohoto zdrojového programu. Jinak zobrazí chybové zprávy.
V tomto výukovém programu se naučíte
- Proč potřebujete Syntax Analyzer?
- Důležitá terminologie analyzátoru syntaxe
- Proč potřebujeme analýzu?
- Techniky analýzy
- Chyba - metody obnovy
- Gramatika:
- Notační konvence
- Bezkontextová gramatika
- Odvození gramatiky
- Syntaxe vs. Lexikální analyzátor
- Nevýhody používání syntaxových analyzátorů
Proč potřebujete Syntax Analyzer?
- Zkontrolujte, zda je kód platný gramaticky
- Syntaktický analyzátor vám pomůže aplikovat pravidla na kód
- Pomůže vám zajistit, aby každá otevírací závorka měla odpovídající závěrečnou rovnováhu
- Každá deklarace má typ a ten 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ů nad nějakou abecedou.
- Lexéma: Lexemie je syntaktická jednotka jazyka na nejnižší úrovni (např. Celkem, začátek).
- Token: Token je jen kategorie lexémů.
- Klíčová slova a vyhrazená slova - Jedná se o 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.
- Šumová slova - Šumová slova jsou volitelná, která se vkládají do příkazu, aby se zvýšila čitelnost věty.
- Komentáře - Je to velmi důležitá součást dokumentace. Zobrazuje se většinou pomocí, / * * / nebo // mezer
- Oddělovače - Jedná se o syntaktický prvek, který označuje začátek nebo konec nějaké syntaktické jednotky. Jako výrok nebo výraz „začátek“… „konec“ nebo {}.
- Znaková sada - ASCII, Unicode
- Identifikátory - Jedná se o omezení délky, které vám pomůže snížit čitelnost věty.
- Operátorské 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ě vytvořen, a pokud ne, odmítněte jej.
Následují důležité úkoly prováděné analyzátorem v návrhu kompilátoru:
- Pomáhá vám detekovat všechny typy chyb syntaxe
- Najděte pozici, ve které došlo k chybě
- Jasný a přesný popis chyby.
- Obnova po chybě bude pokračovat a najdete další chyby v kódu.
- Nemělo by to ovlivnit kompilaci „správných“ programů.
- Analýza musí odmítnout neplatné texty hlášením syntaktických chyb
Techniky analýzy
Techniky analýzy jsou rozděleny do dvou různých skupin:
- Parsování shora dolů,
- Analýza zdola nahoru
Parsování shora dolů:
V sestupné konstrukci syntaktické analýzy stromu syntézy začíná u kořene a poté pokračuje směrem k listům.
Dva typy analýzy shora dolů jsou:
- 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í syntaktický analyzátor používá výhledový bod, který ukazuje na další vstupní symboly. Backtracking není problém s touto technikou analýzy. Je známý jako analyzátor LL (1)
- Rekurzivní analýza sestupu:
Tato technika syntaktické analýzy rekurzivně analyzuje vstup, aby vytvořil prase strom. Skládá se z několika malých funkcí, jedna pro každého neterminálu v gramatice.
Analýza zdola nahoru:
Při analýze zdola nahoru v návrhu kompilátoru začíná konstrukce parsovacího stromu s dovolenou a poté se zpracovává směrem ke svému kořenu. Nazývá se také syntaktická analýza snižující posun. Tento typ analýzy v návrhu kompilátoru je vytvořen pomocí některých softwarových nástrojů.
Chyba - metody obnovy
Časté 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 hlásit všechny chyby nalezené v programu. Analyzátor tedy kdykoli došlo k chybě. Mělo by to zvládnout a pokračovat v analýze zbývajícího vstupu. Program může mít v různých fázích procesu kompilace následující typy chyb. V analyzátoru lze implementovat pět běžných metod obnovy chyb
Obnova režimu výpisu
- V případě, že analyzátor narazí na chybu, pomůže vám provést nápravná opatření. To umožňuje zbytek vstupů a stavů analyzovat dopředu.
- Například přidání chybějícího středníku je v metodě obnovení režimu výpisu. Návrhář syntaktické analýzy však musí být při provádění těchto změn opatrný, protože jedna nesprávná korekce 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 nezpracovává vstup z chybného vstupu do oddělovače, jako středník. Toto je jednoduchá metoda obnovy chyby.
- V tomto typu metody obnovy analyzátor odmítá vstupní symboly jeden po druhém, dokud není nalezena jedna určená skupina synchronizačních tokenů. Synchronizační tokeny obvykle 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 zbývajícího vstupu. Může nahradit předponu zbývajícího vstupu nějakým řetězcem, což pomáhá analyzátoru pokračovat v procesu.
Produkce chyb
- Obnova výroby po chybě rozšíří gramatiku jazyka, který generuje chybné konstrukce. Analyzátor poté provede diagnostiku chyb o této konstrukci.
Globální korekce:
- Kompilátor by měl při zpracování nesprávného vstupního řetězce provést co největší počet změn. Vzhledem k nesprávnému vstupnímu řetězci a a gramatice c budou algoritmy hledat analyzovaný strom pro související řetězec b. Stejně jako některá vložení, odstranění a úpravy z tokenů potřebných k transformaci an na b jsou co nejmenší.
Gramatika:
Gramatika je soubor strukturálních pravidel popisujících jazyk. Gramatiky přiřazují strukturu jakékoli větě. Tento termín také odkazuje na studium těchto pravidel a tento soubor obsahuje morfologii, fonologii a syntaxi. Je schopen popsat mnoho syntaxe programovacích jazyků.
Pravidla formální gramatiky
- Symbol neterminálu by se měl objevit nalevo od alespoň jedné produkce
- Symbol cíle by se nikdy neměl zobrazovat napravo od :: = jakékoli produkce
- Pravidlo je rekurzivní, pokud se v jeho RHS objeví LHS
Notační konvence
Symbol notační konvence lze označit uzavřením prvku do hranatých závorek. Jedná se o libovolnou posloupnost instancí prvku, kterou lze označit uzavřením prvku do složených závorek, za kterým následuje symbol hvězdičky, {…} *.
Jedná se o výběr alternativy, která může používat symbol v rámci jediného pravidla. V případě potřeby může být uzavřeno v závorkách ([,]).
Dva typy oblasti konvence notace Terminál a Non-terminály
1. Terminály:
- Malá písmena v abecedě, například a, b, c,
- Symboly operátora, jako +, -, * atd.
- Interpunkční symboly, jako jsou závorky, hash, čárka
- 0, 1,…, 9 číslic
- Odvážné řetězce jako id nebo if, cokoli, co představuje jeden symbol terminálu
2. Terminál:
- Velká písmena jako A, B, C
- Názvy malých kurzív: výraz nebo některé
Bezkontextová gramatika
CFG je levo rekurzivní gramatika, která má alespoň jednu produkci tohoto typu. Pravidla v bezkontextové gramatice jsou hlavně rekurzivní. Analyzátor syntaxe kontroluje, zda konkrétní program splňuje všechna pravidla bezkontextové gramatiky. Pokud to splní, mohou analyzátory syntaxe těchto pravidel vytvořit pro tento program syntaktický strom.
expression -> expression -+ termexpression -> expression - termexpression-> termterm -> term * factorterm -> expression/ factorterm -> factor factorfactor -> ( expression )factor -> id
Odvození gramatiky
Odvození gramatiky je posloupnost gramatického pravidla, které transformuje počáteční symbol na řetězec. Odvození dokazuje, že řetězec patří do jazyka gramatiky.
Odvození nejvíce vlevo
Když je sentenciální forma vstupu naskenována a nahrazena v pořadí zleva doprava, je známá jako derivace zleva. Senciální formulář, který je odvozen derivací nejvíce vlevo, se nazývá levý sentenciální formulář.
Odvození nejvíce vpravo
Skenování derivace zcela vpravo a nahraďte vstup produkčními pravidly, zprava doleva, sekvence. Je známá jako pravá derivace. Senciální forma, která je odvozena z derivace zcela vpravo, se nazývá pravostranná forma.
Syntaxe vs. Lexikální analyzátor
|
Analyzátor syntaxe |
Lexikální analyzátor |
|
Analyzátor syntaxe se zabývá hlavně 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 rozpoznal 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žívání syntaxových analyzátorů
- Nikdy nezjistí, zda je token platný nebo ne
- Nepomůže vám určit, zda je operace prováděná na typu tokenu platná nebo ne
- Nemůžete se rozhodnout, že token je deklarován a inicializován před jeho použitím
souhrn
- Syntaxová 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éma, token, klíčová slova a vyhrazená slova, šumová slova, komentáře, oddělovače, znaková sada, identifikátory jsou některé důležité pojmy používané při analýze syntaxe v konstrukci překladače
- Parse zkontroluje, zda je vstupní řetězec správně vytvořen, a pokud ne, odmítněte jej
- Techniky syntaktické analýzy jsou rozděleny do dvou různých skupin: Parsování shora dolů, Parsování 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 popisujících jazyk
- Symbol notační konvence lze označit uzavřením prvku do hranatých závorek
- CFG je levo-rekurzivní gramatika, která má alespoň jednu produkci typu
- Odvození gramatiky je posloupnost gramatického pravidla, které transformuje počáteční symbol na řetězec
- Analyzátor syntaxe se zabývá hlavně rekurzivními konstrukcemi jazyka, zatímco lexikální analyzátor usnadňuje úlohu syntaktického analyzátoru v DBMS
- Nevýhodou metody Syntax analyzer je, že nikdy nezjistí, zda je token platný nebo ne