ТИП 2: контекстно-свободные языки

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

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

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

ТИП 3: регулярные языки

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

Распознаватели

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

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

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

 

 

Как видно из рисунка, распознаватель состоит из следующих основных компонентов:

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

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

· внешней (рабочей) памяти, которая может хранить некоторую информацию в процессе работы распознавателя и в отличие от памяти УУ может иметь неограниченный объем.

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

Конфигурация распознавателя определяется следующими параметрами:

- содержимое входной цепочки символов и положение считывающей головки в ней;

- состояние УУ;

- содержимое внешней памяти.

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

Распознаватели можно классифицировать в зависимости от вида составляющих их компонентов: считывающего устройства, устройства управления (УУ) и внешней памяти.

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

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

По видам внешней памяти распознаватели бывают следующих типов:

- распознаватели без внешней памяти;

- распознаватели с ограниченной внешней памятью;

- распознаватели с неограниченной внешней памятью.

Вместе эти три составляющих позволяют организовать общую классификацию распознавателей.

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

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

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

Для языков с фразовой структурой (тип 0) необходим распознаватель, равномощный машине Тьюринга - недетерминированный двусторонний автомат, имеющий неограниченную внешнюю память.

Для контекстно-зависимых языков (тип 1) распознавателями являются двусторонние недетерминированные автоматы с линейно ограниченной внешней памятью.

Для контекстно-свободных языков (тип 2) распознавателями являются односторонние недетерминированные автоматы с магазинной (стековой) внешней памятью.

Для регулярных языков (тип 3) распознавателями являются односторонние недетерминированные автоматы без внешней памяти - конечные автоматы.

Грамм-ки и распозн-ли - 2 независимых метода, кот-ые идеально м.б. использованы для определ-я какого-л. языка. Однако при разработке компил-ра для нек-го языка программ-я возникает задача, кот-ая требует связать между собой эти методы задания языков. Разработчики компил-ра всегда имеют дело с уже определенным языком программ-я. Грамматика для синтаксич.конструкций этого языка известна. Она, как правило, четко описана в стандарте языка. Задача разработчиков заключ. в том, чтобы построить распозн-ль для заданного языка, кот-ый затем будет основой синтаксич.анализатора в компил-ре. Т.о., задача разбора в общем виде заключ-ся в следующем: на основе имеющейся грамм-ки нек-го языка построить расп-ль для этого языка. Заданная грамм-ка и распозн-ль д.б. эквива-ны, то есть определять один и тот же язык.

 

Цепочки вывода

Цепочка b Î V* непосредственно выводима из цепочки a Î V⁺ в грамматике G = (VT, VN, P, S) (обозначим a ® b), если a = x₁gx₂, b = x₁dx₂, где x₁, x₂, d Î V*, g Î V⁺ и правило вывода g ® d содержится в P.

Цепочка b Î V* выводима из цепочки a Î V⁺ в грамматике G = (VT, VN, P, S) (обозначим a Þ b), если существуют цепочки g₀, g₁, ... , g_n (n >= 0), такие, что a = g₀ ® g₁ ® ... ® g_n= b.

Последовательность g₀, g₁, ... , g_n называется выводом длины n.

Тогда языком, порождаемым грамматикой G = (VT, VN, P, S), называется множество L(G) = {a Î VT* | S Þ a}.

Другими словами, L(G) - это все цепочки в алфавите VT, которые выводимы из S с помощью P.

Цепочка a Î V*, для которой S Þ a, называется сентенциальной формой в грамматике G = (VT, VN, P, S). Таким образом, язык, порождаемый грамматикой, можно определить как множество терминальных сентенциальных форм.

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

Вывод цепочки b Î (VT)* из S Î VN в контекстно-свободной грамматике G = (VT, VN, P, S), называется левым (левосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого левого нетерминала.

Вывод цепочки b Î (VT)* из S Î VN в контекстно-свободной грамматике G = (VT, VN, P, S), называется правым (правосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого правого нетерминала.

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

Например, для цепочки a+b+a в грамматике G = ({a,b,+}, {S,T}, {S ® T | T+S; T ® a | b}, S) можно построить выводы:

(1) S®T+S®T+T+S®T+T+T®a+T+T®a+b+T®a+b+a

(2) S®T+S®a+S®a+T+S®a+b+S®a+b+T®a+b+a

(3) S®T+S®T+T+S®T+T+T®T+T+a®T+b+a®a+b+a

Здесь (2) - левосторонний вывод, (3) - правосторонний, а (1) не является ни левосторонним, ни правосторонним, но все эти выводы являются эквивалентными в указанном выше смысле.

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

Дерево называется деревом вывода (или деревом разбора) в контекстно-свободной грамматике G = {VT, VN, P, S), если выполнены следующие условия:

(1) каждая вершина дерева помечена символом из множества (VN È VT È e ) , при этом корень дерева помечен символом S; листья - символами из (VT È e);

(2) если вершина дерева помечена символом A Î VN, а ее непосредственные потомки - символами a₁, a₂, ... , a_n, где каждое a_i Î (VT È VN), то A ® a₁a₂...a_n - правило вывода в этой грамматике;

(3) если вершина дерева помечена символом A Î VN, а ее единственный непосредственный потомок помечен символом e, то A ® e - правило вывода в этой грамматике.

Пример дерева вывода для цепочки a+b+a в грамматике G:

Дерево вывода можно строить нисходящим либо восходящим способом.

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

Метод восходящего разбора заключается в том, что исходную цепочку пытаются “свернуть” к начальному символу S; на каждом шаге ищут подцепочку, которая совпадает с правой частью какого-либо правила вывода; если такая подцепочка находится, то она заменяется нетерминалом из левой части этого правила.

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

 

19) Преобразование грамматик

1. Если при описании грамматики указаны только правила вывода Р, то будем считать, что большие латинские буквы обозначают нетерминальные символы, S - цель грамматики, все остальные символы - терминальные.

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

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

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

(1) первый символ исходной цепочки a₁a₂...a_n# заменяем нетерминалом A, для которого в грамматике есть правило вывода A ® a₁ (другими словами, производим "свертку" терминала a₁ к нетерминалу A);

(2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: полученный на предыдущем шаге нетерминал A и расположенный непосредственно справа от него очередной терминал a_i исходной цепочки заменяем нетерминалом B, для которого в грамматике есть правило вывода B ® Aa_i (i = 2, 3,.., n) и т.д.

Это эквивалентно построению дерева разбора методом "снизу-вверх": на каждом шаге алгоритма строим один из уровней в дереве разбора, "поднимаясь" от листьев к корню.

При работе этого алгоритма возможны следующие ситуации:

(1) прочитана вся цепочка; на каждом шаге находилась единственная нужная "свертка"; на последнем шаге свертка произошла к символу S. Это означает, что исходная цепочка принадлежит языку (a₁a₂...a_n# Î L(G)).

(2) прочитана вся цепочка; на каждом шаге находилась единственная нужная "свертка"; на последнем шаге свертка произошла к символу, отличному от S. Это означает, что исходная цепочка не принадлежит языку (a₁a₂...a_n# Ï L(G)).

(3) на некотором шаге не нашлось нужной свертки, т.е. для полученного на предыдущем шаге нетерминала A и расположенного непосредственно справа от него очередного терминала ai исходной цепочки не нашлось нетерминала B, для которого в грамматике было бы правило вывода B ® Aa_i. Это означает, что исходная цепочка не принадлежит языку (a₁a₂...a_n# Ï L(G)).

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

⇐ Предыдущая45678910111213Следующая ⇒

Поделиться: