1.1.1 Цепочки символов и операции над ними
Сначала дадим все необходимые определения и введём некоторые понятия. Большинство из них достаточно очевидны, но всё же рекомендуется с ними ознакомиться.
Над цепочками можно выделить следующие операции:
Для пустой цепочки l справедливы следующие равенства:
1.1.2 Понятие языка. Способы задания языков
В общем случае язык – это заданный набор символов и правил, устанавливающих способы комбинации этих символов между собой для записи осмысленных текстов. Основой любого языка является алфавит, определяющий набор допустимых символов.
Большая часть следующих утверждений основана на теории множеств.
Примеры
1. Для языка L={01,11} замыканием Клини будет бесконечное множество цепочек вида L*={λ,01,11,0101,1111,0111,1101, 010101, 010111, 011101, 110101, 110111, 111101, 011111, 111111, …}.
2. Язык L={01,010,111,100} не обладает префиксным свойством, т.к. цепочка ‘01’ является префиксом цепочки ‘010’. В то же время он обладает суффиксным свойством, т.к. в нём нет ни одной цепочки, которая была бы суффиксом какой-то другой цепочки.
Язык состоит из бесконечного множества цепочек символов над некоторым алфавитом, или слов. Но не любая цепочка символов над этим алфавитом принадлежит языку, т.к. существуют правила построения допустимых цепочек для каждого конкретного языка. Указать эти правила – значит задать язык. Существуют три основных способа задания языка:
Генераторы и распознаватели являются основными инструментами задания бесконечного языка конечными средствами. Существует определенная классификация языков по их типу, и для каждого класса языков имеются эквивалентные способы задания с помощью генераторов и распознавателей. Далее рассмотрим эти способы более подробно.
В любом языке можно выделить его синтаксис и семантику. Кроме того, трансляторы имеют дело также с лексическими конструкциями (лексемами), которые задаются лексикой языка. Дадим определения этих понятий.
Синтаксис языка – это набор правил, определяющий допустимые конструкции языка. Чаще всего синтаксис языка можно задать в виде строгого набора правил, но полностью это справедливо только для формальных языков.
Семантика языка – это раздел, определяющий значение предложений языка. Семантика определяет “содержание языка”, т.е. задаёт значение всех допустимых цепочек языка. Для большинства языков семантика определяется неформальными методами.
Лексика – это словарный запас языка. Лексическая единица (лексема) – конструкция, которая состоит из элементов алфавита языка и не содержит в себе других конструкций. Т.е. лексема может содержать в себе только элементарные символы алфавита и не может содержать других лексем. Например, лексемами русского языка являются слова, а пробелы и знаки препинания представляют собой разделители. Лексемами алгебры являются числа, знаки математических операций, обозначения функций и т.п. В языках программирования лексемы – это ключевые слова, идентификаторы, константы, метки, знаки операций.
Языки программирования занимают промежуточное место между формальными и естественными языками. С формальными языками их объединяют строгие синтаксические правила, на основе которых строятся предложения языка. От естественных языков в языки программирования перешли лексические единицы, представляющие основные ключевые слова (чаще это английские слова, но бывают и слова других языков).
Для задания языка программирования необходимо решить три основных вопроса:
С помощью теории формальных языков удается решить (полностью или частично) только первые два вопроса.
Первый вопрос решается легко. Алфавит языка и представляет собой множество его допустимых символов. Для языков программирования это, как правило, тот набор символов, который можно ввести с клавиатуры.
Второй вопрос в теории формальных языков решается только частично. Для всех языков программирования существуют синтаксические правила, но их недостаточно для строгого определения всех возможных синтаксических конструкций. Дополнительные ограничения накладываются семантикой языка и неформально оговариваются для каждого отдельного языка программирования. Это, например, необходимость предварительного описания переменных и функций, необходимость соответствия типов переменных и констант в выражениях, формальных и фактических параметров в описаниях и вызовах процедур и функций, и т.п.
Отсюда следует, что практически все языки программирования, строго говоря, не являются формальными языками. Поэтому во всех трансляторах, кроме синтаксического разбора и анализа предложений языка, дополнительно предусмотрен семантический анализ.
Третий вопрос вообще не относится к теории формальных языков. Для ответа на него нужно использовать другие подходы, например:
Любой разработчик программ так или иначе использует первый подход – это комментарии в программе, построение её блок-схемы, разработка документации или любое другое описание алгоритма. Все эти способы ориентированы на человека, но универсального способа проверить, насколько описание в действительности соответствует программе, пока не существует. Для изложения программы на языке, понятном машине – в машинных командах – существуют трансляторы.
Второй подход используется при отладке программы; оценку результатов выполнения программы при отладке осуществляет человек.
Разработчикам компиляторов так или иначе приходится решать вопрос о смысле программ.
Во-первых, компилятору для преобразования исходной программы в последовательность машинных команд необходимо иметь представление о том, какая последовательность команд должна соответствовать той или иной части программы. Обычно такие последовательности сопоставляют базовым конструкциям входного языка – используется первый подход к изложению смысла программы.
Во-вторых, многие современные компиляторы позволяют выявить сомнительные с точки зрения смысла места в исходной программе – например, недостижимые операторы, неиспользуемые переменные, неопределенные результаты функций и т.п. Обычно компилятор указывает такие места в виде предупреждений, на которые разработчик может обращать или не обращать внимание. Для этого компилятор должен иметь представление о том, как программа будет выполняться, т.е. используется второй подход.
Но в любом случае осмысление исходной программы закладывает в компилятор его создатель, который руководствуется неформальными методами – как правило, описанием входного языка. В теории формальных языков вопрос о смысле программ не решается.
Итак, возможности трансляторов по проверке осмысленности исходной программы практически равны нулю, поэтому семантические ошибки остаются на совести авторов программ.
Выше, когда шла речь о различных способах задания языков, как наиболее реальные были выделены второй и третий способ, а именно: задание языка с помощью генераторов и распознавателей. В качестве генераторов в общем случае могут использоваться грамматики, а для более узкого класса языков – регулярные выражения. В качестве распознавателей, как правило, применяются автоматы различных типов (в зависимости от класса языка). В первой главе будет рассмотрен способ задания языков с помощью грамматик.
1.2.1 Понятие грамматики и формальное определение.
Форма Бэкуса-Наура
Грамматика в общем представляет собой описание способа построения цепочек языка. Например, для естественных языков это набор правил построения различных выражений и предложений. Для многих языков (в том числе для языков программирования) возможно использовать формализованное описание, т.е. некую математическую систему, описывающую язык. Грамматика задаёт правила порождения цепочек языка, следовательно, является генератором – реализует второй способ задания языка.
Формальное описание грамматики построено на основе системы правил, или продукций. Правило представляет собой упорядоченную пару цепочек символов (a ,b ), которую обычно записывают как a ® b и читают как “a порождает b ”.
Грамматика языка программирования содержит правила двух типов: первые (определяющие синтаксические конструкции языка) легко поддаются формальному описанию; вторые (определяющие семантические ограничения языка) обычно излагаются в неформальном виде. Поэтому любое описание языка программирования обычно состоит из двух частей: сначала формально излагаются правила построения синтаксических конструкций, затем на естественном языке даётся описание семантических правил. Для компилятора семантические ограничения должны быть представлены в виде алгоритмов проверки правильности программы.
Замечание: Говоря далее о грамматиках языков программирования, будем иметь в виду только правила построения синтаксических конструкций языка.
Формально грамматика G определяется как четвёрка G(VT,VN,P,S), где VT – множество терминальных символов (символы алфавита языка);
VN – множество нетерминальных символов (вспомогательные символы, ими могут быть слова, понятия, конструкции языка); причём множества терминальных и нетерминальных символов не пересекаются: VTÇ
VN=Æ
; V=VTÈ
VN – полный алфавит грамматики G; P – множество правил вида a
®
b
, где a
Î
V+, b
Î
V*; SÎ
VN – начальный (целевой) символ грамматики G, с которого начинается процесс порождения цепочек языка.
Нетерминальные символы участвуют в процессе порождения цепочек языка, но в окончательном виде цепочки языка состоят только из символов терминального алфавита.
В зависимости от вида правил грамматики классифицируются по типам. Эту классификацию рассмотрим далее. Но существуют некоторые общие принципы построения правил любой грамматики:
Во множестве правил грамматики может быть несколько правил, имеющих одинаковые левые части, например: a ® b 1, a ® b 2, …, a ® b n. Тогда эти правила записываются в одну строку: a ® b 1½ b 2½…½ b n.
Рассмотренная форма записи правил грамматики называется формой Бэкуса-Наура. В ней, как правило, нетерминальные символы заключаются в угловые скобки <>.
Пример: грамматика порождения целых десятичных чисел со знаком.
G({0,1,2,3,4,5,6,7,8,9,–,+}, {<число>,<чс>,<цифра>}, P, <число>).
P:
<число> ® <чс>½ +<чс>½ –<чс>
<чс> ® <цифра>½ <чс><цифра>
<цифра> ® 0½ 1½ 2½ 3½ 4½ 5½ 6½ 7½ 8½ 9
В данной грамматике множество нетерминальных символов содержит 3 элемента (символы <число>,<чс>,<цифра>), множество терминальных символов – 12 элементов (10 цифр и два знака), множество P – 15 правил, записанных в три строки. Начальный символ грамматики – <число>.
В грамматике можно изменить названия нетерминальных символов без какого-то изменения языка, заданного ею. Терминальные символы изменять нельзя! Они соответствуют алфавиту задаваемого языка. В случае изменения множества терминальных символов изменится и алфавит языка.
Рассмотренную в примере грамматику для целых десятичных чисел со знаком можно переписать в виде:
G¢ ({0,1,2,3,4,5,6,7,8,9,–,+}, {S,T,F}, P, S).
P:
S ® T½ +T½ –T
T ® F½ TF
F ® 0½ 1½ 2½ 3½ 4½ 5½ 6½ 7½ 8½ 9.
Формальные грамматики определяют бесконечное множество цепочек языка с помощью конечного набора правил.
Это становится возможным благодаря использованию рекурсивных правил, в которых нетерминальный символ выражается сам через себя. Рекурсия при этом может быть непосредственной (явной), когда символ определяется сам через себя в одном правиле; или косвенной (неявной), когда такое переопределение происходит через цепочку правил.
В грамматиках G и G¢ явная рекурсия присутствует во второй части второго правила: <чс> ® <чс><цифра>, T ® TF.
Чтобы рекурсия не была бесконечной, участвующий в ней нетерминальный символ должен обязательно присутствовать в левой части другого правила, где он определяется, минуя самого себя. В грамматиках G и G¢ это достигается в первой части второго правила: <чс> ® <цифра>, T ® F.
Явно или неявно, рекурсия всегда присутствует в грамматиках любых реальных языков программирования. Как правило, в грамматиках реального языка программирования присутствует не одно, а множество правил, построенных с помощью рекурсии.
1.2.2 Другие способы задания грамматик
Кроме формы Бэкуса-Наура, существуют и другие способы записи правил грамматик, а именно запись с использованием метасимволов и графическое представление.
Запись правил грамматик с использованием метасимволов предполагает, что в строке правила могут присутствовать особые символы – т.н. метасимволы, которые трактуются специальным образом. Обычно в этой роли используются () круглые, [] квадратные и {} фигурные скобки, а также “,” запятые и “” ””кавычки. Они имеют следующий смысл:
Правила рассмотренной выше грамматики G порождения целых десятичных чисел со знаком в записи с применением метасимволов будут иметь следующий вид:
<число> ® [(+, –)] <цифра>{<цифра>}
<цифра> ® (0,1,2,3,4,5,6,7,8,9)
Эти правила означают, что “число есть цепочка символов, которая может начинаться со знака + или – (причём этот знак может и отсутствовать), дальше должна обязательно содержать одну цифру, за которой может следовать (хотя и не обязательно) последовательность цифр любой длины”.
Грамматика стала более понятной, кроме того, удалось полностью избежать рекурсии, заменив её символом итерации {}. Эта форма наиболее употребима для одного из типов грамматик, а именно – для регулярных грамматик, которые будут рассмотрены ниже.
При записи правил в графическом виде вся грамматика представляется в виде набора специальным образом построенных диаграмм. Эта форма доступна только для грамматик контекстно-свободных и регулярных типов, но этого достаточно, чтобы её можно было использовать для задания известных языков программирования.
В такой форме записи каждому нетерминальному символу соответствует диаграмма, построенная в виде направленного графа. Граф имеет следующие типы вершин:
Каждая диаграмма имеет только одну точку входа и одну точку выхода, но сколько угодно вершин других типов. Вершины соединяются направленными дугами, из входной точки дуги могут только выходить, в выходную точку – только входить. Все остальные вершины должны иметь как минимум по одной выходной и одной входной дуге.
Чтобы построить цепочку символов, соответствующую нетерминальному символу грамматики, нужно рассмотреть диаграмму для этого символа. Начав движение от точки входа, нужно двигаться по дугам до точки выхода, помещая при этом все встречающиеся по пути нетерминальные символы или терминальные цепочки в результирующую цепочку. Через любую вершину графа можно пройти один раз, ни разу или сколь угодно много раз, в зависимости от пути движения. Если результирующая цепочка содержит нетерминальные символы, нужно в свою очередь рассмотреть соответствующие им диаграммы, до тех пор, пока не будет получена цепочка, состоящая полностью из терминальных символов. Для получения цепочки заданного языка процесс порождения необходимо начинать с диаграммы начального символа грамматики.
Данный способ в основном применяется в литературе при изложении грамматик языков программирования. Он удобен для пользователей – разработчиков, но практического применения в компиляторах не имеет.
От того, к какому типу относится тот или иной язык программирования, зависит сложность распознавателя для этого языка. Для некоторых типов языков в принципе невозможно построить компилятор, который анализировал бы исходные тексты на этих языках за приемлемое время на основе ограниченных вычислительных ресурсов.
1.3.1 Классификация грамматик по Хомскому
Формальные грамматики классифицируются по структуре их правил. Если все без исключения правила грамматики удовлетворяют определённой структуре, то её относят к заданному типу. Если хотя бы одно правило грамматики не удовлетворяет требованиям структуры, то она не попадает в заданный тип. Если правила грамматики соответствуют структуре нескольких типов, то она будет отнесена по классификации к самому простому из них.
Пусть грамматика обозначена как G(VT,VN,P,S), V=VTÈ VN. В соответствии с иерархией Хомского выделяют 4 типа грамматик.
На структуру их правил не накладывается никаких ограничений, т.е. правила имеют вид: a ® b , где a Î V+, b Î V*. Это самый общий тип грамматик. Грамматики, которые относятся только к этому и не могут быть отнесены ни к какому другому типу, являются самыми сложными.
К этому типу относятся два основных класса грамматик.
Контекстно-зависимые грамматики имеют правила вида a 1Aa 2 ® a 1b a 2, где a 1,a 2ÎV*, AÎ VN, b Î V+.
Неукорачивающие грамматики имеют правила вида a ® b , где a ,b Î V+, ½ b ½ ³ ½ a ½ .
В КЗ-грамматиках при построении предложений заданного языка один и тот же нетерминальный символ может быть заменен различными терминальными цепочками в зависимости от контекста, в котором он встречается. Цепочки a 1 и a 2 в правилах обозначают контекст: a 1 – левый контекст, a 2 – правый контекст. В общем случае они могут быть пустыми.
В неукорачивающих грамматиках при построении предложений языка цепочка символов заменяется на цепочку не меньшей длины.
Эти два класса грамматик эквивалентны.
При построении компиляторов такие грамматики не применяются, поскольку языки программирования имеют более простую структуру и могут быть построены с помощью грамматик других типов.
Контекстно-свободные (КС) грамматики имеют правила вида A ® b , где AÎ VN, b Î V+. В правой части у них стоит всегда хотя бы один символ. Их отличие от предыдущих типов состоит в том, что левая часть правил должна состоять ровно из одного нетерминального символа. Такие грамматики еще называют неукорачивающими контекстно-свободными (НКС) грамматиками.
Существует почти эквивалентный им класс укорачивающих контекстно-свободных (УКС) грамматик, отличие которого в том, что он допускает пустую цепочку, т.е. правила имеют вид A ® b , где AÎ VN, b Î V*. В дальнейшем, если возможность наличия в языке пустой цепочки не имеет принципиального значения, будем говорить просто о КС-грамматиках. КС-грамматики широко используются при описании синтаксических конструкций языков программирования.
В правой части правил грамматик этого типа может присутствовать не более одного нетерминального символа, причём он должен быть расположен во всех правилах одной грамматики с одной и той же стороны от цепочки терминалов, а требования к левой части правил совпадают с предыдущим типом. К этому типу относятся два эквивалентных класса грамматик: леволинейные и праволинейные (их название определяется местоположением нетерминального символа в правой части правил относительно терминальной цепочки). Для любой праволинейной грамматики можно построить эквивалентную ей леволинейную, задающую тот же язык, и наоборот.
Леволинейные грамматики могут иметь правила двух видов: A ® Bg , или A ® g , где A,BÎ VN, g Î VT*. Нетерминальный символ в правой части правил размещается слева от цепочки терминалов.
Праволинейные грамматики имеют правила тоже двух видов: A ® g B, или A ® g , где A,BÎ VN, g Î VT*. Соответственно нетерминальный символ находится справа от терминальных.
Регулярные грамматики используются при описании простейших конструкций языков программирования: идентификаторов, констант, строк, комментариев и т.д. Они очень просты и удобны в использовании, поэтому в компиляторах на их основе строятся функции лексического анализа входного языка.
Из определения типов видно, что любая регулярная грамматика является также КС-грамматикой, или любая грамматика может быть отнесена к типу 0. В то же время существуют УКС-грамматики, которые не относятся к типу 1, поскольку могут содержать правила вида A ® l , недопустимые в этом типе. В общем, сложность грамматики обратно пропорциональна тому максимально возможному номеру типа, к которому может быть отнесена эта грамматика. Самыми простыми являются грамматики типа 3, самыми сложными – типа 0.
1.3.2 Классификация языков
Языки классифицируются согласно иерархии Хомского в соответствии с типами грамматик, с помощью которых они заданы, причем из всех эквивалентных грамматик, задающих один и тот же язык, выбирается грамматика с максимально возможным номером, т.е. самая простая. Сложность языков соответствует сложности грамматик. От классификационного типа языка зависит и сложность распознавателя этого языка.
Это самые сложные языки, для распознавания которых требуются вычислители, равномощные машине Тьюринга. Для такого языка невозможно построить компилятор, который выполнил бы разбор за ограниченное время на основе ограниченных вычислительных ресурсов.
Практически все естественные языки относятся к этому типу. Одно и то же слово в естественном языке может иметь различный смысл в зависимости от контекста и играть различную роль в предложении. Такие языки далее рассматриваться не будут.
В общем случае время на распознавание языка типа 1 экспоненциально зависит от длины исходной цепочки символов.
Языки и грамматики этого типа используются в переводе текстов на естественных языках. Распознаватели, построенные на их основе, позволяют анализировать тексты с учётом контекстной зависимости в предложениях входного языка, хотя в общем случае для точного перевода всё же требуется вмешательство человека. Такие грамматики могут использоваться в сервисных функциях проверки орфографии в языковых процессорах.
Однако языки программирования имеют более простую структуру, поэтому в компиляторах КЗ-языки не применяются.
КС-языки лежат в основе большинства современных языков программирования, на их основе работают некоторые командные процессоры, допускающие управляющие команды цикла и условия.
В общем случае время на распознавание предложений языка этого типа полиномиально зависит от длины цепочки символов (это кубическая или квадратичная зависимость в зависимости от класса языка). Но среди КС-языков существует много классов, для которых эта зависимость линейна, и многие языки программирования можно отнести к одному из таких классов. КС-языки будут рассматриваться подробно.
Это самый простой тип языков, и они являются наиболее широко распространенным типом, используемым в вычислительных системах. Время на распознавание цепочек языка линейно зависит от их длины. Поэтому иногда эти языки ещё называют линейными.
Для работы с такими языками используются регулярные множества и выражения, конечные автоматы. Далее они будут рассмотрены подробно.
1.3.3 Контрольные вопросы
а) Множество всех цепочек из {0,1,a,b,c}*, начинающихся с 0 или 1.
б) Множество всех цепочек из {0,1}*, длины которых делятся на три.
в) Множество всех цепочек из {0,1}*, содержащих подцепочку ’101’.
г) Множество цепочек из {0,1,a,b}*, заканчивающихся цепочкой ’01a’.
д) Множество всех цепочек из {0,1}*, содержащих четное число нулей и четное число единиц.
1.4.1 Цепочки вывода. Сентенциальная форма
Выводом называется процесс порождения цепочек языка на основе правил определяющей язык грамматики.
Цепочка b = d 1g d 2 называется непосредственно выводимой из цепочки a = d 1w d 2 в грамматике G(VT,VN,P,S), V=VTÈ VN, d 1,g ,d 2ÎV*, w Î V+, если в грамматике G существует правило w ® g Î P. Непосредственная выводимость обозначается a Þ b . Т.е. цепочка b непосредственно выводима из цепочки a в том случае, если можно взять несколько символов в цепочке a , заменить их на другие символы согласно правилу грамматики и получить при этом цепочку b . В формальном определении любая из цепочек d 1, d 2 (или обе) может быть пустой. В пределе вся цепочка a может быть заменена на цепочку b , тогда в грамматике должно существовать правило a ® b Î P.
Цепочка b называется выводимой из цепочки a – обозначается a Þ * b , если выполняется одно из двух следующих условий:
Это рекурсивное определение выводимости цепочки. Т.е. b выводима из цепочки a , если она либо непосредственно выводима, либо можно построить последовательность непосредственно выводимых цепочек от a к b : a Þ g 1 Þ g 2 Þ … Þ g i Þ g i+1 … Þ g n Þ b . Такая последовательность непосредственно выводимых цепочек называется выводом или цепочкой вывода, а каждый переход – шагом вывода. Если b непосредственно выводима из a (a Þ b ), то имеется всего один шаг вывода.
Если вывод содержит два или более шагов, то говорят, что b нетривиально выводима из a : a Þ + b . Если количество шагов вывода известно, его можно указать у знака выводимости цепочек: a Þ 4 b означает, что b выводима из a за 4 шага. Запись a Þ 0 b означает, что цепочки равны. Целесообразно при записи цепочки вывода на каждом шаге над знаком выводимости указывать номер правила, согласно которому выполнен этот шаг.
Грамматика, в которой для любой цепочки порождаемого языка существует единственная цепочка вывода, называется однозначной.
Вывод называется законченным, если из полученной цепочки нельзя сделать более ни одного шага, т.е. если полученная цепочка пустая или содержит только терминальные символы грамматики: b Î VT*. Цепочка, полученная в результате законченного вывода, называется конечной цепочкой вывода.
Цепочка символов a Î V* называется сентенциальной формой грамматики G(VT,VN,P,S), если она выводима из целевого символа грамматики S: S Þ * a . Если цепочка получена в результате законченного вывода, она называется конечной сентенциальной формой.
Вывод называется левосторонним, если в нём на каждом шаге вывода правило грамматики применяется к самому левому нетерминальному символу в цепочке. Аналогично определяется правосторонний вывод. Если символы заменяются в произвольном порядке, вывод нельзя отнести ни к какому из типов. Для КС - грамматик для любой сентенциальной формы всегда можно построить левосторонний или правосторонний вывод. Для грамматик более сложных типов это не всегда возможно (структура правил не всегда позволяет заменять крайний левый или крайний правый нетерминальные символы в цепочке).
Рассмотрим снова пример грамматики целых десятичных чисел со знаком.
G ({0,1,2,3,4,5,6,7,8,9,–,+}, {S,T,F}, P, S).
P: S ®
T½
+T½
–T
T ®
F½
TF
F ®
0½
1½
2½
3½
4½
5½
6½
7½
8½
9.
Построим в ней несколько цепочек вывода, причём в качестве начала будем брать не только целевой символ, но и другие символы или их сочетания.
Здесь (1) – (4) – конечные сентенциальные формы, поскольку цепочка в (2) может быть получена из целевого символа грамматики (хотя в этом примере и получена из нетерминала T); (5) – просто сентенциальная форма (не конечная). В выводе (6) в явном виде не присутствует сентенциальная форма, хотя цепочка 1210 и является конечной сентенциальной формой. Для того, чтобы это подтвердить, достаточно построить другой вывод этой цепочки из целевого символа. А цепочка TFT не является сентенциальной формой, т.к. её невозможно получить из целевого символа. Все выводы, за исключением (5), являются законченными. На примере (3), (4) видно, что одна и та же цепочка может быть получена посредством разных выводов. Выводы (2), (4), (6) – правосторонние, (1) – левосторонний, (3), (5) – ни то, ни другое.
Деревом вывода грамматики G называется дерево (граф), которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям:
По структуре правил дерево вывода всегда можно построить для грамматик типа 2 и 3. Для строго формализованного построения дерева удобнее пользоваться левосторонним либо правосторонним выводом. Дерево вывода можно построить двумя способами: сверху вниз (обычно левосторонний вывод) и снизу вверх (обычно правосторонний).
Алгоритм построения дерева сверху вниз:
При построении дерева снизу вверх процесс построения начинается с листьев, в качестве которых выбираются терминальные символы цепочки языка. Они образуют последний уровень дерева; далее в грамматике выбирается соответствующее правило, согласно которому один или несколько символов цепочки могут быть “свёрнуты” в нетерминальный символ – (при левостороннем или правостороннем выводе это крайние символы в слое дерева) они соединяются с новой вершиной; и так до тех пор, пока все вершины не окажутся соединены в корневой вершине.
Поскольку компилятор читает программу сверху вниз и слева направо, для построения дерева сверху вниз обычно используется левосторонний вывод.
Пример: Рассмотрим деревья вывода для сентенциальных форм (1) и (2). Подробно рассмотрим построение для формы (1).
Дерево строится сверху вниз. Номера шагов обозначены цифрами. Процесс начинается с корня (он помечен целевым символом), далее при выводе применялось правило S ® –T (первый шаг), следовательно, в следующем уровне будут две вершины (“–” и “Т”). Вершина “–” помечена терминальным символом, значит, это лист. Вершина “Т” представляет собой нетерминал и вновь раскрывается по правилу T ® TF согласно ранее построенному выводу (второй шаг). Поскольку вывод левосторонний, каждый раз в цепочке вывода очередное правило применяется к крайнему левому нетерминалу. Поэтому следующим заменяется нетерминал Т, как самый левый в цепочке вывода (она в настоящий момент имеет вид –TF), и это третий шаг… Процесс продолжается до тех пор, пока все вершины не получат в качестве меток терминальные символы.
Для формы (2) построение отличается тем, что в качестве начального символа вместо целевого S взят нетерминал Т, а вывод использован правосторонний.
Построение дерева снизу вверх является более неоднозначным процессом. Рассмотрим его для вывода формы (4). При этом будем двигаться по цепочке вывода от её конца к началу. Сначала строим листья “2”, “6” и “3”. Последним шагом было правило F ® 2. Оно позволяет заменить терминальный символ ‘2’ на ‘F’ (схема 1). Следующие правила T ® F и F ® 6 (схема 2). Далее по правилу T ® TF нетерминалы T и F сворачиваются в T (схема 3). И наконец после применения правил F ® 3, T ® TF и S ® T получается итоговое дерево (схема 4).
1.5.1 Общая схема распознавателя
В числе прочих задач компилятор должен определить принадлежность некоторого текста к конкретному языку. В отношении исходной программы компилятор выступает в роли распознавателя, а человек, создавший программу – в роли генератора цепочек этого языка.
Распознаватель – это специальный алгоритм, позволяющий для некоторой цепочки символов определить, принадлежит ли она заданному языку. Это один из способов задания языка.
Распознаватель входит в состав компилятора и является частью программного обеспечения компьютера.
Условная схема распознавателя имеет следующий вид:
Основные компоненты распознавателя:
Алфавит распознавателя конечен; он включает в себя все допустимые символы входных цепочек, а также некоторый дополнительный алфавит символов, которые могут обрабатываться УУ и храниться в рабочей памяти распознавателя.
В процессе своей работы распознаватель может выполнять некоторые элементарные операции, такие как чтение входного символа, сдвиг головки, доступ к рабочей памяти для чтения или записи информации, изменение состояния УУ.
Работа распознавателя состоит из последовательности шагов, или тактов. То, каким должен быть этот такт, определяется текущим входным символом, состоянием УУ и символом, извлеченным из памяти. Итак,
Такт состоит из следующих моментов:
В процессе работы распознавателя происходит смена конфигураций. Конфигурация распознавателя (мгновенное описание) определяется следующими параметрами:
Конфигурация называется начальной, если УУ находится в начальном состоянии, входная головка обозревает самый левый символ на входной ленте, а память имеет заранее установленное начальное содержимое.
Конфигурация называется заключительной, если УУ находится в одном из множества заключительных состояний, а входная головка обозревает правый концевой маркер или сошла с ленты.
Распознаватель допускает входную цепочку символов, если, находясь в начальной конфигурации, в которой данная цепочка записана на входной ленте, он может проделать конечную последовательность шагов, заканчивающуюся одной из его заключительных конфигураций.
Некоторые виды распознавателей могут из начальной конфигурации проделать различные последовательности шагов, из которых, может быть, лишь некоторые (или даже одна) приведут к заключительной конфигурации. В таком случае входная цепочка является допущенной.
Язык, определяемый распознавателем – это множество всех цепочек, которые допускает этот распознаватель.
Распознаватели классифицируют в зависимости от вида составляющих их компонентов: считывающего устройства, устройства управления и внешней памяти.
По видам считывающего устройства распознаватели могут быть двусторонними и односторонними. Односторонние распознаватели допускают перемещение считывающей головки по ленте только в одном направлении, обычно слева направо (такой распознаватель называется левосторонним). Такие распознаватели не возвращаются назад к уже прочитанной части цепочки. Двусторонние распознаватели допускают перемещение считывающей головки в любом направлении.
По видам устройства управления распознаватели бывают детерминированные и недетерминированные. Распознаватель является детерминированным, если для любой допустимой конфигурации существует не более одной следующей конфигурации. Если для любой допустимой конфигурации единственно возможна ровно одна следующая конфигурация, то такой распознаватель является детерминированным полностью определённым, иначе он неполностью определённый. Для недетерминированного распознавателя на некотором шаге возможно совершить несколько альтернативных переходов в различные конфигурации. При этом может оказаться, что только одна из возможных последовательностей шагов приводит в заключительную конфигурацию.
По видам внешней памяти распознаватели бывают следующих типов:
Распознаватели без внешней памяти моделируются конечными автоматами и используют в процессе работы только конечную память УУ.
Размер внешней памяти распознавателей второго типа ограничен. Эти ограничения могут носить характер некоторой функциональной зависимости от длины исходной цепочки символов – линейной, полиномиальной, экспоненциальной и т.п. Кроме того, может быть указан способ организации внешней памяти – стек, очередь, список и т.п. Например, широко распространены распознаватели с памятью магазинного типа, которая организована по стековому принципу.
В распознавателях последнего типа предполагается, что для их работы может потребоваться внешняя память неограниченного объема, вне зависимости от длины входной цепочки. У таких распознавателей используется память с произвольным методом доступа.
Все три рассмотренных составляющих организуют общую классификацию распознавателей. Например, в ней возможен такой тип: “односторонний детерминированный полностью определённый распознаватель с линейно ограниченной стековой памятью”. Тип распознавателя в классификации определяет его сложность в целом. Сложность распознавателя напрямую связана с типом языка, цепочки которого он должен определять.
Например, для языков типа 1 (КЗ) распознавателями являются двусторонние недетерминированные автоматы с линейно ограниченной внешней памятью. Такой алгоритм уже может быть реализован в ПО компьютера. Но экспоненциальная зависимость времени разбора от длины входной цепочки существенно ограничивает применение распознавателей для КЗ-языков. Такие распознаватели, как правило, применяются для автоматизированного перевода текстов на естественных языках, когда временные ограничения на разбор текста несущественны.
Для КС-языков распознавателями являются односторонние недетерминированные автоматы с магазинной (стековой) внешней памятью. Кроме того, среди всего множества КС-языков можно выделить подкласс детерминированных языков, для которых распознавателями являются детерминированные автоматы с магазинной памятью – ДМПА. Этот класс языков наиболее интересен для построения компиляторов.
Для языков программирования более целесообразно строить компиляторы на основе КС-языков, дополняя их семантическим анализатором, чем использовать в качестве основы КЗ-языки – такая комбинация имеет более высокую скорость работы.
Для регулярных языков распознавателями являются односторонние недетерминированные распознаватели без внешней памяти – конечные автоматы (КА). Кроме того, любой недетерминированный КА всегда может быть преобразован в детерминированный (ДКА). В компиляторах распознаватели на основе регулярных языков используются для лексического анализа текста исходной программы. Регулярные языки находят применение также во многих областях, связанных с разработкой ПО вычислительных систем.
Грамматики и распознаватели – два независимых метода, которые реально могут быть использованы для определения языка. Однако при разработке компилятора для некоторого языка программирования возникает задача, которая требует связать между собой эти два метода.
Разработчики компилятора имеют дело с конкретным языком программирования, т.е. грамматика языка уже известна. Задача разработчиков состоит в построении распознавателя данного языка, который явится основой синтаксического анализатора в компиляторе.
Итак, задача разбора формулируется следующим образом: на основе имеющейся грамматики некоторого языка необходимо построить распознаватель для этого языка. Заданная грамматика и распознаватель должны быть эквивалентны, т.е. определять один и тот же язык.
В общем виде эта задача может быть решена не для всех типов языков, хотя для КС и регулярных языков задача разбора разрешима и существуют некоторые формальные методы её решения.
Компилятор должен не просто дать ответ, принадлежит ли входная цепочка данному языку, но и определить её смысл. Фактически работа распознавателя в составе компилятора заключается в построении дерева разбора, которое затем используется для генерации кода. Кроме того, если исходная цепочка не принадлежит к заданному языку, компилятор должен не просто установить факт ошибки, но и по возможности определить её тип и местоположение.