Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 53
Текст из файла (страница 53)
Такая грамматика называется неоднозначной. ь Исключение неоднозначности. Для многих полезных грамматик, в частности, описывающих структуру программ в обычных языках программирования, можно найти эквивалентные однозначные грамматики. К сожалению, однозначная грамматика часто оказывается сложнее, чем простейшая неоднозначная грамматика для данного языка. Существуют также некоторые КС-языки, обычно специально скон- струированные, которые являются существенно неоднозначными, т.е.
все грамматики для этих языков неоднозначны. ь Синтаксические анализаторы. Контекстно-свободная грамматика является ос- новным понятием для реализации компиляторов и других процессоров языков программирования. Инструментальные средства, вроде ТАСС, получают на вход КС-грамматику и порождают синтаксический анализатор — часть компилятора, распознающую структуру компилируемых программ. ь Определения тииа документа. Развивающийся стандарт Х)чН. для распределения информации посредством ччеЬ-документов имеет нотацию, называемую РТР, для описания структуры таких документов. Для этого в документ записываются вложенные семантические дескрипторы.
РТР является, по существу, КС-грамматикой, язык которой — это класс связанных с этим определением документов. Литература Контекстно-свободная грамматика была впервые предложена Хомским как способ описания естественных языков в [41. Бэкус и Наур вскоре использовали подобную идею для описания машинных языков Фортран [2~ и Алгол [7~. В результате КС-грамматики иногда называются "формами Бэкуса-Наура", или БНФ.
ГЛАВА 5. КОН'ГЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ 230 Неоднозначность в грамматиках была выделена в качестве проблемы почти одноврекеяяо Кантором [3] и Флойдом [5], Существенная неоднозначность была впервые указана Гроссом [6]. О приложениях КС-грамматик в компиляции рекомендуем прочитать в [1].
РТР описаны в документе о стандартах ХМ1. [8]. !. А. Ч. АЬо, К. ЯегЬ1, апд 5. Р. (5!!шап, Сотр/!егеи рг!пс!р/ег, Тес/гп/г!иед апЫ Тоо!з, АгМ!зоп-%ез!еу, Кеаг!!п8 МА, 1986. (Ахо А. В., Сети Р., УльманДж. Компиляторы: принципы, технологии и инструменты. — Мх Издательский дом "Вильямс", 2001.) 2. 1. 5Ч.
Вас!сиз, "ТЬе зупгах апд вешал!!сз о( гЬе ргорозег! !пгегпаг!опа1 а!8еЬга!с !апйиа8е о( ГЬе Улг!сЬ АСМ-ГРАММ сопГегепсе", Ргос. !пг/. Соп/ оп !фогта!гоп Ргосезз/п8 (1959), ()ЫЕЬСО, рр. 125 — 132. 3. Р,С.Сапгог, "Оп !Ье ашЬ!8шгу ргоЬ!еш оГ Вас!гиз яузгешз", ./. АСМ 9:4 (!962), рр. 477 — 479. 4. Н. СЬопЫсу, "ТЬгее шог[е!з Гог гЬе безспрбоп о( !апбиабе",!КЕ Тгапз. оп!и/огтаггоп Т!геогу 2:3 (1956), рр. 113-124. (Хомский Н. Три модели для описания языка. — Кибернетический сборник, вып. 2. — Мс ИЛ, ! 961.
— С. 237 — 266.) 5, К. Чгг. Р1оуг], "Оп ащЬ!8и!гу !и рЬгаяе-зггисгиге !ап8иабез", Соте. АСМ 5:10 (1962), рр. 526-534. 6. М бгозз, "1пЬегепг тпЬ|8шгу о(пипйпа! Нпеаг 8гашгпагз", /~фогтаг!оп апг/Сои!го/7:3 (1964), рр. 366 — 368. 7. Р. г4аиг еГ а!., "Керогг оп гЬе а!8ог!1Ьш!с 1ап8иа8е А1.б01. 60", Сотт. АСМ3:5 (1960), рр. 299-3! 4. См. также Сотт. АСМ 6;1 (1963), рр.
1 — 17. (Алгоритмический язык Алгол 60. — Мх Мир, 1965.) 5Чог!б-%к]е-ЧЧеЬ Сопзогг!иш, Ьтгр: //ихх. мЗ. отд/ТК/КЕС-хп~1 (1998). ЛИПРАТУРА 231 ГЛАВА 6 Автоматы е магазинной памятью Контекстно-свободные языки задаются автоматами определенного типа. Такой автомат казывается автоматом с магазинной памятью, или магазинным автоматом, и является расширением недетерминированного конечного автомата с а-переходамн, представляющего собой один из способов определения регулярных языков. Магазинный автомат— по, по существу, к-НКА с добавлением магазина. Магазин может читаться, в его вершияу могут добавляться (заталкиваться, помешаться, заноситься) или с его вершины могут сниматься символы точно так же, как в структуре данных типа "магазин". В этой главе определяются две различные версии магазинных автоматов: одна из них допускает при достижении допускающего состояния, как это делают конечные автоматы, а другая — при опустошении магазина независимо от состояния.
Показывается, что эти дка варианта допускают контекстно-свободные языки, т.е. грамматики могут быть преобразованы в эквивалентные магазинные автоматы, и наоборот. Также вкратце рассматривается подкласс детерминированных магазинных автоматов. Множество допускаемых кмн языков включает все регулярные языки, но является собственным подмножеством КС-языков. Поскольку механизмом своей работы они весьма похожи на синтаксические анализаторы, важно знать, какие языковые конструкции могут быть распознаны ими, а какие — нет. 6.1.
Определение автоматов с магазинной памятью В этом разделе магазинный автомат представлен сначала неформально, а затем — как формальная конструкция. 6.1.1. Неформальное введение Магазинный автомат — это, по существу, недетерминированный конечный автомат с опереходами и одним дополнением — магазином, в котором хранится цепочка "иагазанных символов'*. Присутствие магазина означает, что в отличие от конечного автомата магазинный автомат может "помнить" бесконечное количество информации. Одяако в отличие от универсального компьютера, который также способен запоминать неограниченные объемы информации, магазинный автомат имеет доступ к информации в магазине только с одного его конца в соответствии с принципом "последним пришел— первым ушел" ("!авт-!и-бтзт-оцт").
Вследствие этого существуют языки, распознаваемые некоторой программой компьютера и нераспознаваемые ни одним магазинным автоматом. В действительности, магазинные автоматы распознают в точности КС-языки. Многие языки контекстно-свободны, включая, как мы видели, некоторые нерегулярные, однако существуют языки, которые просто описываются, но не являются контекстно-свободными. Мы увидим это в разделе 7.2. Примером такого языка является (О" 1 "2" ! и > 1), т.е.
множество цепочек, состоящих из одинаковых групп символов О, 1 и 2. Допустить/отвергнуть Вход †-чь- Рис. б. й магазинный автомат как конечный автомат с магазинной структурой банных Магазинный автомат можно рассматривать неформально как устройство, представленное на рис. 6.1. *'Конечное управление" читает входные символы по одному. Магазинный автомат может обозревать символ на вершине магазина и совершать переход на основе текущего состояния, входного символа и символа на вершине магазина. Он может также выполнить "спонтанный" переход, используя к в качестве входного символа.
За один переход автомат совершает следующие действия. Прочитывает и пропускает входной символ, используемый при переходе. Если в качестве входа используется к, то входные символы не пропускаются. Переходит в новое состояние, которое может и не отличаться от предыдущего. Заменяет символ на вершине магазина некоторой цепочкой. Цепочкой может быть к, что соответствует снятию с вершины магазина. Это может быть тот же символ, который был ранее на вершине магазина, т.е. магазин не изменяется.
Автомат может заменить магазинный символ, что равносильно изменению вершины без снятий и заталкиваний. Наконец, символ может быть заменен несколькими символами — это равносильно тому, что (возможно) изменяется символ на вершине, а затем туда помещаются один или несколько новых символов. ПРимеР6.1.РассмотРим Язык акта= !вик)и В (0+ 1) ). Этот Язык обРазован палиндромами четной длины над алфавитом (О, 1) и порождается КС-грамматикой (см. рис. 5.1) с исключенными продукциями Р— е О и Р -+!. ГЛАВА 6. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ 234 Дадим следующие неформальное описание магазинного автомата, допускающего 1 Е,, 1. Работа начинается в состоянии с),, представляющем "догадку", что не достигнута середина входного слова, т.е, конец слова ж, за которым должно следовать его отражение.
В состоянии и, символы читаются и их копии по очереди записываются в магазин. В любой л~омент можно предположить, что достигнута середина входа, т.е. конец слова ю. В этот момент слово ж находится в магазине: левый конец слова на дне магазина, а правый в на вершине. Этот выбор отмечается спонтанным переходом в состояние с)ь Поскольку автомат недетерминирован, в действительности предполашются обе возможности, т.е. что достигнут конец слова зк, но можно оставаться в состоянии пе и продолжать читать входные символы и записывать их в магазин. 3. В состоянии с), входные символы сравниваются с символами на вершине магазина. Если они совпадают, то входной символ пропускается, магазинный удаляется, и работа продолжается. Если же они не совпадают, то предположение о середине слова неверно, т.е.
за предполагаемым и не следует и . Эта ветвь вычислений отбрасывая ется, хотя другие могут продолжаться и вести к тому, что цепочка допускается. 4, Если магазин опустошается, то действительно обнаружен вход зк, за которым следует зк . Прочитанный к этому моменту вход допускается.
6.1.2. Формальное определение автомата с магазинной памятью Формальная запись магазинного автомата (МП-автомата) содержит семь компонентов и выглядит следующим образом. )з = Щ Е, Г, 4 с)ь гь Р) Компоненты имеют такой смысл. Д: конечное множество состояний, как и у конечного автомата. Е: конечное множество входных символов, такое же, как у конечного автомата.
Г: конечный магазинный алфавит. Он не имеет конечноавтоматного аналога и явля- ется множеством символов, которые можно помещать в магазин. б; функция переходов. Как и у конечных автоматов, д управляет поведением автомата. Формально, аргументами б являются тройки б1с), а, Х), в которых ег — состояние из множества Д, а — либо входной символ, либо пустая цепочка к, которая, по предположению, не принадлежит входному ачфавиту, Х вЂ” магазинный символ из Г. Вы- ' Можно было бы также построить магазинный автомат ляя ) ь языка, грамматика которого представлена на рис.
5.1. Однако ! „, несколько проще и позволит иач сосредоточиться на идеях, квсзюшихся магазинных автоматов. 6.1. ОПРЕДЕЛЕНИЕ АВТОМАТОВ С МАГАЗИННОЙ ПАМЯТЬЮ 236 ход б образуют пары (р, у), где р — новое состояние, а у — цепочка магазинных символов, замешаюшаяХна вершине магазина. Например, если у= а, то магазинный символ снимается, если у= Х то магазин не изменяется, а если у= ! 7, то Х заменяется на 7, и У помещается в магазин.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
