Написване на компилатор за парсери LALR (1). Част 1

Въведение или защо са необходими анализатори

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

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

И така, защо някой би искал да напише парсер и какво точно е той? Анализаторът е код, който придава семантично значение на входящ набор от символи. Тоест тези символи се анализират и въз основа на този анализ програмата разбира как да тълкува тези букви и цифри. Един прост пример е "1 + 2", след или по време на процеса на синтактичен анализ, знакът "+" е не просто символ плюс, а обозначението на двоичен оператор за събиране, а в "+3" това е знак за унарно число оператор. Това е очевидно за повечето хора, но колата не е така.

Два вида парсери

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

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

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

Вторият подход е по-лесен за показване, отколкото за обяснение:

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

Ползи от описанието на граматиката:

Въпреки всичко това програмирането „с печалба“ има редица предимства:

Входният праг е много по-нисък. Тоест, на почти всеки програмист може да се каже - „седнете и напишете кода“, а парсерът ще бъде програмиран в предложения стил. За да съставите официална граматика, трябва да имате малък, но все пак важен обем теория - основите на математическата логика, да разберете конструкцията на граматиката, да притежавате инструмент за генериране на код.
Въпреки факта, че граматиката може да опише почти всичко, има изключения. Освен това към тях се добавят ограничени инструменти. Директното кодиране има най-голяма гъвкавост.
Има и много мъничък плюс - всичко е на едно място. Тоест с нормалната организация на програмата можете да маркирате ключовите фрагменти от логиката и веднага да разберете тяхната същност. В първата версия всъщност имаме два необходими екрана - схематичен екран + екран с код. Понякога трябва да превключвате между тях, за да изясните нюансите. Това не е много удобно. Но отново това е изключително малко предимство, особено когато се има предвид вторият плюс на отделното кодиране.

Структура на парсер

Излишно е да казвам, че аз, както повечето нормални програмисти, почти винаги приемам първия подход. Отново не са необходими знания за прилагане на втория и нямам допълнителна теория за него. Следователно по-нататък говоря за структурата на синтактичния анализатор, основан на формалната граматика.

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

На първо място, струва си да разберем какви са тези компоненти. Лексикалният анализатор получава като вход поток от символи от посочената азбука (букви, цифри, използвани символи и т.н.). След това той разбива този поток на по-сложни примитиви (такъв оксиморон, да), така наречените символи или терминали. Например, вместо последователност от цифри с някаква дължина, анализаторът получава „Number“ с атрибут, равен на стойността на това число. Ще обясня защо е необходимо по-долу. След това анализаторът, базиран на символи и правила за съставяне на символи от втория йерархичен ред (първият е символите), така наречените нетерминали, събира изходно дърво. Този ADT уникално представлява структурата на разпознатите данни. И накрая, последният етап е семантичният анализ на полученото дърво и изпълнението на бизнес логиката. Този етап е представен в първия списък.

Защо е необходим лексикален анализатор, ако той действително може да бъде интегриран в синтактичната част? В крайна сметка каква е разликата коя азбука да се получи - оригиналната или новата синтетична. Отговорът е съвсем очевиден - първо, това обикновено е стесняване на азбуката, тоест опростяване на семантиката; второ, премахваме едно или дори няколко по-ниски нива на дървото, като същевременно запазваме изцяло неговите свойства. Ясно е, че лексикалният анализатор не трябва да влиза в ролята на синтактичен и още повече семантичен, следователно не бива да връща 3 на „1 + 2“, но най-простите действия, като формиране на числа, са напълно подходящи. Нека усложним малко примера и да разгледаме изходното дърво в два случая. В същото време ще покажа какво е дървото на онези, които не са разбрали съвсем кратко обяснение.

Анализиране на изрази 12 + 34

Дори и с такъв прост пример може да се види, че е по-удобно анализът да се раздели на поне 2 етапа. В допълнение, специализацията на лексикалния анализатор позволява използването на по-ефективни алгоритми, различни от анализирането на граматики. Основната разлика, в допълнение към представения по-горе емпиричен лексер, от анализатора е липсата на правила за извод, по-точно те могат да бъдат представени неявно, но вдясно ще има само азбучни символи и правилата никога няма връзка с останалите нетерминали на lexer. Тоест те са самостоятелни и описват само очаквания поток от символи.

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

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

LL срещу LR или слон срещу кит

Писането на добър лексер е отделна голяма тема, така че по-нататък ще опиша само развитието на парсер.

Има две групи анализатори - възходящ (LR) и низходящ (LL).

Те вземат името си от метода за извод на дървото. Първият изгражда дървото отдолу нагоре, вторият отгоре надолу. Ще се спра малко върху това и ще дам най-тъпите алгоритми.

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

Парсерът LL се опитва да направи обратното - за всеки входящ знак познайте на кое правило принадлежи. Най-примитивният е изборът на алтернативи (например EXPR може да се разгъне в ADD или SIGN, т.е. 2 алтернативи) на първия символ и рекурсивно спускане с нов набор от правила, които произвеждат нетерминали от избрания път. И така докато правилата слязат до терминалите. Описанието е доста сложно, ще бъде много по-лесно да се разбере в кода:

Кой парсер да използвате е въпрос на вкус. Почти във всички характеристики те са еднакви. Има мотор за това, че Съветите са използвали LL (x), а на Запад - LR (x), но не знам доколко това е вярно. Лично на мен LR ми хареса идеологически, ще говоря за него по-подробно в следващата част.

PS: Важността на правилното писане на парсери може да се види точно в статията, като се разгледа неосветената втора кодова секция, която е обвита в същия блок източник като първия пример.