Карпов - Основы построения трансляторов (2005), страница 10

е. всегда). Оказывается, что этот вид продукции СВ-+ВС с перестановкой нетерминалов очень просто представить тремя продукциями с эквивалентными возможностями. Действительно, пусть Л вЂ” новый нетерминал. Построим вместо одной продукции СВ-+ВС три другие продукции: СВ-+СЯ, СА — +ВЯ, ВЛ вЂ” >ВС. Очевидно, что последовательное применение этих продукций приведет к перестановке С и В, причем это достигнуто с помощью только контекстно-зависимых проду.<ций, удовлетворяющих ограничениям для грамматик типа 1. Итак, язык Х~ можно породить грамматикой б~ с контекстно-зависимыми продукциями, и поэтому он является контекстно-зависимым языком (т. е.

языком типа 1): 5-+аЛВС ~ аЬС СВ-+СА СА — >ВЛ В11 — >ВС Ы вЂ” ~Ы сС вЂ” +сс Языки и грамматики КС-грамматики представляют наибольший интерес в информатике. Контекстно-свободными продукциями может быть представлено большинство правил языков программирования высокого уровня, хотя во многих таких языках есть правила, требующие более сложных механизмов определения. Например, согласованность типов в операторах присваивания требует контекстнозависимой подстановки выра>кения правой части после того, как тип объекта левой части определен.

Другими подобными правилами являются требование согласованности формальных и фактических операторов процедур, запрет использования неописанных переменных и т. и. Несмотря на наличие подобных контекстно-зависимых требований, все языки программирования задаются именно КС-грамматиками, а контекстно-зависимые правила и ограничения задаются на естественном языке как дополни'г~льные ограничения. При трансляции их выполнение проверяется специальныйи семантическими программами, что не нарушает общей идеи рассмотрения синтаксиса языков программирования как заданного контекстно-свободными грамматиками. 2.5.4.

Грамматики типа 3 В грамматиках этого типа ограничения накладываются на правую часть продукций. Эти ограничения приводят к тому, что порождаемые языки этого типа являются автоматными, и распознающее их автоматическое устройство— это конечный автомат. Отсюда следует, что для языков типа 3 существует очень эффективный ~линейный по сложности) алгоритм синтаксического анализа, описывающий работу конечного автомата. Однако языки типа 3 имеют сравнительно узкое применение в информатике из-за их ограниченных порождающих возможностей. Такими языками, например, нельзя описать даже скобочные структуры арифметических выражений и, конечно, любые вложенные конструкции.

2.5.5. Вложение грамматик и языков для порождающих грамматик Хомского Очевидно, что по виду правил все грамматики типа Ж являются собственным подмножеством грамматик типа (Ф вЂ” 1). Действительно, например, грамматика б4 с правилом аЬ-+Ба является грамматикой типа О, но не является грамматикой типа 1. Грамматика 6'„является грамматикой типа 1, но не является грамматикой типа 2.

Не совсем очевидно, однако, что типы грамматик формируют иерархию также и в том смысле, что семейство языков, генерируемых грамматиками типа Ж, является собственным подмножеством семейства языков, генерируемых грамматиками типа (Л" — 1). Действительно, каждый язык может быть порож- Языки и грамматики алгоритма человеком. Человек имеет конечную память, и в этом смысле его можно представить системой с конечным числом состояний.

Исходная информация к алгоритму обычно представляется в виде последовательности (цепочки) символов. Выполняя алгоритм, человек-вычислитель использует дополнительную память (например, листы бумаги) для записи информации, причем эта запись производится им последовательно, символ за символом. При вычислениях человек может возвращаться к ранее записанной информации, стирать некоторую информацию и т. д. Таким образом, элелынтарными оиерищияли при выпо.иении сигорипта .можно счи~нсинь зстись и стирание спмвои в цепочке си1толов, а тсклсе иеренесение вниыс ния с одно;о участка наияти па другой. Поэтому предложенная Тьюрингом формальная модель вычислителя — Машина Тьюринга (МТ) — отличается от системы с конечным управлением (конечного автомата) только в двух аспектах: она имеет одну бесконечную рабочую ленту, с которой читает и куда пишет символы, и одну головку чтения-записи, которая может двигаться по рабочей ленте в любую сторону (рис.

2.12). Такая свобода движения головки чтения-записи, по сути, означает возможность создавать и впоследствии анализировать промежуточную информацию любого объема. Как оказывается, такое простое расширение возможностей радикально увеличивает вычислительную мощность машин Тьюринга по сравнению с обычными конечными автоматами. Рис. 2.12. Определение машины Тьюринга Машина Тьюринга работает по тактам. На каждом такте она читает символ из ооозреваемой ячейки рабочей ленты, изменяет свое состояние в зависимости л своего внутреннего состояния и прочитанного символа и печатает символ Глава 2 в обозреваемую ячейку рабочей ленты, после чего ее головка чтения-записи перемещается на одну позицию влево, вправо или остается на месте. Описание функционирования МТ можно считать ее программой, в которой перечислено конечное число пятерок ~команд) <к„а, р, у, О>, где.~, и, р и у имеют тот же смысл, что и в конечном автомате: находясь в состоянии л и встретив символ а в обозреваемой ячейке входной ленты, автомат переходит в состояние р и пишет в эту ячейку символ у вместо символа а.

Символ В команды показывает направление перемещения головки по рабочей ленте, которое может быть одним из трех значений: У вЂ” влево, Я вЂ” вправо и Н вЂ” оставаться на месте. Иными словами, программа МТ вЂ” это просто конечный список аргументов и соответствующих им результатов частично-определенной функции переходов и выходов б:5хЛ-+ЬхХх1'. Машина 1 ьюринга (МТ) имеет один конечный рабочий алфавит Х, в котором входные и выходные символы не различаются: выходной символ, напечатанный на ленте, машина может читать в последующих тактах.

Для удобства обычно считают, что Л содержит пустой символ Л, находящийся во всех ячейках рабочей ленты слева и справа от конечной цепочки "значащих" символов в начале работы. Пусть МТ находится в состоянии д, и в обозреваемой ячейке ленты содержится символ х. Если в программе МТ нет команды для пары <о, х>, то МТ останавливается. Если в программе МТ несколько команд для дагнюй пары <О, х>, то это недетерминированная машина Тьюринга, в ней случайно вьюирается для выполнения одна из нескольких возможных команд с левой частью =о, л>.

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

Построим машину Тьюринга„распознающую язык ~а с' ~. Представлять МТ будем подобно конечному автомату с помощью графа переходов, в котором кажд~й команде <о, х, р, у, Х)> соответствует ребро, направленное из вершины, помеченной состоянием о, в вершину, помеченную состоянием р. Само Языки и грамматики ребро помечено входным символом х, выходным символом у и направлением движения головки й (рис.

2.13). Рис. 2ЛЗ. Графическое представление команды машины Тьюринга сд, х, р, у, 0)> Именно эта последняя деталь (указание направления движения головки по входной ленте) отличает граф переходов МТ от графа переходов конечного автомата. Начальная конфигурация этой МТ (когда она находится в начальном состоянии у, а головка расположена против крайнего правого символа входной цепочки) и несколько промежуточных конфигураций, возникающих при ее раооте (рис. 2.14), поясняют алгоритм распознавания.

Рис. 2.14. Граф переходов машины Тьюринга, распознающей язык (а"с"~, и несколько ее конфигураций при обработке входной цепочки "ааассс" Глава 2 ПРИМЕР 2Л9. Рассмотрим машину Тьюринга — преобразователь (рис. 2.15), находящую наибольший общий делитель двух положительных целых чисел, заданных в унарной системе счисления, в которой числу У соответствует Ж последовательных символов '1'. В начальной конфигурации машины Тьюринга пусть головка указывает на последнюю единицу первого из двух заданных чисел. Рис. 2.15. Машина Тьюринга Рис. 2.16. Граф переходов машины Тьюринга, вычисляющей НОД двух чисел, и несколько ее конфигураций при обработке пары чисел <4, 6> Языки и грамматики Программу этой машины Тьюринга зададим с помощью графа переходов (рис. 2.16).

Стратегия вычисления ИОД двух чисел здесь — это повторяющиеся действия по нахождению меньшего из двух чисел и вычитанию его из большего до тех пор, пока не получатся равные числа. Алгоритм работы этой М 1' поясняется последовательно возникающими ее конфигурациями при обработке входа (4, б) на рис. 2.16. Машина Тьюринга, построенная для распознавания языка, может представить этот язык, поскольку она является конечным устройством.

В общем случае, все языки типа О представимы недетерминированными машинами Тьюринга. 2.6.2. Линейно-ограниченные автоматы Машина Тьюринга называется линейно-ограниченным автоматом, если существует такое число С, что в процессе обработки входной ленты, на которой в начальной конфигурации находится цепочка о, машина не может использовать более, чем С~ аз ~ ячеек ленты. Таким образом, объем памяти такого автомата не является неограниченным, как у машины Тьюринга, а определяется длиной последовательности входных символов. Для таких автоматов доказана следующая теорема. И ТЕОРЕМА 2.2. Множество цепочек над конечным словарем является языком типа 1 (контекстно-зависимым) тогда и только тогда, когда оно является множеством последовательностей, распознаваемых некоторым недетерминированным линейно-ограниченным автоматом.