Анализ на синтаксиса: Типове разбор на компилатор отгоре надолу и отдолу нагоре

Синтаксисният анализ в процеса на проектиране на компилатора идва след фазата на лексикалния анализ. Известно е още като Дърво на синтактичен анализ или Синтаксисно дърво. Parse Tree е разработено с помощта на предварително дефинирана граматика на езика. Синтаксисният анализатор също проверява дали дадена програма изпълнява правилата, подразбиращи се от контекстно-свободна граматика. Ако удовлетворява, анализаторът създава дърво за анализ на тази изходна програма. В противен случай ще покаже съобщения за грешка.

Защо ви е необходим синтактичен анализатор?

• Проверете дали кодът е валиден граматически
• Синтактичният анализатор ви помага да прилагате правила към кода
• Помага ви да се уверите, че всяка отваряща скоба има съответен затварящ баланс
• Всяка декларация има тип и този тип трябва да съществува

Важна терминология на синтактичния анализатор

Важни терминологии, използвани в процеса на анализ на синтаксиса:

• Присъда: Изречение е група от знаци над някаква азбука.

• Лексема: Лексемата е синтактична единица от най-ниско ниво на език (напр. общо, начало).

• Token: Лексемата е просто категория лексеми.

• Ключови думи и запазени думи – Това е идентификатор, който се използва като фиксирана част от синтаксиса на израз. Това е запазена дума, която не можете да използвате като име на променлива или идентификатор.

• Шумни думи – Шумните думи са незадължителни, които се вмъкват в изявление, за да се подобри четливостта на изречението.

• Коментари – Това е много важна част от документацията. Показва се предимно чрез /* */ или//Празно (интервали)

• Разделители – Това е синтактичен елемент, който маркира началото или края на някаква синтактична единица. Подобно на изявление или израз, "начало"..."край" или {}.

• Набор символи – ASCII, Unicode

• Идентификатори – Това е ограничение на дължината, което ви помага да намалите четливостта на изречението.

• Operaтор символи – + и – изпълнява две основни аритметични операции.
• Синтактични елементи на езика

Защо се нуждаем от анализ?

Анализът също така проверява дали входният низ е добре оформен и ако не е, го отхвърля.

Следват важни задачи, изпълнявани от анализатора при проектирането на компилатора:

• Помага ви да откриете всички видове синтактични грешки
• Намерете позицията, в която е възникнала грешка
• Ясно и точно описание на грешката.
• Възстановяване от грешка, за да продължите и да намерите допълнителни грешки в кода.
• Не трябва да засяга компилирането на „правилни“ програми.
• Анализът трябва да отхвърля невалидни текстове чрез докладване на синтактични грешки

Техники за анализиране

Техниките за разбор се разделят на две различни групи:

• Разбор отгоре надолу,
• Разбор отдолу нагоре

Разбор отгоре надолу

При конструкцията за анализ отгоре надолу на дървото за анализ започва от корена и след това продължава към листата.

Два вида анализ отгоре надолу са:

1. Предсказуем анализ:

Предсказуемият анализ може да предвиди коя продукция трябва да се използва за замяна на конкретния входен низ. Предсказуемият анализатор използва точка за гледане напред, която сочи към следващите входни символи. Обратното проследяване не е проблем с тази техника за анализ. Известен е като LL(1) Parser

2. Рекурсивен анализ на спускане:

Тази техника за синтактичен анализ рекурсивно анализира входа, за да създаде дърво на молитви. Състои се от няколко малки функции, по една за всеки нетерминал в граматиката.

Разбор отдолу нагоре

При синтактичния анализ отдолу нагоре в дизайна на компилатора, конструкцията на дървото за синтактичен анализ започва с оставянето и след това се обработва към своя корен. Нарича се също като синтактичен разбор на shift-reduce. Този тип разбор в дизайна на компилатора се създава с помощта на някои софтуерни инструменти.

Грешка – Методи за възстановяване

Често срещани грешки, възникващи при анализиране в системния софтуер

• Лексикален: Име на неправилно въведен идентификатор
• Синтактичен: небалансирани скоби или липсваща точка и запетая
• Семантичен: несъвместимо присвояване на стойност
• логичен: Безкраен цикъл и недостъпен код

Анализаторът трябва да може да открива и докладва всяка открита грешка в програмата. Така че, когато възникне грешка, анализаторът. Трябва да може да се справи с него и да продължи анализирането на оставащия вход. Една програма може да има следните видове грешки на различни етапи от процеса на компилиране. Има пет общи метода за възстановяване на грешки, които могат да бъдат внедрени в анализатора

Възстановяване на режим на изявление

• В случай, че анализаторът срещне грешка, той ви помага да предприемете коригиращи стъпки. Това позволява останалите входове и състояния да се анализират напред.
• Например добавянето на липсваща точка и запетая идва в метода за възстановяване в режим на израз. Въпреки това дизайнерът на анализ трябва да бъде внимателен, докато прави тези промени, тъй като една грешна корекция може да доведе до безкраен цикъл.

Възстановяване в паник режим

• В случай, че синтактичният анализатор срещне грешка, този режим игнорира останалата част от израза и не обработва вход от грешен вход към разделител, като точка и запетая. Това е прост метод за възстановяване на грешки.
• При този тип метод за възстановяване анализаторът отхвърля входните символи един по един, докато бъде намерена една определена група от синхронизиращи токени. Синхронизиращите токени обикновено използват разделители като или.

Възстановяване на ниво фраза

• Компилаторът коригира програмата чрез вмъкване или изтриване на токени. Това му позволява да продължи да анализира от мястото, където е било. Той извършва корекция на оставащия вход. Той може да замени префикс на оставащия вход с някакъв низ, което помага на анализатора да продължи процеса.

Продукции на грешки

• Възстановяването при производство на грешки разширява граматиката за езика, който генерира грешните конструкции. След това анализаторът извършва диагностика на грешки относно тази конструкция.

Глобална корекция

• Компилаторът трябва да прави възможно най-малко промени, докато обработва неправилен входен низ. Като се има предвид неправилен входен низ a и граматика c, алгоритмите ще търсят дърво за анализ на свързан низ b. Като някои вмъквания, изтривания и модификации, направени от токени, необходими за трансформиране на an в b, са възможно най-малко.

граматика

Граматиката е набор от структурни правила, които описват език. Граматиките придават структура на всяко изречение. Този термин също се отнася до изучаването на тези правила и този файл включва морфология, фонология и синтаксис. Той е в състояние да опише много от синтаксиса на програмни езици.

Правила на граматиката на формата

• Символът за нетерминал трябва да се появи отляво на поне една продукция
• Символът за гол никога не трябва да се показва отдясно на ::= на която и да е продукция
• Правилото е рекурсивно, ако LHS се появява в неговия RHS

Нотационни конвенции

Символът за условни обозначения може да бъде обозначен чрез ограждане на елемента в квадратни скоби. Това е произволна последователност от екземпляри на елемента, която може да бъде обозначена чрез ограждане на елемента в скоби, последвани от символ звездичка, { … }*.

Това е избор на алтернатива, която може да използва символа в рамките на едно правило. Може да бъде ограден със скоби ([,] ), когато е необходимо.

Два типа нотационни конвенции в областта Терминални и Нетерминални

1. Терминали:

• Малки букви в азбуката като a, b, c,
• Operaили символи като +,-, * и др.
• Препинателни знаци като скоби, решетка, запетая
• 0, 1, …, 9 цифри
• Удебелени низове като id или if, всичко, което представлява един символ на терминала

2. Нетерминали:

• Главни букви като A, B, C
• Имена с малки букви в курсив: изразът или някои

Безконтекстна граматика

CFG е ляво-рекурсивна граматика, която има поне една продукция от типа. Правилата в безконтекстната граматика са предимно рекурсивни. Синтаксисен анализатор проверява дали конкретна програма отговаря на всички правила на граматиката без контекст или не. Ако отговаря, тези анализатори на синтаксиса на правилата могат да създадат дърво за анализ на тази програма.

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

Извеждане на граматика

Извеждането на граматика е последователност от граматично правило, което трансформира началния символ в низа. Изводът доказва, че низът принадлежи към езика на граматиката.

Най-ляво извеждане

Когато изреченската форма на въвеждане се сканира и заменя в последователност отляво надясно, това е известно като най-ляво извеждане. Изреченската форма, която е получена от най-лявата деривация, се нарича ляво-изреченска форма.

Най-дясно извеждане

Сканиране на най-дясното извличане и заместване на входа с производствени правила, отдясно наляво, последователност. Известно е като най-дясно извеждане. Изреченската форма, която се извлича от най-дясната деривация, е известна като дясно изреченска форма.

Синтаксис срещу лексикален анализатор

Синтаксисен анализатор	Лексикален анализатор
Синтаксисният анализатор се занимава основно с рекурсивни конструкции на езика.	Лексикалният анализатор улеснява задачата на синтактичния анализатор.
Синтаксисният анализатор работи върху токени в изходна програма, за да разпознае смислени структури в езика за програмиране.	Лексикалният анализатор разпознава токена в изходна програма.
Той получава входни данни под формата на токени от лексикални анализатори.	Той отговаря за валидността на токена, предоставен от синтактичен анализатор

Недостатъци на използването на синтактични анализатори

• Той никога няма да определи дали даден токен е валиден или не
• Not ви помага да определите дали операция, извършена върху тип маркер, е валидна или не
• Не можете да решите, че токенът е деклариран и инициализиран, преди да бъде използван

Oбобщение

• Синтаксисният анализ е втора фаза от процеса на проектиране на компилатора, която идва след лексикалния анализ
• Синтактичният анализатор ви помага да прилагате правила към кода
• Изречение, Лексема, Токен, Ключови думи и запазени думи, Шумни думи, Коментари, Разделители, Набор от символи, Идентификатори са някои важни термини, използвани в анализа на синтаксиса при изграждането на компилатор
• Анализът проверява дали входният низ е добре оформен и ако не е, го отхвърля
• Техниките за разбор са разделени на две различни групи: разбор отгоре надолу, разбор отдолу нагоре
• Лексикални, синтактични, семантични и логически са някои често срещани грешки, възникващи по време на метода на анализ
• Граматиката е набор от структурни правила, които описват език
• Символът за условни обозначения може да бъде обозначен чрез ограждане на елемента в квадратни скоби
• CFG е ляво-рекурсивна граматика, която има поне една продукция от типа
• Извеждането на граматика е последователност от граматично правило, което трансформира началния символ в низа
• Синтаксисният анализатор се занимава основно с рекурсивни конструкции на езика, докато лексикалния анализатор улеснява задачата на синтактичния анализатор в СУБД
• Недостатъкът на метода на анализатора на синтаксиса е, че той никога няма да определи дали даден токен е валиден или не