Описание синтаксиса

Для обоснования таких структур нам потребуется определение их синтаксиса. Первое представление структур управления использовало для их описания естественный язык, как например: "Условный оператор начинается ключевым словом if, за которым следует…". Такой стиль полезен для первого знакомства, но не позволяет задать общий способ спецификации – он многословен и недостаточно точен. Нам нужно нечто обратное – сжатость определения и математическая строгость.

Таким требованиям отвечает БНФ, Бэкуса-Наура форма (BNF – Backus-Naur Form), главный предмет изучения этой лекции. Наряду с этой темой будут рассмотрены способы описания абстрактного синтаксиса, даны набросок разработки синтаксического анализатора (parser), введение в теорию конечных автоматов и кратко описана история вопроса.

2.1. Роль БНФ

Мы видели, что полное описание языка программирования включает три уровня: лексический, синтаксический, семантический. БНФ задают только спецификацию синтаксиса. Перед продолжением чтения следует освежить в памяти ранее введенные понятия – категория, терминал, нетерминал, образец, синтаксическое дерево.

Почувствуй историю

Первоначальная БНФ

История языков программирования началась в пятидесятые годы прошлого столетия. Первым языком, получившим широкое распространение, стал язык Фортран (FORTRAN – FORmula TRANslator), предназначавшийся для научных вычислений и спроектированный командой из фирмы IBM под руководством Джона Бэкуса в 1954 году. В 1956 году для него был разработан компилятор, что предопределило успех и послужило толчком к созданию множества языков программирования.

Вскоре американские и европейские группы объединили усилия для проектирования международного стандарта языка, ставшего известным в 1956 году под именем Algol 58 (имя произведено от ALGOrithmic Language и вначале писалось буквами в верхнем регистре – ALGOL). Наибольшее распространение получила следующая версия этого языка – Algol 60.

При подготовке спецификаций обнаружилась необходимость лучшего способа описания синтаксиса, чем тот неформальный подход, который использовал Джон Бэкус при описании Фортрана. К этому времени Джон Бэкус входил в состав рабочей группы, создававшей язык Algol и предложившей нотацию, которая была известна первоначально как БНФ (Бэкуса Нормальная Форма). В 1964 году Дональд Кнут в письме в журнал "Communications of the ACM" просил учесть заслуги по разработке нотации другого члена комитета – Питера Наура из Дании, сохранив акроним БНФ, но изменив его расшифровку (Бэкуса-Наура Форма).

С тех пор было предложено много различных вариаций БНФ. В спецификациях языка Pascal – потомка языка Algol – его автор Никлас Вирт предложил графический вариант БНФ, который также стал широко использоваться.

(рис 2.1)

(рис 2.2)

Языки и их грамматики

Для наших целей язык – это множество "предложений", каждое из которых задается конечной последовательностью лексем из некоторого "словаря". Например, простейшим правильным предложением языка Eiffel является текст класса:

class A end
        

Это предложение состоит из трех лексем: двух ключевых слов и идентификатора. Тексты, встречающиеся на практике, – тексты полезных классов – имеют значительно больше лексем.

Не каждая последовательность лексем из словаря языка является предложением этого языка: переставив лексемы end A class, мы не получим текст, задающий описание класса. Синтаксис языка и определяет, какие последовательности лексем являются предложениями языка, а какие нет. Спецификация синтаксиса называется грамматикой.

Грамматика

Грамматикой языка называется конечное множество правил, позволяющих создавать на основе словаря языка последовательности лексем, такие, что:

любая последовательность лексем, полученная в результате применения конечного числа правил, является предложением языка;

любое предложение языка может быть получено конечным применением правил.

Из определения следует, что любое предложение языка может быть выведено путем применения правил (утверждение 2) и что любой такой вывод дает предложение языка (утверждение 1).

Большинство языков потенциально бесконечно. Например, число возможных программ на Eiffel бесконечно. Эта теоретическая возможность не создает никаких практических проблем, во-первых, потому, что в нашей жизни мы можем иметь дело только с конечным множеством программ, но, что более важно, каждый текст класса – предложение языка Eiffel – является конечной последовательностью терминалов. Последовательность может быть очень длинной, но она не может быть бесконечной.

Конечное множество правил должно позволять порождать бесконечный язык, должно позволять, например, создавать описание всех возможных классов на языке Eiffel. Это опять-таки не должно нас беспокоить. Нам не нужны все возможные классы, нам нужны только те, что интересуют нас. Достаточно, что мы знаем, что правила способны породить описание каждого возможного класса.

БНФ – это нотация для определения грамматик. Это пример метаязыка – языка, служащего для описания других языков, таких как языки программирования.

БНФ и другие приемы, рассматриваемые в этой лекции, применимы не только к языкам программирования, но и к любым формальным языкам, искусственным нотациям со строго определенной структурой. HTML, формат текстов Web-страниц, XML, формат структурированных текстов широкого применения, служат примерами формальных языков, не являющихся языками программирования в обычном смысле. Фактически, исходные исследования формализации грамматики языка были связаны с пониманием естественных языков с их сложностью и нерегулярностью.

Основы БНФ

Для описания грамматик будем использовать форму БНФ, называемую БНФ-Е, в частности, служащую стандартом описания Eiffel. Есть много других вариантов, таких как расширенная БНФ (EBNF- Extended BNF), определенная международным стандартом. В дальнейших обсуждениях термин БНФ будет применяться к любому варианту. Специфические свойства БНФ-Е будут отмечаться особо. Разница скорее в стиле, чем в существе дела.

БНФ позволяет нам задать грамматику языка – некоторую, а не вполне определенную грамматику, поскольку разные грамматики могут описывать один и тот же язык.

БНФ состоит из следующих частей, каждая из которых задается конечным множеством.

Конечное множество ограничителей, к которым, как мы видели, относятся базисные ключевые слова (class, if …) и специальные символы (точка, запятая …).

Конечное множество категорий, задающих структурные единицы языка. Примером категории является понятие Class, представляющее текст класса, и категория Conditional, представляющая текст условного оператора. Соглашение, принятое в БНФ-Е, требует, чтобы имя категории начиналось с большой буквы. Напоминаю, что конкретный пример категории называется образцом. Каждый конкретный условный оператор является образцом категории Conditional.

Конечное множество продукций, где каждая продукция связана с некоторой категорией и задает форму ее образцов. Продукция для Conditional определяет форму любого условного оператора: вначале идет if, затем образец булевского выражения и так далее.

Каждая продукция определяет синтаксис образца категории через ограничители и другие категории. Вот пример продукции для категории Conditional:

$$Construct\;\triangleq\;if\;\;Then\_part\_list\;[Else\_part]\;end$$

Это правило говорит, что любой образец Conditional – любой условный оператор – состоит из ключевого слова if, ограничителя, за которым следует образец категории Then_part_list, за которым, возможно, следует образец категории Else_part, ключевое слово end завершает конструкцию. Квадратные скобки отмечают возможные конструкции, которых может и не быть. Категории Then_part_list и Else_part имеют собственные продукции.

Каждая продукция определяет одну категорию, стоящую слева от символа $$\triangleq$$, который читается как "по определению является". В правой части этого определения стоит БНФ-выражение, задающее структуру образца категории. Такое использование продукций позволяет нам выделять два вида категорий.

Категория, определяемая продукцией грамматики, называется нетерминалом.

Другие категории являются терминалами. Примерами терминалов в грамматике Eiffel служат категория Idenifier (идентификатор) и Integer (целое), чьи образцы являются идентификаторами, такими как имя класса Preview, и целочисленные константы, такие как 34. Грамматика не определяет терминальные категории, их синтаксис определяется на более низком лексическом уровне.

Понятия терминала и нетерминала не являются новыми. Мы встречались с ними ранее при построении абстрактных синтаксических деревьев, где терминалы играли роль листьев дерева, а нетерминалы были внутренними узлами.

Причина отнесения некоторых категорий к терминалам и их определения вне грамматики – чисто прагматическая: эти категории имеют простую структуру, для которой мощь БНФ кажется избыточной. Идентификатор, например, – это начинающаяся с буквы простая последовательность букв, цифр и подчеркивания. Это правило может быть выражено лексическими приемами, изучаемыми в этой лекции.

На синтаксическом уровне (БНФ-грамматики) образцы терминальных категорий задаются лексемами, подобно ограничителям. В отличие от ограничителей, каждый из которых представляет фиксированную лексему, такую как ключевое слово или специальный символ, большинство терминальных категорий, таких как Identifier и Integer, имеют бесконечное множество возможных образцов. БНФ-грамматика не интересуется содержимым лексем, рассматривая их как неделимые атомарные единицы.

Для любого языка особое значение имеет категория, описывающая структуру самого верхнего уровня; для Eiffel – это категория Class. Такой нетерминал (top construct) называется вершинной (начальной, главной) категорией языка. Предложения языка – тексты классов в нашем случае – являются образцами вершинной категории.

Отличия языка от метаязыка

Продукция, приведенная для категории Conditional, показывает, что БНФ включает символы трех разных видов.

Символы метаязыка: они относятся к самой БНФ, позволяя описать структуру продукции. В пример с Conditional такими символами являются символ $$\triangleq$$ и квадратные скобки, сигнализирующие о возможности присутствия конструкции, заключенной в скобки.

Элементы языка, непосредственно принадлежащие языку, который описывается грамматикой. К таким элементам относятся ключевые слова и ограничители, используемые в языке.

Имена категорий, как терминальных, так и нетерминальных. Они принадлежат мета-языку, где обозначают элементы описываемого языка. Терминалы, как сказано, задают лексемы. Нетерминалы задают синтаксические структуры. Например, каждый образец Conditional является синтаксической структурой, которая содержит подструктуру, такую как Then_part_list.

Во избежание недоразумений нужно быть внимательным и отличать символы языка от символов метаязыка

В цветном оригинале книги используются разные цвета для символов разного вида. В черно-белом варианте контекст позволяет понять, какому языку принадлежит символ. Символов метаязыка относительно немного и они, как правило, отличаются по начертанию от символов языка. Для совпадающих символов – квадратных скобок, двоеточия – в БНФ символы языка Eiffel будут заключаться в кавычки.

Термин "образец" (spacimen) на первых порах мог вызывать недоумение. Казалось бы, следовало использовать привычный термин "экземпляр" (instance), но этот термин уже занят – он описывает объекты. Экземпляр класса – это объект, появляющийся во время выполнения, образец класса – это текст, задающий текст некоторого конкретного класса.

2.2. Продукции

Продукция определяет синтаксис одной категории. Она имеет следующую форму:

$$Construct\;\triangleq\;Definition$$

В левой части продукции задается определяемая категория, а в правой – ее определение, выраженное в терминах категорий (терминалов и нетерминалов) и ограничителей. В зависимости от формы определения различают три вида продукций: конкатенацию, выбор и повторение.

Конкатенация

Конкатенация – это продукция, перечисляющая последовательность из нуля и более категорий; они следуют в определенном порядке и некоторые из них, возможно, заключены в квадратные скобки, что и определяет их возможность отсутствия. Наша первая продукция для Conditional является таким примером:

$$Construct\;\triangleq\;if\;\;Then\_part\_list\;[Else\_part]\;end$$

Такая продукция задает, что каждый образец категории, стоящей слева, по определению состоит из последовательности (конкатенации) стоящих справа образцов, идущих в заданном порядке, с тем исключением, что "возможные" образцы могут отсутствовать.

Конкатенация просто означает связывание двух или более элементов в цепочку (catena в латыни). Это слово часто применяется в программировании. Мы говорим о конкатенации двух строк, когда вторая строка присоединяется к первой. Ее использование в БНФ немного претенциозно, поскольку можно было бы просто говорить о "последовательности". Но опять-таки в языке программирования мы уже задействовали этот термин, говоря о "последовательности операторов" – нашей первой структуре управления. Чтобы избежать недоразумений, мы используем термин "Последовательность", говоря о конструкциях Eiffel, и термин "Конкатенация", когда речь идет о БНФ-продукциях. Аналогичное различие существует между терминами "Выбор" и "Условный оператор", "Повторение" и "Цикл". Первый термин используется при описании БНФ, второй – при описании конструкций языка программирования.

Выбор

Продукция "Выбор" перечисляет одну или несколько категорий, разделенных метасимволом вертикальной черты. Вот пример определения категории Instruction (оператор):

$$Instruction\;\triangleq\;Conditional\;|\;Loop\;|\;Compound\;|\;Assignment\;|\;Call$$

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

Повторение

Продукция "Повторение" перечисляет две категории, стоящие справа от символа определения: одну нетерминальную, которую следует повторить, другую – обычно терминальную, используемую как разделитель. Для примера определим категорию Compound (составной оператор), которая задает последовательность операторов, разделенных символом точка с запятой:

$$Compound\;\triangleq\;\{Instruction\;";"\;\ldots\}*$$

Из этого определения следует, что образец составного оператора является последовательностью из нуля или более образцов операторов, каждый отделяется от следующего, если тот есть, символом "точка с запятой". В соответствии с этим правилом возможные образцы имеют вид:

пусто (ни одного оператора);

inst1

inst1; inst2

inst1; inst2; inst3

"и так далее".

Здесь inst1, inst2, inst3 являются образцами операторов.

Мы знаем, что в Eiffel точка с запятой, используемая в качестве разделителя, не является обязательной. Хотя это свойство может быть отражено грамматикой, более удобно правило грамматики оставить в приведенной здесь форме, дополнив его правилом, не использующим БНФ и устанавливающим безвредность пропуска разделителя.

В продукции использованы новые метасимволы, задающие повторение. Метасимвол * – символ, широко используемый в математике, означает "ноль или более раз". Метасимвол "многоточие" означает повторение элементов с разделителями, фигурные скобки используются для группировки элементов.

Такое продукционное правило для составного оператора с возможностью нулевого повторения означает, что допускается пустой составной оператор. Это может быть полезно в некоторых случаях, например, можно корректно писать:

if some_condition then        [S1]
else
    instruction_1
    instruction_2
end
        

Здесь пустая then-часть законна, поскольку синтаксически здесь стоит составной оператор, пустой в этом конкретном случае. Этот пример можно переписать в более понятной форме:

if not some_condition then    [S2]
    instruction_1
    instruction_2
end
        

Но первая форма может быть предпочтительнее, учитывая процесс обновления программы, когда then–часть, предположительно, будет заполнена позже.

При определении некоторых категорий однократное присутствие образца обязательно, но возможно его повторение. В этом случае вместо метасимвола * (ноль или более) используется другой метасимвол, так же широко применяемый в математике для этих же целей, – символ + (один или более). Приведем теперь полное определение категории Conditional, включая определения входящих в нее категорий:

$$Conditional\;\triangleq\;if\;Then\_part\_list\;[Else\_part]\;end\\Then\_part\_list\;\triangleq\;\{Then\_part\;elseif\;\ldots\}^+\\Then\_part\;\triangleq\;Boolean\_expression\;then\;Compound\\Else\_part\;\triangleq\;else\;Compound$$

Продукция "Повторение", используемая в определении категории Then_part_list, показывает, что для образца категории допустимы такие формы:

cond1 then inst1
— Один образец Then_part
cond1 then inst1 elseif cond2 then inst2
— Два образца Then_part
cond1 then inst1 elseif cond2 then inst2 elseif cond3 then inst3
— Три образца Then_part
        

Пример можно продолжать, поскольку число образцов в этой конструкции может быть произвольно большим. Заметьте, что категория Then_part_list, задающая список, не может быть определена как возможно отсутствующая. В определении категории Conditional после if должна следовать хотя бы одна Then_part.

Правила грамматики

В БНФ – любом варианте – очевидное правило построения продукций состоит в том, что в правой части определения могут встречаться только ограничители, терминалы и нетерминалы. Для написания грамматики достаточно перечислить продукции, определяющие эти три множества, простыми соглашениями.

Ограничители описывают себя сами с дополнительным соглашением, что ключевые слова появляются в БНФ так, как они пишутся, а специальные символы появляются в кавычках.

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

Если категория появляется в левой части хотя бы одной продукции, то он относится к нетерминалам.

В противном случае категория относится к терминалам. В этом случае ее определение должно появляться на лексическом уровне спецификации языка.

Случай 3 предполагает, что нетерминал может появляться в левой части более чем одной продукции. В БНФ-Е это не допускается, но разрешается для большинства вариантов БНФ, где две различные продукции, определяющие один нетерминал:

$$A\;\triangleq\;Def1$$

$$A\;\triangleq\;Def2$$

интерпретируются как одна продукция "Выбор":

$$A\;\triangleq\;Def1\;|\;Def2$$

Варианты БНФ допускают в одной продукции смешение различных механизмов определения продукций – конкатенации, выбора, повторения, как в этом примере:

$$A\;\triangleq\;B\;|\;C\;[D]\;\{E\;";"\;\ldots\}*$$

БНФ-Е отвергает такое смешение стилей.

Почувствуй методологию

БНФ-Е правило

Каждый нетерминал должен появляться в левой части только одной продукции, называемой определением нетерминала.

Каждая продукция должна быть одного вида: "Конкатенация", "Выбор" или "Повторение", следуя приведенным выше определениям.

Вышеприведенный пример определения категории А должен быть записан в БНФ-Е с использованием трех продукций:

$$A\;\triangleq\;B\;|\;Concat\\Concat\;\triangleq\;C\;[D]\;Repet\\Repet\;\triangleq\;\{E\;";"\;\ldots\}*$$

Вместе с несколькими нотационными соглашениями это правило стиля задает специфику БНФ- Е, отличающую ее от других вариантов.

При написании определений языков я обнаружил, что это правило ведет к введению дополнительных понятий – нетерминалов, таких как Concat и Repet в последнем примере, а ранее Then_part_list, что в конечном итоге позволяет выработать более понятное описание языка.

Оно также позволяет дать лучшую оценку размера языка. Если допустимо смешивать различные виды продукций в одной, то можно иметь сравнительно небольшое число продукций, создавая видимость простоты языка. Так как этого нельзя делать в БНФ-Е, то число продукций является хорошим индикатором синтаксической сложности языка.

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

Все, что нужно знать о БНФ, уже сказано. Для эффективного использования этого метода описания языков рассмотрим некоторые прагматические наблюдения.

Применение БНФ

БНФ описание позволяет:

понять синтаксис существующих языков (не только языков программирования);

определить синтаксис языка, который предстоит спроектировать;

написать синтаксический анализатор – парсер (parser).

Второе применение не столь фантастично, как кажется с первого взгляда. Возможно, вам еще не скоро придется проектировать язык общецелевого применения – соперник таких языков, как С#, Java или Eiffel. Но программистам довольно часто приходится иметь дело с "малыми" языками. Всякий раз, когда приходится обрабатывать данные сложного формата, эти данные можно рассматривать как предложения некоторого языка, синтаксис которого удобно задать, используя БНФ. Упражнения этой лекции потребуют от вас выполнения подобной работы.

Третье приложение (построение анализатора) полезно при написании компиляторов и других инструментов, предназначенных для обработки программ, а в более общем случае – структурированных текстов. Одна из первых задач для таких инструментов – это реконструкция структуры текста в форме абстрактного синтаксического дерева. Это работа анализатора, как мы увидим в следующей лекции. Любому анализатору необходимо формальное описание синтаксиса языка – он может получить его из БНФ-грамматики.

Язык, порождаемый грамматикой

БНФ-грамматику можно рассматривать двумя дополняющими способами, вытекающими из двух предложений в определении понятия грамматики.

Это механизм распознавания, позволяющий определить, является ли некоторая последовательность из терминальных образцов и ограничителей фразой нашего языка, и, если это так, восстановить ее синтаксическую структуру. Эта точка зрения на грамматику полезна при написании анализатора.

Грамматика является также порождающим механизмом: применяя ее правила, можно сгенерировать все фразы языка, одну за другой.

Вторая точка зрения на практике менее полезна, но в то же время важна. Давайте исследуем ее немного глубже. Для порождения всех возможных образцов любого нетерминала – в частности, начального (или, что то же, вершинного) символа грамматики – достаточно анализировать продукцию, определяющую этот символ (напомним, что в БНФ-Е такая продукция единственная).

Р1	Для конкатенации – породить все возможные последовательности образцов перечисленных категорий, учитывая, что категории со статусом "возможные" могут как присутствовать, так и отсутствовать.
Р2	Для повторения – породить все последовательности из нуля и более образцов (одну или более для знака +) указанной категории с заданным разделителем элементов последовательности.
Р3	Если на любом из предыдущих шагов встретился нетерминал, применяйте тот же процесс для порождения его собственных образцов.
Р4	Для выбора применяйте предыдущие шаги ко всем перечисленным категориям и собирайте все образцы, порожденные каждой из категорий.

Эти четыре механизма порождения предложений применяйте до тех пор, пока хоть одно из них будет применимо. В конечном счете будут порождены все предложения языка. Процесс этот обычно не завершается, поскольку, как мы видели, языки, представляющие интерес на практике, являются бесконечными.

Применяя этот процесс к нетерминалу А, чья продукция использует В, возможно, придется применять те же правила – на шагах Р3 и Р4 – к другим категориям.

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

Последнее наблюдение может вызывать некоторое опасение. Что, если, применяя процесс к А, мы должны будем применить его к В, а это приведет к тому, что мы снова встретим А? Продукция для составного оператора является хорошим примером:

$$Compound\;\triangleq\;\{Instruction\;";"\;\ldots\}*$$

Определение включает категорию Instruction, продукция для которой включает категорию $$Compound :\;\triangleq$$

$$Instruction\;\triangleq\;Conditional\;|\;Compound\;|\;\ldots Other\;choices\;\ldots$$

Заметьте, что и определение категории Conditional включает категорию Compound. Если попытаться понять структуру Compound, разыскивая его образцы путем применения вышеприведенных правил, то кажется, что мы впадем в цикл – вывод, не имеющий смысла.

Определение понятия, в котором явно или неявно понятие определяется через само себя, называется рекурсивным. Рекурсия – использование рекурсивных определений – самая популярная вещь во всех областях программирования, и мы посвятим ей отдельную лекцию. Но уже здесь, где нет практически полезных грамматик, не использующих рекурсию, мы убедимся в важности рекурсивных грамматик.

Начнем изучение с небольшого примера. Рассмотрим мини-язык с тремя ключевыми словами heads, tails, stop (головы, хвосты и остановка). Других терминалов в этом языке не будет. Начальным нетерминалом будет категория Game, и вся грамматика задается тремя продукциями – выбором и двумя конкатенациями:

$$Game\;\triangleq\;Head\_start\;|\;Tail\_start\;|\;stop\\Head\_start\;\triangleq\;heads\;Game\\Tail\_start\;\triangleq\;tails\;Game$$

Ситуация напоминает ситуацию с категориями Conditional, Instruction, Compound, определяемыми друг через друга.

Время теста!

Можете ли вы породить образцы категории Game, принадлежащие языку, который порожден этой грамматикой? Что является образцами категорий Head_start и Tail_start? Постарайтесь дать ответ прежде, чем продолжите чтение.

Из-за рекурсии грамматика может показаться бессмысленной. Но будем прагматиками и спросим себя, нельзя ли использовать грамматику для генерирования образцов, применяя описанный выше процесс. Заметим, что в продукции для Game одна из ветвей, stop, является терминальной, что позволяет сгенерировать первое предложение (образец Game):

stop

Но теперь мы можем использовать полученную информацию для генерирования образцов Head_start и Tail_start, определяемых через Game. Соответствующие продукции скажут нам, что heads stop является образцом Head_start, а tails stop – образцом Tail_start. Воспользуемся этими образцами в продукции для Game, получим два новых образца:

heads stop

tails stop

Получив эти образцы, и применяя тот же процесс, можно получить следующее множество образцов:

heads heads stop

heads tails stop

tails heads stop

tails tails stop

Этот процесс удвоения образцов можно продолжать. Становится понятным и общая конструкция образца Game: он представляет последовательность "голов" и "хвостов", идущих в произвольном порядке, она заканчивается терминалом stop. Нетрудно доказать, что любая такая последовательность является образцом. Немного сложнее доказательство того, что образцов другого вида для Game нет.

Очень простой язык этой грамматики с начальным нетерминалом Game можно рассматривать как все последовательности возможных исходов бросания монеты при игре в "орел или решка". Последовательность заканчивается в тот момент, когда игрок кричит stop. Этот язык можно описать и не рекурсивной грамматикой:

$$Game1\;\triangleq\;Throw\_sequence\;stop\qquadИгра\;\triangleq\;Последовательность\_бросков\;стоп\\Throw\_sequence\;\triangleq\;\{Throw\;\ldots\}^+ \quad Последовательность\_бросков\;\triangleq\;\{Бросок\;\ldots\}^+\\Throw\;\triangleq\;heads\;|\;tails\qquad\qquad\qquad\;\; Бросок\;\triangleq\;Орел\;|\;Решка$$

Грамматика задана тремя продукциями, первая из которых является конкатенацией, вторая – повторением с пустым разделителем, третья – выбором.

Этот пример показывает, что не имеет смысла говорить о том, что язык однозначно определяет грамматику. Один и тот же язык может быть описан разными грамматиками. Но с другой стороны, каждая грамматика вполне однозначно определяет язык, так что можно говорить о языке, порожденном грамматикой.

Применяя для генерирования языка продукционные правила, мы использовали стратегию, в которой терминалы предпочтительнее нетерминалов. Выбрав другую стратегию, можно впасть в бесконечный цикл, не сгенерировав ни единого предложения. Например, начав с первой возможности для нетерминала Game, получим Head_start, а после его замены – heads Game. Многократно применяя эту же стратегию для Game, получим последовательность, в которой всегда присутствует нетерминал Game, что не дает создать предложение языка, которое по определению состоит только из терминальных символов.

Во избежание подобных ситуаций процессу генерирования языка необходимы подходящие стратегии, или эвристики, подобные той, которая применялась для выбора – если есть ветвь, содержащая только терминалы, то выбирается такая ветвь, в противном случае выбирается продукция, начинающаяся с лексемы.

Даже при наличии таких эвристик процесс генерации не создаст ни одного предложения языка, если его грамматика полностью рекурсивна. Для запуска процесса генерации необходимо, чтобы по меньшей мере некоторые выборы включали только лексемы. Грамматики, такие как

$$A\;\triangleq\;A$$

или

$$A\;\triangleq\;B\\B\;\triangleq\;A$$

бесполезны. Эти проблемы подробно будут обсуждаться в лекции, посвященной рекурсии. Более тонким случаем являются грамматики, содержащие лексемы, но являющиеся леворекурсивными, как в следующем примере:

$$Instruction\;\triangleq\;Compound\;|\;Assignment\\Compound\;\triangleq\;Instruction\;";"\;Instruction$$

Для простоты в этой грамматике Assignment считается терминалом, определенным вне грамматики (по аналогии с лексемами, определяемыми на уровне лексического анализа). Эта грамматика имеет смысл и порождает такие предложения, как:

assignment_1

assignment_1; assignment_2

и так далее. Для получения конструктивного вида таких рекурсивных определений необходима общая теория, набросок которой будет дан позднее.

Одна из форм грамматики, позволяющая справиться с возникающими сложностями и написать простой синтаксический анализатор, называется LL(1)-грамматикой. Эта грамматика характеризуется тем свойством, что первого символа разбираемого предложения языка достаточно для однозначного выбора нетерминала, определяющего это предложение. Грамматика языка Eiffel близка к LL(1)-грамматике. Например, если первая лексема равна if, то соответствующий оператор может быть только условным (нетерминал Conditional); если первая лексема – from, то оператор цикла и так далее.

2.4. Описание абстрактного синтаксиса

Синтаксис, который мы изучали в этой лекции, задавал конкретный синтаксис программы со всеми ее ключевыми словами, ограничителями и прочими деталями, которые играют важную синтаксическую роль, позволяя избежать двусмысленностей, но не несут никакой семантики. Ранее мы встречались с абстрактным синтаксисом, в котором эти детали отсутствовали, оставляя только те элементы, что несут за собой смысл.

Мы видели, как описать результирующую синтаксическую структуру, используя АСД (Абстрактное Синтаксическое Дерево), такое как ранее показанное дерево, задающее синтаксис нашего класса Preview1.

(рис 2.3) Абстрактное синтаксическое дерево

Как отмечалось, проще построить конкретное синтаксическое дерево, содержащее все символы исходного текста. Некоторые компиляторы так и поступают, но обычно в этом нет необходимости. Для последующих фаз компиляции, таких как семантический анализ, генерация кода и его оптимизация, синтаксические маркеры не играют роли. Все, что нужно для представления структуры программы, в точности содержится в АСД.

Если бы нашей целью было описание абстрактного синтаксиса, без обращения к конкретному синтаксису, то нужды в новом формализме не было бы. Вполне достаточно использовать БНФ, опуская все лексемы, не являющиеся категориями лексической грамматики, в частности, опуская ключевые слова. Для последней продукции, специфицирующей Compound, точку с запятой можно было бы опустить, оставив просто Instruction Compound.

В таких приложениях, как синтаксический анализ и компиляция исходных текстов, эта грамматика не принесла бы пользы, поскольку, очевидно, здесь требуется конкретная грамматика, обсуждаемая до сих пор. Но она может играть свою роль, помогая в изучении тех структурных свойств текстов, которые не зависят от деталей внешнего вида этих текстов.

2.5. Превращение грамматики в анализатор

Одно из приложений БНФ, как отмечалось, в том, что грамматика является руководством для построения компилятора, начиная с фазы синтаксического анализа. Компиляторы, обычно являются синтаксически управляемыми: анализатор создает АСД, а последующие фазы компиляции продолжают работать на этой структуре данных, добавляя семантическую информацию (этот процесс называется декорированием дерева).

Детальное рассмотрение процесса построения синтаксически управляемого компилятора или просто анализатора выходит за пределы данного курса. При желании можно познакомиться с идеями применяемых методов, изучая библиотеку EiffelParse. В этой библиотеке реализован не самый эффективный механизм разбора, но ее методы представляют понятную и практическую иллюстрацию применения ОО-принципов этой книги для построения анализатора и компилятора. Сам Eiffel использует более традиционные подходы разбора, с которыми можно ознакомиться, изучая библиотеку "GOBO".

Идея, стоящая за EiffelParse, состоит в том, чтобы строить нужные классы непосредственно по грамматике БНФ-Е. Для каждой категории грамматики строится небольшой класс, являющийся наследником одного из классов библиотеки EiffelParse: AGGREGATE, CHOICE, REPETITION (соответственно для продукций "Конкатенация", "Выбор" и "Повторение"). Например, для конкатенации класс будет просто перечислять различные компоненты, стоящие в правой части продукции, связывая каждую компоненту с классом, подобным образом описывающим конструкцию. Следует быть внимательным, имея дело с левой рекурсией, но в остальном классы являются зеркальным отражением продукций БНФ-Е. Транслятор YOOC, разработанный Кристиной Мингинс, создает классы непосредственно по грамматике.

Для разбора входного текста достаточно вызвать EiffelParse – процедуру parse для соответствующей категории. В результате для нее будет создано АСД. Затем можно добавить семантическую обработку любого типа, используя методы синтаксического класса. Этот подход демонстрирует мощь и элегантность ОО-моделирования процесса анализа и компиляции языка программирования.

2.6. Лексический уровень и регулярные автоматы

Для терминальных конструкций, таких как идентификаторы и числа, БНФ не создает продукций, возлагая их спецификацию на лексический уровень. По этой причине терминальные категории называются также лексическими категориями. Их спецификация появляется в "лексической грамматике", дополняющей БНФ-грамматику.

Лексические категории в БНФ

На синтаксическом уровне, покрываемом БНФ, лексемы (терминалы и ограничители) являются атомами. На лексическом уровне нас интересует внутренняя структура этих атомов. Например (используя соглашения Eiffel):

идентификатор – это последовательность символов, первый из которых является буквой (в верхнем или нижнем регистре), а остальные могут быть буквами, цифрами или знаком подчеркивания "_";

целое – это последовательность десятичных цифр (0-9), которые также могут содержать подчеркивание при разделении групп цифр в больших числах для облегчения чтения: 123_456_789;

целочисленная_ константа (целое_со_знаком) – это целое, с возможно предшествующим знаком + или -.

Такие категории нетрудно выразить через БНФ (упражнение попросит вас проделать это). Но для таких простых конструкций обычно используют специфические лексические приемы, к изучению которых мы приступаем. Это позволяет избежать перегрузки грамматики продукциями для базисных структур, которые могут быть описаны более просто, и резервировать БНФ-грамматику для спецификации структур языка более высокого уровня, допускающих, в частности, вложенность.

Соответственно, компиляторы не используют анализатор (парсер) для разбора образцов терминалов, для этих целей применяется лексический анализатор (лексер).

Регулярные грамматики

Для определения структуры лексических категорий, таких как в вышеприведенных примерах, мы можем использовать регулярную грамматику – упрощенную версию БНФ.

Нетерминалами такой грамматики являются категории, подобные идентификаторам и целым, которые выступают в роли терминалов в БНФ. Для задания их структуры регулярная грамматика имеет собственные терминалы, обычно символы, принадлежащие некоторым категориям, например:

$$Letter\;\triangleq\;'a'\;|\;'b'\;|\;'c'\;|\;'d'\;|\;'e'\;|\;'f'\;|\;'g'\;|\;'h'\;|\;'i '\;|\;'j '\;|\;'k '\;|\;'l '\;|\;'m'\\'n'\;|\;'o'\;|\;'p'\;|\;'q'\;|\;'r'\;|\;'s'\;|\;'t '\;|\;'u'\;|\;'v'\;|\;'w'\;|\;'x'\;|\;'y'\;|\;'z'\\Decimal\_digit\;\triangleq\;'0 '\;|\;'1'\;|\;'2'\;|\;'3'\;|\;'4'\;|\;'5'\;|\;'6'\;|\;'7'\;|\;'8'\;|\;'9'\\Underscore\;\triangleq\;'\_'$$

Каждая категория выражается как выбор между единичными символами, показанными в одинарных кавычках. Такие категории являются по-настоящему терминальными (атомарными), не подлежащими дальнейшим уточнениям. Общепринято использовать специальную нотацию для последовательно идущих символов, учитывая порядок их следования в алфавите; так что продукцию для Letter, добавив еще буквы в верхнем регистре, можно записать в виде:

$$Letter\;\triangleq\;'a'\;\ldots\;'z'\;|\;'A'\;\ldots\;'Z'$$

Аналогично можно определить Decimal_digit как '0'.. '9'. Регулярная грамматика может иметь те же виды продукций, что и БНФ, но со слегка отличными соглашениями и важными ограничениями:

в продукциях "Выбор" можно использовать интервалы для задания множества символов;

при определении лексической категории продукцией "Конкатенация" в последовательности символов не должно быть пробелов. Если вы определяете категорию как А В, то любой образец категории состоит из образца А, за которым следует без всяких разделителей образец В, никаких символов не должно быть между ними. Если языку требуется понятие разделителя, то его следует ввести явно в регулярную грамматику как лексическую категорию;

повторение имеет упрощенную форму: если А означает ранее введенную категорию, то А* и А+ означают "ноль или более повторений А" и "один или более повторений А" соответственно. Опять-таки никаких разделителей или пробелов между образцами А не предполагается;

никакая рекурсия, ни прямая, ни косвенная не допускается в грамматике. Простой способ выполнения этого запрета состоит в установлении порядка применения правил. Другой способ состоит в добавлении правила, согласно которому определение категории может ссылаться только на уже определенные категории.

В отличие от БНФ-Е регулярная грамматика позволяет смешивать различные виды продукций (поскольку на правила наложены существенные ограничения). Введение скобок позволяет устранить любую двусмысленность. Регулярная грамматика с учетом этих замечаний позволяет дать точные определения для рассмотренных нами лексических категорий:

$$Identifier\;\triangleq\;Letter\;(Letter\;|\;Digit\;|\;Underscore)^*\\Integer\_constant\;\triangleq\;Decimal\_digit^+$$

Выражения, допускаемые только что определенными правилами, называются регулярными выражениями, а язык, определяемый регулярной грамматикой, – регулярным языком. Отметим следующее свойство.

Теорема: "Каноническая форма регулярного языка"

Любой регулярный язык может быть описан регулярной грамматикой, чьи продукционные правила не содержат в правой части никаких нетерминалов.

Доказательство следует из запрета рекурсивных определений. Как обсуждалось выше, любой появляющийся в правой части нетерминал определен в предыдущих правилах, поэтому вместо него можно подставить его определение. Понятно, что первое правило в такой грамматике содержит только терминалы в правой части, а в остальных правилах нетерминалы могут быть исключены, что и доказывает наше утверждение.

Например:

$$A\;\triangleq\;T1\;|\;T2\;|\;T3^*\\B\;\triangleq\;T4^+\;|\;A\\C\;\triangleq\;A\;B$$

Применяя процесс, описанный при доказательстве теоремы, можно построить эквивалентную грамматику, порождающую тот же язык.

$$A\;\triangleq\;T1\;|\;T2\;|\;T3^*\qquad\text{ — Без изменений}\\B\;\triangleq\;T4^+\;|\;T1\;|\;T2\;|\;T3^*\quad\text{ — Получено заменой A}\\C\;\triangleq\;(T1\;|\;T2\;|\;T3*) (T4+\;|\;T1\;|\;T2\;|\;T3*)$$

Возможно, грамматика не стала более понятной, но свойство исключения нетерминалов в ней выполняется. Аналогично доказывается более сильное утверждение: любой регулярный язык может быть задан одним регулярным выражением. В нашем примере таковым является описание категории С, рассматриваемой как начальный символ грамматики.

Теорема высвечивает принципиальное ограничение регулярных языков: они не поддерживают рекурсивную вложенность. Мы видели, что язык программирования, подобный Eiffel, содержит условный оператор, где в качестве выполняемого оператора может быть любой оператор – условный оператор, оператор цикла и любой другой с неограниченной глубиной вложенности. В БНФ можно описать такие ситуации благодаря рекурсивно определяемым продукциям; с регулярными грамматиками этого сделать нельзя.

Зато регулярные грамматики удобны для задания правил описания лексем – первичных элементов языка. Когда нужно описать лексему, состоящую из одного или нескольких символов одного вида, за которыми следует один из трех специальных символов, за которым возможно следует последовательность символов еще одного вида, для таких ситуаций регулярная грамматика – то, что требуется.

Конечные автоматы

За кулисами регулярных выражений стоит математическая теория конечных автоматов. Для первого знакомства с этой теорией, о которой можно многое сказать, удобно воспользоваться визуальной иллюстрацией конечного автомата. Конечный автомат – это граф, с узлами, представляющими состояния автомата, и дугами, помеченными элементами некоторого базисного конечного множества. В нашем примере элементы представляют терминальные символы и имена категорий.

Следующий пример задает синтаксическую структуру квалифицированного вызова метода в Eiffel с возможными аргументами, подобно вызову Line8.extend(new_station):

(рис 2.4) Конечный автомат, распознающий вызов метода

Конечный автомат можно рассматривать как машину, обрабатывающую входную строку символ за символом. Процесс начинается в узле, задающем начальное состояние, затем продолжается, следуя выходящим из узла дугам, если таковые дуги имеются. Из выходящих дуг выбирается та, которая помечена очередным символом входной строки. Следуя дуге, попадаем в узел автомата, в который ведет выбранная дуга. Это называется переходом из одного состояния в другое. На входе x9.f_g(a,a), наш автомат стартует в состоянии 1, входной символ x станет причиной перехода в состояние 2, затем 9 станет причиной перехода в то же самое состояние 2. Символ "точка" переведет автомат в состояние 3, f переведет в 4, подчеркивание и g оставят в 4. Появление круглой открывающей скобки переведет автомат в состояние 5, из которого автомат, обрабатывая список аргументов, будет переходить в состояние 6 и снова возвращаться в 5. Появление закрывающей скобки переведет автомат в заключительное состояние 7, у которого нет выходящих дуг.

Язык, распознаваемый конечным автоматом, – это множество всех строк, на которых автомат, начиная работать в начальном состоянии, переходит в конечное состояние, полностью прочитав строку. Строки Line8.extend (new_station) и x9.f_g(a, a) принимаются нашим автоматом и принадлежат языку, им распознаваемому. Строки не принадлежат языку автомата, если:

автомат достиг состояния, в котором нет дуги, соответствующей следующему входному символу. Для нашего автомата такой может быть строка a.b.c (допустимая в Eiffel, но не допускаемая рассматриваемым автоматом); обработав начальную часть строки a.b, автомат перейдет в состояние 4 и остановится, поскольку в этом состоянии нет дуги, помеченной точкой – очередным символом строки. Заметьте, что отказ будет верен и для заключительного состояния, если входная строка не обработана полностью, например, для строки x.f(a),a;

обработаны все символы входной строки, но автомат не достиг конечного состояния. Примером является строка a, приводящая в состояние 2, которое не является заключительным.

Основная теорема, связывающая регулярные языки и конечные автоматы, утверждает, что любой язык, заданный регулярной грамматикой, распознается конечным автоматом. Верно и обратное утверждение, что доказывает эквивалентность регулярных языков и языков, распознаваемых конечными автоматами. Не доказывая эту теорему, проиллюстрируем ее, построив для нашего автомата регулярную грамматику с языком, определяемым последней категорией:

$$Identifier\;\triangleq\;Letter\;(Letter\;|\;Digit\;|\;Underscore)^*\\Another\_argument\;\triangleq\;\;, \;Identifier\\Argument\_list\;\triangleq\;"("\;Identifier\;Another\_argument^*\;")"\\Feature\_call\;\triangleq\;Identifier\;"."\;Identifier\;[Argument\_list]$$

Вызовы методов, распознаваемые этой грамматикой, являются подмножеством возможных в Eiffel вызовов, где выражения для аргументов допускают, подобно операторам, вложенность, как в вызове x.f(y.h(z.i)). Вышеприведенная лексическая грамматика и связанный с ней конечный автомат не распознают такие вызовы, поскольку аргумент для них может быть только идентификатором. Как только мы выходим за пределы лексем, так сразу требуется вся мощь БНФ. Заметьте, соглашение БНФ-Е для Повторения, включающее возможность появления разделителя, делает более удобным определение категории Argument_list, позволяя определить эту категорию одной продукцией, в правой части которой стоит {Identifier "," …}+.

Вышеприведенное описание автомата является детерминированным, и вот в каком смысле: начальное состояние автомата единственно, и в каждом узле не может быть несколько дуг с одним и тем же приписанным символом. Поэтому в процессе распознавания, проиллюстрированном выше, у автомата на каждом шаге не более одного перехода. Для недетерминированных автоматов это ограничение снимается. Можно, однако, доказать, что оба вида автоматов распознают один и тот же класс языков.

Конечные автоматы обеспечивают основу создания лексических анализаторов, часть компилятора, ответственную за распознавание лексем. Фактически, не представляет особого труда определить конечный автомат по регулярной грамматике, а затем по этому определению построить непосредственно программу, распознающую лексемы. Такая схема используется в лексических анализаторах.

x: SOME_TYPE
        

if c then a + b end