ПОЗНАЙ ИНТУИТА, Лекция,Описание на синтаксиса

2.3. Използване на БНФ

Всичко, което трябва да знаете за БНФ вече е казано. За да използваме този метод за ефективно описание на езиците, нека разгледаме някои прагматични наблюдения.

Приложение на БНФ

Описанието на BNF ви позволява да:

разбират синтаксиса на съществуващите езици (не само езици за програмиране);
определят синтаксиса на езика, който ще се проектира;
напишете анализатор - анализатор (парсер).

Второто приложение не е толкова фантастично, колкото изглежда на пръв поглед. Може да ви отнеме известно време, за да проектирате език с общо предназначение, който да съперничи на езици като C#, Java или Eiffel. Но програмистите доста често трябва да се справят с "малки" езици. Всеки път, когато трябва да се обработват данни в сложен формат, тези данни могат да се разглеждат като изречения на някакъв език, чийто синтаксис е удобно специфициран с помощта на BNF. Упражненията в тази лекция ще изискват от вас подобна работа.

Третото приложение (изграждане на анализатор) е полезно при писане накомпилатории други инструменти за обработка на програми и по-общо структурирани текстове. Една от първите задачи за такива инструменти е да реконструира структурата на текста под формата наабстрактно синтактично дърво. Това е работата на анализатора, както ще видим в следващата лекция. Всеки парсер се нуждае от формално описание на синтаксиса на езика - може да го получи от BNF граматика.

Език, генериран от граматиката

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

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

Втората гледна точка е по-малко полезна на практика, но в същото време важна. Нека го изследваме малко по-дълбоко. За да генерирате всички възможни екземпляри на който и да е нетерминал, по-специално, началния (или, което е същото, връх) символ на граматиката, е достатъчно да анализирате производството, което дефинира този символ (припомнете си, че има само едно такова производство в BNF-E).

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

Рекурсивни граматики

Последното наблюдение може да предизвика известно безпокойство. Какво ще стане, ако прилагайки процеса към A, трябва да го приложим към B и това ще доведе до факта, че отново срещаме A? Продукцията за съставния израз е добър пример:

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

Време за тест!

Рекурсията може да направи граматиката да изглежда безсмислена. НоНека бъдем прагматични и се запитаме дали можем да използваме граматиката за генериране на модели чрез прилагане на процеса, описан по-горе. Обърнете внимание, че в продукцията за Game един от клоновете, stop, е терминален, което позволява генерирането на първото изречение (пробата на Game):

Но сега можем да използваме тази информация, за да генерираме примерите Head_start и Tail_start, дефинирани от Game. Съответните продукции ще ни кажат, че heads stop е Head_start модел, а tails stop е Tail_start модел. Използвайки тези модели в продукцията за Game, получаваме два нови модела:

главите спират
опашки спират

След получаване на тези проби и прилагане на същия процес може да се получи следният набор от проби:

главите спират
глави опашки стоп
опашки глави спират
опашки опашки стоп

Този процес на удвояване на пробите може да продължи. Общата конструкция на примера на играта също става ясна: тя представлява последователност от „глави“ и „опашки“ в произволен ред, завършва със стоп терминал. Лесно е да се докаже, че всяка такава последователност е проба. Малко по-трудно е да се докаже, че няма образци от друг вид за Game.

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

Граматиката е дадена от три продукции, първата от които е конкатенация, втората е повторение с празен разделител, а третата е избор.

Използвайки производствени правила за генериране на език, ниеизползва стратегия, при която терминалите са предпочитани пред нетерминалите. Избирайки различна стратегия, можете да попаднете в безкраен цикъл, без да генерирате нито една оферта. Например, започвайки с първата възможност за нетерминалната игра, получаваме Head_start и след като я заменим, получаваме heads Game. Многократно прилагайки същата стратегия за Игра, получаваме последователност, в която винаги присъства нетерминалната Игра, което не прави възможно създаването на езиково изречение, което по дефиниция се състои само от крайни знаци.

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

Дори и с такава евристика, процесът на генериране няма да генерира никакви изречения на езика, ако неговата граматикае напълнорекурсивна. За да започне процесът на генериране, е необходимо поне някои от изборите да включват само токени. граматики като

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

За простота тази граматика третира Assignment като терминал, дефиниран извън граматиката (подобно на токените, дефинирани на лексикално ниво). Тази граматика има смисъл и генерира изречения като:

задание_1
задание_1; задание_2

и така нататък. За да се получи конструктивна форма за такива рекурсивни определения, е необходима обща теория, скица на която ще бъде дадена по-късно.