XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 108
Текст из файла (страница 108)
Д.В.1. О методах сиитаксивесхого ввалила КС-лвыхов 689 2) существует не более одной команды с левой частью дЛа, причем если такая команда существует, то не существует ни одной команды с левой частью два', где а е У 0(Л) и а'— конец цепочки а, и не существует ни одной команды с левой частью даа, а Е У. Связь между ДМП-автоматами и Ьхс(и)-грамматиками устанавливается следующей теоремой. Теорема 8.14. Язык допускается ДМП-автоматом тогда и только тогда, когда он порождается некоторой Асс(х)-грамма тикой. Определение 8.14. Язык называют детперлепипровамныи ХС-лзыиоле, если он допускается некоторым ДМП-автоматом. Заметим, что поскольку для произвольного МП-автомата (в отличие от конечных автоматов), вообще говоря, не может быть построен эквивалентный ему ДМП-автомат, то класс детерминированных КС-языков строго содержится в классе всех КС-языков.
Для детерминированных КС-языков может быть предложена стратегия восходящего анализа, называемая стпрптпегиеб „перенос — свершиа". Суть ее состоит в следующем: входная цепочка посимвольно переписывается в магазин до тех пор, пока в магазине не сформируется основа (однозначно определяемая прочитанной частью цепочки и не более чем й буквами непрочитанной части для некоторого фиксированного й > О). Сформированная в магазине основа заменяется соответствующим нетерминалом.
Если после этой замены в верхних ячейках магазина опять получилась основа, то она вновь всвертываетсяв в нетерминал, и так до тех пор, пока не окажется, что либо вся входная цепочка прочитана, а в магазине кроме начального символа в верхней ячейке осталась аксиома грамматики, либо цепочка еще не прочитана, а в верху магазина основы нет, либо, наконец, цепочка прочитана, а в верху магазина ни аксиомы, ни основы нет. 690 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ В первом случае мы имеем „допуск" цепочки (успешный результат синтаксического анализа), во втором необходимо возобновить процесс „переноса", т.е. продолжить переписывание входной цепочки в магазин, а в третьем констатировать „недопуск" (синтаксическую ошибку). Согласно теореме 8.14, подобный алгоритм может быть запрограммирован в системе команд некоторого ДМП-автомата (точнее, ДМП-автомата с выходной лентой, на которой записываются номера применяемых правил грамматики и/или сигнал ошибки).
Строгая теория ЬВ(я)-грамматик весьма сложна и никак не может быть даже фрагментарно изложена в рамках настоящего учебника. Мы рассмотрим в заключение один пример. Пример 8.26. Приведем ДМП-автомат для анализа языка. правильных скобочных структур, порождаемых грамматикой Я -~ () ~ (о') ~ о'о'. Точнее, мы рассмотрим язык правильных скобочных структур с „концевым маркером" *: записывая на ленту правильную скобочную структуру, в конце ставим символ *. Система команд анализирующего ДМП-автомата имеет следующий вид: В этой системе команд до и дэ — соответственно начальное заключительное состояния; а Е ((,)); а' Е ((, ),Я); П вЂ” на- 9оаП -+ 91 Па, доаа' -+ 91 а'а, 91ЛО -+ 918, 91Л(Я) -+ 918, 91ЛЯЯ-+ д,Я, 91Л7 + 9071 91ЛПа -+ 90Па, 91аПЯ -+ 91ПЯа, 91*Пэ" -+ 90П.
(1) (2) (8) (4) (5) (6) (7) (8) (9) Д.8.1. О методак снптакснческого анллнэа КС-клыков 691 чальный символ магазина (нззываемый иногда „маркером дна магазина"); у — произвольная цепочка, длина которой равна 3 и которая не равна (Я) и не оканчивается цепочкой 0 или ЯЯ. Легко убедиться в том, что записанная система команд действительно определяет ДМП-автомат (см. теорему 8.13). Команды (1) и (2) обеспечивают перенос в магазин входной цепочки, команды (3) — (5) — команды свертки, команды (6) — (8) обеспечивают переход нз фазы свертки в фазу переноса, если в магазине нет основы, а команда (9) переводит автомат в заключительное („допускающее") состояние в случае правильной входной цепочки.
Проанализируем на данном ДМП-автомате цепочку х = Ц))0*, которая является правильной скобочной структурой. Имеем последовательность конфигураций": ) (чо 0) 0* пО ~ (91 )) О* п(0 ) (чо )) О* п(0 ) е (91 )О* п(0> е (91,>0*,п(Я> ) (4уо,)0*,п(з> ) )- (дм О*, п(Я)) Е- (91, О*, ПЯ) $- (д1 )* и еО ) )- (бо,)*,П,90 )- (9,+,пят> )- (91,*,пят> )- )-( м,~,пя>)-(9„Л,П>. у Рассмотрение перехода от ЬВ(к)-грамматик к ДМП-автоматам и наоборот выходит за рамки нашего изложения.
На простейшем примере мы продемонстрировали только работу детерминированного восходящего анализатора. 'Здесь мы нспольэоваен угловые скобкн () дле обоэначеннл конфнгурацвй, чтобы не путать с круглыми скобкамн (), лвллввцнмнса термнналамн грамматики. 692 а кОнтекстнО-сВОБОдные языки Дополнение 8.2. Семантика формальных языков Классическая теория формальных языков, как уже отмечалось, занималась исключительно синтаксисом языков, изучая методы порождения н распознавания множеств слов. Семантиика формальных языков, сравнительно молодал ветвь теории, занимается способами сопоставленнл некоего „смысла" словам (цепочкам) языка. Необходимость в построении точного математического понлтня „смысла" днктуется развитием информационных технологнй, прежде всего тютнологнн проектирования компнллторов.
Рассмотренные вьппе языковые модели определенным образом связаны с этапами этой технологии. Текст входной программы, как известно, англнзнруется в несколько проходов. На первом проходе производится лекснческнй анализ, а именно проверяется правильность простейших элементов текста, называемых лексемами. Примерами лексем могут служить идентификаторы н константы, разрешенные синтаксисом входного языка программирования. В процессе лексического аналнза не проверяется синтаксическая правильность всей программы в целом, а проверяется только сннтакснческгл правильность лексем (в частности, правильность написания идентификаторов н констант).
Так как лексемы обычно являются элементамн некоторого регулярного языка, то базовой моделью для лексического анализатора является модель конечного автиоматиа. Если текст программы успешно прошел этап лексического анализа, то тогда проверяетсл его глобальнгл сннтакснческгл правильность. Прн этом каждая лексема рассматрнваетсл как буква. Здесь применяются методы синтаксического англнз, в частности рассмотренные вьппе (см. Д.8.1).
В предположении, что синтаксис языка программирования описан КС-граммапти- Д.8.2 Семавтнка формальных язьпсов 693 кой, основой для построения синтаксических анализаторов, как мы уже видели, выбирается модель МП-автиомаща. По завершении синтаксического анализа строится дерево вывода входной программы. После этого переходят к этапу генерации объектного кода, т.е. внутреннего машинного представления входного текста. Это значит, что выполняется перевод с некоторого языка программирования на язык машинных кодов. Но чтобы выполнить перевод текста на другой язык, необходимо каким-то образом понять его „смысл". Следовательно, анализ уже синтаксически проверенной программы с точки зрения ее „смысла" (семантический аналю) необходимо предшествует самой генерации объектного кода.
И прежде всего необходимо уточнить математически, что такое „смысл" (как раньше мы математически определяли синтаксис в терминах грамматик и автоматов). В этом дополнении мы рассмотрим некоторые методы формального (математического) определения семантики для КС- языков. Тем самым мы всюду в дальнейшем предполагаем, что язык, семантика которого определяется, может быть задан некоторой КС-грамматикой. Сразу же необходимо сделать уточнение. Как мы уже заметили ранее, исследуя явление неоднозначное~ив в КС-языках, „смысл" следует сопоставлять не самим словам языка, а деревьям их вывода: меняя дерево вывода данной цепочки, мы меняем и ее „смысл", понимаем ее по-другому (см.
8.1). Далее, можно сопоставлять „смысл" не только словам языка, точнее, деревьям вывода этих слов из аксиомы грамматики, но и так называемым фразам языка — терминальным цепочкам, выводимым ю разных нетерминалов грамматики. Например, фраза „...а так как мне бумаги не хватило" не является законченным предложением русского языка, но имеет, очевидно, какой-то „смысл". Точно так же оператор присваивания, „вынутый" из какой-то программы на какомто языке программирования, не является „программой", не может рассматриваться как элемент данного языка, но мы 694 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ в состоянии сопоставить ему тот или иной „смысл".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
