Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 37
Текст из файла (страница 37)
В языке Рег! это окружение доступно при помаши специального ассоциативного массива зЕ1чН. Одним из элементов этого окружения (в системе Е1Х!Х) является идентификатор (Ю) пользователя. В Рег1 достаточно написать следующий оператор: рг!пс "пользователь этой программы: теин('ц5ей'!ьп" и на экране монитора будет напечатано имя пользователя (перетиснная окружения ()ЯК(с), причем не потребуется определять, где в окружении хранится информация об 10 пользователя. Этот пример показывает, как легко Рег! интегрируется в операционную систему для создания сценариев обработки процессов. Простая программа Рег! состоит из последовательности операторов рг1 пЬ.
Она также включает обычные последовательности структур управления наподобие циклов Еог, иб11е и цпг11 и условного оператора 1(. Особенно удобен оператор (огезсй, который позволяет совершать цикл по всем элементам массива и выполнять для каждого из них какие-то действия, не зная заранее о размерах массива.
В Рег!, как и в некоторые другие языки создания процессов, встроена возможность обрабатывать регулярные выражения. Логическая операция =- представляет собой результат сопоставления строки с образцом. Операция 5ЕмН( 915Ей')г-янг проверяет, содержится лп в строке зЕпЧ('05Ей') регистрационное имя ынг (то есть зарегистрирован ли пользователь этой программы под указанным именем). Операция !-, напротив, осуществляет проверку на отсутствие соответствия. Регулярные выражения в языке Рег! В языке Рег! предусмотрена непосредственная трансляция регулярных выражений.
Например, для распознавания регулярного выражения' а'Ь' служит следующий сценарий Рег1: У!тцзг!Ьтп/рег1 йсообпение операционной снсгене а ган. что зго сценарий на языке Рег1 1 = <5ТЬ!ньн йсчнгыванне введенной строки в специальную переменную В 11 11 а+Ь+111(рг1пс "уезьп";) е1зе (рг1п1 "по1п";1 Образец г"лг' сравнивается с введенной пользователем строкой'. Проверка строки на соответствие регулярному выражению а Ь' будет успетпной, если строка содержит цепочку символов, удовлетворяющую заданному регулярному выражению, начиная с первого символа (") в строке и заканчивая последним ($).
Если бы нужно было просто определить, содержит ли введенная строка еттутри себя цепочку символов, удовлетворяющих регулярному выражению з'Ь', то мы бы использовали образец /а+Ь+гг. (Дополнительную информацию об операциях с регулярными выражениями можно найти в приложении, раздел Пч Е) Это регулярное выражение задает цепочку символов, начинаюцьуюся с одного или более симполов а, за которыми обязательно слелует олин нли более символов Ь.
— Прмчмч. нлуч. Ред. В Рог! образец, заданный регулярным выражением, по умолчанию сопоставляется с солержимым спенизльной псрсиенной В . — Примеч. ллуч.ред. 130 Глава 3. Вопросы трансляции языка Рег! легко позволяет проверять соответствие строк заданному образцу и осуществлять подстановку новых значений: В = 'аааЬЬЬЬ', йорнсваиваеи всгроенной переиенной 1 значение 'аааЬЬЬЬ' 1г 1вца+Ис!1(рг1ЬС "В аое $11о".) е1ве (ргзос "чаз11п"); В этом примере в!Х/У! означает следующую операцию: найти в переменной 1 цепочку символов, соответствующую образцу ~, и заменить строкой у.
Образец а+ соответствует строке, содержащей один и более символов а, в нашем примере в исходной строке ему соответствует цепочка ааа, и поэтому эта часть строки заменяется символом с. Из-за того что образец заключен в скобки, переменной 1! присваивается значение цепочки, соответствующей образцу, поэтому в итоге будет напечатано "сЬЬЬЬ апг! ааа", то есть будет представлен результат замены в соответствии с образцом и часть исходной строки, соответствующей заданному образцу. 3.3.4. Автоматы с магазинной памятью В предыдущем разделе мы обсуждали конечные автоматы и установили, что те языки, которые лопускаются такими автоматами, эквивалентны языкам, построенным при помощи регулярных грамматик. Такивк образом, между регуляршями грамматиками и конечными автоматами имеется определенное соответствие.
Аналогично мы используем НФ Б-грамматики для генерации цепочек некоторого языка и можем использовать абстрактную машину, распознающую, принадлежит ли заданная цепочка этому языку, В этом случае мы можем создать машину, называемую ивтоиатом сгнагаэиявой памятью, или МП-ивтоматом, эквивалентную уже знакомым нам НФБ-грамматикам. МП-автомат (РпзЫозеп Ацгошайоп, РВА) — это абстрактная машина, похожая на конечный автомат. МП-автомат также имеет конечный набор состояний, но, кроме того, в нем имеется стек (магазин). В М П-автомате осуществляются следующие переходы (такты); 1) считываются введенный символ и верхний символ в стеке; 2) в зависимости от этих двух значений состояние автомата меняется, и в стек записывается ноль или более символов; 3) цепочка считается допустимой, если стек становится пустым (может оыть реализован и другой вариант; строка лопускается, если МП-автомат достигает своего конечного состояния.
Можно показать, что эти два варианта эквивалентны). Легко заметить, что такие МП-автоматы обладают большими возможностями, чем КА. МП-автоматы могут распознавать цепочки типа а"Ь", которые не распознаготся при помощи КА. Нужно только поместить все символы а в стек и затем извлекать их оттуда по одному по мере того, как вводятся символы Ь. Если после ввода последнего Ь стек окажется пустым, то такая строка допускается МП-автоматом. Менее очевидно то, что языки, допускаемые МП-автоматами, эквивалентны контекстно-свободным языкам. Однако рассмотрим процесс левостороннего вы- 3.3.
Формальные модели трансляции 131 вода цепочки символов'. В таком случае сентенциальную форму можно сохранить в стеке, Действия МП-автомата таковы. 1. Если верхним символом в стеке является терминальный, то он сравнивается с очередным введенным символом и в случае совладения удаляется из стека. Несовпадение символов означает ошибку. 2. Если верхним символом в стеке является нетерминальный символ х, то он заменяется некоторой строкой а, где гх — правая часть правила х -ь а.
Такой МП-автомат моделирует левосторонний вывод для некоторой контекстно-свободной грамматики. Приведенная конструкция фактически формирует недетермннированный МП-автомат, эквивалентный соответствующей НФБ-грамматике. На втором шаге работы нашего автомата можно использовать более одного правила вида х -ь а, и не всегда ясно, какое из них следует выбрать. Недепгерминироеанный МН-автомат определяется аналогично недетерминированному конечному автомату. Цепочка допускается подобным автоматом, если существует необходимая для этого последовательность переходов.
Как соотносятся друг с другом детерминированный и недетерминированный МП-автоматы, если сравнивать их с аналогичными конечными автоматами? В данном случае существует отличие. Рассмотрим набор палиндромов, то есть строк, которые одинаково читаются в обоих направлениях, задаваемых следующей грамматикой: 5;= 050г151г2 При помощи детерминированного МП-автомата мы можем распознать такие строки следующим образом: 1) при чтении все символы 0 и 1 помегцаем в стек; 2) при считывании символа 2 автомат переходит в новое состояние; 3) сравниваем каждый новый введенный символ с верхним символом в стеке и удаляем его из стека.
Теперь рассмотрим следующее множество палиндромов: 5:;= 050г151гбг1 В этом случае мы никогда не будем знать, где находится середина строки. Для распознавания таких палиндромов автомату придется ее найти. Например, в случае палиндрома 011010110 последовательность действий МП-автомата могла бы быть такой: Стек орааннааетоя и Стек Середина 1ююгго гоюгго продолжение яь ' дыаод а контекстно-свободной грамматике называется леаосторонним, если ее правила применяются к самому левому ахождению нетсрминального символа каждой цепочки аыаоаа.
Приведенное доказатсльстао экяиаалентности языкоа, допускаемых Мп-аатоматаьги, и контекстно-саободных языков осноаыаастся па том, что а произаолыюй контекстно-свободной грамматике можно построить эквивалентный любому выводу леаосторонний вывод. — Примеч. науч. ред. 132 Глава 3. Вопросы трансляции языка Продолжение таблицы Стек сравнивается с Середина Стек 010110 10110 0110 110 1О 0 01 01! 0110 01101 011010 0110101 01101011 Только пятый шаг — когда автомат определяет, что первой половиной палиндрома является 0110,— заканчивается успешно. Если некоторая последовательность шагов определения середины цепочки приводит к се полному грамматическому разбору, то такая цепочка считается допустимой с точки зрения данной грамматики. 3.3.5.
Общие алгоритмы грамматического разбора После появления работы Хомского со временем стало ясно, что каждый тип формальной грамматики тесно связан с определенным автоматом — простой абстрактной машиной, которая обычно определяется как машина, считывающая с входной рабочей ленты последовательность символов, хранящихся в ес ячейках, и производящая выходную ленту, в ячейках которой содержатся символы другой последовательности.
К сожалению, здесь возникает проблема. Поскольку НФБ-грамматика может оказаться неоднозначной, соответствующий сй автомат должен быть нвдвтерминированным (то есть может быть несколько вариантов перехода, из которых автомат должен выбрать наиболее подходящий). Нсдетсрминированный МП-автомат может распознавать любые цепочки, порождаемые контекстно-свободной грамматикой, используя стратегию предположений (Кцезз!пя з!та!еду). Однако для целей программирования и трансляции программ требуются более ограниченные в своих действиях автоматы (детерминированные автоматы), которым не приходится заниматься предположениями. Хотя регулярной грамматике всегда соответствует детерминированный аппарат, в случае НФБ-грамматики это верно, только если грамматика является однозначной и выполнены неко~орые другие требования. Для однозначных НФБ- грамматик были разработаны методы непосредственного грамматического разбора.
Одним из самых первых был метод рекурсивного спуска. Болыпим шагом вперед стало открытие Кнутом класса так называемых ЕК-грамматик (!е(г го г!й!!! рагз!пя а!Копг!!и!з — грамматика с ограниченным левым контекстом), которые описывают все НФБ-грамматики, распознаваемые детерминированным МП-автоматом. Класс 1К(1)-грамматик включает все такие грамматики, в которых требуется знать один только следуюп1ий символ, чтобы в процессе грамматического разбора принять правильное решение. Я1Л- (Б!и!р!е 1 К вЂ” простая 1.К) и 1.А! К- 3.4. Грамматический разбор на основе метода рекурсивного спуска 133 (1лока!теат) ЕК вЂ” 1Л с «заглядыванием впереди) гралтматики являются подклассами класса ЕВ-грамматик, которые приводят к эффективным методам грамматического разбора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
