Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 23
Текст из файла (страница 23)
Иначе говоря, мы хотим иметь алгоритм, который для произвольной контекстно-зависимой грамматики 6 и входной цепочки и! определял бы, принадлежит ли эта цепочка языку Е(6) (см. упр. 2.1.18). Если допустить, что среди правил контекстно-зависимой грамматики есть только одно е-правило (не снимая с грамматики остальных ограничений), то расширенный класс грамматик уже способен порождать все рекурсивно-перечислимые множества (см. упр. 2.1.20). Грамматика примера 2.8 — это грамматика без Ограничений. Заметьтс, что она не является пи праволинейной, ни контекстно-свободнои, ни контекстно-зависимой. Соглашение. Если язык Л порождается грамматикой типа х, то В называется языком типа х.
Это соглашение относится ко всем „типам х", которые мы уже определили, и к тем, которые еще определим. ГЛ. 2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ Таким образом, язык Е (0) примера 2.3 — праволипейиый, язык ь'(6„) примера 2.4 — контекстно-свободный, а язык А (б) примера 2.5 — контекстно-зависимый. Язык, порожденный грамматикой примера 2.6,— зто язык без ограничений, а язык (!ею(его (а, Ь)' и юФ е) — контекстно-зависимый, Определенные ийми четыре типа грамматик и языков часто называют иерархией Холекого. Соглашение. Далее мь! будем пользоваться сокращениями КС и КЗ для терминов „контекстно-свободиый" и „контекстно-зависимый" соответственно. Каждый праволинейный язык является КС-языком, и существуют КС-языки (например, (О" 1")п) 1)), которые ие являются праволинейными.
КС-языки, не содержащие пустой цепочки, образуют собственный подкласс КЗ-языков. А они в свою очередь образуют собственный подкласс рекурсивных множеств, которые собственно включены в класс рекурсивно-перечислимых множеств. Последние порождаются грамматиками общего вида. Доказательства этих фактов оставляем в качестве упражнений. Часто определя1от контекстно-зависимые языки как языки, определенные нами ранее, плюс все языки вида Т,() (е), где Т.— контекстно-зависимый язык в смысле нашего определения.
В таком случае КС-языки образуют собственное подмножество КЗ-языков. Следует подчеркнуть, что, если язык задан какой-то грамматикой, это еще пе зйачит, что его нельзя породить менее мощной грамматикой. Например, контекстно-свободная грамматика 5 А51е А-~0(1 порождает язык (О, 1)*, который, как мы уже видели, можно породить и праволииейной грамматикой. Следует также упомянуть о том, что в последнее время были введены грамматические модели, не входящие в иерархию Хомского. Введение новых моделей грамматик отчасти объясняется Р з',.
ай е н ззаЗЗ"-" "" '~ у з Некоторые из этих моделейпрйведенйв упражнениях. 2.1.4. Распознаватели Второй распространенный метод, обеспечивающий задание языка конечными средствами, состоит в использовании распознавателей. В сущности, распознаватель — это очень схематизированный алгоритм, определяющий некоторое множество. Распознаватель можно изобразить так, как показано на рис. 2.1. 112 2Л.
СПОСОВЫ ОПРЕДЕЛЯНИЯ ЯЗЫКОВ Распознавательсостоит из трех частей †входн ленты, управ- ляющего устройства с конечной памятью и вспомогательной, или ! рабочей, памяти. 1 Ьодлаа канвах ага гав Рнс, 2,!. Распознаватель. Входную ленту можно рассматривать как линейную последовательность клеток, или ячеек, причем каждая ячейка содержит точно один входной символ из некоторого конечного входного алфавита.
Самую левую и самую правую ячейки могут занимать особые концевые маркеры; маркер может стоять только на правом конце ленты; маркеров может ие быть совсем. Входная головка в каждый данный момент читает, или, как иногда говорят, обозревает, одну входную ячейку. За один шаг работы распознавателя входная головка может сдвинуться на одну ячейку влево, остаться неподвижной или сдвинуться на о иу ячейку вправо. Распознаватель, который никогда не передвигает свою входную головку влево, называется односторонни Я. Обычно предполагается, что входная головка только читает, т. е. в ходе работы распознавателя символы на входной ленте не меняются.
Но можно рассматривать и такие распознаватели, входная головка которых и читает и пишет. Паиятью распознавателя может быть любого типа хранилище информации, или данных. Мы предполагаем, что алфавит памяти конечен и хранящаяся в памяти информация построена, или образована, только из символов этого алфавита.
Предпо- ГЛ. 1. ЭЛЕМЕНТЫ ТЕОРПИ ЯЗЫКОБ 1.!. СПОСОБЫ ОПРЕДЕЛЕНИЯ ЯЗЫКОВ лагается также, что в любой момент времени можно конечными средствами описать содержимое и структуру памяти, хотя с те- чением времени объем памяти может становиться сколь угодно большим. Важный пример вспомогательной памяти — магазинная память (или попросту магазин), которую можно описать абст- рактно как цепочку символов памяти; например, 2,Я,...Л„, где Ел для всех 1=- (, 2, ...„и принадлежит конечному алфавиту памяти Г и 2,— „верхний" символ магазина (или, как еще го- ворят, находится наверху или на вершине магазина). Поведение вспомогательной памяти для заданного класса распознавателей можно охарактеризовать с помощью двух функ- ций: функции доступа к памяти и функции преобразования па- мяти. Функция "доступа к палляти — зто отображение множества возможных состояний, илн конфигураций, памяти в конечное множество информационных символов, которое может совпадать с алфавитом памяти, Например, единственная информация, доступная в каждый данный момент в магазине,— верхний символ.
Таким образом, функция доступа к магазинной памяти !' — это такое отображе- ние Г" в Г, что Г(В!...7„)=7,. функция преобразован!ля памяти — зто отображение, описы- вающее изменения памяти. Она отображает состояние памяти и упраеллющую цепочку в состояние памяти. Если предполагается, что операция над магазинной памятью заменяет верхний символ . конечной цепочкой символов памяти, то соответствующую функ- цию преобразования памяти можно определить как такое ото- бражение д: Г" хГ" — Г*, что д(2,2ь 2„, Р, Х,)=Р,...РД...2„ Если верхний символ магазина Л, заменяется пустой цепочкой, то 2, станет верхним символом и объектом очередного доступа к памяти. Вообще именно тип памяти определяет название распозна- вателя.
Например, распознаватель, память которого организо- вана как магазин, можно назвать распознавателем с магазинной памятью (обычно его называют автоматом с магазинной памятью). Ядром распознавателя является управля!Бщее устройство с конечной памятью, под которым можно понимать программу, управляющу!о поведением распознавателя. Управляющее устрой- ство' представляет собой конечное множество состояний вместе с отображением, которое описывает, как меняются состояния в соответствии с текущим входным символом (т. е, находящимся под входной головкой) и текущей информацией, извлеченной из памяти.
Управляющее устройство опрсделяет также, в каком направлении сдвинуть входную головку н какую информацию поместись в память. 1!4 Распознаватель работает, проделывая некоторую последовательность шагов, или тактов. В начале !пакта читается текущий входной символ и с помощью функции доступа исследуется память. Текущий входной символ и информация, извлеченная из памяти, вместе с текущим состоянием управляющего устройства определяют, каким должен быть этот такт. Собственно такт состоит из следующих моментов: (!) входная головка сдвигается на одну ячейку влево, одну ячейку вправо или сохраняется в исходном положении, (2) в память помещается некоторая информация, (3) изменяется состояние управляющего устройства.
Поведение распознавателя удобно описывать в терминах конфигураций распознавателя. Конфигурация — зто как бы мгновенный снимок распознавателя, на котором изображены (!) состояние управляющего устройства, (2) содержимое входной ленты вместе с положением входной головки, (3) содержимое памяти. Управляющее устройство распознавателя может быть детерминированным или недетерминированным, Если управляющее устройство недетермллнированное, то для каждой конфигурации существует конечное множество возможных следующих шагов, любой из которых распознаватель может сделать, исходя из этой конфигурации.
Управляющее устройство называется дегперминированнь м, если для каждой конфигурации существует не более одного возможного следующего шага. Недетерминироаанные распознаватели — удобная математическая абстракция, но, к сожалению, нх обычно трудно моделировать на практике. В следующих разделах мы дадим несколько примеров и укажем приложения недетермипированных распознавателей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
