Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE 30
Цепочкой символов (или строкой ) называют произвольную последовательность символов, записанных один за другим. Понятие символа (или буквы) является базовым в теории формальных языков и не нуждается в определении.
Далее цепочки символов будем обозначать греческими буквами: α, β, γ
Итак, цепочка — это последовательность, в которую могут входить любые допус тимые символы. Строка, которую вы сейчас читаете, является примером цепочки, допустимые символы в которой — строчные и заглавные русские буквы, знаки препинания и символ пробела. Но цепочка — это необязательно некоторая ос мысленная последовательность символов. Последовательность «аввв.-аагрьь ,.лл» — тоже пример цепочки символов.
Для цепочки символов важен состав и количество символов в ней, а также поря док символов в цепочке. Один и тот же символ может произвольное число раз входить в цепочку. Поэтому цепочки «а» и «аа», а также «аб» и «ба» — это раз личные цепочки символов. Цепочки символов α и β равны (совпадают), α = β, если они имеют один и тот же состав символов, одно и то же их количество и одинаковый порядок следования символов в цепочке.
Количество символов в цепочке называют длиной цепочки. Длина цепочки сим волов α обозначается как | α |. Очевидно, что если α = β. то и |α| = |β|.
Основной операцией над цепочками символов является операция конкатенации (объединения или сложения) цепочек.
Конкатенация (сложение, объединение) двух цепочек символов — это дописывание второй цепочки в конец первой. Конкатенация цепочек α и β обозначает ся как αβ . Выполнить конкатенацию цепочек просто: например, если α = «аб», а β = «вг», то αβ = «абвг».
Так как в цепочке важен порядок символов, то очевидно, что операция конкате нации не обладает свойством коммутативности, то есть в общем случае α и β такие, что αββα. Также очевидно, что конкатенация обладает свойством ассо циативности, то есть (αβ)γ=α(βγ).
Можно выделить еще две операции над цепочками.
Обращение цепочки — это запись символов цепочки в обратном порядке. Обра щение цепочки α обозначается как α R. Если α = «абвг», то α R = «гвба». Для опе рации обращения справедливо следующее равенство R = R R.
Итерация (повторение) цепочки n раз, где n N, n > 0 — это конкатенация це почки самой с собой n раз. Итерация цепочки n раз обозначается как n. Для операции повторения справедливы следующие равенства : 1 = , 2 = , 3 = , ... и т. д.
Среди всех цепочек символов выделяется одна особенная — пустая цепочка. Пустая цепочка символов — это цепочка, не содержащая ни одного символа. Пустую цепочку здесь везде будем обозначать греческой буквой (в литературе ее иногда обозначают латинской буквой е или греческой ).
Для пустой цепочки справедливы следующие равенства:
В общем случае язык — это заданный набор символов и правил, устанавливаю щих способы комбинации этих символов между собой для записи осмысленных текстов. Основой любого естественного или искусственного языка является ал фавит, определяющий набор допустимых символов языка.
Алфавит — это счетное множество допустимых символов языка. Будем обозна чать это множество символом V. Интересно, что согласно формальному опре делению, алфавит не обязательно должен быть конечным (перечислимым) мно жеством, но реально все существующие языки строятся на основе конечных алфавитов.
Цепочка символов является цепочкой над алфавитом V: (V), если в нее вхо дят только символы, принадлежащие множеству символов V. Для любого алфа вита V пустая цепочка может как являться, так и не являться цепочкой (V). Это условие оговаривается дополнительно.
Если V — некоторый алфавит, то:
Справедливо равенство: V" = V+ {}.
Языком L над алфавитом V: L(V) называется некоторое счетное подмножество цепочек конечной длины из множества всех цепочек над алфавитом V. Из этого определения следуют два вывода: во-первых, множество цепочек языка не обяза но быть конечным; во-вторых, хотя каждая цепочка символов, входящая в язык, обязана иметь конечную длину, эта длина может быть сколь угодно большой и формально ничем не ограничена.
Все существующие языки подпадают под это определение. Большинство реаль ных естественных и искусственных языков содержат бесконечное множество це почек. Также в большинстве языков длина цепочки ничем не ограничена (напри мер, этот длинный текст — пример цепочки символов русского языка). Цепочку символов, принадлежащую заданному языку, часто называют предложением языка, а множество цепочек символов некоторого языка L(V) — множеством предложе ний этого языка.
Для любого языка L(V) справедливо: L(V) V*.
Язык L(V) включает в себя язык L'(V): L'(V) L(V), если L(V): L'(V). Множество цепочек языка L'(V) является подмножеством множества цепочек языка L(V) (или эти множества совпадают). Очевидно, что оба языка должны строится на основе одного и того же алфавита.
Два языка L(V) и L'(V) совпадают (эквивалентны): L'(V) = L(V), если L'(V) L(V) и L(V) L'(V); или, что то же самое: L'(V): L(V) и L(V): L’(V). Множества допустимых цепочек символов для эквивалентных языков должны быть равны.
Два языка L(V) и L'(V) почти эквивалентны: L'(V) L(V), если L'(V){}= L(V){}. Множества допустимых цепочек символов почти эквивалентных языков могут различаться только на пустую цепочку символов.
Итак, каждый язык — это множество цепочек символов над некоторым алфави том. Но кроме алфавита язык предусматривает и задание правил построения до пустимых цепочек, поскольку обычно далеко не все цепочки над заданным алфа витом принадлежат языку. Символы могут объединяться в слова или лексемы — элементарные конструкции языка, на их основе строятся предложения — более сложные конструкции. И те и другие в общем виде являются цепочками симво лов, но предусматривают некоторые правила построения. Таким образом, необ ходимо указать эти правила, или, строго говоря, задать язык.
Язык задать можно тремя способами:
1. Перечислением всех допустимых цепочек языка.
2. Указанием способа порождения цепочек языка (заданием грамматики языка).
3. Определением метода распознавания цепочек языка.
Первый из методов является чисто формальным и на практике не применяется, так как большинство языков содержат бесконечное число допустимых цепочек и перечислить их просто невозможно. Трудно себе представить, чтобы появи лась возможность перечислить, например, множество всех правильных текстов на русском языке или всех правильных программ на языке Pascal. Иногда, для чисто формальных языков, можно перечислить множество входящих в них цепо чек, прибегнув к математическим определениям множеств. Однако этот метод уже стоит ближе ко второму способу.
Например, запись L({0,1}) - {0n1n, n > 0} задает язык над алфавитом V = {0,1}, со держащий все последовательности с чередующимися символами 0 и 1, начинаю щиеся с 0 и заканчивающиеся 1. Видно, что пустая цепочка символов в этот язык не входит. Если изменить условие в этом определении с n > 0 на n>=0, то получим почти эквивалентный язык L'({0,1}), содержащий пустую цепочку.
Второй способ предусматривает некоторое описание правил, с помощью кото рых строятся цепочки языка. Тогда любая цепочка, построенная с помощью этих правил из символов алфавита языка, будет принадлежать заданному языку. На пример, с правилами построения цепочек символов русского языка вы долго и упорно знакомились в средней школе.
Третий способ предусматривает построение некоторого логического устройства (распознавателя) — автомата, который на входе получает цепочку символов, а на выходе выдает ответ: принадлежит или нет эта цепочка заданному языку. На пример, читая этот текст, вы сейчас в некотором роде выступаете в роли распо знавателя (надеюсь, что ответ о принадлежности текста русскому языку будет положительным).
Говоря о любом языке, можно выделить его синтаксис и семантику. Кроме того, трансляторы имеют дело также с лексическими конструкциями (лексемами), ко торые задаются лексикой языка. Ниже даны определения для всех этих понятий.
Синтаксис языка — это набор правил, определяющий допустимые конструкции языка. Синтаксис определяет «форму языка» — задает набор цепочек символов, которые принадлежат языку. Чаще всего синтаксис языка можно задать в виде строгого набора правил, но полностью это утверждение справедливо только для чисто формальных языков. Даже для большинства языков программирования набор заданных синтаксических конструкций нуждается в дополнительных по яснениях, а синтаксис языков естественного общения вполне соответствует об щепринятому мнению о том, что «исключения только подтверждают правило».
Например, любой окончивший среднюю школу может сказать, что строка «3+2» является арифметическим выражением, а «З 2 +» — не является. Правда, не каж дый задумается при этом, что он оперирует синтаксисом алгебры.
Семантика языка — это раздел языка, определяющий значение предложений языка. Семантика определяет «содержание языка» — задает значение для всех допустимых цепочек языка. Семантика для большинства языков определяется неформальными методами (отношения между знаками и тем, что они обозначают, изучаются семиотикой). Чисто формальные языки лишены какого-либо смысла. Возвращаясь к примеру, приведенному выше, и используя семантику алгебры, мы можем сказать, что строка «З + 2» есть сумма чисел 3 и 2, а также то, что «3 + 2 = 5» — это истинное выражение. Однако изложить любому ученику син таксис алгебры гораздо проще, чем ее семантику, хотя в данном случае семанти ку как раз можно определить формально.
Лексика — это совокупность слов (словарный запас) языка. Слово или лексиче ская единица (лексема) языка — это конструкция, которая состоит из элементов алфавита языка и не содержит в себе других конструкций. Иначе говоря, лекси ческая единица может содержать только элементарные символы и не может со держать других лексических единиц.
Лексическими единицами (лексемами) русского языка являются слова русского языка, а знаки препинания и пробелы представляют собой разделители, не обра зующие лексем. Лексическими единицами алгебры являются числа, знаки мате матических операций, обозначения функций и неизвестных величин. В языках программирования лексическими единицами являются ключевые слова, иденти фикаторы, константы, метки, знаки операций; в них также существуют и разде лители (запятые, скобки, точки с запятой и т. д.).
Языки программирования занимают некоторое промежуточное положение меж ду формальными и естественными языками. С формальными языками их объ единяют строгие синтаксические правила, на основе которых строятся предло жения языка. От языков естественного общения в языки программирования пе решли лексические единицы, представляющие основные ключевые слова (чаще всего это слова английского языка, но существуют языки программирования, чьи ключевые слова заимствованы из русского и других языков). Кроме того, из алгебры языки программирования переняли основные обозначения математиче ских операций, что также делает их более понятными человеку.
Для задания языка программирования необходимо решить три вопроса:
Только первые два вопроса полностью или частично удается решить с помощью теории формальных языков.
Первый вопрос решается легко. Определяя алфавит языка, мы автоматически определяем множество допустимых символов. Для языков программирования алфавит — это чаще всего тот набор символов, которые можно ввести с клавиа туры. Основу его составляет младшая половина таблицы международной коди ровки символов (таблицы ASCII), к которой добавляются символы националь ных алфавитов.
Второй вопрос решается в теории формальных языков только частично. Для всех языков программирования существуют правила, определяющие синтаксис языка, но как уже было сказано, их недостаточно для того, чтобы строго опре делить все возможные синтаксические конструкции. Дополнительные ограниче ния накладываются семантикой языка. Эти ограничения оговариваются в не формальной форме для каждого отдельного языка программирования. К таким ограничениям можно отнести необходимость предварительного описания пере менных и функций, необходимость соответствия типов переменных и констант в выражениях, формальных и фактических параметров в вызовах функций и др.
Отсюда следует, что практически все языки программирования, строго говоря, не являются формальными языками. И именно поэтому во всех трансляторах, кроме синтаксического разбора и анализа предложений языка, дополнительно предусмотрен семантический анализ.
Третий вопрос в принципе не относится к теории формальных языков, посколь ку, как уже было сказано, такие языки лишены какого-либо смысла. Для ответа на него нужно использовать другие подходы. В качестве таких подходов можно указать следующие:
Все, кто писал программы, так или иначе обязательно использовали первый под ход. Комментарии в хорошей программе — это и есть изложение ее смысла. По строение блок-схемы, а равно любое другое описание алгоритма программы — это тоже способ изложить смысл программы на другом языке (например, языке графических символов блок-схем алгоритмов, смысл которого, в свою очередь, изложен в соответствующем ГОСТе). Да и документация к программе — тоже способ изложения ее смысла. Но все эти способы ориентированы на человека, которому они, конечно же, более понятны. Однако не существует пока универ сального способа проверить, насколько описание соответствует программе.
Машина же понимает только один язык — язык машинных команд. Но изложить программу на языке машинных команд — задача слишком трудоемкая для чело века, как раз для ее решения и создаются трансляторы.
Второй подход используется при отладке программы. Оценку же результатов выполнения программы при отладке выполняет человек. Любые попытки пору чить это дело машине лишены смысла вне контекста решаемой задачи.
Например, предложение в программе на языке Pascal вида: i:=0; while i=0 do i:=0; может быть легко оценено любой машиной как бессмысленное. Но если в задачу входит обеспечить взаимодействие с другой параллельно выполняемой программой или, например, просто проверить надежность и долговечность про цессора или какой-то ячейки памяти, то это же предложение покажется уже не лишенным смысла.
Некоторые успехи в процессе проверки осмысленности программ достигнуты в рамках систем автоматизации разработки программного обеспечения (CASE-системы). Их подход основан на проектировании сверху вниз — от описания за дачи на языке, понятном человеку, до перевода ее в операторы языка программирования. Но такой подход выходит за рамки возможностей трансляторов, поэто му здесь рассматриваться не будет.
Однако разработчикам компиляторов, так или иначе, приходится решать вопрос о смысле программ. Во-первых, компилятор должен все-таки преобразовать исходную программу в последовательность машинных команд, а для этого ему необходимо иметь представление о том, какая последовательность команд соот ветствует той или иной части исходной программы. Обычно такие последова тельности сопоставляются базовым конструкциям входного языка (далее будет рассмотрено, как это можно сделать). Здесь используется первый подход к изло жению смысла программы. Во-вторых, многие современные компиляторы по зволяют выявить сомнительные с точки зрения смысла места в исходной про грамме — такие, как недостижимые операторы, неиспользуемые переменные, неопределенные результаты функций и т. п. Обычно компилятор указывает та кие места в виде дополнительных предупреждений, которые разработчик может принимать или не принимать во внимание. Для достижения этой цели компиля тор должен иметь представление о том, как программа будет выполняться — используется второй подход. Но в обоих случаях осмысление исходной програм мы закладывает в компилятор его создатель (или коллектив создателей) — то есть человек, который руководствуется неформальными методами (чаще всего, описанием входного языка). В теории формальных языков вопрос о смысле про грамм не решается.
Итак, на основании изложенных положений можно сказать, что возможности трансляторов по проверке осмысленности предложений входного языка сильно ограничены, практически даже равны нулю. Именно поэтому большинство из них в лучшем случае ограничиваются рекомендациями разработчикам по тем местам исходного текста программ, которые вызывают сомнения с точки зрения смысла. Поэтому большинство трансляторов обнаруживает только незначитель ный процент от общего числа смысловых («семантических») ошибок, а следова тельно, подавляющее число такого рода ошибок всегда, к большому сожалению, остается на совести автора программы.
Грамматика — это описание способа построения предложений некоторого язы ка. Иными словами, грамматика — это математическая система, определяющая язык.
Фактически, определив грамматику языка, мы указываем правила порождения цепочек символов, принадлежащих этому языку. Таким образом, грамматика — это генератор цепочек языка. Она относится ко второму способу определения языков — порождению цепочек символов.
Грамматику языка можно описать различными способами; например, грамма тика русского языка описывается довольно сложным набором правил, которые изучают в начальной школе. Но для многих языков (и для синтаксической части языков программирования в том числе) допустимо использовать формальное описание грамматики, построенное на основе системы правил (или продукций).
Правило (или продукция) — это упорядоченная пара цепочек символов ( ). В правилах очень важен порядок цепочек, поэтому их чаще записывают в виде (или =). Такая запись читается как « порождает » или « по опреде лению есть ».
Грамматика языка программирования содержит правила двух типов: первые (определяющие синтаксические конструкции языка) довольно легко поддают ся формальному описанию; вторые (определяющие семантические ограничения языка) обычно излагаются в неформальной форме. Поэтому любое описание (или общепринятый стандарт) языка программирования обычно состоит из двух частей: вначале формально излагаются правила построения синтаксических кон струкций, а потом на естественном языке дается описание семантических пра вил. Естественный язык понятен человеку, пользователю, который будет писать программы на языке программирования; для компилятора же семантические ограничения необходимо излагать в виде алгоритмов проверки правильности про граммы (речь, как уже было сказано выше, не идет о смысле программ, а только лишь о семантических ограничениях на исходный текст). Такой проверкой в компиляторе занимается семантический анализатор — специально для этого раз работанная часть компилятора.
Далее, говоря о грамматиках языков программирования, будем иметь в виду только правила построения синтаксических конструкций языка. Однако следует помнить, что грамматика любого языка программирования в общем случае не ог раничивается только этими правилами.
Язык, заданный грамматикой G, обозначается как L(G).
Две грамматики G и G' называются эквивалентными, если они определяют один и тот же язык: L(G) = L(G'). Две грамматики G и G' называются почти эквива лентными, если заданные ими языки различаются не более чем на пустую цепоч ку символов: L(G) {} = L(G') {}.
Для полного формального определения грамматики кроме правил порождения цепочек языка необходимо задать также алфавит языка.
Формально грамматика G определяется как четверка G(VT,VN,P,S), где:
Множество V = VN VT называют полным алфавитом грамматики G.
Рассмотрим множества VN и VT. Множество терминальных символов VT содер жит символы, которые входят в алфавит языка, порождаемого грамматикой. Как правило, символы из множества VT встречаются только в цепочках правых час тей правил, если же они встречаются в цепочке левой части правила, то обязаны быть и в цепочке правой его части. Множество нетерминальных символов VN содержит символы, которые определяют слова, понятия, конструкции языка. Каж дый символ этого множества может встречаться в цепочках как левой, так и пра вой частей правил грамматики, но он обязан хотя бы один раз быть в левой час ти хотя бы одного правила. Правила грамматики строятся так, чтобы в левой части каждого правила был хотя бы один нетерминальный символ.
Эти два множества не пересекаются: каждый символ может быть либо терми нальным, либо нетерминальным. Ни один символ в алфавите грамматики не может быть нетерминальным и терминальным одновременно. Целевой символ грамматики — это всегда нетерминальный символ.
Во множестве правил грамматики может быть несколько правил, имеющих оди наковые правые части, вида: n. Тогда эти правила объединя ют вместе и записывают в виде: ||n|. Одной строке в такой записи соот ветствует сразу n правил.
Такую форму записи правил грамматики называют формой Бэкуса—Наура. Форма Бэкуса—Наура предусматривает, как правило, также, что нетерминальные сим волы берутся в угловые скобки: < >. Иногда знак «—>» в правилах грамматики заменяют на знак «::=» (что характерно для старых монографий), но это всего лишь незначительные модификации формы записи, не влияющие на ее суть.
Ниже приведен пример грамматики для целых десятичных чисел со знаком:
G({0,1,2,3,4,5,6,7,8,9,-,+},{<число>,<чс>,<цифра>},Р,<число>)
Р:
<число> —> <чс> | +<чc> | -<чс>
<чс> -> <цифра> | <чс><цифра>
<цифра> ->0|1|2|3|4|5|6|7|8|9
Рассмотрим составляющие элементы грамматики G:
Следует отметить, что символ <чс> — это бессмысленное сочетание букв русско го языка, но это обычный нетерминальный символ грамматики, такой же, как и два других. Названия нетерминальных символов не обязаны быть осмысленны ми, это сделано просто для удобства понимания правил грамматики человеком. В принципе в любой грамматике можно полностью изменить имена всех нетерминальных символов, не меняя при этом языка, заданного грамматикой, — точно также, например, в программе на языке Pascal можно изменить имена идентифи каторов, и при этом не изменится смысл программы.
Для терминальных символов это неверно. Набор терминальных символов всегда строго соответствует алфавиту языка, определяемого грамматикой.
Вот, например, та же самая грамматика для целых десятичных чисел со знаком, в которой нетерминальные символы обозначены большими латинскими буквами. (Далее это будет часто применяться в примерах):
G'({0,1,2,3,4,5,6,7,8,9,-,+},(S,T,F},P,S)
Р:
S -> Т | +Т | -Т
Т -> F | TF
F-> 0|1|2|3|4|5|6|7|8|9
Здесь изменилось только множество нетерминальных символов. Теперь VN = {S,T,F}. Язык, заданный грамматикой, не изменился — грамматики G и G' эк вивалентны.
Особенность формальных грамматик в том, что они позволяют определить бес конечное множество цепочек языка с помощью конечного набора правил (конеч но, множество цепочек языка тоже может быть конечным, но даже для простых реальных языков это условие обычно не выполняется). Приведенная выше в примере грамматика для целых десятичных чисел со знаком определяет беско нечное множество целых чисел с помощью 15 правил.
Возможность пользоваться конечным набором правил достигается в такой фор ме записи грамматики за счет рекурсивных правил. Рекурсия в правилах грам матики выражается в том, что один из нетерминальных символов определяется сам через себя. Рекурсия может быть непосредственной (явной) — тогда символ определяется сам через себя в одном правиле, либо косвенной (неявной) — тогда то же самое происходит через цепочку правил.
В рассмотренной выше грамматике G непосредственная рекурсия присутствует в правиле: <чс>-><чс><цифра>, а в эквивалентной ей грамматике G' — в правиле: T->TF.
Чтобы рекурсия не была бесконечной, для участвующего в ней нетерминального символа грамматики должны существовать также и другие правила, которые оп ределяют его, минуя самого себя, и позволяют избежать бесконечного рекурсив ного определения (в противном случае этот символ в грамматике был бы просто не нужен). Такими правилами являются <чс>-><цифра> — в грамматике G и T->F — в грамматике G'.
В теории формальных языков более ничего сказать о рекурсии нельзя. Но, чтобы полнее понять смысл рекурсии, можно прибегнуть к семантике языка — в рас смотренном выше примере это язык целых десятичных чисел со знаком. Рас смотрим его смысл.
Если попытаться дать определение тому, что же является числом, то начать мож но с того, что любая цифра сама по себе есть число. Далее можно заметить, что любые две цифры — это тоже число, затем — три цифры и т. д. Если строить определение числа таким методом, то оно никогда не будет закончено (в матема тике разрядность числа ничем не ограничена). Однако можно заметить, что каж дый раз, порождая новое число, мы просто дописываем цифру справа (посколь ку привыкли писать слева направо) к уже написанному ряду цифр. А этот ряд цифр, начиная от одной цифры, тоже в свою очередь является числом. Тогда определение для понятия «число» можно построить таким образом: «число — это любая цифра, либо другое число, к которому справа дописана любая цифра». Именно это и составляет основу правил грамматик G и G' и отражено во второй строке правил в правилах <чс>-><цифра> | <чс><цифра> и T->F|TF. Другие правила в этих грамматиках позволяют добавить к числу знак (первая строка правил) и дают определение понятию «цифра» (третья строка правил). Они элементарны и не требуют пояснений.
Принцип рекурсии (иногда его называют «принцип итерации», что не меняет сути) — важное понятие в представлении о формальных грамматиках. Так или иначе, явно или неявно рекурсия всегда присутствует в грамматиках любых ре альных языков программирования. Именно она позволяет строить бесконечное множество цепочек языка, и говорить об их порождении невозможно без пони мания принципа рекурсии. Как правило, в грамматике реального языка програм мирования содержится не одно, а целое множество правил, построенных с помо щью рекурсии.
Форма Бэкуса—Наура — удобный с формальной точки зрения, но не всегда дос тупный для понимания способ записи формальных грамматик. Рекурсивные определения хороши для формального анализа цепочек языка, но не удобны с точки зрения человека. Например, то, что правила <чс>—><цифра>|<чс><цифра> отражают возможность для построения числа дописывать справа любое число цифр, начиная от одной, неочевидно и требует дополнительного пояснения.
Но при создании языка программирования важно, чтобы его грамматику пони мали не только те, кому предстоит создавать компиляторы для этого языка, но и пользователи языка — будущие разработчики программ. Поэтому существуют другие способы описания правил формальных грамматик, которые ориентирова ны на большую понятность человеку:
Выше упоминались различные типы грамматик, но не было указано, как и по какому принципу они подразделяются на типы. Для человека языки бывают простые и сложные, но это субъективное мнение, которое зависит от личности человека.
Для компиляторов языки также можно разделить на простые и сложные, но в данном случае существуют жесткие критерии для этого разделения. Как будет показано далее, от того, к какому типу относится тот или иной язык программирования, зависит сложность распознавателя для этого языка. Чем сложнее язык, тем выше вычислительные затраты компилятора на анализ цепочек исходной программы, написанной на этом языке, а следовательно, сложнее сам компиля тор и его структура. Для некоторых типов языков в принципе невозможно по строить компилятор, который бы анализировал исходные тексты на этих языках за приемлемое время на основе ограниченных вычислительных ресурсов (имен но поэтому до сих пор невозможно создавать программы на естественных язы ках, например на русском или английском).
Формальные грамматики классифицируются по структуре их правил. Если все без исключения правила грамматики удовлетворяют некоторой заданной струк туре, то ее относят к определенному типу. Достаточно иметь в грамматике одно правило, не удовлетворяющее требованиям структуры правил, и она уже не по падает в заданный тип.
По классификации Хомского выделяют четыре типа грамматик.
На структуру их правил не накладывается никаких ограничений: для граммати ки вида G(VT,VN,P,S), V = VN VT правила имеют вид: ->, где V+, V*.
Это самый общий тип грамматик. В него подпадают все без исключения фор мальные грамматики, но часть из них, к общей радости, может быть также отне сена и к другим классификационным типам. Дело в том, что грамматики, которые относятся только к типу 0 и не могут быть отнесены к другим типам, являются самыми сложными по структуре.
Практического применения грамматики, относящиеся только к типу 0, не имеют.
В этот тип входят два основных класса грамматик.
Контекстно-зависимые грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: A2->2, где 12V*, A VN, V+
Неукорачивающие грамматики G(VT,VN,P,S), V = VNVT имеют правила вида:
->, где , V+, ||>=||
Структура правил КЗ-грамматик такова, что при построении предложений за данного ими языка один и тот же нетерминальный символ может быть заменен на ту или иную цепочку символов в зависимости от того контекста, в котором он встречается. Именно поэтому эти грамматики называют «контекстно-зависимы ми». Цепочки и 2 в правилах грамматики обозначают контекст ( — левый контекст, а 2 — правый контекст), в общем случае любая из них (или даже обе) может быть пустой. Говоря иными словами, значение одного и того же символа может быть различным в зависимости от того, в каком контексте он встречается.
Неукорачивающие грамматики имеют такую структуру правил, что при построе нии предложений языка, заданного грамматикой, любая цепочка символов мо жет быть заменена на цепочку символов не меньшей длины. Отсюда и название «неукорачивающие».
Доказано, что эти два класса грамматик эквивалентны. Это значит, что для лю бого языка, заданного контекстно-зависимой грамматикой, можно построить неукорачивающую грамматику, которая будет задавать эквивалентный язык, и наоборот: для любого языка, заданного неукорачивающей грамматикой, мож но построить контекстно-зависимую грамматику, которая будет задавать эквива лентный язык.
При построении компиляторов такие грамматики не применяются, поскольку языки программирования, рассматриваемые компиляторами, имеют более про стую структуру и могут быть построены с помощью грамматик других типов.
Контекстно-свободные (КС) грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: A->, где A VN, V+.
Такие грамматики также иногда называют неукорачивающими контекстно-свободными (НКС) грамматиками (видно, что в правой части правила у них должен всегда стоять как минимум один символ).
Существует также почти эквивалентный им класс грамматик — укорачивающие контекстно-свободные (УКС) грамматики G(VT,VN,P,S), V = VNVT ,правила которых могут иметь вид: A->, где A VN, V*.
Разница между этими двумя классами грамматик заключается лишь в том, что в УКС-грамматиках в правой части правил может присутствовать пустая це почка (), а в НКС-грамматиках — нет. Отсюда ясно, что язык, заданный НКС-грамматикой, не может содержать пустой цепочки. Доказано, что эти два класса грамматик почти эквивалентны. В дальнейшем, когда речь будет идти о КС-грамматиках, уже не будет уточняться, какой класс грамматики (УКС или НКС) имеется в виду, если возможность наличия в языке пустой цепочки не имеет принципиального значения.
КС-грамматики широко используются при описании синтаксических конструк ций языков программирования. Синтаксис большинства известных языков про граммирования основан именно на КС-грамматиках, поэтому в данном курсе им уделяется большое внимание.
Внутри типа КС-грамматик кроме классов НКС и УКС выделяют еще целое множество различных классов грамматик, и все они относятся к типу 2. Далее, когда КС-грамматики и КС-языки будут рассматриваться более подробно, на не которые из этих классов грамматик и их характерные особенности будет обраще но особое внимание.
К типу регулярных относятся два эквивалентных класса грамматик: леволинейные и праволинейные.
Леволинейные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила двух видов: А->В или А->, где A,BVN, VT*.
В свою очередь, праволинейные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила тоже двух видов: А-> В или А->, где A,BVN, VT*.
Эти два класса грамматик эквивалентны и относятся к типу регулярных грам матик.
Регулярные грамматики используются при описании простейших конструкций языков программирования: идентификаторов, констант, строк, комментариев и т. д. Эти грамматики исключительно просты и удобны в использовании, поэтому в компиляторах на их основе строятся функции лексического анализа входного языка (принципы их построения будут рассмотрены далее).
Типы грамматик соотносятся между собой особым образом. Из определения типов 2 и 3 видно, что любая регулярная грамматика является КС-грамматикой, но не наоборот. Также очевидно, что любая грамматика может быть отнесена и к типу 0, поскольку он не накладывает никаких ограничений на правила. В то же время существуют укорачивающие КС-грамматики (тип 2), которые не являют ся ни контекстно-зависимыми, ни неукорачивающими (тип 1), поскольку могут содержать правила вида «А->», недопустимые в типе 1. В целом можно сказать, что сложность грамматики обратно пропорциональна тому максимально воз можному номеру типа, к которому может быть отнесена грамматика. Граммати ки, которые относятся только к типу 0, являются самыми сложными, а грамма тики, которые можно отнести к типу 3 — самыми простыми.
Языки классифицируются в соответствии с типами грамматик, с помощью кото рых они заданы. Причем, поскольку один и тот же язык в общем случае может быть задан сколь угодно большим количеством грамматик, которые могут отно ситься к различным классификационным типам, то для классификации самого языка среди всех его грамматик всегда выбирается грамматика с максимально возможным классификационным типом. Например, если язык L может быть за дан грамматиками G1 и G2, относящимися к типу 1 (контекстно-зависимые), грамматикой G3, относящейся к типу 2 (контекстно-свободные), и грамматикой G4, относящейся к типу 3 (регулярные), то сам язык должен быть отнесен к типу 3 и является регулярным языком.
От классификационного типа языка зависит не только то, с помощью, какой грамматики можно построить предложения этого языка, но также и то, насколь ко сложно распознать эти предложения. Распознать предложения — значит, по строить распознаватель для языка (третий способ задания языка). Сами распо знаватели, их структура и классификация будут рассмотрены далее, здесь же можно указать, что сложность распознавателя языка напрямую зависит от клас сификационного типа, к которому относится язык.
Сложность языка убывает с возрастанием номера классификационного типа языка. Самыми сложными являются языки типа 0, самыми простыми — языки типа 3.
Согласно классификации грамматик, существуют также четыре типа языков.
Это самые сложные языки, которые могут быть заданы только грамматикой, от носящейся к типу 0. Для распознавания цепочек таких языков требуются вычис лители, равномощные машине Тьюринга. Поэтому можно сказать, что если язык относится к типу 0, то для него невозможно построить компилятор, который гарантированно выполнял бы разбор предложений языка за ограниченное время на основе ограниченных вычислительных ресурсов.
К сожалению, практически все естественные языки общения между людьми, строго говоря, относятся именно к этому типу языков. Дело в том, что структура и значение фразы естественного языка может зависеть не только от контекста данной фразы, но и от содержания того текста, где эта фраза встречается. Одно и то же слово в естественном языке может не только иметь разный смысл в зави симости от контекста, но и играть различную роль в предложении. Именно по этому столь велики сложности в автоматизации перевода текстов, написанных на естественных языках, а также отсутствуют (и видимо, никогда не появятся) компиляторы, которые бы воспринимали программы на основе таких языков.
Далее языки с фразовой структурой рассматриваться не будут.
Тип 1 — второй по сложности тип языков. В общем случае время на распознава ние предложений языка, относящегося к типу 1, экспоненциально зависит от длины исходной цепочки символов.
Языки и грамматики, относящиеся к типу 1, применяются в анализе и переводе текстов на естественных языках. Распознаватели, построенные на их основе, по зволяют анализировать тексты с учетом контекстной зависимости в предложе ниях входного языка (но они не учитывают содержание текста, поэтому в общем случае для точного перевода с естественного языка все же требуется вмешатель ство человека). На основе таких грамматик может выполняться автоматизиро ванный перевод с одного естественного языка на другой, ими могут пользоваться сервисные функции проверки орфографии и правописания в языковых процес сорах.
В компиляторах КЗ-языки не используются, поскольку языки программирова ния имеют более простую структуру, поэтому здесь они подробно не рассматри ваются.
КС-языки лежат в основе синтаксических конструкций большинства современ ных языков программирования, на их основе функционируют некоторые до вольно сложные командные процессоры, допускающие управляющие команды цикла и условия. Эти обстоятельства определяют распространенность данного класса языков.
В общем случае время на распознавание предложений языка, относящегося к типу 1, полиномиально зависит от длины исходной цепочки символов (в зависи мости от класса языка это либо кубическая, либо квадратичная зависимость).
Однако среди КС-языков существует много классов языков, для которых эта за висимость линейна. Многие языки программирования можно отнести к одному из таких классов.
КС-языки подробно рассматриваются в главе «Контекстно-свободные языки» данного учебного пособия.
Регулярные языки — самый простой тип языков. Наверное, поэтому они явля ются самым распространенным и широко используемым типом языков в облас ти вычислительных систем. Время на распознавание предложений регулярного языка линейно зависит от длины исходной цепочки символов.
Как уже было сказано выше, регулярные языки лежат в основе простейших кон струкций языков программирования (идентификаторов, констант и т. п.), кро ме того, на их основе строятся многие мнемокоды машинных команд (языки ассемблеров), а также командные процессоры, символьные управляющие коман ды и другие подобные структуры.
Регулярные языки — очень удобное средство. Для работы с ними можно исполь зовать регулярные множества и выражения, конечные автоматы. Регулярные языки подробно рассматриваются в следующей главе учебного пособия.
Классификация языков идет от простого к сложному. Если мы имеем дело с ре гулярным языком, то можно утверждать, что он также является и контекстно-свободным, и контекстно-зависимым, и даже языком с фразовой структурой. В то же время известно, что существуют КС-языки, которые не являются регу лярными, и существуют КЗ-языки, которые не являются ни регулярными, ни контекстно-свободными.
Далее приводятся примеры некоторых языков указанных типов.
Рассмотрим в качестве первого примера ту же грамматику для целых десятич ных чисел со знаком
G({0,1,2,3,4,5,6,7,8,9,-,+},(S,T,F},P,S)
Р:
S -> Т | +Т | -Т
Т -> F | TF
F-> 0|1|2|3|4|5|6|7|8|9
По структуре своих правил данная грамматика G относится к контекстно-сво бодным грамматикам (тип 2). Конечно, ее можно отнести и к типу 0, и к типу 1, но максимально возможным является именно тип 2, поскольку к типу 3 эту грамматику отнести никак нельзя: строка T->F | TF содержит правило T->TF, которое недопустимо для типа 3, и, хотя все остальные правила этому типу соот ветствует, одного несоответствия достаточно.
Для каждого языка программирования (как, наверное, и для многих других язы ков) важно не только уметь построить текст программы на этом языке, но и оп ределить принадлежность имеющегося текста к данному языку. Именно эту задачу решают компиляторы в числе прочих задач (компилятор должен не толь ко распознать исходную программу, но и построить эквивалентную ей результи рующую программу). В отношении исходной программы компилятор выступает как распознаватель, а человек, создавший программу на некотором языке, высту пает в роли генератора цепочек этого языка.
Распознаватель (или разборщик) — это специальный алгоритм, который позво ляет определить принадлежность цепочки символов некоторому языку. Задача распознавателя заключается в том, чтобы на основании исходной цепочки дать ответ, принадлежит ли она заданному языку или нет. Распознаватели, как было сказано выше, представляют собой один из способов определения языка.
В общем виде распознаватель можно отобразить в виде условной схемы, пред ставленной на рис. 9.5.
Рис. 9.5. Условная схема распознавателя
Следует подчеркнуть, что представленный рисунок — всего лишь условная схе ма, отображающая работу алгоритма распознавателя. Ни в коем случае не стоит искать подобного устройства в составе компьютера. Распознаватель, являющийся частью компилятора, представляет собой часть программного обеспечения ком пьютера.
Как видно из рисунка, распознаватель состоит из следующих основных компо нентов:
Распознаватель работает с символами своего алфавита — алфавита распознава теля. Алфавит распознавателя конечен. Он включает в себя все допустимые сим волы входных цепочек, а также некоторый дополнительный алфавит символов, которые могут обрабатываться УУ и храниться в рабочей памяти распознава теля.
В процессе своей работы распознаватель может выполнять некоторые элемен тарные операции, такие как чтение очередного символа из входной цепочки, сдвиг входной цепочки на заданное количество символов (вправо или влево), доступ к рабочей памяти для чтения или записи информации, преобразование информации в памяти, изменение состояния УУ. То, какие конкретно операции должны выполняться в процессе работы распознавателя, определяется в УУ.
Распознаватель работает по шагам или тактам. В начале такта, как правило, счи тывается очередной символ из входной цепочки, и в зависимости от этого симво ла УУ определяет, какие действия необходимо выполнить. Вся работа распозна вателя состоит из последовательности тактов. В начале каждого такта состояние распознавателя определяется его конфигурацией. В процессе работы конфигура ция распознавателя меняется.
Конфигурация распознавателя определяется следующими параметрами:
Для распознавателя всегда задается определенная конфигурация, которая счи тается начальной конфигурацией. В начальной конфигурации считывающая головка обозревает первый символ входной цепочки, УУ находится в заданном начальном состоянии, а внешняя память либо пуста, либо содержит строго опре деленную информацию.
Кроме начального состояния для распознавателя задается одна или несколько конечных конфигураций. В конечной конфигурации считывающая головка, как правило, находится за концом исходной цепочки (часто для распознавателей вводят специальный символ, обозначающий конец входной цепочки).
Распознаватель допускает входную цепочку символов , если, находясь в началь ной конфигурации и получив на вход эту цепочку, он может проделать последо вательность шагов, заканчивающуюся одной из его конечных конфигураций.
Формулировка «может проделать последовательность шагов» более точна, чем прямое указание «проделает последовательность шагов», так как для многих распознавателей при одной и той же входной цепочке символов из начальной конфигурации могут быть допустимы различные последовательности шагов, не все из которых ведут к конечной конфигурации.
Язык, определяемый распознавателем, — это множество всех цепочек, которые допускает распознаватель.
Далее в главах этого пособия рассмотрены конкретные типы распознавателей для различных типов языков. Но все, что было сказано здесь, относится ко всем без исключения типам распознавателей для всех типов языков.
Распознаватели можно классифицировать в зависимости от вида составляющих их компонентов: считывающего устройства, устройства управления (УУ) и внеш ней памяти.
По видам считывающего устройства распознаватели могут быть двусторонние и односторонние.
Односторонние распознаватели допускают перемещение считывающей головки по ленте входных символов только в одном направлении. Это значит, что на каж дом шаге работы распознавателя считывающая головка может либо переместить ся по ленте символов на некоторое число позиций в заданном направлении, либо остаться на месте. Поскольку все языки программирования подразумевают нота цию чтения исходной программы «слева направо», то так же работают и все рас познаватели. Поэтому, когда говорят об односторонних распознавателях, то пре жде всего имеют в виду левосторонние, которые читают исходную цепочку слева направо и не возвращаются назад к уже прочитанной части цепочки.
Двусторонние распознаватели допускают, что считывающая головка может пе ремещаться относительно ленты входных символов в обоих направлениях: как вперед, от начала ленты к концу, так и назад, возвращаясь к уже прочитанным символам.
По видам устройства управления распознаватели бывают детерминированные и недетерминированные.
Распознаватель называется детерминированным в том случае, если для каждой допустимой конфигурации распознавателя, которая возникла на некотором шаге его работы, существует единственно возможная конфигурация, в которую распо знаватель перейдет на следующем шаге работы.
В противном случае распознаватель называется недетерминированным. Неде терминированный распознаватель может иметь такую допустимую конфигу рацию, для которой существует некоторое конечное множество конфигураций, возможных на следующем шаге работы. Достаточно иметь хотя бы одну такую 'конфигурацию, чтобы распознаватель был недетерминированным.
По видам внешней памяти распознаватели бывают следующих типов:
У распознавателей без внешней памяти эта память полностью отсутствует. В про цессе их работы используется только конечная память устройства управления, доступ к внешней памяти не выполняется.
Для распознавателей с ограниченной внешней памятью размер внешней памяти ограничен в зависимости от длины исходной цепочки символов. Эти ограниче ния могут налагаться некоторой зависимостью объема памяти от длины цепоч ки — линейной, полиномиальной, экспоненциальной и т. д. Кроме того, для та ких распознавателей может быть указан способ организации внешней памяти — стек, очередь, список и т. п.
Распознаватели с неограниченной внешней памятью предполагают, что для их работы может потребоваться внешняя память неограниченного объема (как пра вило, вне зависимости от длины входной цепочки). У таких распознавателей предполагается память с произвольным методом доступа.
Вместе эти три составляющих позволяют организовать общую классификацию распознавателей. Например, в этой классификации возможен такой тип: «дву сторонний недетерминированный распознаватель с линейно ограниченной сте ковой памятью».
Тип распознавателя в классификации определяет сложность создания такого распознавателя, а следовательно, сложность разработки соответствующего про граммного обеспечения для компилятора. Чем выше в классификации стоит рас познаватель, тем сложнее создавать алгоритм, обеспечивающий его работу. Раз рабатывать двусторонние распознаватели сложнее, чем односторонние. Можно заметить, что недетерминированные распознаватели по сложности выше детер минированных. Зависимость затрат на создание алгоритма от типа внешней па мяти также очевидна.
Как было показано в предыдущей главе, классификация распознавателей (вид входящих в состав распознавателя компонентов) определяет сложность алгорит ма работы распознавателя. Но сложность распознавателя также напрямую связа на с типом языка, входные цепочки которого может принимать (допускать) рас познаватель.
Выше было определено четыре основных типа языков. Доказано, что для каждого из этих типов языков существует свой тип распознавателя с определенным со ставом компонентов и, следовательно, с заданной сложностью алгоритма работы.
Для языков с фразовой структурой (тип 0) необходим распознаватель, равномощный машине Тьюринга — недетерминированный двусторонний автомат, имею щий неограниченную внешнюю память. Поэтому для языков данного типа нель зя гарантировать, что за ограниченное время на ограниченных вычислительных ресурсах распознаватель завершит работу и примет решение о том, принадлежит или не принадлежит входная цепочка заданному языку. Отсюда можно заклю чить, что практического применения языки с фразовой структурой не имеют (и не будут иметь), а потому далее они не рассматриваются.
Для контекстно-зависимых языков (тип 1) распознавателями являются двусто ронние недетерминированные автоматы с линейно ограниченной внешней памя тью. Алгоритм работы такого автомата в общем случае имеет экспоненциальную сложность — количество шагов (тактов), необходимых автомату для распознава ния входной цепочки, экспоненциально зависит от длины этой цепочки. Следо вательно, и время, необходимое на разбор входной цепочки по заданному алго ритму, экспоненциально зависит от длины входной цепочки символов.
Такой алгоритм распознавателя уже может быть реализован в программном обес печении компьютера — зная длину входной цепочки, всегда можно сказать, за какое максимально возможное время будет принято решение о принадлежности цепочки данному языку и какие вычислительные ресурсы для этого потребуют ся. Однако экспоненциальная зависимость времени разбора от длины цепочки существенно ограничивает применение распознавателей для контекстно-зависи мых языков. Как правило, такие распознаватели применяются для автоматизи рованного перевода и анализа текстов на естественных языках, когда временные ограничения на разбор текста несущественны (следует также напомнить, что, по скольку естественные языки более сложны, чем контекстно-зависимый тип, то после такой обработки часто требуется вмешательство человека). В компилято рах для анализа текстов на различных языках программирования контекстно-за висимые распознаватели не применяются, поскольку скорость работы компиля тора имеет существенное значение, а синтаксический разбор текста программы можно выполнять в рамках более простого, контекстно-свободного типа языков.
Поэтому в рамках этого учебного пособия контекстно-зависимые языки также не рассматриваются.
Для контекстно-свободных языков (тип 2) распознавателями являются односто ронние недетерминированные автоматы с магазинной (стековой) внешней па мятью — МП-автоматы. При простейшей реализации алгоритма работы такого автомата он имеет экспоненциальную сложность, однако путем некоторых усо вершенствований алгоритма можно добиться полиномиальной (кубической) за висимости времени, необходимого па разбор входной цепочки, от длины этой цепочки. Следовательно, можно говорить о полиномиальной сложности распо знавателя для КС-языков.
Среди всех КС-языков можно выделить класс детерминированных КС-языков, распознавателями для которых являются детерминированные автоматы с магазинной (стековой) внешней памятью — ДМП-автоматы. Эти языки обладают свойством однозначности — доказано, что для любого детерминированного КС-языка всегда можно построить однозначную грамматику. Кроме того, для таких языков существует алгоритм работы распознавателя с квадратичной сложно стью. Поскольку эти языки являются однозначными, именно они представляют наибольший интерес для построения компиляторов.
Более того, среди всех детерминированных КС-языков существуют такие классы языков, для которых возможно построить линейный распознаватель — распозна ватель, у которого время принятия решения о принадлежности цепочки языку имеет линейную зависимость от длины цепочки. Синтаксические конструкции практически всех существующих языков программирования могут быть отнесе ны к одному из таких классов языков. Это обстоятельство очень важно для раз работки современных быстродействующих компиляторов. Поэтому в главе, по священной КС-языкам, в первую очередь будет уделено внимание именно таким классам этих языков.
Тем не менее, следует помнить, что только синтаксические конструкции языков программирования допускают разбор с помощью распознавателей КС-языков. Сами языки программирования, как уже было сказано, не могут быть полностью отнесены к типу КС-языков, поскольку предполагают некоторую контекстную зависимость в тексте исходной программы (например, такую, как необходимость предварительного описания переменных). Поэтому кроме синтаксического раз бора практически все компиляторы предполагают дополнительный семантиче ский анализ текста исходной программы. Этого можно было бы избежать, если построить компилятор на основе контекстно-зависимого распознавателя, но ско рость работы такого компилятора была бы недопустима низка, поскольку время разбора в таком варианте будет экспоненциально зависеть от длины исходной программы. Комбинация из распознавателя КС-языка и дополнительного семан тического анализатора является более эффективной с точки зрения скорости разбора исходной программы.
Для регулярных языков (тип 3) распознавателями являются односторонние неде терминированные автоматы без внешней памяти — конечные автоматы (КА). Это очень простой тип распознавателя, который всегда предполагает линейную зависимость времени на разбор входной цепочки от ее длины. Кроме того, конеч ные автоматы имеют важную особенность: любой недетерминированный КА всегда может быть преобразован в детерминированный. Это обстоятельство су щественно упрощает разработку программного обеспечения, обеспечивающего функционирование распознавателя.
Простота и высокая скорость работы распознавателей определяют широкую об ласть применения регулярных языков.
В компиляторах распознаватели на основе регулярных языков используются для лексического анализа текста исходной программы — выделения в нем про стейших конструкций языка, таких как идентификаторы, строки, константы и т. п. Это позволяет существенно сократить объем исходной информации и упрощает синтаксический разбор программы. Более подробно взаимодействие лексическо го и синтаксического анализаторов текста программы рассмотрено дальше, в гла ве, посвященной структуре компилятора. На основе распознавателей регулярных языков функционируют ассемблеры — компиляторы с языков ассемблера (мне мокода) в язык машинных команд.
Кроме компиляторов регулярные языки находят применение еще во многих областях, связанных с разработкой программного обеспечения вычислительных систем. На их основе функционируют многие командные процессоры как в сис темном, так и в прикладном программном обеспечении. Для регулярных языков существуют развитые, математически обоснованные механизмы, которые позво ляют облегчить создание распознавателей. Они положены в основу существую щих разнообразных программных средств, которые позволяют автоматизировать этот процесс.
Грамматики и распознаватели — два независимых метода, которые реально мо гут быть использованы для определения какого-либо языка. Однако при разра ботке компилятора для некоторого языка программирования возникает задача, которая требует связать между собой эти методы задания языков.
Разработчики компилятора всегда имеют дело с уже определенным языком программирования. Грамматика для синтаксических конструкций этого языка из вестна. Она, как правило, четко описана в стандарте языка, и хотя форма опи сания может быть произвольной, ее всегда можно преобразовать к требуемому виду (например, к форме Бэкуса—Наура или к форме описания с использованием метасимволов). Задача разработчиков заключается в том, чтобы построить рас познаватель для заданного языка, который затем будет основой синтаксического анализатора в компиляторе.
Таким образом, задача разбора в общем виде заключается в следующем: на осно ве имеющейся грамматики некоторого языка построить распознаватель для это го языка. Заданная грамматика и распознаватель должны быть эквивалентны, то есть определять один и тот же язык (часто допускается, чтобы они были почти эквивалентны, поскольку пустая цепочка во внимание обычно не принимается).
Задача разбора в общем виде может быть решена не для всех типов языков. Но как было сказано выше, разработчиков компиляторов интересуют, прежде всего, контекстно-свободные и регулярные языки. Для данных типов языков доказано, что задача разбора для них разрешима. Более того, для них найдены формальные методы ее решения. Описанию и обоснованию именно методов решения задачи разбора и будет посвящена большая часть материала последующих глав.
Поскольку языки программирования не являются чисто формальными языками и несут в себе некоторый смысл (семантику), то задача разбора для создания ре альных компиляторов понимается несколько шире, чем она формулируется для чисто формальных языков. Компилятор должен не просто дать ответ, принадле жит или нет входная цепочка символов заданному языку, но и определить ее смысловую нагрузку. Для этого необходимо выявить те правила грамматики, на основании которых цепочка была построена. Фактически работа распознавате лей в составе компиляторов сводится к построению в том или ином виде дерева разбора входной цепочки. Затем уже это дерево разбора используется компиля тором для синтеза результирующего кода.
Кроме того, если входная цепочка символов не принадлежит заданному языку — исходная программа содержит ошибку, — разработчику программы не интересно просто узнать сам факт наличия ошибки. В данном случае задача разбора также расширяется: распознаватель в составе компилятора должен не только устано вить факт присутствия ошибки во входной программе, но и по возможности оп ределить тип ошибки и то место в цепочке символов, где она встречается.
Конечным автоматом (КА) называют пятерку следующего вида:
M(Q,V,,q0,F),
где
КА называют полностью определенным, если в каждом его состоянии сущест вует функция перехода для всех возможных входных символов, то есть
aV, qQ (a,q) = R,R Q.
Работа конечного автомата представляет собой последовательность шагов (или тактов). На каждом шаге работы автомат находится в одном из своих состояний Q,(в текущем состоянии), на следующем шаге он может перейти в другое состоя ние или остаться в текущем состоянии. То, в какое состояние автомат перейдет на следующем шаге работы, определяет функция переходов . Она зависит не только от текущего состояния, но и от символа из алфавита V, поданного на вход автомата. Когда функция перехода допускает несколько следующих состояний автомата, то КА может перейти в любое из этих состояний. В начале работы ав томат всегда находится в начальном состоянии q0. Работа КА продолжается до тех пор, пока на его вход поступают символы из входной цепочки V+.
Видно, что конфигурацию КА на каждом шаге работы можно определить в виде (q,,n), где q — текущее состояние автомата, qQ; — цепочка входных симво лов, V+; n — положение указателя в цепочке символов, n N {0}, n || (N — множество натуральных чисел). Конфигурация автомата на следующем шаге — это (q',,n+l), если q' (a,q) и символ a V находится в позиции n+1 цепочки . Начальная конфигурация автомата: (q0,,0); заключительная конфигурация ав томата: (f,,n), fQ, n = ||, она является конечной конфигурацией, если f F.
КА M(Q,V,,q0,F) принимает цепочку символов V+, если, получив на вход эту цепочку, он из начального состояния q0 может перейти в одно из конечных со стояний f F. В противном случае КА не принимает цепочку символов.
Язык L(M), заданный КА M(Q,V,,q0,F), — это множество всех цепочек симво лов, которые принимаются этим автоматом. Два КА эквивалентны, если они за дают один и тот же язык.
Таким образом, КА является распознавателем для формальных языков. Далее будет показано, что КА — это распознаватели для регулярных языков.
КА часто представляют в виде диаграммы или графа переходов автомата.
Граф переходов КА — это направленный помеченный граф, с символами состоя ний КА в вершинах, в котором есть дуга (p,q) p,q Q , помеченная символом aV, если в КА определена (а,р) и q (a,p). Начальное и конечные состояния авто мата на графе состояний помечаются специальным образом (начальное состояние — дополнительной пунктирной линией, конечное состоя ние — дополнительной сплошной линией).
Рассмотрим конечный автомат
M({H, A, B, S},{a, b},, H,{S}); : (Н, b) = В, (В, а) = А, (A,b) = {B,S}.
Ниже на рис. 10.1 приведен пример графа состояний для этого КА.
Рис. 10.1. Граф переходов недетерминированного конечного автомата
Для моделирования работы КА его удобно привести к полностью определенно му виду, чтобы исключить ситуации, из которых нет переходов по входным сим волам. Для этого в КА добавляют еще одно состояние, которое можно условно назвать «ошибка». На это состояние замыкают все неопределенные переходы, а все переходы из самого состояния «ошибка» замыкают на него же.
Если преобразовать подобным образом рассмотренный выше автомат М, то по лучим полностью определенный автомат: M({H, A, B, E, S},{a, b},, H,{S}); ; (Н, a) = E, (Н, b) = В, (В, а) = А, (В, b) = E, (A, a) = {E}, (A,b) = {B,S}, (E, a) = {E}, (E, b) = {E}, (S, a) = {E}, (S, b) = {E}.
Состояние Е как раз соответствует состоянию «ошиб ка». Граф переходов этого КА представлен на рис. 10.2.
Рис. 10.2. Граф переходов полностью определенного недетерминированного конечного автомата
Конечный автомат M(Q,V,,q0,F) называют детерминированным конечным авто матом (ДКА), если в каждом из его состояний для любого входного символа функ ция перехода содержит не более одного состояния: a V, q Q: либо (a,q) = {r}, r Q, либо (a,q) = .
В противном случае конечный автомат называют недетерминированным.
ДКА может быть задан в виде пятерки:
M(Q,V,,q0,F)
где Q — конечное множество состояний автомата; V — конечное множество до пустимых входных символов; — функция переходов, отображающая VQ в множество Q: (a,q) = r, a V, q,rQ; q0 — начальное состояние автомата Q, q0Q , F — непустое множество конечных состояний автомата, F Q , F.
Если функция переходов ДКА определена для каждого состояния автомата, то автомат называется полностью определенным ДКА: a V, q Q: либо (a,q) = r, r Q.
Моделировать работу ДКА существенно проще, чем работу произвольного КА.
Доказано, что для любого КА можно построить эквивалентный ему ДКА. По этому используемый произвольный КА стремятся преобразовать в ДКА. При построении компиляторов чаще всего используют полностью определенный ДКА.
Контекстно-свободными (КС) называются языки, определяемые грамматиками типа G(VT,VN,P,S), в которых правила Р имеют вид: А-> , где A VN и V*, V=VT VN.
Распознавателями КС-языков служат автоматы с магазинной памятью (МП-ав томаты).
В общем виде МП-автомат можно определить следующим образом:
R(Q,V,Z, ,q0, z0,F),
где Q — множество состояний автомата; V — алфавит входных символов автома та; Z — специальный конечный алфавит магазинных символов автомата (обычно он включает в себя алфавиты терминальных и нетерминальных символов грам матики), VZ; — функция переходов автомата, которая отображает множество Q(V{})Z на конечное множество подмножеств P(Q Z*); q0Q — начальное состояние автомата; z0Z — начальный символ магазина; FQ — множество ко нечных состояний.
МП-автомат в отличие от обычного КА имеет стек (магазин), в который можно помещать специальные «магазинные» символы (обычно это терминальные и не терминальные символы грамматики языка). Переход из одного состояния в дру гое зависит не только от входного символа, но и от одного или нескольких верх них символов стека. Таким образом, конфигурация автомата определяется тремя параметрами: состоянием автомата, текущим символом входной цепочки (поло жением указателя в цепочке) и содержимым стека.
МП-автомат условно можно представить в виде схемы на рис. 11.1.
Рис. 11.1. Общая условная схема автомата с магазинной памятью (МП-автомата)
Конфигурация МП-автомата описывается в виде тройки (q, ) Q V* Z*, кото рая определяет текущее состояние автомата q, цепочку еще непрочитанных сим волов на входе автомата и содержимое магазина (стека) . Вместо в конфи гурации можно указать пару ( n), где V* — вся цепочка входных символов, a n N{0}, n 0 — положение считывающего указателя в цепочке.
Тогда один такт работы автомата можно описать в виде (q,a,z) (q', , ), если (q', )(q,a,z), где q,q' Q, aV{}, V*, z Z {}, Z*. При выполнении такта (перехода) из стека удаляется верхний символ, соответствующий условию перехода, и добавляется цепочка, соответствующая правилу перехода. Первый символ цепочки становится верхушкой стека. Допускаются переходы, при кото рых входной символ игнорируется (и тем самым он будет входным символом при следующем переходе). Эти переходы (такты) называются переходами (-так тами). Аналогично, автомат не обязательно должен извлекать символ из стека — когда z=, этого не происходит.
МП-автомат называется недетерминированным, если из одной и той же его конфигурации возможен более чем один переход.
Начальная конфигурация МП-автомата, очевидно, определяется как (q0, ,z0), V*. Множество конечных конфигураций автомата — (q, , ), q F, Z*.
МП-автомат допускает (принимает) цепочку символов, если, получив эту цепоч ку на вход, он может перейти в одну из конечных конфигураций, — когда при окончании цепочки автомат находится в одном из конечных состояний, а стек содержит некоторую определенную цепочку. Тогда входная цепочка принимает ся (после окончания цепочки автомат может сделать произвольное количество -переходов). Иначе цепочка символов не принимается.
Язык, определяемый МП-автоматом, — это множество всех цепочек символов, которые допускает данный автомат. Язык, определяемый МП-автоматом R, обо значается как L(R). Два МП-автомата называются эквивалентными, если они определяют один и тот же язык. Если два МП-автомата R1 и R2 определяют один и тот же язык, это записывается как L(R1) = L(R2).
МП-автомат допускает цепочку символов с опустошением магазина, если при окончании разбора цепочки автомат находится в одном из конечных состояний, а стек пуст — конфигурация (q, , ), q F. Если язык задан МП-автоматом R, который допускает цепочки с опустошением стека, это обозначается так: L(R). Для любого МП-автомата всегда можно построить эквивалентный ему МП-ав томат, допускающий цепочки заданного языка с опустошением стека. То есть МП-автомата R: МП-автомат R', такой что L(R) = L (R').
Кроме обычного МП-автомата существует также понятие расширенного МП-ав томата.
Расширенный МП-автомат может заменять цепочку символов конечной длины в верхней части стека на другую цепочку символов конечной длины. В отличие от обычного МП-автомата, который на каждом такте работы может изымать из сте ка только один символ, расширенный МП-автомат может изымать за один такт сразу некоторую цепочку символов, находящуюся на вершине стека. Функция переходов для расширенного МП-автомата отображает множество Q (V{})Z* на конечное множество подмножеств P(QZ*).
Доказано, что для любого расширенного МП-автомата всегда можно построить эквивалентный ему обычный МП-автомат (обратное утверждение очевидно, так как любой обычный МП-автомат является и расширенным МП-автоматом). Та ким образом, классы МП-автоматов и расширенных МП-автоматов эквивалент ны и задают один и тот же тип языков.
МП-автомат называется детерминированным, если из одной и той же его конфигурации возможно не более одного перехода в следующую конфигурацию.
Формально для детерминированного МП-автомата R(Q,V,Z, ,q0, z0,F), функция переходов может q Q, aV, z Z иметь один из следующих трех видов:
1. (q,a,z) содержит один элемент: (q,a,z) = {(q',)}, Z* и (q, ,z) = .
2. (q,a,z) = и (q, ,z) содержит один элемент: (q, ,z) = {(q', )}, Z*.
3. (q,a,z) = и (q, ,z) =.
Класс ДМП-автоматов и соответствующих им языков значительно уже, чем весь класс МП-автоматов и КС-языков. В отличие от обычного конечного автомата, не для каждого МП-автомата можно построить эквивалентный ему ДМП-авто-мат. Иными словами, в общем случае невозможно преобразовать недетермини рованный МП-автомат в детерминированный.
Детерминированные МП-автоматы (ДМП-автоматы) определяют очень важный класс среди всех КС-языков, называемый детерминированными КС-языками. Доказано, что все языки, принадлежащие к классу детерминированных КС-язы ков, могут быть построены с помощью однозначных КС-грамматик. Поскольку однозначность — это важное и обязательное требование в грамматике любого язы ка программирования, ДМП-автоматы представляют особый интерес для созда ния компиляторов. Синтаксический распознаватель цепочек любого языка про граммирования может быть построен на основе ДМП-автомата.
Кроме того, доказано, что для любого ДМП-автомата всегда можно построить эквиьалентный ему ДМП-автомат, который будет учитывать входную цепочку до конца — не допускать бесконечной последовательности -переходов по завер шении цепочки. Это значительно облегчает моделирование работы ДМП-автоматов.
Все без исключения синтаксические конструкции языков программирования за даются с помощью однозначных КС-грамматик (неоднозначность, конечно же, ни в одном компиляторе недопустима). Синтаксические структуры этих языков относятся к классу детерминированных КС-языков и могут распознаваться с по мощью ДМП-автоматов. Поэтому большинство распознавателей, которые будут рассмотрены далее, относятся к классу детерминированных КС-языков.
Распознаватели с возвратом — это самый примитивный тип распознавателей для КС-языков. Логика их работы основана на моделировании недетерминированно го МП-автомата.
Поскольку моделируется недетерминированный МП-автомат (который в общем виде не преобразуется в детерминированный), то на некотором шаге работы мо делирующего алгоритма возможно возникновение нескольких допустимых сле дующих состояний автомата. В таком случае существуют два варианта реализа ции алгоритма.
В первом варианте на каждом шаге работы алгоритм должен запоминать все воз можные следующие состояния МП-автомата, выбирать одно из них, переходить в это состояние и действовать так до тех пор, пока либо не будет достигнуто ко нечное состояние автомата, либо автомат не перейдет в такую конфигурацию, когда следующее состояние будет не определено. Если достигнуто одно из ко нечных состояний — входная цепочка принята, работа алгоритма завершается. В противном случае алгоритм должен вернуть автомат на несколько шагов на зад, когда еще был возможен выбор одного из набора следующих состояний, вы брать другой вариант и промоделировать поведение автомата с этим условием. Алгоритм завершается с ошибкой, когда все возможные варианты работы авто мата будут перебраны и ни одно из возможных конечных состояний не было достигнуто.
Во втором варианте алгоритм моделирования МП-автомата должен на каждом шаге работы при возникновении неоднозначности с несколькими возможными следующими состояниями автомата запускать новую свою копию для обработки каждого из этих состояний. Алгоритм завершается, если хотя бы одна из выпол няющихся его копий достигнет одно из конечных состояний. При этом работа всех остальных копий алгоритма прекращается. Если ни одна из копий алгорит ма не достигла конечного состояния МП-автомата, то алгоритм завершается с ошибкой.
Второй вариант реализации алгоритма связан с управлением параллельными процессами в вычислительных системах, поэтому сложен в реализации. Кроме того, на каждом шаге работы МП-автомата альтернатив следующих состояний может быть много, а количество возможных параллельно выполняющихся про цессов в операционных системах ограничено, поэтому применение второго ва рианта алгоритма осложнено. По этим причинам большее распространение по лучил первый вариант алгоритма, который предусматривает возврат к ранее запомненным состояниям МП-автомата — отсюда и название «разбор с возвра тами».
Следует отметить, что, хотя МП-автомат является односторонним распознавате лем, алгоритм моделирования его работы предусматривает возврат назад, к уже прочитанной части цепочки символов, чтобы исключить недетерминизм в пове дении автомата (который невозможно промоделировать).
Есть еще одна особенность в моделировании МП-автомата: любой практически ценный алгоритм должен завершаться за конечное число шагов (успешно или неуспешно). Алгоритм моделирования работы произвольного МП-автомата в об щем случае не удовлетворяет этому условию. Например, даже после считывания всей входной цепочки символов МП-автомат может совершить произвольное (в том числе и бесконечное) число -переходов. В том случае, если цепочка не принята, это может привести к бесконечному количеству шагов моделирующего алгоритма, который по этой причине никогда не будет закончен.
Чтобы избежать таких ситуаций, алгоритмы разбора с возвратами строят не для произвольных МП-автоматов, а для МП-автоматов, удовлетворяющим некото рым заданным условиям. Как правило, эти условия связаны с тем, что МП-авто мат должен строиться на основе грамматики заданного языка только после того, как она подвергнется некоторым преобразованиям. Поскольку преобразования грамматик сами по себе не накладывают каких-либо ограничений на входной класс КС-языков (в результате преобразования мы всегда получаем эквивалент ную грамматику), то они и не ограничивают применимости алгоритмов разбора с возвратами — эти алгоритмы применимы для любого КС-языка, заданного произвольной КС-грамматикой или МП-автоматом.
Алгоритмы разбора с возвратами обладают экспоненциальными характеристика ми. Это значит, что вычислительные затраты алгоритмов экспоненциально зави сят от длины входной цепочки символов: , VT*, n = ||. Конкретная зависи мость определяется вариантом реализации алгоритма.
Доказано, что в общем случае при первом варианте реализации для произволь ной КС-грамматики G(VT,VN,P,S) время выполнения данного алгоритма Тэ бу дет иметь экспоненциальную зависимость от длины входной цепочки, а необхо димый объем памяти Мэ — линейную зависимость от длины входной цепочки:
Тэ = О(еn) и Мэ = O(n). При втором варианте реализации, наоборот, время вы полнения данного алгоритма Тэ будет иметь линейную зависимость от длины входной цепочки, а необходимый объем памяти Мэ — экспоненциальную зависи мость от длины входной цепочки: Тэ = О(n) и Мэ = O(еn).
Экспоненциальная зависимость вычислительных затрат от длины входной це почки существенно ограничивает применимость алгоритмов разбора с возврата ми. Они тривиальны в реализации, но имеют неудовлетворительные характери стики, поэтому могут использоваться только для простых КС-языков с малой длиной входных предложений языка.
Возможность использовать эти алгоритмы в реальных компиляторах весьма сомнитель на, поскольку длина входной цепочки может достигать нескольких тысяч и даже десят ков тысяч символов. Очевидно, что время работы алгоритма при экспоненциальной зависимости требуемых вычислительных ресурсов от длины входной цепочки символов будет в таком варианте явно неприемлемым даже на самых современных компьютерах.
Для многих классов КС-языков существуют более эффективные алгоритмы распознавания, поэтому алгоритмы разбора с возвратами применяются редко.
Далее рассмотрены два основных варианта таких алгоритмов.
Этот распознаватель моделирует работу МП-автомата с одним состоянием q: R({q}, V,Z, ,q,S,{q}). Автомат распознает цепочки КС-языка, заданного КС-грамматикой G(VT,VN,P,S). Входной алфавит автомата содержит терминальные символы грамматики: V = VT, а алфавит магазинных символов строится из тер минальных и нетерминальных символов грамматики: Z = VTVN.
Начальная конфигурация автомата определяется так: (q, ,S) — автомат пребы вает в своем единственном состоянии q, считывающая головка находится в нача ле входной цепочки символов VT*, в стеке лежит символ, соответствующий целевому символу грамматики S.
Конечная конфигурация автомата определяется так: (q, ,) — автомат пребывает в своем единственном состоянии q, считывающая головка находится за концом входной цепочки символов, стек пуст.
Функция переходов МП-автомата строится на основе правил грамматики:
Этот МП-автомат уже был рассмотрен выше.
Работу данного МП-автомата можно неформально описать следующим образом:
если на верхушке стека автомата находится нетерминальный символ А, то его можно заменить на цепочку символов к, если в грамматике языка есть правило А-> , не сдвигая при этом считывающую головку автомата (этот шаг работы на зывается «подбор альтернативы»); если же на верхушке стека находится терми нальный символ а, который совпадает с текущим символом входной цепочки, то этот символ можно выбросить из стека и передвинуть считывающую головку на одну позицию вправо (этот шаг работы называется «выброс»). Данный МП-ав томат может быть недетерминированным, поскольку при подборе альтернативы в грамматике языка может оказаться более одного правила вида А—>, следовательно, тогда функция (q, ,A) будет содержать более одного следующего со стояния — у автомата будет несколько альтернатив.
Данный МП-автомат строит левосторонние выводы для грамматики G(VT,VN, P,S). Для моделирования такого автомата необходимо, чтобы грамматика G(VT, VN,P,S) не была леворекурсивной (в противном случае, очевидно, автомат мо жет войти в бесконечный цикл). Поскольку, как было доказано выше, произволь ную КС-грамматику всегда можно преобразовать к нелеворекурсивному виду, то этот алгоритм применим для любой КС-грамматики, следовательно, им можно распознавать цепочки любого КС-языка.
Рассмотренный МП-автомат строит левосторонние выводы и читает цепочку входных символов слева направо. Поэтому для него естественным является по строение дерева вывода сверху вниз. Такой распознаватель называется нисходя щим.
Решение о том, выполнять ли на каждом шаге работы МП-автомата выброс или подбор альтернативы, принимается однозначно. Моделирующий алгоритм дол жен обеспечивать выбор одной из возможных альтернатив и хранение информа ции о том, какие альтернативы на каком шаге уже были выбраны, чтобы иметь возможность вернуться к этому шагу и подобрать другие альтернативы. Такой алгоритм разбора называется алгоритмом с подбором альтернатив.
Существует масса способов реализации алгоритма, моделирующего работу этого МП-автомата. Рассмотрим один из примеров реализации алгоритма нисходяще го распознавателя с возвратом.
Для работы алгоритма используется МП-автомат, построенный на основе исход ной грамматики G(VT,VN,P,S). Для удобства работы все правила из множест ва Р в грамматике G представим в виде A->1|2|…|n, то есть пронумеруем все возможные альтернативы для каждого нетерминального символа AVN. Вход ная цепочка символов имеет вид =a1a2…an, || = n. В алгоритме используется также еще дополнительное состояние автомата b (от «back» — «назад»), которое сигнализирует о выполнении возврата к уже прочитанной части входной цепоч ки. Для хранения уже выбранных альтернатив используется дополнительный стек L2, который может содержать следующую информацию:
символы aVT входного языка автомата;
символы вида Aj, где A VN — это означает, что среди всех возможных правил для символа А была выбрана альтернатива с номером j.
В итоге алгоритм работает с двумя стеками: l1 — стек МП-автомата и L2 — стек возвратов. Оба они представлены в виде цепочек символов. Символы в цепочку стека l1 помещаются слева, а в цепочку стека L2 — справа. В целом состояние ал горитма на каждом шаге определяется четырьмя параметрами: (Q, i, L1, L2), где Q — текущее состояние автомата (q или b); i — положение считывающей голов ки во входной цепочке символов (1 < i <= n+1); L1 — содержимое стека МП-ав томата; L2 — содержимое дополнительного стека.
Начальным состоянием алгоритма является состояние (q, 1, S, ), где S — целе вой символ грамматики. Алгоритм начинает свою работу с начального состояния и циклически выполняет шесть шагов до тех пор, пока не перейдет в конечное состояние или не обнаружит ошибку. На каждом шаге алгоритма проверяется, соответствует ли текущее состояние алгоритма заданному для данного шага ис ходному состоянию, и выполняются ли заданные дополнительные условия. Если это требование выполняется, алгоритм переходит в следующее состояние, уста новленное для этого шага, если нет — шаг пропускается, алгоритм переходит к следующему шагу.
Алгоритм предусматривает циклическое выполнение следующих шагов.
Шаг 1 (Разрастание), (q, i, А, ) —> (q, i, 1, A1), если A->1 — это первая из всех возможных альтернатив для символа А.
Шаг 2 (Успешное сравнение), (q, i, a, ) -> (q, i+1, , а), если а = аi , aVT.
Шаг 3 (Завершение). Если состояние соответствует (q, n+1, , ), то разбор завер шен, алгоритм заканчивает работу, иначе (q, i, , ) -> (b, i, , ), когда in+1.
Шаг 4 (Неуспешное сравнение), (q, i, а, ) —> (b, i, а, ), если а ai, aVT.
Шаг 5 (Возврат по входу), (b, i, , а) —> (q, i-1, a, )), aVT.
Шаг 6 (Другая альтернатива). Исходное состояние (b, i, j, Aj), действия:
В случае успешного завершения алгоритма цепочку вывода можно построить на основе содержимого стека L2, полученного в результате выполнения алгоритма. Цепочка вывода строится следующим образом: поместить в цепочку номер пра вила m, соответствующий альтернативе А—>j , если в стеке содержится символ Aj; все символы aVT, содержащиеся в стеке L2, игнорируются.
Этот алгоритм может быть напрямую использован для построения распознава телей. Следует помнить, что для применения этого алгоритма исходная грам матика не должна быть леворекурсивной. Если это условие не удовлетворяет ся, то грамматику предварительно надо преобразовать к нелеворекурсивному виду.
Рассмотрим в качестве примера грамматику G ({+.-,/,*, a, b}, {S, R, T, F, E}, P, S) с правилами (это нелеворекурсивная грамматика):
Р:
S -> Т | TR
R -> +T | -Т | +TR | -TR
Т -> Е | EF
F -> *Е | /Е | *EF | /EF
Е -> (S) | а | b
Проследим разбор цепочки а+(а*b) из языка этой грамматики с помощью алго ритма нисходящего распознавателя с возвратами. Работу алгоритма будем пред ставлять в виде последовательности его состояний, взятых в скобки {} (фигурные скобки используются, чтобы не путать их с круглыми скобками, предусмотрен ными в правилах грамматики). Альтернативы будем нумеровать слева направо, правила — слева направо и сверху вниз. Для пояснения каждый шаг работы со провождается номером шага алгоритма, который был применен для перехода в очередное состояние (записывается перед состоянием через символ «:» — двое точие).
Алгоритм работы нисходящего распознавателя с возвратами при разборе цепоч ки а+(а*b) будет выполнять следующие шаги:
На основании полученной цепочки номеров альтернатив S2T1E2R1T1E1S1T2E2F1E3
построим последовательность номеров примененных правил: 2, 7, 14, 3, 7, 13, 1, 8, 14, 9, 15. Получаем левосторонний вывод: S => TR => ER => aR => a+T => a+E => a+(S) => a+(T) => a+(EF) => a+(aF) => a+(a*E) => a+(a*b). Соответствующее ему дерево вывода приведено на рис. 11.2.
Рис. 11.2. Дерево вывода для грамматики без левых рекурсий
Из приведенного примера очевиден недостаток алгоритма нисходящего разбора с возвратами — значительная временная емкость: для разбора достаточно корот кой входной цепочки (всего 7 символов) потребовалось 68 шагов работы алго ритма. Такого результата и следовало ожидать, исходя из экспоненциальной зависимости необходимых для работы алгоритма вычислительных ресурсов от длины входной цепочки. Это существенный недостаток данного алгоритма.
Преимуществом данного алгоритма можно считать простоту его реализации. Прак тически этот алгоритм разбора можно использовать только тогда, когда извест но, что длина исходной цепочки символов заведомо не будет большой (не боль ше нескольких десятков символов). Для реальных компиляторов такое условие невыполнимо, но для некоторых небольших распознавателей вполне допустимо, и здесь данный алгоритм разбора может найти применение именно благодаря своей простоте.
Еще одно преимущество алгоритма — его универсальность. На его основе можно распознавать входные цепочки языка, заданного любой КС-грамматикой, доста точно лишь привести ее к нелеворекурсивному виду (а это можно сделать с любой грамматикой, см. раздел «Преобразование КС-грамматик. Приведенные грамма тики»). Интересно, что грамматика даже не обязательно должна быть однознач ной — для неоднозначной грамматики алгоритм найдет один из возможных ле-носторонних выводов.
Сам по себе алгоритм разбора с подбором альтернатив, использующий возвраты, • не находит применения в реальных компиляторах. Однако его основные принци пы лежат в основе многих нисходящих распознавателей, строящих левосторон ние выводы и работающих без использования возвратов. Методы, позволяющие строить такие распознаватели для некоторых классов КС-языков, рассмотрены далее. Эти распознаватели будут более эффективны в смысле необходимых вы числительных ресурсов, но алгоритмы их работы уже более сложны, кроме того, они не являются универсальными.
Этот распознаватель строится на основе расширенного МП-автомата с одним состоянием q: R({q},V,Z,,q,S,{q}). Автомат распознает цепочки КС-языка, задан ного КС-грамматикой G(VT,VN,P,S). Входной алфавит автомата содержит тер минальные символы грамматики: V = VT; а алфавит магазинных символов стро ится из терминальных и нетерминальных символов грамматики: Z = VTVN.
Начальная конфигурация автомата определяется так: (q,) — автомат пребыва ет в своем единственном состоянии q, считывающая головка находится в начале входной цепочки символов VT*, стек пуст.
Конечная конфигурация автомата определяется так: (q, S) — автомат пребывает в своем единственном состоянии q, считывающая головка находится за концом входной цепочки символов, в стеке лежит символ, соответствующий целевому символу грамматики S.
Функция переходов МП-автомата строится на основе правил грамматики:
1. (q,A) (q, ), AVN, (VTVN)*, если правило А-> содержится во мно жестве правил Р грамматики G: А-> Р.
2. (q, a)(q, a, ) aVT.
Неформально работу этого расширенного автомата можно описать так: если на верхушке стека находится цепочка символов , то ее можно заменить на нетер минальный символ А, если в грамматике языка существует правило вида А—>, не сдвигая при этом считывающую головку автомата (этот шаг работы называет ся «свертка»); с другой стороны, если считывающая головка автомата обозревает некоторый символ входной цепочки а, то его можно поместить в стек, сдвинув при этом головку на одну позицию вправо (этот шаг работы называется «сдвиг» или «перенос»). Сам алгоритм, моделирующий работу такого расширенного ав томата, называется алгоритмом «сдвиг-свертка» или «перенос-свертка» (по на званиям основных действий алгоритма).
Данный расширенный МП-автомат строит правосторонние выводы для грамматики. Для моделирования такого автомата необходимо, чтобы грамматика G(VT, VN, P, S) не содержала -правил и цепных правил (иначе, автомат может войти в бесконечный цикл из сверток). Поскольку произвольную КС-грамматику всегда можно преобразовать к виду без -правил и цепных правилБ о этот алгоритм применим для любой КС-граматики, следовательно, им можно распознавать цепочки любого КС-языка.
Этот расширенный МП-автомат строит правосторонние выводы и читает цепочку входных символов слева направо. Поэтому для него естественным является построение дерева вывода снизу вверх. Такой распознаватель называется восходящим.
Данный расширенный МП-автомат потенциально имеет больше неоднозначностей, чем рассмотренный выше МП-автомат, основанный на алгоритме подбора альтернатив. На каждом шаге работы автомата надо решать следующие вопросы:
Чтобы промоделировать работы этого расширенного МП-автомата, надо на каждом шаге запоминать все предпринятые действия, чтобы иметь возможность вернуться к уже сделанному шагу и выполнить эти же действия по-другому. Этот процесс должен повторяться до тех пор, пока не будут перебраны все возможные варианты.
Табличные распознаватели используют для построения цепочки вывода КС-грамматики другие принципы, нежели МП-автоматы. Как и МП-автоматы, они получают на вход цепочку входных символов = а1а2…an, VT*, | | = n, a по строение вывода основывают на правилах заданной КС-грамматики G(VT,VN,P,S). Принцип их работы заключается в том, что искомая цепочка вывода строится не сразу — сначала на основе входной цепочки порождается некоторое промежу точное хранилище информации объема n*n (промежуточная таблица), а потом уже на его основе строится вывод.
Табличные алгоритмы обладают полиномиальными характеристиками требуе мых вычислительных ресурсов в зависимости от длины входной цепочки. Для произвольной КС-грамматики G(VT,VN,P,S) время выполнения алгоритма Тэ имеет кубическую зависимость от длины входной цепочки, а необходимый объ ем памяти Мэ — квадратичную зависимость от длины входной цепочки: , VT*, n= ||: Тэ = O(n3) и Мэ= О(n2). Квадратичная зависимость объема необходимой памяти от длины входной цепочки напрямую связана с использованием проме жуточного хранилища данных.
Табличные распознаватели универсальны — они могут быть использованы для распознавания цепочек, порожденных с помощью произвольной КС-грамматики (возможно, саму грамматику первоначально потребуется привести к заданному виду, но это не ограничивает универсальности алгоритмов). Кроме того, таблич ные распознаватели — это самые эффективные с точки зрения требуемых вычис лительных ресурсов универсальные алгоритмы для распознавания цепочек КС-языков.
Выше были рассмотрены различные универсальные распознаватели для КС-языков — то есть распознаватели, позволяющие выполнить разбор цепочек для любого КС-языка (заданного произвольной КС-грамматикой). Они универсаль ны, но имеют неудовлетворительные характеристики. Распознаватели с возвра тами имеют экспоненциальную зависимость требуемых для выполнения алго ритма разбора вычислительных ресурсов от длины входной цепочки символов, а табличные распознаватели — полиномиальную. Для практического примене ния в реальных компиляторах такие характеристики являются неудовлетвори тельными.
К сожалению, универсальных распознавателей с лучшими характеристиками для КС-языков построить не удается. Среди универсальных распознавателей лучши ми по эффективности являются табличные.
С другой стороны, универсальные распознаватели для КС-языков на практике и не требуются. В каждом конкретном случае компилятор имеет дело с синтак сическими структурами, заданными вполне определенной грамматикой. Чаще всего эта грамматика является не просто КС-грамматикой, а еще и относится к какому-нибудь из известных классов КС-грамматик (нередко сразу к несколь ким классам). Как минимум грамматика синтаксических конструкций языка про граммирования должна быть однозначной, а это уже значит, что она относится к классу детерминированных КС-языков.
Для многих классов КС-грамматик (и соответствующих им классов КС-языков) можно построить распознаватели, имеющие лучшие характеристики, чем рассмот ренные выше распознаватели с возвратами и табличные. Эти распознаватели уже не будут универсальными — они будут применимы только к заданному классу КС-языков с соответствующими ограничениями, зато они будут иметь лучшие характеристики.
Далее будут рассмотрены некоторые из таких распознавателей. Все они имеют линейные характеристики — линейную зависимость необходимых для выпол нения алгоритма разбора вычислительных ресурсов от длины входной цепочки. Для каждого распознавателя рассматривается класс КС-грамматик, с которым он связан. Это значит, что он может принимать только входные цепочки из КС-языков, заданных такими грамматиками. Всегда описываются ограничения, на лагаемые на правила грамматики, или дается алгоритм проверки принадлежно сти произвольной КС-грамматики к заданному классу.
Однако следует всегда помнить, что проблема преобразования КС-грамматик алго ритмически неразрешима. Если какая-то грамматика не принадлежит к требуе мому классу КС-грамматик, это еще не значит, что заданный ею язык не может быть описан грамматикой такого класса. Иногда удается выполнить преобразо вания и привести исходную грамматику к требуемому виду. Но, к сожалению, этот процесс не формализован, не поддается алгоритмизации и требует участия человека. Чаще всего такую работу вынужден выполнять разработчик компиля тора (правда, выполняется она только один раз для синтаксических конструкций каждого языка программирования).
Существуют два принципиально разных класса распознавателей. Первый — нис ходящие распознаватели, которые порождают цепочки левостороннего вывода и строят дерево вывода сверху вниз. Второй — восходящие распознаватели, кото рые порождают цепочки правостороннего вывода и строят дерево вывода снизу вверх. Названия «нисходящие» и «восходящие» связаны с порядком построения дерева вывода. Как правило, все распознаватели читают входную цепочку симво лов слева направо, поскольку предполагается именно такая нотация в написании исходного текста программ.
Нисходящие распознаватели используют модификации алгоритма с подбором альтернатив. При их создании применяются методы, которые позволяют одно значно выбрать одну и только одну альтернативу на каждом шаге работы МП-автомата (шаг «выброс» в этом автомате всегда выполняется однозначно). Алго ритм подбора альтернатив без модификаций был рассмотрен выше.
Восходящие распознаватели используют модификации алгоритма «сдвиг-сверт ка» (или «перенос-свертка», что то же самое). При их создании применяются методы, которые позволяют однозначно выбрать между выполнением «сдвига» («переноса») или «свертки» на каждом шаге работы расширенного МП-автома та, а при выполнении свертки однозначно выбрать правило, по которому будет производиться свертка. Алгоритм «сдвиг-свертка» без модификаций был рассмот рен выше.
Стремление улучшить алгоритм нисходящего разбора заключается в первую оче редь в определении метода, по которому на каждом шаге алгоритма можно было бы однозначно выбрать одну из всего множества возможных альтернатив. В та ком случае алгоритм моделирования работы МП-автомата не требовал бы возвра та на предыдущие шаги и за счет этого обладал бы линейными характеристика ми от длины входной цепочки. В случае неуспеха выполнения такого алгоритма входная цепочка однозначно не принимается, повторные итерации разбора не выполняются.
Наиболее очевидным методом выбора одной из множества аль тернатив является выбор ее на основании символа VT, обозре ваемого считывающей головкой ав томата на каждом шаге его работы (находящегося справа от положения текущей головки во входной цепочке символов). Поскольку в процессе нисходящего раз бора именно этот символ должен появиться на верхушке мага зина для продви жения считывающей головки автомата на один шаг (условие (q,a,a) = {(q, )}, aVT в функции переходов МП-автомата), то разумно искать альтернативу, где он присутствует в начале цепочки, стоящей в правой части правила грамма тики.
По такому принципу действует алгоритм разбора по методу рекурсивного спуска.
В реализации этого алгоритма для каждого нетерминального символа AVN грамматики G(VN,VT,P,S) строится процедура разбора, которая получает на вход цепочку символов а и положение считывающей головки в цепочке i. Если для символа А в грамматике G определено более одного правила, то процедура разбора ищет среди них правило вида А а, aVT, (VNVT)*, первый сим вол правой части которого совпадал бы с текущим символом входной цепочки а = i. Если такого правила не найдено, то цепочка не принимается. Иначе (если найдено правило А—>а или для символа А в грамматике G существует только одно правило А—>), то запоминается номер правила, и когда а = i, то считываю щая головка передвигается (увеличивается i), а для каждого нетерминального символа в цепочке рекурсивно вызывается процедура разбора этого символа.
Название метода происходит из реализации алгоритма, которая заключается в последовательности рекурсивных вызовов процедур разбора. Для начала разбо ра входной цепочки нужно вызвать процедуру для символа S с параметром i = 1.
Условия применимости метода можно получить из описания самого алгорит ма—в грамматике G(VN,VT,P,S) AVN возможны только два варианта пра вил:
А->, (VNVT)* и это единственное правило для А;
A->a11| a22|…| ann , i: ai VT, i (VNVT)* и если ij, то аiaj.
Этим условиям удовлетворяет незначительное количество реальных грамматик. Это достаточные, но не необходимые условия. Если грамматика не удовлетворя ет этим условиям, еще не значит, что заданный ею язык не может распознаваться с помощью метода рекурсивного спуска. Возможно, над грамматикой просто не обходимо выполнить ряд дополнительных преобразований.
К сожалению, не существует алгоритма, который бы позволил преобразовать произвольную КС-грамматику к указанному выше виду, равно как не существу ет и алгоритма, который бы позволял проверить, возможны ли такого рода пре образования. То есть для произвольной КС-грамматики нельзя сказать, анализи руема ли она методом рекурсивного спуска или нет.
Можно рекомендовать ряд преобразований, которые способствуют приведению грамматики к требуемому виду, но не гарантируют его достижения.
1. Исключение -правил.
2. Исключение левой рекурсии.
3. Добавление новых нетерминальных символов.
Например:
если правило: A->a1| a2|… |an|b11| b22|…| bmm|,
то заменяем его на два: А->аА'| b11| b22|…| bmm|, и A'->1| 2|… |n.
4. Замена нетерминальных символов в правилах на цепочки их выводов.
Например:
если имеются правила:
A->B1| B2|… |Bn|b11| b22|…| bmm|,
B1->11| 12|… |1k,
…
Bn->n1| n2|… |np
заменяем первое правило на
A->11| 12|… |1k|…|n1| n2|… |np| b11| b22|…| bmm|.
В целом алгоритм рекурсивного спуска эффективен и прост в реализации, но имеет очень ограниченную применимость.
Дана грамматика G({a,b,c},(A,B,C,S},P,S):
Р:
S -> аА | bВ
А -> а | bА | сС
В -> b | аВ | сС
С -> АаВb
Необходимо построить распознаватель, работающий по методу рекурсивного спуска.
Видно, что грамматика удовлетворяет условиям, необходимым для построения такого распознавателя.
Напишем процедуры на языке программирования С, которые будут обеспечи вать разбор входных цепочек языка, заданного данной грамматикой. Согласно алгоритму, необходимо построить процедуру разбора для каждого нетерминаль ного символа грамматики, поэтому дадим процедурам соответствующие наиме нования. Входные данные для процедур разбора будут следующие:
Результатом работы каждой процедуры может быть число, отличное от нуля («истина»), или 0 («ложь»). В первом случае входная цепочка символов прини мается распознавателем, во втором случае — не принимается. Для удобства реа лизации в том случае, если цепочка принимается распознавателем, будем воз вращать текущее положение указателя в цепочке. Кроме того, потребуется еще одна дополнительная процедура для ведения записей в массиве последователь ности правил (назовем ее WriteRules).
Теперь для распознавания входной цепочки необходимо иметь целочисленный массив Rules достаточного объема для хранения номеров правил. Тогда работа распознавателя заключается в вызове процедуры proc_S(Str,0,Ru1es,&N), где Str — это входная цепочка символов, N — переменная для запоминания количества при мененных правил (первоначально N = 0). Затем требуется обработка полученно го результата: если результат на 1 превышает длину цепочки — цепочка принята, иначе — цепочка не принята. В первом случае в массиве Rules будем иметь по следовательность номеров правил грамматики, необходимых для вывода цепоч ки, а в переменной N — количество этих правил. На основе этой цепочки можно легко построить дерево вывода.
Объем массива Rules заранее не известен, так как заранее не известно количество шагов вывода. Чтобы избежать проблем с недостаточным объемом статического массива, приведенные выше процедуры распознавателя можно модифицировать так, чтобы они работали с динамическим распределением памяти (изменив про цедуру WriteRules и тип параметра piRul в вызовах остальных процедур). На ло гику работы распознавателя это никак не повлияет. Следует помнить также, что метод рекурсивного спуска основан на рекурсивном вызове множества проце дур, что при значительной длине входной цепочки символов может потребовать соответствующего объема стека вызовов для хранения адресов процедур, их па раметров и локальных переменных.
Из приведенного примера видно, что алгоритм рекурсивного спуска удобен и прост в реализации. Главным препятствием в его применении является то, что класс грамматик, допускающих разбор на основе этого алгоритма, сильно ограничен.
Логическим продолжением идеи, положенной в основу метода рекурсивного спуска, является предложение использовать для выбора одной из множества альтернатив не один, а несколько символов входной цепочки. Однако напрямую переложить алгоритм выбора альтернативы для одного символа на такой же алгоритм для цепочки символов не удастся — два соседних символа в цепочке на самом деле могут быть выведены с использованием различных правил грамматики, по этому неверным будет напрямую искать их в одном правиле. Тем не менее, суще ствует класс грамматик, основанный именно на этом принципе — выборе одной альтернативы из множества возможных на основе нескольких очередных симво лов в цепочке. Это так называемые LL(k)-грамматики. Правда, алгоритм работы распознавателя для них не так очевидно прост, как рассмотренный выше алго ритм рекурсивного спуска.
Грамматика обладает свойством LL(k), k > 0, если на каждом шаге вывода для однозначного выбора очередной альтернативы МП-автомату достаточно знать символ на верхушке стека и рассмотреть первые k символов от текущего поло жения считывающей головки во входной цепочке символов.
Грамматика называется LL(k) -грамматикой, если она обладает свойством LL(k) для некоторого k > 0. (Требование k > 0, безусловно, является разумным — для принятия решения о выборе той или иной альтернативы МП-автомату надо рассмотреть хотя бы один символ входной цепочки. Если представить себе LL-грамматику с k = 0, то в такой грамматике вывод со всем не будет зависеть от входной цепочки. В принципе такая грамматика возможна, но в ней будет всего одна-единственная цепочка вывода. Поэтому практическое применение языка, заданного такого рода грамматикой, представляется весьма сомнительным.)
Название «LL(k)» несет определенный смысл. Первая литера «L» происходит от слова «left» и означает, что входная цепочка символов читается в направлении слева направо. Вторая литера «L» также происходит от слова «left» и означает, что при работе распознавателя используется левосторонний вывод. Вместо «k» в названии класса грамматики стоит некоторое число, которое показывает, сколь ко символов надо рассмотреть, чтобы однозначно выбрать одну из множества аль тернатив. Так, существуют LL(1)-грамматики, LL(2)-грамматики и другие классы.
В совокупности все LL(k)-грамматики для всех k>0 образуют класс LL-грамматик.
На рис. 12.1 схематично показано частичное дерево вывода для некоторой LL(k)-грамматики. В нем обозначает уже разобранную часть входной цепочки , ко торая построена на основе левой части дерева у. Правая часть дерева х — это еще не разобранная часть, а А — текущий нетерминальный символ на верхушке стека МП-автомата. Цепочка х представляет собой незавершенную часть цепочки вы вода, содержащую как терминальные, так и нетерминальные символы. После за вершения вывода символ А раскрывается в часть входной цепочки , а правая часть дерева х преобразуется в часть входной цепочки . Свойство LL(k) предпо лагает, что однозначный выбор альтернативы для символа А может быть сделан на основе k первых символов цепочки , являющейся частью входной цепоч ки .
Алгоритм разбора входных цепочек для LL(k)-грамматики носит название «k-предсказывающего алгоритма». Принципы его выполнения во многом соответст вуют функционированию МП-автомата с той разницей, что на каждом шаге работы этот алгоритм может просматривать k символов вперед от текущего поло жения считывающей головки автомата.
Рис. 12.1. Схема построения дерева вывода для LL(k)-грамматики
Для LL(k)-грамматик известны следующие полезные свойства:
Кроме того, известно, что все грамматики, допускающие разбор по методу рекур сивного спуска, являются подклассом LL(1) -грамматик. То есть любая грамма тика, допускающая разбор по методу рекурсивного спуска, является LL(1)-грам матикой (но не наоборот!).
Есть, однако, неразрешимые проблемы для произвольных КС-грамматик:
Это несколько ограничивает применимость LL(k)-грамматик, поскольку не все гда для произвольной КС-грамматики можно очевидно найти число k, для кото рого она является LL(k)-грамматикой, или узнать, существует ли вообще для нее такое число k.
Для LL(k)-грамматики при k>l совсем не обязательно, чтобы все правые части правил грамматики для каждого нетерминального символа начинались с k различ ных терминальных символов. Принципы распознавания предложений входного языка такой грамматики накладывают менее жесткие ограничения на правила грамматики, поскольку k соседних символов, по которым однозначно выбирает ся очередная альтернатива, могут встречаться и в нескольких правилах грамма тики (эти условия рассмотрены ниже). Грамматики, у которых все правые части правил для всех нетерминальных символов начинаются с k различных терми нальных символов, носят название «сильно LL(k)-грамматик». Метод построе ния распознавателей для них достаточно прост, алгоритм разбора очевиден, но, к сожалению, такие грамматики встречаются крайне редко.
Для LL(1)-грамматики, очевидно, для каждого нетерминального символа не мо жет быть двух правил, начинающихся с одного и того же терминального симво ла. Однако это менее жесткое условие, чем то, которое накладывает распознава тель по методу рекурсивного спуска, поскольку в принципе LL(1)-грамматика допускает в правой части правил цепочки, начинающиеся с нетерминальных символов, а также -правила. LL(1) -грамматики позволяют построить достаточ но простой и эффективный распознаватель, поэтому они рассматриваются далее отдельно в соответствующем разделе.
Поскольку все LL(k) -грамматики используют левосторонний нисходящий рас познаватель, основанный на алгоритме с подбором альтернатив, очевидно, что они не могут допускать левую рекурсию. Поэтому никакая леворекурсивная грам матика не может быть LL-грамматикой. Следовательно, первым делом при по пытке преобразовать грамматику к виду LL-грамматики необходимо устранить в ней левую рекурсию (соответствующий алгоритм был рассмотрен выше).
Класс LL-грамматик широк, но все же он недостаточен для того, чтобы покрыть все возможные синтаксические конструкции в языках программирования (к ним относим все детерминированные КС-языки). Известно, что существуют детер минированные КС-языки, которые не могут быть заданы LL(k)-грамматикой ни для каких k. Однако LL-грамматики удобны для использования, поскольку по зволяют построить распознаватели с линейными характеристиками (линейной зависимостью требуемых для работы алгоритма распознавания вычислительных ресурсов от длины входной цепочки символов).
Для построения распознавателей LL(k)-грамматик используются два важных мно жества, определяемые следующим образом:
Формально эти два множества могут быть определены следующим образом:
FIRST(k, ) = {VT* | либо || k и =>*, либо ||>k и а=>*х, x(VT VN)*}, (VTVN)*, k>0.
FOLLOW(k,A) ={VT* | S=>*A и FIRST(,k), VT*}, AVN, k>0.
Очевидно, что если имеется цепочка терминальных символов VT*, то FIRST(k,) — это первые k символов цепочки .
Доказано, что грамматика G(VT,VN,P,S) является LL(k )-грамматикой тогда и только тогда, когда выполняется следующее условие: А-> Р и А-> Р (): FIRST(k,) FIRST(k, ) = для всех цепочек со таких, что S =>* A.
Иначе говоря, если существуют две цепочки вывода:
S =>* A => z =>*
S =>* A => t =>*
то из условия FIRST(k,) = FIRST(k,) следует, что z = t.
На основе этих двух множеств строится алгоритм работы распознавателя для LL(k)-грамматик, который представляет собой k-предсказывающий алгоритм для МП-автомата, заданного так: R({q},VT,Z, ,q,S,{q}), где Z = VTVN, а S - целевой символ грамматики G. Функция переходов автомата строится на основе управ ляющей таблицы М, которая отображает множество (Z{}) VT*k на множест во, состоящее из следующих элементов:
Конфигурацию распознавателя можно отобразить в виде конфигурации МП-автомата с дополнением цепочки , в которую помещаются номера применен ных правил. Поскольку автомат имеет только одно состояние, его в конфигура ции можно не указывать. Если считать, что Х — это символ на верхушке стека автомата, — непрочитанная автоматом часть входной цепочки символов, а = FIRST(k,), то работу алгоритма распознавателя можно представить сле дующим образом:
Цепочка = FIRST(k, ) носит в работе автомата название «аванцепочка».
Таким образом, для создания алгоритма распознавателя языка, заданного произ вольной LL(k)-грамматикой, достаточно уметь построить управляющую табли цу М. Управляющую таблицу М, а также множества FIRST и FOLLOW можно получить на основе правил исходной грамматики.
При k= 1 все существенно проще. Методы построения для LL(l)-грамматик, а также проверки принадлежности грамматики к классу LL(l)-грамматик рас смотрены ниже.
Для LL(l)-грамматик алгоритм работы распознавателя предельно прост. Он за ключается всего в двух условиях, прове ряемых на шаге выбора альтернати вы. Исходными данными для этих условий являются символ aVT, обозреваемый считываю щей головкой МП-автомата (текущий символ входной цепочки), и символ AVN, находящийся на верхушке стека автомата.
Эти условия можно сформулировать так:
Если ни одно из этих условий не выполняется (нет соот ветствующих правил), то цепочка не принадлежит заданному языку и МП-автомат не принимает ее (алго ритм должен сигна лизировать об ошибке).
Работа автомата на шаге «выброса» остается без измене ний.
Кроме того, чтобы убедиться, является ли заданная грам матика G(VT,VN,P,S) LL(1)-грамматикой, необходимо и доста точно проверить следующее условие:
для каждого символа AVN, для которого в грамматике существует более одного правила вида А -> 1||…|n, должно выполняться требование
FIRST(l, iFOLLOW(l,A)) FIRST(l, jFOLLOW(l,A)) = i j, ni>0, nj>0.
Очевидно, что если для символа AVN отсутствует правило вида А->, то соглас но этому требованию все множества FIRST(l, 1), FIRST(1, 2), .... FIRST(l, n) должны попарно не пересекаться, если же присутствует правило А->, то они не должны также пересекаться со множеством FOLLOW(1,A). Отсюда видно, что LL(1)-грамматика не может содержать для одного и того же нетерминального символа AVN двух правил, начинающихся с одного и того же терминального символа.
Условие, накладываемое на правила LL(1)-грамматики, является довольно жест ким. Очень немногие реальные грамматики могут быть отнесены к классу LL(1)-грамматик. Например, даже довольно простая грамматика G({a},{S}, {S->a|aS}, S) не удовлетворяет этому условию (хотя она является LL(2)-грамматикой и даже регулярной праволинейной грамматикой).
Иногда удается преобразовать правила грамматики так, чтобы они удовлетворя ли требованию LL(1)-грамматик. Например, приведенная выше грамматика может быть преобразована к виду G'({a},{S,A}, {S->aA, A-> |S}, S). В такой форме она уже является LL(1)-грамматикой (это можно проверить). Но формального метода преобразовать произвольную КС-грамматику к виду LL(1)-грамматики или убедиться в том, что такое преобразование невозможно, не существует. Пер вое преобразование правил грамматики, которое можно рекомендовать, — устра нение левой рекурсии. Второе преобразование носит название «левая фактори зация», оно уже было упомянуто выше при знакомстве с методом рекурсивного спуска. Это преобразование заключается в следующем: если для символа AVN существует ряд правил
A-> a1| a2|… |an|1|2|…|m, i: i(VTVN)*, j: j(VTVN)*, aVT
и ни одна цепочка символов j не начинается с символа а, тогда во множество не терминальных символов грамматики VN добавляется новый символ А', а прави ла для А и А' записываются следующим образом: A-> aA’|1|2|…|m и A’-> 1| 2|… |n. Левую факторизацию можно применять к правилам грамматики несколько раз с целью исключить для каждого нетерминального символа правила, начинающие ся с одних и тех же терминальных символов. Однако применение этих двух пре образований отнюдь не гарантирует, что произвольную КС-грамматику удастся привести к виду LL(1)-грамматики.
Для того чтобы запрограммировать работу МП-автомата, выполняющего разбор входных цепочек символов языка, заданного LL(1)-грамматикой, надо научить ся строить множества символов FIRST(l, x) и FOLLOW(1, A). Для множества FIRST(l, x) все очевидно, если цепочка х начинается с терминального симво ла, если же она начинается с нетерминального символа В (х = By, x (VTVN)+, y (VTVN)*), то FIRST(l, x) = FIRST(1,B). Следовательно, для LL(1)-грамматик остается только найти алгоритм построения множеств FIRST(1,B) и FOLLOW(1,A) для всех нетерминальных символов A, BVN.
Исходными данными для этих алгоритмов служат правила грамматики.
Алгоритм строит множества FIRST(1,A) сразу для всех нетерминальных сим волов грамматики G(VT,VN,P,S), AVN. Для выполнения алгоритма надо пред варительно преобразовать исходную грамматику G(VT,VN,P,S) в граммати ку G'(VT,VN',P',S'), не содержащую -правил (см. алгоритм преобразования в разделе «Преобразование КС-грамматик, Приведенные грамматики», глава 11). На основании полученной грамматики G' и выполняется построение множеств FIRST(l, A) для всех A VN (если A VN, то согласно алгоритму преобразования также справедливо AVN'). Множества строятся методом последовательно го приближения. Если в результате преобразования грамматики G в граммати ку G' множество VN' содержит новый символ S', то при построении множества FIRST(1, A) он не учитывается.
Алгоритм состоит из нескольких шагов.
Шаг 1. Для всех AVN: FIRST0(l, A) = {X | А->Х P, X (VTVN), (VTVN)*} (первоначально вносим во множество первых символов для каждого нетерми нального символа А все символы, стоящие в начале правых частей правил для этого символа А); i:=0.
Шаг 2. Для всех AVN: FIRSTi+1(1, A) = FIRSTi(1, A) FIRSTi(1,B), для всех не терминальных символов B (FIRSTi(l,A) VN).
Шаг 3. Если AVN: FIRSTi+1(l,A) FIRSTi(1,A), то i:=i+l и вернуться к шагу 2, иначе перейти к шагу 4.
Шаг 4. Для всех AVN: FIRST(1,A) = FIRSTi(1,A) \ VN (исключаем из постро енных множеств все нетерминальные символы).
Алгоритм строит множества FOLLOW(1,A) сразу для всех нетерминальных сим волов грамматики G(VT,VN,P,S), AVN. Для выполнения алгоритма предвари тельно надо построить все множества FIRST(1,A), AVN. Множества строят ся методом последовательного приближения. Алгоритм состоит из нескольких шагов.
Шаг 1. Для всех AVN: FOLLOW0(l,A) = {X | В->АХ P, BVN, X (VTVN), (VTVN)*} (первоначально вносим во множество последующих символов для каждого нетерми нального символа А все символы, которые в правых частях пра вил встречаются непосредственно за символом A); i:=0.
Шаг 2. FOLLOW0(l, S) = FOLLOW0(l, S) {} (вносим пустую цепочку во мно жество последующих символов для целевого символа S — это означает, что в конце разбора за целевым символом цепочка кончается, иногда для этой цели используется специальный символ конца цепочки: k).
Шаг 3. Для всех AVN: FOLLOW’i(1,А) = FOLLOWi(1,A) FIRST(1,B), для всех нетерминальных символов B (FOLLOWi(l,A) VN).
Шаг 4. Для всех AVN: FOLLOW"i (1,А) = FOLLOW’i(1,A) FOLLOW’i(1,B), для всех нетерминальных символов B (FOLLOW'i(l,A) VN) и существует пра вило В->.
Шаг 5. Для всех A VN: FOLLOWi+1(l,A) = FOLLOW"i(1,A) FOLLOW"i(1,B), для всех нетерминальных символов B VN, если существует правило В->А, (VTVN)*.
Шаг 6. Если AVN: FOLLOWi+1(l,A) FOLLOWi(1,A), то i:=i+l и вернуться к шагу 3, иначе перейти к шагу 7.
Шаг 7. Для всех AVN: FOLLOW(l, A) = FOLLOWi(1,A) \ VN (исключаем из построенных множеств все нетерминальные символы).
Восходящие распознаватели выполняют построение дерева вывода снизу вверх. Результатом их работы является правосторонний вывод. Функционирование таких распознавателей основано на модификациях алгоритма «сдвиг-свертка» (или «перенос-свертка»).
Идея состоит в том, чтобы модифицировать этот алгоритм таким образом, чтобы на каждом шаге его работы можно было однозначно дать ответ на следующие во просы:
что следует выполнять: сдвиг (перенос) или свертку;
какую цепочку символов выбрать из стека для выполнения свертки;
какое правило выбрать для выполнения свертки (в том случае, если сущест вует несколько правил вида A1->, A2->, … An->).
Тогда восходящий алгоритм распознавания цепочек КС-языка не требовал бы выполнения возвратов, поскольку сам язык мог бы быть задан детерминирован ным расширенным МП-автоматом. Конечно, как уже было сказано, это нельзя сделать в общем случае, для всех КС-языков (поскольку даже сам класс детер минированных КС-языков более узкий, чем весь класс КС-языков). Но, вероят но, среди всех КС-языков можно выделить такой класс (или классы), для кото рых подобная реализация распознающего алгоритма станет возможной.
В первую очередь можно использовать тот же самый подход, который был поло жен в основу определения LL(k)-грамматик. Тогда мы получим другой класс КС-грамматик, который носит название LR(k)-грамматик.
КС-грамматика обладает свойством LR(k), k 0, если на каждом шаге выво да для однозначного решения вопроса о выполняемом действии в алгоритме «сдвиг-свертка» («перенос-свертка») расширенному МП-автомату достаточно знать содержимое верхней части стека и рассмотреть первые k символов от те кущего положения считывающей головки автомата во входной цепочке сим волов.
Грамматика называется LR(k)-грамматикой, если она обладает свойством LR(k) для некоторого k0.
Название «LR(k)», как и рассмотренное выше «LL(k)», также несет определен ный смысл. Первая литера «L» также обозначает порядок чтения входной цепоч ки символов: слева— направо. Вторая литера «R» происходит от слова «right» и, по аналогии с LL(k), означает, что в результате работы распознавателя получа ется правосторонний вывод. Вместо «k» в названии грамматики стоит число, ко торое показывает, сколько символов входной цепочки надо рассмотреть, чтобы принять решение о действии на каждом шаге алгоритма «сдвиг-свертка». Так, существуют LR(0)-грамматики, LR(1)-грамматики и другие классы.
В совокупности все LR(k)-грамматики для всех k 0 образуют класс LR-грамматик.
На рис. 12.4 схематично показано частичное дерево вывода для некоторой LR(k)-грамматики. В нем обозначает уже разобранную часть входной цепочки , на основе которой построена левая часть дерева . Правая часть дерева х — это еще не разобранная часть, а А — это нетерминальный символ, к которому на очеред ном шаге будет свернута цепочка символов z, находящаяся на верхушке стека МП-автомата. В эту цепочку уже входит прочитанная, но еще не разобранная часть входной цепочки . Правая часть дерева х будет построена на основе части входной цепочки . Свойство LR(k) предполагает, что однозначный выбор дей ствия, выполняемого на каждом шаге алгоритма «сдвиг-свертка», может быть сделан на основе цепочки и k первых символов цепочки , являющихся частью входной цепочки . Этим очередным действием может быть свертка цепочки z к сим волу А или перенос первого символа из цепочки и добавление его к цепочке z.
Рис. 12.4. Схема построения дерева вывода для LR(k)-грамматики
Рассмотрев схему построения дерева вывода для LR(k)-грамматики на рис. 12.4 и сравнив ее с приведенной выше на рис. 12.1 схемой для LL(k)-грамматики, можно предположить, что класс LR-грамматик является более широким, чем класс LL-грамматик. Основанием для такого предположения служит тот факт что на каждом шаге работы распознавателя LR(k)-грамматики обрабатывается больше информации, чем на шаге работы распознавателя LL(k)-грамматики. Действительно, для принятия решения на каждом шаге алгоритма распознава ния LL(k)-грамматики используются первые k символов из цепочки , а для принятия решения на шаге распознавания LR(k)-грамматики — вся цепочка и еще первые k символов из цепочки . Очевидно, что во втором случае можно проанализировать больший объем информации и, таким образом, построить вы вод для более широкого класса КС-языков.
Для LR(k)-грамматик известны следующие полезные свойства:
Есть, однако, неразрешимые проблемы для произвольных КС-грамматик (они аналогичны таким же проблемам для других классов КС-грамматик):
Кроме того, для LR-грамматик доказано еще одно очень интересное свойство — класс LR-грамматик полностью совпадает с классом детерминированных КС-языков. То есть, во-первых, любая LR(k)-грамматика задает детерминированный КС-язык (это очевидно следует из однозначности всех LR-грамматик), а во-вто рых, для любого детерминированного КС-языка можно построить LR-грамматику, задающую этот язык.
В принципе класс LR-грамматик очень удобен для построения распознавателей детерминированных КС-языков (а все языки программирования, безусловно, относятся к этому классу). Но тот факт, что для каждого детерминированного КС-языка существует задающая его LR-грамматика, еще ни о чем не говорит, по скольку из-за неразрешимости проблемы преобразования отсутствует алгоритм, который позволил бы эту грамматику построить всегда. Данный детерминиро ванный КС-язык может быть изначально задан грамматикой, которая не отно сится к классу LR-грамматик. В таком случае совсем не очевидно, что для этого языка удастся построить распознаватель на основе LR-грамматики, потому что в общем случае нет алгоритма, который бы позволил эту грамматику получить, хотя и известно, что она существует. То, что проблема не разрешима в общем случае, совсем не означает, что ее не удастся решить в конкретной ситуации. И здесь факт существования LR-грамматики для каждого детерминированного КС-языка играет важную роль — всегда есть смысл в каждом конкретном случае пытаться построить такую грамматику.
Для того чтобы формально определить LR(k) свойство для КС-грамматик, вве дем понятие пополненной КС-грамматики. Грамматика G' является пополнен ной грамматикой, построенной на основании исходной грамматики G(VT,VN,P,S), если выполняются следующие условия:
Фактически пополненная КС-грамматика строится таким образом, чтобы ее це левой символ не встречался в правой части ни одного правила. Если нужно, то в исходную грамматику G для этого добавляется новый терминальный символ S', который становится целевым символом, и новое правило S'->S. Очевидно, что пополненная грамматика G' эквивалентна исходной грамматике G, то есть L(G’) = L(G).
Теперь рассмотрим формальное определение LR(k) свойства.
Если для произвольной КС-грамматики G в ее пополненной грамматике G' для двух произвольных цепочек вывода из условий:
1. S' =>* aAw => w
2. S' =>* Вх => у
3. FIRST(k, w) = FIRST(k, y)
следует, что Aw = Bx (то есть = , А = В и х = у), то доказано, что граммати ка G обладает LR(k) свойством. Очевидно, что тогда и пополненная граммати ка G' также обладает LR(k) свойством.
Еще одним распространенным классом КС-грамматик, для которых возмож но построить восходящий распознаватель без возвратов, являются грамматики предшествования. Так же как и распознаватель рассмотренных выше LR-грамматик, распознаватель для грамматик предшествования строится на основе алго ритма «сдвиг-свертка» («перенос-свертка.
Принцип организации распознавателя входных цепочек языка, заданного грам матикой предшествования, основывается на том, что для каждой упорядоченной пары символов в грамматике устанавливается некоторое отношение, называемое отношением предшествования. В процессе разбора входной цепочки расширен ный МП-автомат сравнивает текущий символ входной цепочки с одним из сим волов, находящихся на верхушке стека автомата. В процессе сравнения проверя ется, какое из возможных отношений предшествования существует между этими двумя символами. В зависимости от найденного отношения выполняется либо сдвиг (перенос), либо свертка. При отсутствии отношения предшествования ме жду символами алгоритм сигнализирует об ошибке.
Задача заключается в том, чтобы иметь возможность непротиворечивым образом определить отношения предшествования между символами грамматики. Если это возможно, то грамматика может быть отнесена к одному из классов грамматик предшествования.
Существует несколько видов грамматик предшествования. Они различаются по тому, какие отношения предшествования в них определены и между какими ти пами символов (терминальными или нетерминальными) могут быть установле ны эти отношения. Кроме того, возможны незначительные модификации функ ционирования самого алгоритма «сдвиг-свертка» в распознавателях для таких грамматик (в основном на этапе выбора правила для выполнения свертки, когда возможны неоднозначности).
Выделяют следующие виды грамматик предшествования:
Далее будут рассмотрены два наиболее простых и распространенных типа — грамматики простого и операторного предшествования.
Грамматикой простого предшествования называют такую приведенную КС-грам матику (КС-грамматика называется приведенной, если она не содержит циклов, бесплодных и недостижимых символов и -правил) G(VN,VT,P,S), V = VTVN, в которой:
1. Для каждой упорядоченной пары терминальных и нетерминальных символов выполняется не более чем одно из трех отношений предшествования:
2. Различные правила в грамматике имеют разные правые части (то есть в грам матике не должно быть двух различных правил с одной и той же правой ча стью).
Отношения =•, <• и •> называют отношениями предшествования для символов. Отношение предшествования единственно для каждой упорядоченной пары символов. При этом между какими-либо двумя символами может и не быть от ношения предшествования — это значит, что они не могут находиться рядом ни в одном элементе разбора синтаксически правильной цепочки. Отношения пред шествования зависят от порядка, в котором стоят символы, и в этом смысле их нельзя путать со знаками математических операций - они не обладают ни свой ством коммутативности, ни свойством ассоциативности. Например, если извест но, что Bi •> Bj, то не обязательно выполняется Bj <• Вi, (поэтому знаки предшест вования иногда помечают специальной точкой: -•, <•, •>).
Для грамматик простого предшествования известны следующие полезные свой ства:
Метод предшествования основан на том факте, что отношения предшествования между двумя соседними символами распознаваемой строки соответствуют трем следующим вариантам:
Исходя из этих соотношений, выполняется разбор строки для грамматики пред шествования.
Суть принципа такого разбора можно пояснить на рис. 12.5. На нем изображена входная цепочка символов в тот момент, когда выполняется свертка цепоч ки . Символ а является последним символом подцепочки , а символ b — первым символом подцепочки . Тогда, если в грамматике удастся установить непроти воречивые отношения предшествования, то в процессе выполнения разбора по алгоритму «сдвиг-свертка» можно всегда выполнять сдвиг до тех пор, пока меж ду символом на верхушке стека и текущим символом входной цепочки сущест вует отношение <• или =•. А как только между этими символами будет обнаружено отношение •>, так сразу надо выполнять свертку. Причем для выполнения свертки из стека надо выбирать все символы, связанные отношением =•. То, что все различные правила в грамматике предшествования имеют различные правые части, гарантирует непротиворечивость выбора правила при выполнении свертки.
Таким образом, установление непротиворечивых отношений предшествования между символами грамматики в комплексе с несовпадающими правыми частями различных правил дает ответы на все вопросы, которые надо решить для органи зации работы алгоритма «сдвиг-свертка» без возвратов.
Рис. 12.5. Отношения между символами входной цепочки в грамматике предшествования
На основании отношений предшествования строят матрицу предшествования грамматики. Строки матрицы предшествования помечаются первыми (левыми) символами, столбцы — вторыми (правыми) символами отношений предшество вания. В клетки матрицы на пересечении соответствующих столбца и строки по мещаются знаки отношений. При этом пустые клетки матрицы говорят о том, что между данными символами нет ни одного отношения предшествования.
Матрицу предшествования грамматики сложно построить, опираясь непосредст венно на определения отношений предшествования. Удобнее воспользоваться двумя дополнительными множествами — множеством крайних левых и множе ством крайних правых символов относительно нетерминальных символов грам матики G(VN,VT,P,S), V = VTVN. Эти множества определяются следующим образом:
Иными словами, множество крайних левых символов относительно нетерми нального символа А — это множество всех крайних левых символов в цепочках, которые могут быть выведены из символа А. Аналогично, множество крайних правых символов относительно нетерминального символа А — это множество всех крайних правых символов в цепочках, которые могут быть выведены из символа А.
Тогда отношения предшествования можно определить так:
Такое определение отношений удобнее на практике, так как не требует построе ния выводов, а множества L(A) и R(A) могут быть построены для каждого не терминального символа AVN грамматики G(VN,VT,P,S), V = VTVN по очень простому алгоритму.
Шаг 1. AVN:
R0(A) = {X | A->yX, XV, yeV*}, L0(A) = {X | A->Xy, XV, yV*}, i := 1.
Для каждого нетерминального символа А ищем все правила, содержащие А в ле вой части. Во множество L(A) включаем самый левый символ из правой части правил, а во множество R(A) — самый крайний правый символ из правой части. Переходим к шагу 2.
Шаг 2. AVN:
Ri(А) - Ri-1(A) Ri-1(B), В (Ri-1(A) VN),
Li(A) = Li-1(A) Li-1(B), B (Li-1(A) VN).
Для каждого нетерминального символа А: если множество L(A) содержит нетер минальные символы грамматики А', А", ..., то его надо дополнить символами, входящими в соответствующие множества L(A'), L(A"), ... и не входящими в L(A). Ту же операцию надо выполнить для R(A).
Шаг 3. Если AVN: Ri(A) Ri-1(A) или Li(A) Li-1(A), то i:=i+l и вернуться к шагу 2, иначе построение закончено: R(A) = Ri(A) и L(A) = Li(A).
Если на предыдущем шаге хотя бы одно множество L(A) или R(A) для неко торого символа грамматики изменилось, то надо вернуться к шагу 2, иначе по строение закончено.
После построения множеств L(A) и R(A) по правилам грамматики создается матрица предшествования. Матрицу предшествования дополняют символами н и к (начало и конец цепочки). Для них определены следующие отношения предшествования:
н<• X, aV, если S=>*Xy, где SVN, yV* или (с другой стороны) если XL(S);
к •>X, aV, если S=>*yX, где SVN, y V* или (с другой стороны) если XR(S).
Здесь S — целевой символ грамматики.
Матрица предшествования служит основой для работы распознавателя языка, заданного грамматикой простого предшествования.