Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 59
Текст из файла (страница 59)
Используя табл. 5.2, можно убедиться в соблюдении нужного условия, т, е. в том, что множества начальных и последующих символов операторов не пересекаются. Тем самым разрешается применение правил построения программы грамматического разбора В1 — В?. Таблица Б.З. Начальные и ннешиие симнолы н ПЛ(0 Начальные симеоны марьина с (з! самана 3 Внешние символы Р (3! сопы чаг Ргоседиге идентидтикитор и са11 Ьея(п и вне ггдснтпфиклтор саи Ьзд!п 1! тчш(е осЫ + — ( идентификатор число + — ( идентификатор число идентибнгкатор число ( Влок .; епд йеп до ОператоР Условие Выпал<ение Слагаемое Миожи тел ь .; ) и епд йеп до 1) 1+в епб йеп до :) и+— епд йеп до идгнтггбнгкатор число ( Внимательный читатель должен был заметить, что основные символы ПЛ/О не являются обычными отдельными буквами, как было в предыдуших примерах.
Они могут быть такими последовательностями, как, например, ВЕП1)т) или (:=). Как и в программе 5.3, для работы с чисто внешними представлениями или прн лексической обработке входной последовательности символов используется так называемый сканер. Он оформлен в виде процедуры де!аугп, задача которой — выбрать из входного файла очередной основной символе,сканер выполняет следующие действия: 1. Пропускает разделители (пробелы).
2. Распознает зарезервированные слова, талие, ьак ВЕ(л1~, Е)т))Э и т. и. ц Структура языков и трансляторы При чтении входной последователь- насти сканер де1зрт использует локальную процедуру де1ей, которая читает очередной символ. Кроме этой основной задачи де1ей также: 1. Распознает и пропускает информацию о концах строк. 2.
Переписывает входной файл в выходной, формируя, таким образом, распечатку программы. 3. Печатает в начале каждой строки ее номер нлп другую подобную информацию. С помощью сканера осуществляется необходимый просмотр вперед на один символ. Кроме того, вспомогательная процедура де1ей допускает просмотр еще на один входной символ.
Следовательно, наш транслятор «заглядывает» вперед на один основной символ плюс один вход'г ной символ. Д1одробно эти процедуры показаны в программе 5.4, которая представляет собой полную программу грамматического разбора для ПЛ/О. В действительности она уже несколько расширена в том смысле, что попутно собирает идентифнказ торы описанных констант, переменных и процедур в таблицу. При появлении идентификатора внутри оператора он ищется в этой таблице, так как нужно установить, был ли идентификатор должным образом описан.
Отсутствие такого описания можно рассматривать как синтаксическую ошибку, поскольку это формальная ошибка прн построении текста программы, а именно использование «незаконного» символа. Тот факт, что эту ошибку можно обнаружить лишь с помощью хранения информации в таблице, есть следствие присущей языку контекстной зависимости, проявляющейся в следующем правиле: всв идентификаторы соответствующего контекста должны быть описаны. На самом деле практически все языки программирования в этом смы'ле контекстно зависимы; тем не менее Рис.
З.б, Диаграмма зависимости дяя ПЛ10. 3, Распознает незарезервированные слова в качестве идентификаторов. Текущий идентификатор присваивается глобальной переменной, называемой Ы. 4. Распознает последовательности цифр в качестве чисел. Значение числа присваивается глобальной переменной пипь 5. Распознает пары специальных знаков, такие, как (:=). 8. Прогеаила ераяиегяееского разбора для П,710 355 контекстно-свободный синтаксис позволяет их описать наилучшим образом и очень полезен прн построении транслято. ров для этих языков.
Проверка некоторых контекстных зависимостей может легко включаться в общие схемы, примером чему служит использование таблицы идентификаторов в рассматриваемой программе. Перед тем как строить отдельные процедуры грамматического разбора, соответствующие отдельным синтаксическим графам, полезно установить, как зти графы взаимосвязаны.
Для э~ого строится так называемая диаграмма зависимости; она изображает связи между графами, т. е, для каждого графа 6 указывает все такие графы 6~ ... 6„, с помощью ргойгага Р1.0 [1прий огариг); [транслятор с ПЛ/О, только синтаксический анализ) 1айе1 99; сонз1 попч = 11; [число зарезервированных слов» гхтах =* 100," [длина таблииы имен) тпах — 14; [максимальное число инар в числах) а1 10; [длина имен) йуре еутЬо1 (пи1, Иеп1, питЬег; р)из, оп[пил, г1тег, з1аг1ь ойазут, ед1, пед, 1гг, 1ед, ягг, «ед, 1рагеп, грагеп, готта, зет1со1оп, рег1ой, Ьесотез, Ьейтзут, епагут, уОчп, 1йепгут, жй11елут, г[озут, са11еут, сопггзут, гангут, ргосеут); ауа =- расйей аггау [1 ..
а1» оу сйаг; оЬуесг - (сопзгапй гапаЬ1е, ргосейиге); таг сй: сйаг; [последний прочигпанный входной символ) зут: еучпйо1; [последний прочитанный символ языка) И: а11а; [последнее прочитанное имя ) пит: 1пгейег; [последнее прочитанное число) сс: 1пгеяег; [счетчик символов) П: Ьиейег; [длина строки) Ы: 1пгеяег; Ипе: аггау [1 ., 8 1» о1 сйаг; а: аКа; нога: актау [1., поги» ог а[уа1 иркут: аггау [1, . поги» о1 зутБо1> езут: аггау [сйаг» оГ еутйо1; 1аБ)е: аггау [О., гхтах» ог гесогй пате: а[уа; й1па': оЬресС еий; епй е1ее !1сЬ == " .йеи Ъеп1п гегсЬ; КсЬ =- ' ' !Ьеп Ъее!п тут:= Ьесотез; бе!сЬ епй е1ее аут:= ли1; епй е!ее Ьерйп аут:=- ггугп«сЬ»! ае!сЬ епй е|и1 «це!юут»; ргосейиге Ыос1с (!х: !пгекег); ргосейиге еп!ег (Ь; оЬ1ссг); Ьеп1п «зались обьекта в таблицу) гх:= гх + 1; п1!Ь гаЫе«гх» йо Ьеп!плате '.= И; Иий: Ь; епй епй «ел!се»; апис!!оп рог!г!оп (И: а1!а); !и!еаег; тег 1: 1пгскег; Ъеи!и «поиск имени И в таблице) !аЫе«О»лате:= И; 1:= гх,' иЫ1е гаЫе«!»лате Ф Ийо1:= 1 — 1; рог!г!оп ."= 1 епй «рол!!ол»; ргосейиге сопзМсс1ага!!оп! Ьепш !!аут = Испг гЬеп Ьеп!а ко!вуги; !1юут = еа!йеа Ьепй ае!аут; !раут питЬег йеп Ьеп!а еп!сг (сепг!апг)! бе!вуги еай е1ее сггог (2) епй е1ее еггог (3) еай е1ее еггог (4) епй «сопгИес1ага!!оп»; ргосейиге гагре!ага!!оп; Ьеп!а )г аут ' = Иелг йеп Ьепш еп!ег (гаггаЫе)! ке!аут епй е1ее вггог (4) епй !гам!сс!ага!Ил»; ркоеедше к1агетсп11 чак г: 1гггедег; ркосейше схргезх1оп; ркоседцке гсгпг; ркоседшеУасгог; чак г: 1гггсесг," Ъедш Ыюут = 1депгкЬев Ъеа!в г: =- рок1г1оп(гд)1 111 =- О йев еггог (1 1) е1ке 11 гаЬ1еЯ Ипд ргосег1иге йеи еггог (21)1 еекеупг евй е1ае 11 аут = пигпЬег йеп Ъед1в аегкупг евй е1ае 11кут = 1рагсп йев Ьейдв аеьупг; ехргешгоп; 11кут = грагспйевдеиуте1еееггог(22с) евй е1ее еггог (23) евд (уасгог); Ъее!в (гегт) уаског1 чййе зут ш 111тса, к1ак1г) до Ъейй де аут; Засгог евй евй (1сгпг); Ъед1в (ехргшк(оп) Ноут 1в1р1иг, т1пик) йев Ьейдв аеггут; гсгт евй е1ее гегт1 гчЬПе аут й (р1ак, т1пик1 йо Ьей!в Юегкут1 каст евй евд «ехргеш1оп); ркосейше соггдг21огг; Ьеддв Клут огдггкут 1Ьев Ъейш аегкут1 ехргешгоп евй е1ае Ъегк1в ехргеИоп; И вЂ” Фут 1о (са1, пса, 1кк, 1сгЬ дгг, дед)) йев сггог (20) е1ае пМ!е еут =* савва бо Пеиа пеРугП; солзП1сс1ага11оп епй; и аут аеи1со1оп иьеп хеЯт е1ее сггог (5) спи; Ноут = еаюут йеп Ьер5а хе1лут1 тагЛес1ага11оп; пЫ!еюуи = саттон ЬеЬба пегаут; иИес!ага11оп сад; И хуи *= аст1со1оп йеп 5е1юут е)ее еггог (5) епй; вЫ1е лут = угаснут до Ьепш 8ейут; Н аут Ысп1 ббеа Ьеа1п спгег (ргосейпге)1 аейуи еай е1ве еп ог (4); М аут = депе'со1оп йеп гегаув е)ее еггог (5); Ь1осй (гх); М аув «ст1со1оп йеа 5есаув еЬе еггог Д1 ий 1 ейиевепФ епй (Ь1осп) 1 Ьеай (оспоепап программа) 5ос сЬ: = 'А' Фо ' йо саутин: = пп11 ыогс1( 1):~ 'Веии '; нога( 2) Зиад 'сАИ.
жоЫ( 3): 'сонет'; иог4( 4): * 'по мог4( Я: 'ейо '; ыогг1( б): пг иог4 7):= '000 '; жоЫ( 8): 'РВОснияе'; иог4( 9): тнем ', "ьогй((О): = 'члп м~ог411) ,'= 'Внн.е" ~юугп( Ц:= Ье51пгуи; паут( 2): .са11луи; паут( 3);= сопхмув; юут( 4) = йюущ праут( 5);= епйут1 н>юув( б) ! с тЯт; улут( 7);= оййут„' пнув( 8): угаснув; аут[ 9):= йепгут; щ т(10); тавут; мюут(11]:= вИехуи; ааутГ+'):= р1аг; агут('-'): = т1пию; ааутГе'):= Ипею; агути: ° а1аюб; асутГ('):= 1рагеп; ггутГ)'):= грагеп; ееутГ='); е51; «сутГД; = савва; б.ч.
Вост аноелсние ири сингакси геских ошибках зги бхутто,'):= рег(ос(; ехут('че'):= иед; ххуог('~'):= Ы; лгут('>'3:= хгг,' слуги('('): — — !егг; АгутГ()'):=. яег1; хгуггг[' );= сепг(со!огг1 росе(огггриг); сс .'= О; Н:=- О; сй;= ' '; )с(с;= а1; йе1зугл; 5/ос/с (О); 11 еуог =,ь рог(ое( ТЬеи егтог (9)1 99: гег1ге(гг еиц . Програчма блк Грамматический разбор Лли ПЛ10.
которых определен 6. Соответственно это определяет, какие процедуры будут вызываться другими процедурамйе Диаграмма зависимости для ПЛ/О показана на рис. 5.5. Циклы на рис. 5,5 обозначагот появление рекурсии. Поэтому важно, чтобы в языке, на котором реализуется транслятор ПЛ/О, была разрешена рекурсия. Кроме того, диаграмма зависимости позволяет сделать выводы об иерархической организации программы грамматического разбора. Например, все процедуры могут содержаться (быть описаны как локальные) в процедуре, которая анализирует конструкцшо (программа) (которая поэтому будет главной программой в программе грамматического разбора). Далее, все процедуры, изображенные ва диаграмме ниже (блок), могут определяться как лока,льные в подпрограмме, представляющей цель разбора (блок).
Разумеется, все эти процедуры вызывают сканер де1зут, который в свою очередь вызывает де1сй. $.9. ВОССТАНОВЛЕНИЕ ПРИ СИНТАКСИЧЕСКИХ ОШИБКАХ До сих пор программа грамматического разбора лишь устанавливала, принадлежит ли входная последовательность символов языку, В качестве побочного результата она также определяла структуру предложения. Но если встречалась неправильная конструкция, задача программы могла считаться выполненной и она могла закончить работу. Разумеется, на практике такая схема неприемлема. Вместо этого транслятор должен выдавать соответствующую диагностику об ошибках и продолжать пропссс грамматического разбора, возможно находя дальнейшие ошибки. '!тобы продолжагь работу, нужно либо сделать какис-го предположения о том, чтб на самом Б Структура яэьп<ов и трансляторы деле имел в виду автор неправильной программы, либо пропустить некоторую часть входной последовательности, лябо сделать и то, н друтое.
Сделать достаточно разумные пред. положения о действительных намерениях программиста — довольно сложно. До сих пор зто не удавалось формализовать, поскольку формальный подход к сшпакспсу н грамматическому разбору нс учп1тывает многие факторы, сильно влияющие на человеческое сознание. Например, распространенной ошибкой является пропуск знаков пунктуации, таких, как точка с запятой 1не только в программированин1), но весьма маловероятно, что кто-то пропустит знак к+э в арифметическом выражении.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
