Учебное пособие 130

114 11 02 12 04 07 13 01 05 00 15 10 03 09 08 06

204 02 01 11 10 13 07 08 15 09 12 05 06 03 00 14

311 08 12 07 01 14 02 13 06 15 00 09 10 04 05 03

110 15 04 02 07 12 09 05 06 01 13 14 00 11 03 08

209 14 15 05 02 08 12 03 07 00 04 10 01 13 11 06

304 03 02 12 09 05 15 10 11 14 01 07 06 00 08 13

113 00 11 07 04 09 01 10 14 03 05 12 02 15 08 06

201 04 11 13 12 03 07 14 10 15 06 08 00 05 09 02

306 11 13 08 01 04 10 07 09 05 00 15 14 02 03 12

101 15 13 08 10 03 07 04 12 05 06 11 00 14 09 02

207 11 04 01 09 12 14 02 00 06 10 13 15 03 05 08

302 01 14 07 04 10 08 13 15 12 09 00 03 05 06 11

Таким образом,

f(Ri-1,Ki) = P(S1(B1),..S8(B8)).

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

S1(B1)S2(B2)S3(B3)..S8(B8)

(продолжение следует)

Этот 32-битовый блок (матрицы Sj содержат 4-битовые значения) преобразуется с помощью матрицы перестановки Р:

Матрица перестановки битов Р

Выбор элемента в матрице Sj осуществляется следующим образом. Пусть на вход поступает 6-битовый блок Bj=b1b2b3b4b5b6, тогда двухбитовое число b1b6 выбирает строку матрицы, а b2b3b4b5 - номер столбца. Результатом Sj(Bj) будет 4-битовое число, расположенное по указанному адресу.

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

ми в позициях 8, 16, 24, 32, 40, 48, 56, 64.

Для удаления контрольных битов и подготовки ключа к работе используется матрица РС-1:

Матрица первоначальной подготовки ключа PC-1

Результат преобразования РС-1(К) разбивается на две половины C0 и D0 по 28 битов каждая. После этого блоки C0 и D0 на каждой итерации последовательно сдвигаются влево. Пусть Ci и Di обозначают значения, полученные после i-й операции:

Ci=LSi(Ci-1) D=LSi(Di-1),

Где LSi представляет собой i-й элемент матрицы сдвига LS:

Матрица сдвигов для вычисления ключа

Полученное значение вновь "перемешивается" в соответствии с матрицей PC-2:

Матрица завершающей обработки ключа PC-2

Таким образом:

Ki= PC-2(CiDi)

Восстановление исходного текста осуществляется по этому алгоритму, но вначале используется ключ К16, затем - К15 и так далее. То есть, сначала проводится перестановка битов в соответствии с матрицей обратной перестановки IP-1, потом следуют 16 циклов шифрования с обратной последовательностью ключей, и наконец, преобразование по матрице начальной перестановки IP.

Для наиболее полного удовлетворения всем требованиям, предъявляемым к коммерческим системам шифрования, реализованы несколь-

ко режимов работы алгоритма DES. Наиболее широкое распространение получили режимы:

·Электронный шифрблокнот (Electronic Codebook) - ECB;

·Цепочка цифровых блоков (Cipher Block Chaining) - CBC;

·Цифровая обратная связь (Cipher Feedback) - CFB;

·Внешняя обратная связь (Output Feedback) - OFB.

DES-ECB

Длинный файл разбивается на 64-битовые отрезки (8 байтов). Каждый из этих блоков кодируется независимо с использованием одного и того же ключа шифрования. Основное достоинство этого алгоритма - простота реализации. Недостаток - относительно слабая устойчивость против квалифицированных криптоаналитиков.

DES-CBC

В этом режиме исходный файл М разбивается на 64-битовые блоки: М=М1М2:Мn. Тогда для всех i=1,N (N-число блоков) результат шифрования Ci будет определяться следующим образом:

C0=начальное значение

Ci=DES(Mi XOR Ci-1)

Дешифрование выполняется в обратном порядке.

C0=начальное значение

Mi=Ci-1 XOR DES (Ci)

Достоинство данного режима состоит в том, что он не позволяет накапливаться ошибкам при передаче. Блок Mi является функцией только Ci-1 и Ci. Поэтому ошибка при передаче приведет к потере только двух блоков исходного текста.

DES-CFB

В этом режиме размер блока отличается от 64. Файл, подлежащий шифрованию (дешифрованию), считывается последовательными блоками длиной t битов (t=1,64). 64-битовый регистр сдвига инициализируется строкой S0, которая может быть либо заполнена пробелами, либо в нее записывается исходное значение ключа К. Предположим, что в результате разбиения на блоки, мы получили N блоков, длиной по t битов каждый (остаток дописывается нулями или пробелами). Тогда для любого i=1,N:

Ci=Mi XOR Pi,

где Pi означает t старших битов предыдущего зашифрованного блока. Обновление сдвигового регистра осуществляется путем удаления его старших N битов и дописывания Ci справа.

Восстановление зашифрованных данных проводится аналогично: Pi и Ci вычисляются следующим образом.

Mi=Ci XOR Pi,

DES-OFB

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

Положим M=M1M2:Mn. Для всех i=1,N,

Ci=Mi XOR Pi

где Pi - старшие t битов операции DES(Si-1). Отличие от режима CFB состоит в методе обновления сдвигового регистра. В данном случае это осуществляется путем отбрасывания старших t битов и дописывания справа Pi.

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

Исходный текст разделяется в соответствии с алгоритмом на блоки по 64 бит каждый. Первый блок исходного текста складывается по модулю два (операция XOR) с начальным вектором, затем зашифровывается с помощью секретного ключа, известного как отправителю, так и получателю сообщения. Полученный 64-битовый блок, в свою очередь, складывается по модулю два со вторым блоком исходного текста и снова шифруется Получается второй 64-битовый блок и операция повторяется до окончания исходного текста. Полученное в результате такой процедуры 64-битовое число является функцией секретного ключа, начального вектора и каждого бита сообщения, вне зависимости от длины последнего. Это число носит название MAC (message authentication code) и дописывается к зашифрованному сообщению, формируя таким образом как бы печать на конверте. Полученное "запечатанное" сообщение передается по каналу связи. Получатель расшифровывает сообщение и, зная секретный ключ и начальное значение вектора, вычисляет свое значение MAC. Если оба кода совпадают, то сообщение передано верно.

ОСНОВЫ СИНТАКСИСА И СЕМАНТИКИ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

Литература

1.А.Ахо, Д.Ульман Теория синтаксического анализа, перевода

икомпиляции. т.1,2 - М.:Мир, 1978.

2.Д. Грис Конструирование компиляторов для цифровых вычислительных машин. - М.:Мир, 1975.

3.Д.В.Варсанофьев, А.Г.Дымченко "Основы компиляции", 1991

4.Р.Хантер. Проектирование и конструирование компиляторов. - М.:Финансы и статистика,1984.

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

Цепочку из одного символа будем обозначать самим символом. Буквы x,y,z,u,v,w,t будем применять для обозначения цепочек. Множество всех цепочек из элементов множества E естественно обозначить через E*. Язык - это подмножество E*. Примеры язы-

n n

ков: Паскаль, Си, { 0 1 | n >= 0 }.

Язык можно задать:

-перечислив все цепочки;

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

-с помощью механизма порождения - грамматики.

Чтобы задать грамматику, требуется указать:

-множество символов алфавита (или терминальных символов) E. Будем обозначать их строчными символами алфавита и цифрами;

-множество нетерминальных символов (или метасимволов), не пересекающееся с E со специально выделенным начальным символом S. Будем обозначать их прописными буквами;

-множество правил вывода, определяющих правила подстановки для цепочек. Каждое правило состоит из двух цепочек (например, x и y), причем x должна содержать по крайней мере один нетерминальный символ; и означает, что цепочку x в процессе

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

x:y.

(Также употребляется запись x ::= y или x -> y)

Более строго, определим понятие выводимой цепочки:

-S - выводимая цепочка;

-если xyz - выводимая цепочка и в грамматике имеется правило y:t, то xtz - выводимая цепочка;

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

Примеры:

S : SS

Для сокращения записи принято использовать символ "или" - "|". Короткая форма записи предыдущих примеров:

Грамматики в свою очередь образуют т.н. метаязык. Выше была описана "академическая" форма записи метаязыка. На практике применяется также другая форма записи, традиционно называемая нормальными формами Бэкуса-Наура (НФБН). Терминалы в НФБН записываются как обычные символы алфавита, а нетерминалы - как имена в угловых скобках <>. Например, грамматику целых чисел без знака можно записать в виде:

<число> : <цифра> | <цифра> <число> <цифра> : 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Рассмотрим язык простейших арифметических формул:

<формула> : (<формула>) | <число> | <формула><знак><формула> <знак> : + | *

Почему "3+5*2" является формулой? Приведем последовательность преобразований цепочек (так называемый "разбор" или "вывод"):

<формула> : <формула> <знак><формула> : <формула><знак><формула><знак><формула> : <число> <знак><формула><знак><формула> :

Сокращенно наличие вывода (цепочки преобразований) будем записывать в виде <формула>::3+5*2. Большинство грамматик допускают несколько различных выводов для одной и той же цепочки из языка. Постройте другой вывод для цепочки "3+5*2".

Если в процессе вывода цепочки правила грамматики применяются только к самому левому нетерминалу, говорят, что получен левый вывод цепочки. Аналогично определяется правый вывод. Какой вывод построен в предыдущем примере?

Изобразим выполняемые замены цепочек в виде т.н. "дерева разбора" (или дерева вывода). По традиции дерево изображается "вверх ногами":

<формула>

Нарисованное дерево имеет ветви (линии) и узлы (помечены терминалами и нетерминалами), из которых растут ветви. Конечные узлы (терминалы) называются листьями. Понятия "поддерево", "корень дерева", видимо, не нуждаются в определении.

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

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

Дерево разбора определяет некоторую структуру цепочки языка. Так, мы видим, что подцепочка "3+5" является "формулой". Это противоречит нашим (интуитивным) понятиям о смысле исходной формулы: 3+5 в отличие от 5*2 не является подвыражением. Мы можем учесть приоритет операций, изменив грамматику:

<формула> : <терм> | <формула> + <терм> <терм> : <элемент> | <терм> * <элемент> <элемент> : (<формула>) | <число>

Как добавить в язык операции вычитания и деления?

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

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

Перевод с одного языка на другой называется трансляцией или компиляцией. Другими словами, компиляция - поиск соответствия написанных программистом предложений структурам, определенным грамматикой и генерация кода для каждого предложения. Грамматика определяет форму (синтаксис) допустимых предложений языка.

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

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

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

Грамматика языка программирования - это формальное описание его синтаксиса. Грамматика в форме Бэкуса-Наура состоит из множества правил вывода, каждое их которых описывает синтаксис некоторой конструкции языка. Например, рассмотрим фрагмент грамматики подмножества языка Паскаль:

1. <prog>::=PROGRAM <prog_name> VAR <dec_list> BEGIN <stmt_list> END.

2.<prog_name>::= id

3.<dec_list>::= <dec>¦<dec_list>;<dec>

4.<dec>::= <id_list>:<type>

5.<type>::= INTEGER

6.<id_list>::= id¦<id_list>,id

7.<stmt_list>::= <stmt>¦<stmt_list>;<stmt>

8.<stmt>::= <assign>¦<for>¦<if>¦<body>

9.<assign>::= id:=<exp>

10.<exp>::= <term>¦<exp> + <term>¦<exp> - <term>

11.<term>::= <factor>¦<term> * <factor>¦<term> DIV <factor>

12.<factor>::= id¦const>(<exp>)

....

n. <body>::=<stmt>¦BEGIN <stmt_list> END

Строки символов в <> называются нетерминальными символами, т.е. именами конструкций. То, что не заключено в <>, называется терминальными символами или лексемами (id, const) и т.п.

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

Второе правило раскрывает структуру конструкции <prog_name>. Лексема id представляет произвольный идентификатор (имя).

Третье правило служит для задания списка описаний перемен-

ных <dec_list>. Элементами списка могут быть либо отдельные нетерминальные символы <dec>, либо разделенные символом ';' список <dec_list> и <dec>. Заметим, что большинство правил вывода являются рекурсивными, т.е. определяются в терминах самих себя.

Правило для записи переменной <dec> строится из списка идентификаторов <id_list>, двоеточия и конструкции <type>, которая для простоты включает только одно значение INTEGER.

Правило <id_list> совпадает с правилом <dec_list>. Однако разделителем в списке идентификаторов является ','.

Описание набора операторов программы <stmt_list> приведено в седьмом правиле. Оператор <stmt> может присутствовать в одном из четырех вариантов: присваивания <assign>, цикла <for>, усло-

вия <if> и блока <body>.

Оператор присваивания в левой части содержит лексему идентификатора переменной, а в правой - правило для задания выражения <exp>. Выражение состоит из отдельных термов (операндов) <term> или из термов, соединенных операциями + и -. Термом может быть <factor> в виде идентификатора, константы или выражения в скобках, а также другой терм, умноженный ('*') или деленный ('/') на <factor>. Обратим внимание на то, что умножение и деление выполняется перед сложением и вычитанием, т.е. * и / имеют более высокий ранг. Аналогичным образом строятся нетерминальные символы других операторов.

Операторный блок <body> записан как дизъюнкция оператора

<stmt> и <stmt_list> в операторных скобках BEGIN END .

ЛЕКСИЧЕСКИЙ АНАЛИЗ

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

PROGRAM 1

VAR 2

BEGIN 3

...

id 22 INTEGER 23

Зарезервированные слова, знаки операций, скобки требуют указания только кода. Для идентификаторов и констант необходимо указывать дополнительную информацию - атрибуты (тип, имя, значения, класс хранения и т.п.). Атрибуты хранятся в таблице символов. Спецификатором лексемы в данном случае является указатель на соответствующий элемент таблицы символов. Пополнение таблицы осуществляется по мере появления новых объектов программы. Сложной задачей является обеспечение приемлемого времени просмотра таблицы символов. Для каждого элемента таблицы строится ХЭШ-функция, значение которой однозначно определяет место элемента в таблице. ХЭШ-функции ключевых лексем вычисляются заранее

ипомещаются в неизменяемую часть таблицы.

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

Сканер должен учитывать соглашения по формату строк прог-

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

СИНТАКСИЧЕСКИЙ АНАЛИЗ

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

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

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

и т.д.

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

Отношение = означает, что обе лексемы имеют одинаковый уровень и должны рассматриваться как составляющие одной конструкции.

1.id1 :=

<=

<= < N1 >

12.id1 := <N3> - <N6> ;

<= < N7 >

13.id1 := <N7> ;

<= N8 >

14.<N8>;

Сканирование слева направо продолжается до тех пор, пока не определится фрагмент, ограниченный отношениями < >. Этот фрагмент интерпретируется как нетерминальный символ Ni и не участвует в дальнейшем разборе.

Метод операторного предшествования можно применить ко всей программе целиком.

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

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

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

Иерархия Хомского. Регулярные языки

Классификация грамматик по сложности соответствующих прог- рамм-распознавателей называется иерархией Хомского. В ней выделены 4 класса грамматик (в порядке возрастания сложности):

а) регулярные (или автоматные). Правила имеют вид:

A : xB или A : x, где x - цепочка терминалов или e; б) контекстно-свободные (или КС). Правила имеют вид:

A : y, где y - цепочка из терминалов и нетерминалов Примеры - "скобочный язык", язык арифметических формул;

в) контекстно-зависимые (неукорачивающие). Правила имеют вид: z : y, где z и y - цепочки из терминалов и нетерминалов, z содержит нетерминал, |z| <= |y|

n n n

Пример: a b c г) без ограничений

Класс языка определяется классом самой простой (в смысле иерархии Хомского) из описывающих его грамматик.

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

Регулярные языки и регулярные выражения

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

Этот класс языков "устроен очень хорошо" - для всех типичных вопросов известны ответы и эффективные алгоритмы. Примеры таких вопросов:

-является ли объединение, пересечение, дополнение регулярных языков регулярным,

-является ли регулярный язык конечным, пустым,

-совпадают ли два регулярных языка,

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

(Замечание. Для других классов иерархии Хомского дела обстоят значительно хуже, например, проблема эквивалентности для КС-язы- ков алгоритмически неразрешима.)

Контекстно-свободные языки

Класс контекстно-свободных языков допускает распознавание с помощью недетерминированного КА со стековой (или магазинной) памятью.

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

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

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

e(A)[x] для каждого правила грамматики A:x а(а)[] для каждого терминала а

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

а(е)[а] для каждого терминала а

е(x)[A] для каждого правила грамматики A:x

Удобно считать, что в начале разбора магазин этого автомата пуст. Тогда в конце разбора в магазине останется символ S.

По недетерминированному КА с магазинной памятью можно построить КС-грамматику. Таким образом класс КС-языков и класс языков, допускаемых автоматами с магазинной памятью, эквивалентны.

К сожалению, не каждый КС-язык допускает разбор с помощью детерминированного автомата. Например, язык цепочек-палиндромов из 0 и 1 не может быть допущен детерминированным КА с магазинной памятью. Таким образом, недетерминированные автоматы со стеком могут распознавать более широкий класс языков, чем детерминированные автоматы со стеком - в этом их существенное отличие от КА. Практический интерес для реализации компиляторов представляют детерминированные КС-языки - собственное подмножество КС-языков, допускающее распознавание с помощью детерминированных автоматов с магазинной памятью.

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

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

Во втором случае детерминированный разбор удобно формализовать в терминах "сдвиг" (перенос символа из входной цепочки в магазин) и "свертка" (применение к вершине магазина какого-либо правила грамматики). При просмотре входной цепочки слева направо при этом будут получаться правые выводы. Проблема в этом случае состоит в выборе между сдвигом и сверткой и в выборе правила для свертки. Следующие лекции будут посвящены практическим методам разбора детерминированных КС-языков сверху вниз и снизу-вверх.

LL(k) языки и грамматики

Рассмотрим дерево вывода в процессе получения левого вывода цепочки. Промежуточная цепочка в процессе вывода состоит из цепочки из терминалов w, самого левого нетерминала A, недовыведенной части x:

-S--

/\

/+А-x-\

/¦ \ -w---u----

Для продолжения разбора требуется заменить нетерминал A по одному из правил вида A:y. Если требуется, чтобы разбор был детерминированным (без возвратов), это правило требуется выбирать специальным способом. Говорят, что грамматика имеет свойство LL(k), если для выбора правила оказывается достаточно рассмотреть только wAx и первые k символов непросмотренной цепочки u. Первая буква L (Left, левый) относится к просмотру входной цепочки слева направо, вторая - к используемому левому выводу.

Определим два множества цепочек:

FIRST(x) - множество терминальных цепочек, выводимых из x, укороченных до k символов.

FOLLOW(A)- множество укороченных до k символов терминальных цепочек, которые могут следовать непосредственно за A в выводимых цепочках.

Грамматика имеет свойство LL(k), если из существования двух цепочек левых выводов:

S :: wAx : wzx :: wu

S :: wAx : wtx :: wv

из условия FIRST(u)=FIRST(v) следует z=t.

В случае k=1 для выбора правила для А, достаточно знать только нетерминал A и а - первый символ цепочки u:

следует выбрать правило A:x, если а входит в FIRST(x) следует выбрать правило A:е, если а входит в FOLLOW(A)

LL(к)-свойство накладывает довольно сильные ограничения на грамматику. Например, LL(2) грамматика

S : aS | a

не обладает свойством LL(1), т.к. FIRST(aS)=FIRST(a)={a}. В дан-

ном случае можно понизить величину k с помощью "факторизации" (вынесения множителя за скобку):

S : aA

A : S | e

Любая LL(k)-грамматика однозначна. Леворекурсивная грамматика не принадлежит классу LL(k) ни для какого k. Иногда удается преобразовать не LL(1)-грамматику в эквивалентную ей LL(1)-грамматику с помощью устранения левой рекурсии и факторизации. Однако проблема существования эквивалентной LL(k)-грамматики для произвольной не LL(k)-грамматики неразрешима.

Существуют детерминированные языки, которые не являются LL(k) n n n 2n

ни для какого k, например - {0 10 U 0 10 | n>=1}.

Пример

Пустые цепочки порождают только нетерминалы Ф1 и Т1. Более одного правила имеется для нетерминалов Ф1 и Т1; множества

FIRST(Ф1), FOLLOW(Ф1) и FIRST(T1), FOLLOW(T1) не пересекаются.

Таким образом, преобразованная грамматика является LL(1). Символы e, помещенные в множества FIRST и FOLLOW имеют разный

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

LR(k)-грамматики

Если в процессе LR-разбора принять детерминированное решение о сдвиге/свертке удается, рассматривая только цепочку x и первые k символов непросмотренной части входной цепочки u (эти k символов называют аванцепочкой), говорят, что грамматика обладает LR(k)-свойством.

-S-- / \ /-x+ \

--w----u--

Различие между LL(k)- и LR(k)-грамматиками в терминах дерева вывода:

-S-

/¦ \

/A \

// \ \ -w---v---u-

Вслучае LL(k)-грамматик однозначно определить правило, примененное к A, можно по w и первым k символам vu, а в случае LR(k)-грамматик - по w,v и первым k символам u. Это нестрогое рассуждение показывает, что LL(k)-языки < LR(k)-языки.

LR(0)-грамматики

Рассмотрим вначале наиболее простые грамматики этого класса - LR(0). При разборе строки LR(0)-языка можно вообще не использовать аванцепочку - выбор между сдвигом и сверткой делается на основании цепочки x (см.картинку). Так как в процессе разбора она изменяется только с правого конца, ее называют стеком. Будем считать, что в грамматике нет бесполезных символов и начальный символ не встречается в правых частях правил - тогда свертка к начальному символу сигнализирует об успешном завершении разбора. Попробуем описать множество цепочек из терминалов и нетерминалов, появляющихся в стеке в процессе всех LR-разбо- ров (другими словами - всех правых выводов из грамматики).

Определим следующие множества:

L(A:v) - левый контекст правила A:v - множество состояний

стека, непосредственно перед сверткой v в A в ходе всех успешных LR-разборов. Очевидно, каждая цепочка из L(A:v) кончается на v. Если у всех таких цепочек отрезать хвост v, то получится множество цепочек, встречающихся слева от A в процессе всех успешных правых выводов. Обозначим это множество L(A) - левый контекст нетерминала A.

Построим грамматику для множества L(A). Терминалами новой грамматики будут терминалы и нетерминалы исходной грамматики, нетерминалы новой грамматики обозначим <L(A)>,... - их значениями будут левые контексты нетерминалов исходной грамматики. Если S - начальный символ исходной грамматики, то грамматика левых контекстов будет содержать правило

<L(S)> : e - левый контекст S содержит пустую цепочку Для каждого правила исходной грамматики, например,

A : B C d E

добавим в новую грамматику правила:

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

Назовем LR(0)-ситуацией правило грамматики с одной отмеченной позицией между символами правой части правила. Например, для грамматики S:A ; A:aAA ; A:b существуют следующие LR(0)-си-

туации: S:_A; S:A_; A:_aAA; A:a_AA; A:aA_A; A:aAA_; A:_b; A:b_. (позиция обозначена символом подчеркивания).

Будем говорить, что цепочка x согласована с ситуацией А:b_c, если x=ab и a принадлежит L(A). (Другими словами, LR-вывод мо-

жет быть продолжен x_... = ab_... :: abc_... :: aA_... :: S_ .)

В этих терминах L(A:b) - множество цепочек, согласованных с ситуацией A:b_, L(A) - цепочки, согласованные с ситуацией A:_b, для любого правила A:b.

Пусть V(u) - множество ситуаций, согласованных с u. Покажем, что функция V - индуктивна.

Если в множество V(u) входит ситуация A:b_cd, то ситуация A:bc_d принадлежит V(uc). (c - терминал или нетерминал; b, d - последовательности (может быть пустые) терминалов и нетерминалов). Других ситуаций вида A:b_d, с непустым b в V(uc) нет. Осталось добавить в V(uc) ситуации вида C:_..., для каждого нетерминала C, левый контекст которого содержит uc. Если ситуация A:..._C... (C-нетерминал) принадлежит множеству V(uc), то uc принадлежит L(C) и V(uc) включает в себя ситуации вида C:_...

для всех C-правил грамматики.

V(e) содержит ситуации S:_... (S-начальный символ), а также ситуации A:_..., если нетерминал A встречается непосредственно после _ в ситуациях, уже включенных в V(e).

Наконец, мы готовы дать определение LR(0)-грамматики. Пусть u - содержимое стека в процессе LR-разбора, V(u)-множество LR(0) ситуаций, согласованных с u. Если V(u) содержит ситуацию вида А:x_ (x-последовательность терминалов и нетерминалов), то u принадлежит L(A:x) и допустима свертка x в A. Если V(u) содержит ситуацию A:..._a... (а-терминал), то допустим сдвиг. Говорят о конфликте сдвиг-свертка, если для одной цепочки u допустимы и сдвиг, и свертка. Говорят о конфликте сверткасвертка, если допустимы свертки по различным правилам.

Грамматика называется LR(0), если для всех состояний стека в процессе LR-вывода нет конфликтов сдвиг-свертка или свертка-свертка.

Рассмотренная выше грамматика является LR(0)-грамматикой. Ее функция V принимает 6 различных значений (вычисляется конечным автоматом с 6 состояниями). В состояниях 0,2,4 возможен только сдвиг, в состоянии 3 - свертка по правилу A:b, в состоянии 5 - свертка A:aAA, в состоянии 1 - свертка S:A - т.е. успешное завершение разбора.

Остается показать, как можно построить модуль, разбирающий предложения LR(0)-языка. Чтобы не вычислять значение функции V заново для каждого нового состояния стека, будем хранить в стеке вместе с каждым символом xi значение V на цепочке (x0...xi).

стек.сделать пустым стек.добавить ( '#', начальное состояние ) цикл

. выбор из V ( стек.вершина.состояние ).действие

. . "сдвиг" =>

. . прочитать очередной символ в ( новый символ )

. . "свертка" =>

. . удалить правую часть правила из стека

. . новый символ := левая часть правила

. . "успех" =>

. . стоп( "успех" )

. конец выбора

. старое состояние := V ( стек.вершина.состояние )

. новое состояние := старое состояние . переход [новый символ]

. если новое состояние = "Ошибка" то стоп( "ошибка" ) конецесли

. стек.добавить ( новый символ, новое состояние ) конец цикла