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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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