Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 60
Текст из файла (страница 60)
Для программы грамматического разбора н то 1ка с запятой, и плюс — просто терминальные символы без какого-либо существенного различия; и для человека точка с запятой почти не имеет значения и в конце строки кажется избыточной, тогда как знак арифметической операции, бесспорно, осмыслен а). При разработке подходягцей системы восстановления следует принимать во внимание многие подобные соображения, которые связаны с конкретным языком и не могут обобщаться для всех контекстно-свободных языков. Все же сушествуктт некоторые правила и рекомендации, действ)чогцие пе только в рамках одного языка, такого, как ПЛ/О.
Для них, пожалуй, характерно, что они в равной мере связаны как с ~сходн~й коинепцпсп языка, так ханизмом восстановления в программе грамматического разбора. Прежде всего совершенно ясно, что эффективное восстановление возможно или, во всяком случае, намного облегчается лишь в случае языка с ггросто11 стрэ1укгурог1. В частности, если при обнаружении ошибки пропускается какая-го часть входной последовательности, то язык обязательно должен содержать слулсвбно~е слова, неправильное употребление которых крайне маловсрояпю и которые поэтому могут использоваться для возобновления грамматического разббра. В ПЛуО зто правило строго соблюдается: каждый оператор начинается с однозначного служебного слова, такого, как Ьеи1п, 11, зчЬ11е; то же относится к описаниям: они начинаются с чаг, сопз1 илн ргоседцге, Мы назовем зто привилол~ слилсебных слов.
Второе правило более непосредственно связано с построением программы грамматического разбора, Для нисходящего ") Моэкет быпч эти соображения натолкнут читателя ~а мысль, что в современных языках программировании слишком уж много внимания было уделено формальной синтаксичссчоя проблгчатпкс. И это па этапе, когда мы ставим заделу обшеиии с, маншпои па сс~сствсином языке~— Приза рсц 5.9. Восстановление нри сингаксинеских он»ирках збз анализа характерно, что цели разбиваются на подцели; при этом процедуры вызывают друтис процедуры, соответст>зуюшие этим подцелям.
Второе правило определяет, что(если процедура грамматического разбора обнаруживает ошибку, то она не должна прекрагцать работу и сообщать о случившемся вызвавшей ее процедуре. Вместо этого она должна самостоятельно продолжать просмотр текста до того места, откуда можно возобновить анализ. Мы назовем это правилом «пе п>однилеай панику».
Из него следует, что нз процедуры грамматического разбора не может быть другого выхода, кроме обычного завершения работы. *,. Правило «не поднимай панику» можно интерпретировать следующим образом; при появлении неправильной конструкции процедура должна пропустить входной текст, пока не встретится символ, который по правилам может следовать за той конструкцией языка, которую она пыталась обнаружить.
Это означает, что каждой процедуре грамматического разбора в момент текущей ее активации должно быть известно множество внешних символов. Поэтому на первом этапе уточнения (или дополнения) мы снабдим каждую процедуру грамматического разбора явным параметром (нуг, который задает возможные внешние символы. В конце каждой процедуры вставляется явная проверка: действительно ли следующий символ входного текста содержится среди этих внешних символов (если это уже не обусловлено логикой программы)? Все же с нашей стороны было бы неразумно при всех обстоятельствах пропускать входной текст до следующего появления такого внешнего символа.
В конце концов, програчмисг мог по ошибке пропустить всего одни симво.т (например, точку с запятой), а игнорирование текста до следу.ощего внешнего символа может иметь гибельные последствия. Поэтому ко множествам символов, которые прекращают пропуск текста, мы добавим служебные слова, отмечающие начало конструкции, которую не следует пропускать. Таким образом, символы, передаваемые в качестве параметров процедуре грамматического разбора, — это симнолос ооэобнонленип, а не просто внешние символы. Мы можем считать, что множества символов возобяовления с самого начала содержат отдельные служебные слова и при проходе иерархии подцелей грамматического разбора постепенно дополняются внешними символами этих подцеле(ь» Для удобства вводится общая подпрограмма, называемая >ез1, — она выполняет описанную выше проверку.
Эта процедура (5,17) имеет три пава- метра: 1, Множество з! допустимых следующих символов; если текущий символ к нему не принадлежит, то имеет место оп>ибка д Структура лзыкоо и тронтллторы 2. Множество з2 дополнительных символов возобновления, появление которых определенно является ошибкой, но которые ни в косм случае нс следует пропускать.
3. Номер и, который присваивается ошибке, если процедура ее обнаружит. ргосе4пге бмг (т1, т2;,тутгг.тег; и: т1гдет); Ьеп!п !à — ~(тгтн ш х1) тйеп Ьея!и еттот(п); т1; =- т1+т2; пЬ11е -г(лунг ш г1) йо яейутп епй (5.17) епй Процедуру (5.17) удобно использовать при входе в процедуру грамматического разбора для проверки, является ли текущий символ допустимым начальным символом анализируемой конструкции. Это рскомендуется во всех случаях, когда про.
цедура Х вызывается безусловно, как в операторе !1 аут =а, !Ьеп 5, е)зе Ц лутц=а„!Ьеп 5„е(ве Х который получен из порождающего правила А н= а,5, !... ! а„5„!Х. (5.18) В этих случаях параметр з! должен содержать лпгогкество начальных символов Х, а з2 — множество внешних символов А (см. табл. 5.2). Подробно эта процедура показана в программе 5.5, которая представляет собой дополненную версию программы 5А. Для удобства читателя вся программа приведена полностью, за исключением инициации глобальных переменных и процедуры де!зуат, оставшихся без изменений, Предполагаемая до сих пор схема пытается возобновить грамматический разбор, вернуться на правильный путь, пропустив одпн илн более символов входного текста. Но это неудачная стратегия во всех случаях, когда ошибка вызвана пропуская символа.
Опыт говорит о том, что такие ошибки фактически связаны с символами, выполняющими чисто сингаксическпс функции и пе представляющими какого-либо действия, Примером слугкит точка с запятой в ПЛ/О. Однако, поскольку множества внешних символов дополнены определспнымн служсбнымн словами, на самом деле грамматический разбор вовремя прекращает пропуск символов, т. е. ведет себя так, аак если бы забытый символ был в тавлен. Зто видно пз той части программы (5.19), которая анализирует б.й. Восггалоалекие крк синтаксических ошибках 363 со».гавные операторы.
Оиа «всгавляет»> пропущенные точки с .шнятой перед ключевымп словами. Множество, называемое иггггйензуз, есть множество начальных символов конструкции «оператор». 11'лунг = Ьефагуггг 1)гев )гей!и де!луги; лгагетепг((зепггео!оп, енгггут)+..глуе); чтйе лут пг 1гетгео(оп)+лгагЬе3луе бо Ьерн (5.19) 1г лунг = нет!со!оп 1)гев яеггут е1ве еж о!; кгагегггеггг(!реггггсо1огг, елй угп)+Хвой евд; 11' еупг = еиггдут 1)геи яеглут е)ае еп ог Енгй О том, насколько успешно эта программа обнаруживает синтаксические ошибки и справляется с необычнымн ситуациями, можно судить по программе ПЛ/О (5.20), Ее распечатка является результатом работы программы 5.5, а в табл.
5.3 перечислены возможные сообщения об ошибках, соответствующие номерам ошибок в программе 5,5, Таблица 3.3, Сообщения об ошибках, выдаваемые транслятором с ПЛ10 !. = вместо ".= 2. г!ет числа после = 3. Нет = после иденпгфнквгора 4, Нет идентификатора после сопз1, чаг, ргосебпге б. Пропущена злпятая нли точкз с запятой 6. Неверный символ после описания процедуры 7, Пет оперзторз 8, Неверный символ после операторной части блока 9. Нет многоточия 1О. Пропущена точка с запитой мелгду операторами 11. Неописанный идентификатор !2.
Недопустпмое присвапваняе константе или процедуре, 13 Требуется: = 14. Нет идентификатора после сан 13. Вызов констагпы илн переменной вместо процедуры 16. Требуется 1иео 17. Требуется точка с запятой илн епб 18 Требуется до 19. Неверный символ после оператора 20. Требуется сравнеяпе 2! Выражение содержит идентификатор процедуры 22 Отсутствует правая скобка 23 Неверный сичвол после множителя 24 Неверный символ в начале выражения 30. Слншкои большое число Программа (5.20) получена в результате намеренного вве.
дсппя синтаксических ошибок в (5,!4) — (5.15). сапа! п1 "".= "0 и — — хп гаг,г,г,:,с,г! е 5 5 ргссейпге тп!ф!у; гаг а,й Ьса!па:=- и; Ь:= у, а;= 0 111 пЫ!еЪ > Ойо !10 Ьеа!п ияЫЬйо=;= ~+ а! !16 !19 а:= 2а; Ь:=- Ь/2! .! 23 епй епй; рсоссйоге к!!г!к!с так !г; 5 сопок Ьо — — 2, к1псс:= 3; 7 1 Ъса!па = х; д != 0; к!:= у; !!3 пЬ!!е гг .- г йо ж;=- !асс!с! ъЬ!!е и~ > у Ъеа!ад~:= (2гд; !г != н/2)! т22 !23 !1н < ! !Ьсп Ьед!и г:= г-и' д:= 9+1 [23 епй спй епй; ркоссйоке усй; гаку",д; Ъсй!и,1;= г! .с ~= у 367 дд Ноеетапоалеепе при епчтаксипеектст ошибка.т мЫ!еу' -'- к де 717 Ъей!и !1/' < и !1теп д,'= К вЂ” 7'.
К я < у !Пев 1': =- .т — к; и:=,т епе1; Ьеи!и х:= пт; у:= и; саП тн16р1у1 х:= 25; у;= 3; саП с1ЬЫе; х .= 84; у:= Зб; саПнеФ; саП х„'х:=- ясе1; все! =х )15 721 т12 ~13 !24 спи, 717 75 77 РНОЯИАМ!НСОМРЬВТЕ (5.20) Депд — ' ' ~ьаа!и 7 Рис. 66. Синтаксис с модифиппрованнмм составным оператором, Любая схема восстановления, реализованная с раразумнымн затратамп, потерпит неудачу, т, е. не сможет адекватно обработать некоторые ошибочные конструкции,~Однако хороший транслятор должен обладать такими важными свойствами; 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
