Ранее был приведен пример использования генераторов лексических и синтаксических анализаторов LEX и YACC для реализации компилятора, почти без пояснений. Входной язык даже не предоставлял возможности написания функций, но выражения и условия могли быть сколь угодно сложными.
Здесь приведены несколько вариантов синтаксически-управляемых компиляторов языка Tiny Context, возможно, немного измененного, но никаких сторонних инструменов не используется:
Большая часть пояснений находится на этой странице.
Как и раньше компилируемая программа должна размещаться в файле с именем c.prg, результат компиляции записывается в файл c.com. Описание грамматики языка должно размещаться в файле c.def. Если DOS недоступен, можно использовать эмулятор DOSBox.
Первая компиляции приведенных примеров выполняется почти также. Проще всего использовать Tiny Context 1.18 (c.118), для его сборки необходимо выполнить командный файл c.bat. Компиляция с помощью DOS-версии Context'a тоже возможна, но она потребует нескольких изменений в исходном тесте:
Добавить в начало текста объявление массива Temp (это связано с различиями в распределении памяти):
В заголовках всех функций с двумя или большим числом аргументов заменить запятые точками с запятой, например:
Приведенные компиляторы могут компилировать друг друга (и себя), но нужно использовать соответствующий им файл описания грамматики языка (c.def).
Как и в Tiny Context параметры функций и локальные переменные размещаются в фиксированных областях памяти, но здесь это не создает никаких проблем, поскольку рекурсия не используется.
Если в исходной реализации правила языка лишь подразумевались, в этих они используются явно. Для записи правил используется нормальная форма Бэкуса. Исходный вариант грамматики приведен ниже. В первой части перечислены лексемы (примерный аналог директив YACC %token), во второй - правила. Лексеме ставятся в соответствие код вида лексемы и значение. Ненулевой код используется чтобы отличить имена типов от всех прочих лексем, значение содержит код операции или размер объекта указанного типа в байтах. Привилу ставится в соответствие код действия, которое дожно быть выполнено при его применении (в YACC вместо этого можно написать фрагмент программы на языке Си). Коды действий будут назначены позже.
Некоторые правила могут показаться избыточными, например
или
Они нужны потому, что при распознавании символов begin и while требуется запоминать текущий адрес чтобы позже выполнить безусловный переход к нему.
Выполняя подстановки одних правил в другие можно получить допустимые в смысле этой грамматики последовательности символов. Некоторые из них будут корректными программами, другие могут быть таковыми при определенных обстоятельствах, третьи заведомо некорректны. Следующие три коротких примера демонстрируют это:
С грамматикой связан ряд вопросов, в том числе вопросы об
По-видимому, однозначность является необходимым свойством, но она не обязательно достигается средствами грамматики. Если заменить правило для Expr следующим (Op - любой арифметический оператор)
Будут потеряны не только приоритеты операций, но и однозначность. Чтобы доказать факт неоднозначности достаточно привести один пример. Выражению
может быть получено двумя разными способами
и
Будет рассмотрен только синтаксический анализатор (и примитивный генератор кода). Лексический анализатор (сканер) ввиду его простоты будет написан вручную (будет использован ранее написанный с небольшими изменениями).
Сканер при просмотре входного файла заглядывает на один символ (алфавита, т.е. на одну букву, цифру и т.д.) вперед, для рассматриваемого языка этого достаточно, для языка Паскаль нужно заглядывать на два символа вперед, для языка Фортран нужно заглядывать на большее число символов вперед, причем это число зависит от текста программы.
Нужно отметить, что и для автоматизации разработки сканеров существуют готовые инструменты. Например LEX (FLEX), использующий аппарат регулярных выражений.
Чтобы реализовать задуманное нужно решить ряд вопросов. Первый из них (самый простой) - чтение приведенного описания и заполнение соответствующих структур данных. Делающий это программный код приведен здесь. Он будет неоднократно использован в дальнейшем.
Каждому встретившемуся в описании символу (терминальному символу, т.е. лексеме, нетерминальному символу, т.е. имени в левой части правила, но не символу алфавита) будет назначен уникальный числовой идентификатор, это позволит заменить все сравнения строк сравнениями чисел. Соответственно сканер должен возвращать идентификатор, он будет определяться поиском в таблице символов.
Сложнее использовать прочитанную грамматику. Возможно, под влиянием доступной, но не оказавшейся полезной литературы первая мысль была считывать лексемы программы, помещать их в стек (эта операция называется переносом) и постоянно сравнивать его вершину с правилами. При совпадении с одним из правил выполнять замену соответствующего числа символов на вершине стека символом из левой части правила (эта операция называется сверткой). Но для приведенной выше грамматики это невозможно, поскольку имеются правила, совпадающие с частями других правил, например:
В некоторых других случаях надлежащее упорядочение правил позволяет разрешить конфликт, например:
Здесь применение второго правила при возможности применения первого приведет к ошибке, поскольку последовательность символов
уже ни во что преобразована быть не может.
Изменение грамматики, отказ от некоторых нужных вещей, введение дополнтельных лексем
и разрешение сканеру обращаться к словарю (а не к таблице символов) позволяют тем не менее реализовать и такой алгоритм разбора. Правила, являющеся частями других правил будут заменены. Например, упомянутое правило для Ref будет заменено на
Помимо этого пришлось сделать еще ряд преобразований, чтобы исключить совпадения одних правил с частями других. Для этого явно использовались предшествующие или последующие символы. Например тот факт, что выражение является фактическим параметром функции определяется по наличию запятой после него:
Это увеличивает объем грамматики и запутывает ее, но все же может быть сделано. Пример приведен здесь.
Исключить совпадения правил можно явно включив в них допустимые предществующие символы. Например, если вместо правила
ввести набор правил
можно исключить преобразование numb в Value при разборе определения массива. Пример приведен здесь. Ясно, что многократное повторение одних и тех же правил это плохо, но может быть добавит некоторое понимание вопроса. Ниже будет показано, как анализатор может разобраться с предшествующими символами самостоятельно.
Этот пример был получен из расмотренного ниже SLR(0)-анализатора.
По крайней мере теоретически возможен прямой перебор всех сверток. Практически это осуществимо лишь для очень коротких программ.
Также можно построить все возможные синтаксически корректные программы, не превосходящие заданной по числу символов и выбрать среди них совпадающую с заданной. Практически и это осуществимо лишь для очень коротких программ.
Существенно лучшие результаты дает рассмотрение вопроса о допустимых правилах и допустимых символах. В самом начале разбора ожидается, что выполняется разбор корректной программы (ей соответствует символ Program) и в конце концов будет применено одно из правил
Символы Declarations и Block могут возникнуть только в результате применения одного из следующих правил
Символ Declarations уже принят во внимание и нового ничего не даст, а символы Declaration и Main могут возникнуть в результате применения одного из следующих правил
Символы TypeName и Header могут возникнуть в результате применения одного из следующих правил
Символ TypeName уже принят во внимание, а вновь встретившийся символ Type может возникнуть в результате применения одного из следующих правил
Более никаких новых нетерминальных символов не встретилось, соответственно добавить новые правила невозможно. Вот полный список найденных правил
Четыре правила начинаются с терминальных символов, соответственно корректная программа может только с одного из них, т.е. с char, byte, word или begin. Допустим, встретился символ char. Он однозначно определяет, что должно быть применено правило
Аналогично, символ Type однозначно определяет, что должно быть применено правило
но его применение возможно только если после Type встретится символ name.
Символ TypeName не определяет однозначно допустимое правило, но определяет множество допустимых правил
Чтобы отразить тот факт, что символ TypeName уже просмотрен используется следующая нотация:
Точки указывают позиции в правилах. В правиле из N символов возможна N+1 позиция. Позиции называются пунктами, множество равновозможных пунктов называется состоянием.
Если далее встретится символ semi или символ lsb, допустимым останется лишь одно из правил. Если же встретится символ lcb, допустимых правил останется два, но следующий символ позволит выбрать одно из них:
Для этого придется разобраться с нетерминальным символом Args примерно также как это было сделано выше с символом Declarations.
Здесь нужно заметить, что для заголовка функции без параметров введено отдельное правило. Альтернатива этому - введение пустого правила для Args
Пустое правило можно распознать по его окружению, но первый вариант анализатора не будет способен это делать.
К сожалению, применение такого подхода также не позволяет работать с исходным вариантом грамматики. Но чтобы сделать его работоспособным изменений потребуется уже немного. Для начала все операторы в выражениях будут иметь одинаковый приоритет, позже это будет исправлено и это не потребует больших усилий. Измененная грамматика и компилятор приведены здесь. Это SLR(0)-анализатор.
Более или менее точный учет символов, могущих встретиться после заданного символа позволяет реализовать анализатор реальных языков программирования не прибегая к существенному усложнению грамматики. Для некоторых грамматик, в том числе и для рассматриваемой, чтобы выбрать между переносом и сверткой достаточно учитывать следующий терминальный символ без учета контекста. Свертка по правилу выполняется если после символа в левой части этого правила может встречаться символ, который будет прочитан следующим. Например в части грамматики, определяющей арифметических выражений с приоритетами
одно из возможных состояний следующее
С точки зрения SLR(0)-анализатора имеет место конфликт между переносом и сверткой. Но в рассматриваемой грамматике после Expr могут встречаться только символы plus, minus, lt, le, eq, ne, ge, gt, rsb, rcb, then, do, comma и semi. Соответственно, если следующий терминальный символ один из перечисленных, перенос приведет к пустому состоянию и следует выполнить свертку Term в Expr. Если же следующий символ star, slash или pct, которые после Expr встречаться не могут, следует выполнить перенос (затем свертку в Op2 и еще один перенос). Если следующий символ отличается от всех перечисленных, анализируемый текст не соответствует грамматике. Это SLR(1)-анализатор. Его реализация требует совсем небольших изменений, они приведены здесь.
Чтобы уяснить принцип его работы имеет смысл рассмотреть грамматику выражений без приоритетов операций и с приоритетами отдельно от всего остального и изобразить на бумаге все возможные состояния анализатора и все символы, которые могут встретиться. Чтобы отделить эту часть грамматики нужно заменить символ Value на терминальный символ numb и добавить в начало еще одно правило (вместо Program):
Можно построить грамматики, причем однозначные, для которых такой анализ не устраняет конфликтов. Для них SLR(1)-анализатор непригоден, но для некоторых из них можно постоить анализатор, учитывающий зависимость допустимых последующих символов от предшествующего контекста.
Его идея состоит в следующем. Как и раньше в самом начале разбора ожидается, что выполняется разбор корректной программы и в конце его будет применено одно из правил:
Символ Declarations может возникнуть только в результате применения одного из следующих правил
Кроме этого, и это самое важное, последующая свертка в Program не будет возможна, если после Declarations не встретится начальный символ Block (т.е. begin). Добавим к списку возможных в начале программы правил эти два и в фигурных скобках укажем, что после них ожидается символ begin:
Вообще-то после Declarations могут встречаться и другие символы, но из одного первого правила грамматики это не следует.
Далее, символ Block может возникнуть только в результате применения правила
Что может встетится после Block? Ответ может быть или ничего (достигнут конец файла) или любой, в том числе и отсутствующий в языке, символ. Пока вместо допустимого символа или символов поставим знак вопроса
и продолжим поиск возможных правил и следующих за ними символов. Рассмотрим первое из добавленных правил
Применение этого правила не будет возможно, если после Declarations не встретится начальный символ Declaration (т.е. char, byte или word). Добавим в список определения Declarations (с ожидаемыми следующими символами):
Второе определяющее Declarations правило
состоит из одного символа Declaration, который определяется тремя правилами:
После Declaration ожидается символ begin, так что и после любого из этих трех правил ожидается он же:
Это похоже на правило свертки Block в Program. Если формально приписать к определяющим Program правилам завершающие символы, устройство всех добавляемых правил станет одинаковым. Если принять решение о том, что после Program не может быть никаких символов (это по крайней мере уменьшает длину получаемого списка), можно записать:
и
Здесь символ # использется для обозначения конца файла.
Подолжая этот процесс и исключая повторы получим замыкание множества пунктов начального состояния анализатора:
Четыре правила (одно из которых повторено восемь раз) начинаются с терминальных символов, соответственно корректная программа может начинаться только с одного из них, т.е. с char, byte, word или begin. Допустим, встретился символ char. Он однозначно определяет подходящее правило
Перенос символа char в стек приводит к состоянию из одного пункта:
Если следующий символ name, то выпоняется свертка char в Type, затем перенос Type в стек, если нет - дальнейшие действия бессмысленны - текст не соответствует грамматике. Таким образом придем к состоянию анализатора из одного повторенного три раза пункта:
Перенос символа name в стек приведет к следующему состянию:
Если следующий символ semi, lsb или lcb, то выпоняется свертка в TypeName и перенос TypeName в стек, иначе фиксируется ошибка - никаких иных символов после Typename быть не должно. При нормальном ходе дела придем к состянию, четыре пункта которого повторены в общей сложности двадцать четыре раза:
Если далее встретится символ semi, перенос его в стек приведет к состоянию из одного пункта, повторенного четыре раза:
Если следующий символ begin, char, byte или word, то выпоняется свертка в Declaration, иначе фиксируется ошибка.
Продолжая процесс получим в итоге символ Program или зафиксируем ошибку. Это LR(1)-анализатор. Его реализация требует изменения функций построения замыкания, и анализа возможности свертки (последняя сводится к сравнению реального и ожидаемого символов), они приведены здесь.
Чтобы уяснить принцип его работы имеет смысл рассмотреть грамматику выражений с приоритетами отдельно от всего остального.
Также нужно заметить, что в программе выражения могут встечаться в разных контекстах и множества могущих следовать за ними символов в разных контекстах различны. Например, если выражение всречается в левой части сравнения в заголовке цикла, множество допустимых следующих символов состоит из шести символов операций сравнения, если же в правой - из одного символа do.
Для рассматриваемой грамматики эти действия избыточны. Кроме того, для хранения информации о состояниях анализатора требуется довольно много памяти, что может затруднить реализацию на машине с небольшой оперативной памятью (т.е. на восьми- или шестнадцатиразрядной машине с 64 килобайтами памяти). Можно уменьшить избыточность LR(1)-анализатора, несколько снизив при этом его общность (LALR(1)-анализатор). При наличии гигабайтов памяти эта проблема несущественна, но LALR(1)-анализаторы YACC/BISON пока никуда не исчезли.
В принципе возможно включить в грамматику правила образования слов языка и исключить лексический анализатор (вместо него потребуется всего лишь функция Read(), возвращающая при каждом вызове слежующий символ текста программы). Но LR(1)-анализатор для этого не очень приспособлен. Cледующие правила приводят к конфликту между переносом и сверткой:
Диапазоны символов ('a'-'z') использованы для сокращения записи, рассмотренные анализаторы не могут их прочесть, так что придется либо повторить каждое такое правило для каждого из символов диапазона, либо изменить загрузчик грамматики.
После считывания символа 'i' и следующего за ним символа 'f', 'n' или 's' невозможно выбрать между переносом и сверткой в name, для принятия решения нужно смотреть более чем один следующий символ. Это содержательный пример не-LR(1)-грамматики.
Конфликт исчезнет если преобразовать грамматику как показано ниже:
Новый символ грамматики temp не может начинаться с символа 'i', равно как и с любого другого символа, с которого начинается слово языка. Это тоже надо явно написать, так что последние два правила должны быть заменены. Также должны быть добавлены правила, содержащие прописные буквы, цифры и, возможно, другие символы.
Имена вроде inli выглядят странно, но формально допустимы. Если есть желание, можно их запретить и этим немного уменьшить число правил.
Приведена только часть правил и выгода от такого объединения синтаксического и лексического анализатора представляется сомнительной.