24738

Теория языков программирования и методы трансляции

Шпаргалка

Информатика, кибернетика и программирование

Если синтаксический анализ предназначен для распознавания и проверки правильности различных конструкций языка с точки зрения их синтаксиса структуры то семантический анализ предназначен для контроля этих конструкций с точки зрения их смыслового содержания. Фаза генерации кода предназначена для перевода промежуточной программы на машинный язык мы будем предполагать коды Ассемблера. Языки...

Русский

2013-08-09

233.96 KB

64 чел.

Теория языков программирования и методы трансляции

1. Языки программирования и формальные языки.   Понятие транслятора и компилятора. Фазы компиляции.   Инструменты и технологии разработки и реализации языков   программирования.

Понятие компилятора и его структура

Любая прикладная программа, написанная на языке программирования высокого уровня или проблемно-ориентированном языке, должна быть переведена в эквивалентную программу на языке машинных команд. Эту эквивалентную программу называют объектной программой или объектным кодом.

Программа, которая переводит исходную программу в эквивалентную ей объектную программу, называется транслятором (поэтому термин "трансляция" эквивалентен термину "перевод").

Транслятор, выполняющий перевод программы с языка высокого уровня (Фортран, Паскаль, Си и др.) в объектную программу (в кодах Ассемблера и т.п.), называется компилятором.

На практике процесс компилирования исходной программы в объектную происходит в несколько этапов, называемых фазами компиляции.

Обычно выделяют три фазы: - лексического анализа;   - фазу синтаксического и семантического анализов; - фазу генерации кода.

 

Лексический анализ реализуется частью компилятора, которая называется лексическим анализатором или сканером. Входом сканера является цепочка символов некоторого алфавита (текст исходной программы). С точки зрения смысла программы некоторые подцепочки этой входной цепочки представляют собой определенные объекты, которые должны рассматриваться как единое целое. Например: имена переменных, константы, зарезервированные слова и т.д. Такие цепочки принято называть лексемами. Задача сканера состоит в выделении лексем из входного текста. Так, после сканирования оператора S:=(a+b)*0.17 будет получена следующая цепочка лексем:

 < переменная>1 :=( < переменная>2  + < переменная>3)*<константа>1

Кроме того, в результате работы сканера каждая лексема заменяется некоторым стандартным обозначением и ссылкой на таблицу, содержащую более подробные сведения о лексемах (мнемонические имена лексем, их типы и др.).

Синтаксический анализ реализуется частью компилятора, называемой анализатором. В этой фазе исследуется цепочка лексем и выясняется, удовлетворяет ли она структурным условиям, сформулированным в определении синтаксиса языка. Выходом синтаксического анализатора служит помеченное дерево, представляющее синтаксическую структуру исходной программы.

Синтаксическое дерево, закодированное и представленное в памяти ЭВМ тем или иным способом (например, в виде связной списочной структуры), называется промежуточной программой.

С фазой синтаксического анализа программы тесно связан ее семантический анализ. Если синтаксический анализ предназначен для распознавания и проверки правильности различных конструкций языка с точки зрения их синтаксиса (структуры), то семантический анализ предназначен для контроля этих конструкций с точки зрения их смыслового содержания.

Обычно синтаксический и семантический анализаторы работают параллельно внутри одной фазы. Когда анализатор распознает в программе очередную языковую конструкцию, он вызывает соответствующую семантическую процедуру.

Фаза генерации кода предназначена для перевода промежуточной программы на машинный язык (мы будем предполагать коды Ассемблера). Алгоритмы генерации кода зависят от формы представления промежуточной программы, от набора команд используемого Ассемблера и других факторов.

2. Способы задания формальных языков. Грамматики, классификация     грамматик и языков. Распознаватели, конечные автоматы, автоматы с магазинной памятью. Регулярные выражения и синтаксические  диаграммы.    Соответствия между способами описания языков.

Языки

ПрограмманаписаннаянаязыкепрограммированиясостоитизоператоровкомандинструкцийкоторыевсвоюочередьсостоятизсимвольныхцепочекВведемнекоторыепонятияиобозначениякасающиесяцепочекиязыков

 символбуквазнак–неопределяемыетермины

 алфавит–множествосимволов

 цепочка–последовательностьсимволоврасположенныхзаписанныходинзадругим

 словострокапредложение–синонимыцепочки

 Обозначения

 е–пустаяцепочканесодержащаясимволов

 –цепочкаизсимволов

 –длинацепочкиколичествосимволоввней

 Цепочкавалфавитевводитсярекурсивнопосредствомследующихутверждений

е–цепочкав

если–цепочкавитоха–цепочкав

у–цепочкавтогдаитолькотогдакогдаонаявляетсятаковойвсилупилип

ПустьпроизвольныецепочкивалфавитеТогда

  1.  хназываетсяпрефиксомцепочкихуау–суффиксом
  2.  уназываетсяподцепочкойцепочкипрефиксисуффикс–тожеподцепочки

Определимследующиеоперациинадцепочками

  1.  еслиху–цепочкитоцепочкахуназываетсяконкатенациейсцеплениемхиу
  2.  обращениемцепочкихобозначаетсяназываетсяцепочказаписаннаявобратномпорядке

Рассмотримследующиемножества

  1.  итерация–этомножествовсехцепочеквалфавитевключаяеочевидночтоэто–бесконечноемножество
  2.  положительнаяитерация–этомножествоцепочекненулевойдлиныте

ПримерПустьтогда





 Языкомвалфавитеназываетсянекотороемножествоцепочекэтогоалфавитате

Пусть–языквалфавитеа–языквалфавитеТогдаязыкиназываетсяконкатенациейсцеплениемпроизведениемязыкови

 Итерацияязыкаобозначаетсяопределяетсяследующимобразом



для



 ПримечаниеЗдесьивдальнейшемзнак“”расположенныйвверхусправаотсимволаобозначаетитерациюамеждусимволами–умножениенапример–умножениеС–итерация

 Позитивнаяитерацияопределяетсякакдляиимеетследующиесвойства

а

б

Пример







 ……

Способызаданияформальныхязыковперечислить

Первыйспособоснованнаиспользованииграмматик

Второйспособзаданияформальныхязыковоснованнаприменениираспознавателей

Заданиеязыкаприпомощиграмматикиосновныеопределения

ПервыйспособоснованнаиспользованииграмматикГрамматикаэтосистемаправилпозволяющаястроить«правильные»илидопустимыецепочкиязыкаПримеромтакойсистемыиспользуемойдлязаданиясинтаксисаязыковпрограммированияявляетсяБНФсмпОпределениеформальнойграмматикиилипростограмматикипринятоевтеорииформальныхязыковвыходиткполусистемамТуэиявляетсяболеестрогимиобщим

ОпределениеГрамматикойназываетсячетверка

где–конечноемножествонетерминальныхсимволов

–конечноемножествотерминальныхсимволовпричем

конечноеподмножествомножестваЭлементамиэтогоподмножестваявляютсяпарыαβназываемыеправиламиграмматикиправиламиподстановкипродукциямиОбычноправилазаписываютсявформеαβ

–выделенныйизмножествасимволназываемыйначальнымсимволомграмматики

ОпределениеПустьзаданаграмматикаОпределимотношениенамножествеследующимобразомесли–цепочкаизиβσто

Языкпорождаемыйграмматикойобозначаетсяопределяетсякакмножествотерминальныхцепочеккоторыемогутбытьвыведеныизначальногосимволаграмматики

КлассификацияграмматикиязыковГрамматикиклассифицируютповидуихправилВыделяютчетыреосновныхклассаграмматикклассификацияХомского

Грамматиканазываетсяправолинейнойесликаждоеправилоизмножестваимеетвид

илигде

Частнымслучаемправолинейныхграмматикявляютсярегулярныеграмматикиимеющиеправилавидаилигде

ГрамматиканазываетсяконтекстносвободнойКСесликаждоеправилоизмножестваРимеетвидгде

ГрамматиканазываетсяконтекстнозависимойКЗесликаждоеправилоизмножестваимеетвидгдеи

Грамматиканеудовлетворяющаяниодномуизограничений
–называется
грамматикойобщеговида

ЗаметимчтосогласноэтимограничениямправолинейныеирегулярныеграмматикивходятвклассКСграмматикВлитературедляобозначенияэтихклассовграмматикиспользуюттакжеследующиеназвания

грамматикаобщеговида–грамматикатипа

КЗграмматика–грамматикатипа

КСграмматика–грамматикатипа

регулярнаяграмматика–грамматикатипа

СпособызаданияформальныхязыковперечислитьЗаданиеязыкаприпомощираспознавателейМоделираспознавателейконечныеавтоматыиавтоматысмагазиннойпамятьюосновныеопределенияпривестипримерыраспознавателей

ВторойспособзаданияформальныхязыковоснованнаприменениираспознавателейРаспознавательэтонекоторыйалгоритмкоторыйвыполняетанализтерминальныхцепочекиустанавливаетявляетсялианализируемаяцепочкасинтаксическиправильнойЕслираспознавательвыдаетответ«да»тоговорятчтоондопускаетцепочкуицепочканазываетсядопустимойЯзыкопределяемыйраспознавателем–этомножествоцепочеккоторыеондопускает

Распознавательможнопредставитьввидеабстрактногоустройстваструктуракоторогопоказананарис

a1

a2

an

……

Входная лента

Читающая головка

Устройство управления с

конечной памятью

Рабочая память

Рис

 ВходнаялентаэтолинейнаяпоследовательностьячееккаждаяизкоторыхсодержитодинсимволнекотороговходногоалфавитаЧитающаяголовкавкаждыймоментобозреваетодинсимволнавходнойлентеЗаодиншагработыраспознавателяголовкаможетсдвинутьсянаоднуячейкувправовлевоилиостатьсянеподвижнойМыбудемрассматриватьтолькоодносторонниераспознавателиукоторыхчитающаяголовканикогданесдвигаетсявлево

 Рабочаяпамять–хранилищеданныхпроизвольнойорганизации

 УправляющееустройствоУУсконечнойпамятьюосновнаячастьраспознавателяопределяющаяегоповедение

Работараспознавателясостоитизтактовакаждыйтактизследующихдействий

  1.  читающаяголовкасдвигаетсявправоилиостаетсянаместе
  2.  врабочуюпамятьпомещаетсянекотораяинформация
  3.  изменяетсясостояниеУУ

ПоведениераспознавателяудобноописыватьвтерминахконфигурацийКонфигурациюможнорассматриватькакмоментальныйснимокраспознавателянакоторомотраженосостояниевсехегоэлементовсостояниеУУположениечитающейголовкиидр

УУисамраспознавательназываетсядетерминированнымеслиизтекущейконфигурацииврезультатевыполнениятактараспознавательможетперейтитольководнуочереднуюконфигурациюинедетерминированным–еслипереходвозможенводнуизмножестваконфигураций

КонечныеавтоматыПростейшимиизраспознавателейявляютсяконечныеавтоматыКА

 ОпределениеКА–этопятеркаобъектовδ

где–конечноемножествосостоянийКА

–конечноемножестводопустимыхвходныхсимволоввходнойалфавит

–функцияпереходовотображениевρздесьρ–множествовсехподмножествмножества

–начальноесостояние

–множествозаключительныхсостояний

ФункцияпереходовзадаетдопустимыепоследовательностипереходовКАизодногосостояниявдругоевзависимостиотчитаемыхавтоматомсимволов

 ОпределениеПараназываетсяконфигурациейКАприэтомконфигурацияназываетсяначальнойагде–конечнойконфигурацией

ТактработыКАможнопредставитьбинарнымотношениемзаданнымнаконфигурациях

 ОпределениеБинарноеотношениестроитсяследующимобразомеслитодлявсех

Обычнымобразомвводятсяотношенияприэтом

  1.  записьсозначаетчтос
  2.  записьсозначаетчтосуществуетпоследовательностьконфигурацийКА…такаячтодлятесоответствуеттраекторииизтактов
  3.  записьссоответствуетнекоторойтраекторииКАпереводящейегоизсвзанекотороечисловключаянольтактов
  4.  записьсоответствуетнекоторойтраекторииКАпереводящейегоизсвзанекотороечислотактов

ГоворятчтоавтоматМдопускаетцепочкуеслидлянекоторогоДругимисловамицепочкадопускаетсяеслисуществуеттраекторияпереводящаяКАизначальнойконфигурациивзаключительнуюврезультатевыполнениякоторойэтацепочкаоказываетсяпрочитанной

 ЯзыкомопределяемымавтоматомМназываетсямножествоцепочек

идлянекоторого

Примерδ

Функциюпереходовδможнозадатьвявномвидеввидефункцииввидетаблицыиливвидеграфапереходовкоторыеприведеныниже

Вявномвиде

δ

δ

δ

δ

δ

δ

Ввидетабл

Таблица

Состояние

Вход

видеграфапереходов

Начало

p

q

r

1

1

0,1

0

0

ПризаданииКАввидетаблицынапересечениикаждойстрокиистолбцазаписываетсясимволсостоянияилимножествосостоянийвкотороепереходитавтоматизтекущегосостояниясоответствующегострокепричтениивходногосимволасоответствующегостолбцу

Приизображенииввидеграфаеговершиныпомечаютсясостояниямиавтоматаадуги–значениямивходныхсимволовКаждаядугапомеченнаявходнымсимволомозначаетчтопричтениивсостоянииавтоматпереходитвсостояниеКрометогоначальноеизаключительноесостояниявыделяютиздругихсостоянийКАтаккакэтопоказановыше

ПустьнавходеКАцепочкатогдаавтоматвыполнитследующуюпоследовательностьтактов



Поскольку–заключительнаяконфигурацияцепочкадопускаеся

Пустьтогда



ицепочканедопускаетсятк–незаключительноесостояние

 

ОпределениеПустьδнедетерминированныйКАНазовемегодетерминированнымеслимножествосодержитнеболееодногоэлементадлявсехи

ТакКАвпримереявляетсядетерминированнымНедетерминированныеКАсложнореализоватьнаобычныхЭВМтаккакэтиавтоматысодержатпараллельныепроцессыВтеорииавтоматовдоказываетсячтоклассязыковопределяемыхнедетерминированнымиКАсовпадаетсклассомязыковопределяемыхдетерминированнымиКАчтоимеетбольшоеприкладноезначениеприпрограммнойреализацииКА

АвтоматысмагазиннойпамятьюДругойважныйвидраспознавателяэтоавтоматсмагазиннойпамятьюМПкоторыйопределяетсяследующимобразом

ОпределениеМПавтоматэтосемеркаобъектов

гдеконечноемножествосимволовсостоянийпредставляющихвсевозможныесостоянияуправляющегоустройстваУУ

конечныйвходнойалфавит

конечныйалфавитмагазинныхсимволов

отображениеρ

начальноесостояниеУУ

символнаходящийсявмагазиневначальныймоментвремениначальныйсимвол

множествозаключительныхсостояний

СтруктураМПавтоматапоказананарис

a1

a2

an

……

Входная лента

(только чтение)

Читающая головка

Устройство управления с

конечной памятью

zm

z1

z2

Стек

(магазин)

Рис

ОпределениеКонфигурациейМПавтоматаРназываетсятройкаобъектов

гдетекущеесостояниеУУ

неиспользованнаячастьвходнойцепочкипричемпервыйсимволцепочкинаходитсяподвходнойголовкойеслиетосчитаетсячтовсявходнаялентапрочитана

содержимоемагазинапричемсамыйлевыйсимволцепочкисчитаетсяверхнимсимволоммагазинаеслиетомагазинсчитаетсяпустым

 ОпределениеТактработыМПавтоматаРбудемпредставлятьввидебинарногоотношенияропределенногонаконфигурацияхБудемзаписыватьреслимножествосодержитгде

 Еслиаетоприведеннаявопределениизаписьтактаозначаетследующее«МПавтоматРнаходясьвсостояниииимеяавкачестветекущеговходногосимволарасположенногонадвходнойголовкойавкачествеверхнегосимволамагазинаможетперейтивновоесостояниесдвинутьвходнуюголовкунаоднуячейкувправоизаменитьверхнийсимволмагазинацепочкоймагазинныхсимволовЕслиетоверхнийсимволпростоудаляетсяизмагазина»

 Еслиаетактназываетсяе–тактомВтакомтактетекущийвходнойсимволнепринимаетсявовниманиеивходнаяголовканесдвигаетсяОднакосостояниеУУисодержимоепамятимогутизменяться

Следующийтактневозможенеслимагазинпуст

 ОпределениеНачальнойконфигурациейМПавтоматаРназываетсяконфигурациявидагдетеУУнаходитсявначальномсостояниивходнаялентасодержитцепочкукоторуюнужнораспознатьавмагазинеестьтольконачальныйсимвол

Заключительнаяконфигурациягде

ГоворятчтоцепочкадопускаетсяМПавтоматомРесли
длянекоторыхи

 ЯзыкопределяемыйдопускаемыйМПавтоматомобозначаетсяэтомножествоцепочекдопускаемыхР

ПримерПустьР

где









СловесноеописаниефункцииМПавтоматкопируетвмагазинначальнуючастьвходнойцепочкисостоящуюизнулейазатемустраняетизмагазинапоодномунулюнакаждуюединицукоторуюонвидитнавходе

Рассмотримкакэтотавтоматраспознаетцепочку

≥



ВтрансляторахчастоиспользуютсямоделиМПавтоматовработающихпопринципу«опустошениямагазина»

 ОпределениеПустьГМПавтоматГоворятчтоРдопускаетцепочкуопустошениеммагазинаеслидлянекоторого

 МПавтоматизпримерадопускаетцепочкиопустошениеммагазина

ВобщемслучаеМПавтоматыкакиконечныеавтоматы–этонедетерминированныеустройстваВажнейшееприкладноезначениеимеютдетерминированныеМПавтоматы

 ОпределениеМПавтоматГназываетсядетерминированнымДМПеслидлякаждыхиГвыполняетсяодноизусловий

содержитнеболееодногоэлементадлякаждогоаи


длявсехаисодержитнеболееодногоэлемента

ОграничениягарантируютчтоприанализецепочкиМПавтоматсделаетединственновозможнуюпоследовательностьтактовкотораяприведетеголибокзаключительнойконфигурацииеслилибокошибочнойесли

  1.  СпособызаданияформальныхязыковперечислитьПраволинейныеирегулярныеязыкиЗаданиеязыкаприпомощирегулярныхвыраженийисинтаксическихдиаграммприменениевязыкахпрограммирования

Способызаданияформальныхязыковперечислить

Первыйспособоснованнаиспользованииграмматик

Второйспособзаданияформальныхязыковоснованнаприменениираспознавателей

Праволинейныеирегулярныеязыки

ГрамматикиклассифицируютповидуихправилВыделяютчетыреосновныхклассаграмматикклассификацияХомского

Грамматиканазываетсяправолинейнойесликаждоеправилоизмножестваимеетвид

илигде

Частнымслучаемправолинейныхграмматикявляютсярегулярныеграмматикиимеющиеправилавида

илигде

Заданиеязыкаприпомощирегулярныхвыраженийисинтаксическихдиаграммприменениевязыкахпрограммирования

МногиеязыковыеконструкцииудобноописываютсярегулярнымивыражениямиЭтивыражениявводятсячерезпонятие«регулярноемножество»

 ОпределениеПустьконечныйалфавитРегулярноемножествовалфавитеопределяетсярекурсивноследующимобразом

–регулярноемножество

–регулярноемножество

–регулярноемножестводлявсех

еслии–регулярныемножестваторегулярнымиявляютсямножества

 объединение

 конкатенация

 итерациягдеитерациямножестваопределяетсятак



для≥



ничтодругоенеявляетсярегулярныммножествомвалфавите

 ОпределениеРегулярныевыражениявалфавитеобозначаютрегулярныемножестваиопределяютсяследующимобразом

–обозначаетпустоемножество

е–обозначаетмножество

еслитоа–обозначает

еслииобозначаютисоответственно

то –обозначает

 –обозначает

 –обозначает

ничтодругоенеявляетсярегулярнымвыражением

 Замечания

Можнопоказатьчто

Лишниескобкимогутустранятьсяизвыраженийеслиэтонеприводиткнедоразумениям

Приоритетыопераций«»«конкатенация»«»

Регулярныевыраженияимеютследующиеалгебраическиесвойстваеслиαβγ–регулярныевыражениятогда

  1.  αββα
  2.  
  3.  αβγαβγ
  4.  αβγαβγ
  5.  αβγαβαγ
  6.  αβγαγβγ
  7.  ααα
  8.  αα
  9.  αα
  10.  ααα

–играетрольнулясвойство

е–играетрольединицысвойство

 ПримерРассмотримпримерырегулярныхвыражений

обозначает

обозначает

обозначает

обозначаетмножествовсехцепочексоставленных

изиизаканчивающихсяцепочкой

обозначаетмножествовсехцепочексоставленныхизиначинающихсясаили

–обозначаетмножествовсехцепочексодержащихчетноечислонулейичетноечислоединиц

ВпрактикеразработкиязыковпрограммированиядляихописаниянередкоиспользуютсинтаксическиедиаграммыСинтаксическаядиаграммаявляетсяэквивалентнымпредставлениемграмматикиязыкаиврядеслучаевонаоказываетсяпредпочтительнеевсилусвоейнаглядности

5. Классификация языков и грамматик. Соответствия между способами задания языков. Соответствия между КС-грамматиками и МП-автоматами. Построение МП-автомата, моделирующего левые выводы по заданной КС-грамматике (построить МП-автомат для конкретной КС-грамматики).

Классификацияграмматикиязыков

КлассификацияграмматикиязыковГрамматикиклассифицируютповидуихправилВыделяютчетыреосновныхклассаграмматикклассификацияХомского

Грамматиканазываетсяправолинейнойесликаждоеправилоизмножестваимеетвид

илигде

Частнымслучаемправолинейныхграмматикявляютсярегулярныеграмматикиимеющиеправилавида

илигде

ГрамматиканазываетсяконтекстносвободнойКСесликаждоеправилоизмножестваРимеетвид

где

ГрамматиканазываетсяконтекстнозависимойКЗесликаждоеправилоизмножестваимеетвид

гдеи

Грамматиканеудовлетворяющаяниодномуизограничений
–называется
грамматикойобщеговида

ЗаметимчтосогласноэтимограничениямправолинейныеирегулярныеграмматикивходятвклассКСграмматикВлитературедляобозначенияэтихклассовграмматикиспользуюттакжеследующиеназвания

грамматикаобщеговида–грамматикатипа

КЗграмматика–грамматикатипа

КСграмматика–грамматикатипа

регулярнаяграмматика–грамматикатипа

Соответствиямеждуспособамизаданияязыков

ДлякаждогоклассаграмматикизклассификацииХомскогосуществуетклассраспознавателейопределяющийтотжесамыйклассязыковЭтосоответствиеможнопредставитьтабл

Языкопределяемый
грамматикой

Языкопределяемыйраспознавателем

Праволинейныйязык

Языкопределяемыйконечнымавтоматом

КСязык

ЯзыкопределяемыйавтоматомсмагазиннойпамятьюМПавтомат

КЗязык

Языкопределяемыйлинейноограниченнымавтоматом

Языкобщеговидарекурсивноперечисляемыйязык

ЯзыкопределяемыймашинойТьюринга

СоответствиямеждуКСграмматикамииМПавтоматами

ВажнейшимсточкизренияприложенийкязыкампрограммированияявляетсясоответствиеКСграмматикиМПавтоматовОсобыйинтереспредставляютдвавидаМПавтоматовкоторыевпроцессеразборамоделируютлевыеиправыевыводывКСграмматикесоответственно

СоответствиеэтихМПавтоматовКСграмматикамопределяетсяследующимидвумяутверждениями

  1.  позаданнойКСграмматикеможнопостроитьМПавтоматтакойчтотераспознаетязыкпутеммоделированиялевыхвыводов
  2.  позаданнойКСграмматикеможнопостроитьМПавтоматтакойчтотераспознаетязыкпутеммоделированияправыхвыводов

ВобоихслучаяхязыкииопределяемыеэтимиМПавтоматамисовпадаютсВдальнейшемвведенныевидыМПавтоматовбудемобозначатьчерезисоответственноВобщемслучаеиявляютсянедетерминированнымиМПавтоматами

ПостроениеМПавтоматамоделирующеголевыевыводыпозаданнойКСграмматикепостроитьМПавтоматдляконкретнойКСграмматики

ПустьКСграмматикатогдаопределяетсяследующимобразом



гдеопределяетсяусловиями

еслиАРтосодержит

длявсех

ПримерПостроимдляграмматикиарифметическихвыраженийимеющихправила

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  

Согласноопределяетсявыражениями







для

ПодадимнавходцепочкуВсилунедетерминированностиприанализеонможетпроделатьмногоразличныхпоследовательностейтактованалогичнопримеруСрединихбудетиметьместопоследовательностьприводящаяикзаключительнойконфигурации

   

   

   

   

   

   

   

   

   

   

   

   

   

Еслипроанализироватьпотактовоеизменениесодержимогомагазинатоможнозаметитьчтооноизменяетсявсоответствиисшагамилевоговыводацепочкивграмматикезаисключениемтактовинакоторыхпроисходитвыбросизмагазинаверхнегосимвола

6. Общая характеристика процесса сканирования. Методики конструирования сканеров (характеристика каждого этапа построения сканера и применяемые методы). Представление результатов сканирования.

Общаяхарактеристикапроцессасканирования

ЛексическийанализилисканированиеобразуетпервыйэтаппроцессакомпиляцииНаэтомэтапесимволысоставляющиеисходнуюпрограммусчитываютсяигруппируютсявотдельныелексическиеэлементыназываемыелексемамиЛексическийанализважендляпроцессакомпиляциипоследующимпричинам

  1.  заменавпрограммеидентификаторовиконстантлексемамиделаетпредставлениепрограммыудобнеедлядальнейшейобработки
  2.  уменьшаетсядлинапрограммыткизнееустраняютсянесущественныепробелыикомментарии

Сточкизренияреализациипроцессасканированияразличаютдваподхода–прямойинепрямойлексическиеанализыПрипрямомлексическоманализетребуетсянайтиоднуизмногихлексемкоторыезаданывописанииданногоязыка

МодельюпрямоголексическогоанализатораслужитмножествоработающихпараллельноконечныхавтоматовКАкаждыйизкоторыхраспознаетлексемызаданноготипаЭтиКАможнопредставитьиреализоватькакодинконечныйпреобразовательмоделирующийработувсехКАивыдающийсигналотомкакойизнихраспозналочереднуюлексему

ПринепрямомлексическоманализетребуетсяпрочитавцепочкусимволовопределитьобразуетлиэтацепочкалексемунекоторогоконкретноготипаВэтомслучаесканерработаетвместессинтаксическиманализаторомкакнекотораяпрограммнаяпроцедурарис

SCAN

(выделение очередной лексемы)

Исходная программа

Синтаксический анализатор

обращение к сканеру

Таблица имен

Рис

СинтаксическийанализаторобращаетсяквсякийразкогдаемунуженновыйсимволприанализетекстапрограммыипостроенияеевнутреннегопредставленияВответнавызовраспознаеточереднуюлексемувисходнойпрограммеипередаетееанализаторучерезтаблицулексем

Непрямойсканерболееэкономиченвсмыслеэкономиипамятитконнесоздаетполнойтаблицылексемдлявсегоисходноготекстапрограммы

ЛексемывязыкахпрограммированиямогутбытьописанырегулярнымивыражениямиатакжесоответствующимирегулярнымиграмматикамиВпговорилосьосоответствиимеждурегулярнымиграмматикамииКАПрактическоезначениеэтогосоответствиясостоитвтомчтодляраспознаваниялексемописываемыхрегулярнымивыражениямиможноиспользоватьсоответствующиеКА

Распознаваниелексемвыполняетсяследующимобразом

  1.  входнаяцепочкасчитываетсядотехпорпокаКАнедостигнетзаключительногосостояния
  2.  подостижениюзаключительногосостоянияКАсигнализируетонахождениилексемыданноготипаисканерзаноситинформациюонейвтаблицуименсимволов

ТакимобразомпроблемупостроениянепрямоголексическогоанализаторадляданноготипалексемможнопредставитькакпроблемупостроенияиреализацииКАкоторыйподостижениюзаключительногосостояниявыдаетнавыходелексемувэтомсмыслеегоможнорассматриватьикакконечныйпреобразовательВобщемслучаетакойКАявляетсянедетерминированнымНКАоднакокакотмечалосьвпНКАможнопреобразоватьвэквивалентныйемудетерминированныйКАРассмотримспособыописаниялексем

Методикиконструированиясканеровхарактеристикакаждогоэтапапостроениясканераиприменяемыеметоды

Подводяитогсодержаниюэтойглавысформулируемметодикиконструированиясканера

 МетодикаЭтаметодикасостоитизпятиэтаповнакаждомизкоторыхрешаетсяоднаиззадачпостроениясканера

 описаниелексемязыкаприпомощирегулярныхвыражений

преобразованиеполученныхвыраженийвсоответствующиеНКА

преобразованиеНКАвКАдлятехлексемгдетакоепреобразованиенеобходимо

конструированиесканераизполученныхКАработающихпоследовательно–вслучаепрямоголексическогоанализаилипараллельнопомеревызова–вслучаенепрямоголексическогоанализа

разработкатаблицыименидругихсвязанныхснейтаблициметодовработыстаблицами

Каждыйизэтихэтаповрассмотренвсоответствующемразделеданнойглавы

 МетодикаЕслиприописаниилексемотдатьпредпочтениесинтаксическимдиаграммамтоможновоспользоватьсясоответствиемимеющимместомеждудиаграммойрегулярнойграмматикойиКАокоторомшларечьвглВэтомслучаепервыетриэтапаметодикиможнозаменитьследующимиэтапами

 описаниелексемприпомощисинтаксическихдиаграммдиаграммыдолжнысодержатьтолькотерминальныесимволы

разметкадиаграммнетерминальнымисимволамииполучениесоответствующихрегулярныхграмматиксмп

преобразованиеполученныхграмматиквсоответствующиеКА

Далееследуетвыполнитьэтапыиметодики

Представлениерезультатовсканирования

ВпроцессеработысканерадолжнабытьсформированатаблицаименидентификаторовдляхраненияинформацииолексемахЭтаинформацияиспользуетсявдальнейшемдлядвухцелей

ВопервыхсцельюсемантическогоконтроляисходноготекстапрограммыНапримересливпрограммеестьоператорвидатокомпилятордолженпроверитьчтоидентификаторвстречаетсявпрограммевкачествеметкисоответствующегооператорааневдругомкачестве

ВовторыхинформациявтаблицеимениспользуетсявовремягенерациикодаНапримересливпрограммеестьоператорвидатогенерируемыйкоддляоперации«»будетзависетьотатрибутовидентификаторовивчастностиоттиповитп

ТакимобразомпослераспознаваниякаждойлексемысканердолжензанестивтаблицуимениххарактеристикиатрибутыКэтиматрибутамотносятсякласслексемыобозначаемыйобычнововнутреннемпредставлениицелымчисломфактическоезначениелексемыфактическоесимволическоеимядополнительнаяинформацияДлявнутреннегопредставлениялексемможетиспользоватьсятабл

Таблица

Класслексемы

Внутреннее
представление

Фактическое
значение

Неопределен



Идентификатор



Целоечисло



Действительноечисло

именалексем

Знакоперации



Зарезервированноеслово



Вещественныймассив



Метка



итд

итд



ДополнительнаяинформацияолексемеобычнопомещаетсявотдельнуюобластьпамятинакоторуюделаетсяссылкаЭтассылкаадрестакжеявляетсяатрибутомлексемыПустьнапримерданфрагментпрограммы

тогдапослееесканированиявтаблицеимендолжнабытьсформированаинформацияпредставленнаявтабл

ДополнительнаяинформациясвязаннаяскаждойконкретнойлексемойзависитотеесмысловогозначенияиможетсодержатьбольшоеколичествоатрибутовНапримервозможночтодляидентификаторанадознатьеготипвещественныйцелыйстроковыйитдбыллионметкойименемпроцедурыпеременнойформальнымпараметромпроцедурыдолженлионраспределятьсявстатическойилидинамическойпамятиитд

Таблица

Внутреннее
представление

Фактическое
значениеимя

Дополнительная
информация

Данныедля

‘’

Данныедля

‘’

Данныедля

‘’

‘

Данныедляконстанты

Ясночтоколичествоатрибутовдлякаждойлексемыбудетразличнымпоэтомудоступкэтимданнымудобноосуществлятьпутемссылокнасоответствующиеадресапамяти

ВсякийразкогдасканерраспознаетлексемуонпроверяетвтаблицеименвстречаласьлиранеетакаяжелексемаЕслинеттосканерзаноситвтаблицуимензначениеэтойлексемывместессоответствующейинформациейЕслижелексемаужеестьвнекоторойячейкетаблицыиментосканервырабатываетнавыходепаруимялексемы

Такимобразомчтобысконструироватьэффективныйкомпиляторнадоуметьподанномуименилексемыбыстроопределятьотведеналидлянееячейкавтаблицеименвставлятьпринеобходимостиэтулексемувычислятьадресаячееквдругихтаблицахсодержащихдополнительнуюинформациюокаждойлексеме

7. Определение синтаксического разбора. Модели анализаторов. Построение левого  анализатора по заданной КС-грамматике (привести пример).

Определениесинтаксическогоразбора СинтаксическийанализвходекоторогоуясняетсяструктураанализируемойцепочкилексемназываетсясинтаксическимразборомВыделяютдвавидаразбораВведемихформальноеопределение

ОпределениеПустьКСграмматикаправилакоторойпронумерованыртогда

  1.  левымразборомцепочкиназываетсяпоследовательностьправилпримененныхприлевомвыводецепочкииз
  2.  правымразборомцепочкиназываетсяобращениепоследовательностиправилпримененныхприправомвыводецепочкииз

Этиразборыможнопредставитьввидепоследовательностиномеровизмножествар

ПримерРассмотримграмматикустакойнумерациейправил













атакжецепочкуиеелевыйиправыйразборыИмеем

  1.  левыйвывод

  1.  левыйразбор
  2.  правыйвывод

  1.  правыйразбор

Моделианализаторов

МПпреобразовательявляетсяестественноймодельюанализаторареализующегоСУсхему

Анализаторыреализующиеметодынисходящегоразборавыдаютнавыходелевыеразборыиназываютсялевымианализаторамиареализующиеметодывосходящегоразборавыдаютправыеразборыиназываютсяправымианализаторами

ЛевыйанализаторреализующийСУсхемуТможномоделироватьприпомощиМПпреобразователяопределяемогоследующимобразом

ОпределениеПусть–КСграмматикавкоторойправилазанумерованыотдорПустьМ–недетерминированныйМПпреобразователь…δгдеопределяетсятак

  1.  содержитαеслиα–правилоизсномером
  2.  длявсехα

Назовемлевыманализаторомдля

ОпределениеПусть–КСграмматикаправилакоторойзанумерованы…ОпределимрасширенныйнедерминированныйМПпреобразователь

…δ

причемверхмагазинарасположенсправаиδопределяетсятак

  1.  δαеслиα–правилоизсномером
  2.  δδдлявсех
  3.  δδ

Назовемправыманализаторомдля

Впрактикеразработкитрансляторовобычноиспользуютсядетерминированныеанализаторыкоторыевыполняютсинтаксическийанализпрограммызаодинпроход–безвозвратакужепрочитаннойчастипрограммыДляпостроениятакиханализаторовнеобходимочтобыязыкпрограммированияисоответствующиеграмматикиописывающиеразличныесинтаксическиеконструкцииязыкаудовлетворялиопределеннымограничениямиобладалиопределеннымисвойствами

ПостроениелевогоанализаторапозаданнойКСграмматикепривестипример

ПримерПостроимлевыйанализатордляграмматики

Здесь…δ

гдеδ

δ

δ

δдлявсех

Анализатор–недетерминированныйидлявходааааонможетвыполнитьмногоразличныхпоследовательностейтактовносрединихбудетиметьместопоследовательностьтактовприводящаякзаключительнойконфигурации



























8. Свойства КС-языков и грамматик. Эквивалентные преобразования КС-

грамматик (перечислить виды преобразований) и их применение в разработке трансляторов. Устранение левой рекурсии и факторизация (привести пример и пояснить на каком этапе разработки языка применяются эти преобразования).

СвойстваКСязыковиграмматик

ЯзыкопределяемыйдетерминированнымМПавтоматомназываетсядетерминированнымКСязыком

РаспознаваниецепочекдетерминированногоКСязыкапроисходитзаодинпроход–безвозвратакужепрочитаннойчастицепочкиинаходясьвтекущейконфигурацииМПавтоматможетвыполнитьединственныйтактпереводящийеговочереднуюконфигурациюДругимисловамизначениеанализируемойцепочкидетерминированноопределяеттраекториюпереводящуюМПавтоматизначальнойконфигурациивзаключительную

ЭтосправедливоивотношениидетерминированныхконечныхиМПпреобразователейиспользуемыхвкачествемоделейтрансляторовдетерминированныхКСязыков

ТакМПпреобразовательизпримерапереводящийарифметическиевыраженияизпрефикснойформывпостфиксную–детерминированныйаанализаторыиизпримеров–недетерминированныетаккаквозможнынесколькотраекторийиприпостроениитраекторииприводящейкзаключительнойконфигурациипоказаннойвпримерахнеобходимывозвратыкужепрочитаннойчастицепочкиОтсюдапроисходятиназванияразныхклассовметодовсинтаксическогоанализаилисинтаксическиуправляемойтрансляцииоднопроходныебезвозвратныедетерминированныесвозвратамисограниченнымивозвратамиидр

ОпределениеоднозначностьнеоднозначностьКСграмматикКСграмматикуназываютнеоднозначнойеслисуществуетхотябыоднацепочкаимеющаядваилиболееразличныхлевыхилиправыхвыводовВтерминахдеревьевэтоозначаетчтооднаитажецепочкаможетиметьдваилиболееразличныхдеревьеввыводаВпротивномслучаеграмматика–однозначна

Неоднозначность–весьманежелательноесвойствограмматикиопределяющейправилаязыкапрограммированиякотороеможетприводитькразнойинтерпретацииоднойитойжеинструкцииоператораязыкапрограммистомикомпиляторомЭтоиллюстрируетследующийпример

ЭквивалентныепреобразованияКСграмматикперечислитьвидыпреобразованийиихприменениевразработкетрансляторов

РассмотримпреобразованияКСграмматикипозволяющиеполучитьграмматикусновымисвойствамибезизмененияязыкапорождаемогоисходнойграмматикойтеПриведемосновныеалгоритмытакихпреобразований

АлгоритмУстранениенедостижимыхсимволов

Алгоритм 5.1

G=(N,,P,S)

G′=(N′,′,P′,S)

Получаемаянавыходеалгоритмановаяграмматикаобладаетсвойствами

  1.  
  2.  длявсехΣ′существуюттакиецепочкиαиβизΣ′чтоαβ

АлгоритмобычноиспользуетсявкачествепроцедурывыполняемойвнутриалгоритмаприводимогонижеВрезультатевыполненияалгоритмаустраняютсяибесполезныеинедостижимыесимволывсмыследанныхвпопределений

Начало

V0={S}; i=1

Vi=Vi-1{X | в P есть

AαXβ и AVi-1}

Vi=Vi-1

i=i+1

N=Vi  N

Σ′=Vi  Σ

P – те правила из P, которые содержат только символы из Vi

G′=(N′,′,P′,S)

0

1

Выход

Алгоритм 5.1

АлгоритмУстранениебесполезныхсимволов

Алгоритм 5.1

G=(N,,P,S)

G′=(N′,′,P′,S)

L(G)

Получаемаянавыходеалгоритмановаяграмматикаобладаетсвойствами

  1.  
  2.  Σ′несодержатбесполезныхинедостижимыхсимволов

Начало

N0=; i=1

Ni=Ni-1{A | (Aα)P и α(Ni-1Σ)*}

Ni=Ni-1

i=i+1

G1=(NNe,,P1,S)

P1 – те правила из P, которые содержат только символы из Ne

0

1

Выход

Ne=Ni

Применить к G1 алгоритм 5.1 и получить G

Алгоритм 5.2

ВрезультатеизустраненынедостижимыесимволыВи

АлгоритмУстранениеправил

Алгоритм 5.3

G=(N,,P,S)

G′=(N′,′,P′,S′)

L(G)

Получаемаянавыходеалгоритмановаяграмматика′обладаетсвойствами

  1.  
  2.  несодержатправил

Начало

Построить Ne={A | AN и AG+e}

(Aα0B1α1B2α2 Bkαk)P, k≥0

Включить в P все правила вида Aα0X1α1X2α2 Xkαk, где Xi – либо Bi, либо e, но не включать правило Ae (т.е. для каждого такого правила, в котором Xi = Bi нужно построить множества правил, путем поочередной замены всех Bi на e)

0

1

Выход

N′=N{S′}

Включить в P правила S′→e | S, где S – новый символ

Алгоритм 5.3

Причем:

BiNe для 1≤ik;

ни один символ цепочки αjNe, 0≤jk

SNe

0

N′=N

S′=S

G′=(N′,,P′,S′)

АлгоритмУстранениецепныхправил

Алгоритм 5.4

G=(N,,P,S)

G′=(N,,P′,S)

Без e-правил

Без e-правил и без цепных правил

Начало

Положить N0={A}

Ni=Ni-1{C | (BC)P и BNi-1}

Ni=Ni-1

i=i+1

Построить P так: если (Bα)P и не является цепным правилом, включить в P правила Aα для всех A, таких, что BNA

0

1

Выход

NA=Ni

G=(N,,P′,S)

Алгоритм 5.4

i=1

Построение множеств NA для всех AN

Устранениелевойрекурсииифакторизацияпривестипримерипояснитьнакакомэтаперазработкиязыкаприменяютсяэтипреобразования

АлгоритмУстранениелевойрекурсии

Алгоритм 5.5

G=(N,,P,S)

G′=(N′,,P′,S)

Приведенная

КС–грамматика

Эквивалентная КС-грамматика без левой рекурсии

Дляустранениянепосредственнойлевойрекурсиивправилахграмматикиможновоспользоватьсярезультатамиследующейлеммы

ЛеммаПустьКСграмматикавкоторой



ВсеА–правилаизиниоднаизцепочекненачинаетсяс

Пусть′где–новыйнетерминала′получаетсяиззаменой–правилнаправила





Тогда

Вприведеннойнижеструктурнойсхемеалгоритмаблокивкоторыхвыполняютсяпреобразованияграмматикиснабженыномерамикоторыебудутиспользоватьсяприрассмотрениипримера

9. Классы лево- и право- анализируемых грамматик (определение). Левые и правые анализаторы. LL(k) – грамматики и их место в разработке языков программирования.    Модель LL(k) – анализатора.

Классылевоиправоанализируемыхграмматикопределение

Впрактикеразработкиязыковпрограммированияипроблемно–ориентированныхязыковобычноиспользуютклассыграмматикдлякоторыхприменимыметодыдетерминированнойтрансляцииВзависимостиотвидаанализаторалевогоилиправогополучаемогонаосноветойилиинойграмматикипоследнююможноотнестикодномуизсоответствующихклассовлевоилиправоанализируемыхграмматик

ОпределениеКСграмматикуназываютлевоанализируемойеслисуществуеттакойДМПпреобразовательРчто

РххТ

иправоанализируемойеслисуществуеттакойДМПпреобразовательРчто

РххТ

где–концевоймаркерпомечающийправыйконецвходнойцепочких

ДругимисловамидлялевоанализируемойграмматикивсегданайдетсяДМПпреобразовательреализующийСУсхемуТтевыдающийлевыеразборывсехцепочекхпорождаемыхграмматикойадляправоанализируемойграмматики–ДМПпреобразовательреализующийСУсхемуТивыдающийправыеразборы

Левыеиправыеанализаторы

МодельюлевогоанализатораявляетсяДМПпреобразовательработающийпопринципуопустошениямагазинасмпструктуракоторогопоказананарис

МодельюанализатораможетслужитьрасширенныйДМПпреобразовательНапомнимчтоверхмагазинаунегорасположенсправаипривыполнениитактацепочкаанеодинсимволвверхумагазинаможетзаменятьсяцепочкой

–грамматикииихместовразработкеязыковпрограммирования

ОченьбольшоеколичествосинтаксическихконструкцийязыкаможноописатьприпомощиграмматикидажеграмматикиДляразработчикакомпиляторапроблемазаключаетсявтомчтобыимеяграмматикунеобладающуюпризнакамиполучитьэквивалентнуюейграмматикугенерирующуютотжеязыктакчто–язык

Всвязисэтимвозникаетдвавопроса

Вселиязыкиобладаютграмматикой

Еслинеттосуществуетлиалгоритмпозволяющийустановитьобладаетлиданныйязыксвойствамитеможнолиегогенерироватьприпомощикакойлибограмматики

ТеориядаетотрицательныйответнаобаэтихвопросаЭтоозначаетчтограмматиканеобладающаясвойствамиможетгенерироватьязыкаможетинетСледовательноэтуграмматикулибоможнопреобразоватьвэквивалентнуюейграмматикулибонельзя

ТакимобразомобщегорешенияэтойпроблемынесуществуетОднаконапрактикевстречаетсямногочастныхслучаевкогдарешениевсежеудаетсянайтипутемпримененияопределенныхприемовпреобразованияисходнойграмматикиврезультатекоторыхизнееустраняютсянежелательныесвойстваКтакимнежелательнымсвойствамотносятся

–наличиелеворекурсивныхциклов

–наличиелеворекурсивныхправил

наличиеправилвкоторыхальтернативныеправыечастиначинаютсяоднойитойжецепочкойсимволов

ИзтеорииизвестночтограмматикаобладающаяэтимисвойстваминеявляетсяграмматикойПреобразованияграмматикиврезультатекоторыхэтисвойстваустраняютсяврядеслучаевнонегарантированноприводяткполучениюграмматики

Модель–анализатора

МодельюлевогоанализатораявляетсяДМПпреобразовательработающийпопринципуопустошениямагазинасмпструктуракоторогопоказананарис

ω

u

x

Входная лента

Читающая головка

Управляющая таблица

$

X

α

Стек

(магазин)

π

Выходная лента

Рис

МоделированиеегоработыудобновыполнятьприпомощитакназываемогопредсказывающегоалгоритмаразбораЭтоталгоритмпытаетсяпроследитьлевыйвыводцепочкизаписаннойнаеговходнойленте

Причтениианализируемойцепочкинаходящейсянавходнойлентевходнаяголовкаможет«заглядыватьвперед»наочередныхсимволовотсюдачисловназваниипредсказывающегоалгоритмаЭтуцепочкуизсимволов«увиденнуювпереди»входнойголовкойбудемназыватьаванцепочкойНарисаванцепочкойслужитподцепочкавходнойцепочки

МагазинсодержитцепочкугдеХ–цепочкамагазинныхсимволовизалфавитаГ–специальныйсимволдлямаркировкиднамагазинаВыходнаялентасодержитцепочкусостоящуюизномеровправил

ОпределениеКонфигурациейпредсказывающегоалгоритмаАназываетсятройкаобъектовгде–неиспользованнаячастьвходнойцепочки

–содержимоемагазина–верхнийсимвол

–выходнаяцепочка

РаботуалгоритмаАопределяетуправляющаятаблицаМ

Гвыбросдопускошибка

гдеГ–цепочкапостроеннаяизмагазинныхсимволов

–номерправилаизмножестваР

НакаждомтактесначалаопределяетсяаванцепочкаиверхнийсимволмагазинаХЗатемрассматриваетсяэлементМХуправляющейтаблицыивсоответствиисегосодержаниемвыполняетсяодноизчетырехдействий

  1.  еслиМХтотеверхнийсимволмагазиназаменяетсяцепочкойиквыходудобавляетсяномерправилавходнаяголовканесдвигается
  2.  еслиМа«выброс»итотеесливерхнийсимволмагазинасовпадаетстекущимвходнымсимволомтоонвыбрасываетсяизмагазинаивходнаяголовкасдвигаетсянаодинсимволвправо
  3.  еслиалгоритмдостигаетконфигурацииработапрекращаетсяивыходнаяцепочканазываетсяразборомпервоначальнойвходнойцепочкиБудемсчитатьчто«допуск»и–допускающаяконфигурация
  4.  еслиХ«ошибка»торазборпрекращаетсяивыдаетсясообщениеобошибкеасоответствующаяконфигурацияназываетсяошибочной

ДлявходнойцепочкииееразбораполучаемогонавыходеалгоритмаАбудемписатьА

ОпределениеПереводомопределяемымалгоритмомАназываетсямножество

А

ОпределениеАлгоритмразбораАдляКСграмматикиназываетсякорректнымесли

  1.  определено
  2.  еслито–левыйразборцепочки

Управляющаятаблицатакогоалгоритманазываетсякорректнойуправляющейтаблицейдляграмматики

Примерпредсказывающийалгоритмдляпростойграмматикисправилами









Управляющаятаблицаприведенаниже

Верхнийсимволмагазина

Аванцепочка





ошибка

А





ошибка

выброс

ошибка

ошибка

ошибка

выброс

ошибка

ошибка

ошибка

допуск

Рассмотримпотактноработуалгоритмадлявходнойцепочки





















ИтакАЛегкоубедитьсячтоэто–левыйразбор

10. Основные функции семантического анализа. Способы представления промежуточной программы. Применение моделей  синтаксически управляемой трансляции (СУ-перевода) в разработке анализаторов.   

Основныефункциисемантическогоанализа

ПроверкасемантическихсоглашенийДлятогочтобы«правильнаясточкизрениясинтаксиса»программамоглабытьфизическиреализовананаЭВМнеобходимочтобыотдельныесинтаксическиеединицыязыкапрограммированияидентификаторыконстантыитписоотношениямеждунимиподчинялисьопределеннымправиламназываемымсемантическимисоглашениямиконтекстнымиусловиями

Приведемпереченьтипичныхдлябольшинстваязыковпрограммированиясемантическихсоглашений

Никакойидентификаторвпрограммномблокенедолженбытьописанбольшеодногоразаеслионименуетследующиеобъекты

  1.  простыепеременные
  2.  метки
  3.  массивы
  4.  процедуры

ОпределяющимвхождениямидентификаторовдолжнысоответствоватьихиспользующиевхожденияНапримеридентификаторМЕТметкипомеченногооператораМЕТимеетопределяющеевхождениеаэтотжеидентификаторвоператоре–использующееИдентификаторыпеременныхвходящиевоператорыприсваиванияилиусловныеоператорытожеимеютиспользующиевхожденияЕслидляиспользующеговхожденияидентификатораегоопределяющеговхожденияненайденотосоглашениеобихсоответствиисчитаетсянарушенным

СоглашениеосоответствиитиповпеременныхконстантидругихобъектоввходящихвсинтаксическуюконструкциюпрограммыДлябольшинстваязыковэтосоглашениенедопускаетприменениеоперацийкоперандамвкачествекоторыхвыступаютзначенияразныхтиповНельзянапримервыполнитьсложениепеременныхиеслиониимеютзначенияПривызовепроцедур–функцийколичествоаргументовиихтипытакжедолжнабытьсогласованысихопределениями

Соглашенияопределяющиеразличныеколичественныеограничения–глубинувложенностиблоковколичестворазмерностеймассивовидр

РеализоватьпроверкунекоторыхсоглашенийоказываетсяособенносложноНапримервтакихязыкахкакПаскальилиСиимеетсявозможностьконструированияновыхтиповданныхизстандартногонаборачтоприводитксложностипроверкисоглашенияосоответствиитипов

РаспределениепамятиПослевыясненияструктурыисемантикипрограммыкомпиляторвыделяетместовпамятикомпьютерадлязначенийпеременныхмассивовидругихструктуривслучаенеобходимостипомещаетсоответствующиеадресавтаблицуидентификаторовВсовременныхтрансляторахприменяютсяразличныемеханизмыраспределенияпамятикоторыевобщемслучаезависятотлогическихструктурданныхязыкапрограммированияиотвозможностейфизическогопредставлениеэтихструктурвпамятиконкретногокомпьютера

Механизмраспределенияпамятиподразумеваетрешениетрехосновныхзадач

  1.  Представлениеструктурданныхязыкапрограммированиявадресномпространствекомпьютера
  2.  Организацияпередачиданныхмеждупроцедурамиблокамипрограммы
  3.  Выделениеосвобождениеиучетпамятивовремявыполненияпрограммы

Врезультатереализацииэтогомеханизманавыходетранслятораформируетсяпрограммасостоящаяиздвухобластей–областикомандиобластиданных

ВобластикомандразмещаютсякомандыобъектнойпрограммыРазмерэтойобластиравенсуммедлинкомандобъектногокода

ВобластиданныхразмещаютсяданныепеременныемассивыидриспользуемыевпрограммеРазмерэтойобластивобщемслучаенефиксированпосколькувпрограммемогутбытьданныесограниченнымвременемсуществованияКрометогомногиесовременныеязыкиимеютсредствапозволяющиепрограммистусамостоятельновыделятьилиосвобождатьпамять

Рассмотрениеразличныхвариантовреализациимеханизмараспределенияпамятиможнонайтивработах

ВедениетаблицыидентификаторовСтаблицейидентификаторовмыужесталкивалисьвпНачальныеэлементытаблицыформируютсявфазелексическогоанализаисходнойпрограммыЗатемпомерераспознаванияописанийидентификатороввфазесинтаксическогоисемантическогоанализатаблицадополняетсяновымиданнымисодержащимидополнительнуюинформациюокаждойлексемеЭтаинформацияиспользуетсядляпроверкисемантическихсоглашенийираспределенияпамятиокоторыхговорилосьвыше

ВобщемслучаечислоатрибутовхарактеризующихразличныетипыидентификатороввтаблицеможетбытьразличнымПриведемтипичныйпереченьатрибутовиспользуемыхвтаблицахидентификаторов

Дляименпеременныхэто

  1.  типданныхвещественныйцелыйстроковыйитд
  2.  точностьмасштабдлина
  3.  видпростаяпеременнаямассивструктураитд
  4.  адресвовремявыполненияпрограммы
  5.  еслимассивточислоизмеренийиеслиграничныепарыизмеренийявляютсяконстантамитоихзначения
  6.  еслиструктураиликомпонентыструктурытосвязьсдругимикомпонентаминапримердлясвязанныхсписков
  7.  признакпараметра–формальныйилифактическийеслиформальныйтотипсоответствияпараметров
  8.  признакобработкиописанияпеременной–обрабатываласьранееилинетэтотатрибутможнорассматриватьвкачестве«служебного»используемогодляуправленияпроцессомведениятаблицы
  9.  существуетлиинструкцияоператорприсваивающаязначениепеременной

Дляименпроцедур

  1.  являетсялионавнешнейпоотношениюкпрограмме
  2.  являетсялионафункциейикаковеетип
  3.  являетсялионарекурсивной
  4.  данныеоееформальныхпараметрах

МногиесовременныеязыкипрограммированияимеютструктурувложенныхблоковипроцедурВэтомслучаеодинитотжеидентификаторможетбытьописанииспользованмногоразвразличныхблокахипроцедурах

Примерфрагментапрограммысблочнойструктуройприведеннижевнейпеременныеаиописанывразныхблоках

Приформированиитаблицыидентификатороввпроцессетрансляциинеобходимочтобыкаждомувстреченномуописаниюидентификаторасоответствовалсвойэлементтаблицывчастностиописаниямидентификатораавразныхблокахбудутсоответствоватьразныеэлементы

ПрииспользованииидентификаторавозникаетпроблемакакнайтинужноесоответствующееописаниевтаблицеОдинизвозможныхспособовеерешениясостоитвсозданиииведенииспискаблоковСтруктурасоставспискаиегосвязьстаблицейидентификаторовдлярассмотренногофрагментапрограммыприведеннарис

procedure proc2(b:real; var a:real);

  begin

    a:=b*b;

  end;

Блок 1

procedure proc1(a1:real; var a,a2:real);

begin

  a:=a1*a1;

  proc2(a,a2);

end;

Блок 2

program test;

  var a,b,c,d :real;

begin

  d:=2.0;

  proc1(d,b,c);

  a:=b+c;

  writeln ('Значение а=',a);

  readln;

end.

Блок 0

Номер блокаНомер

«родительского» блокаКоличество элементов в таблицеУказатель0–4103212

Список блоков

a,b,c,da1,a,a2a,b......

Таблица

идентификаторов

Рис

Указательнаэлементытаблицыотносящиесяк–мублокуиномер«родительского»блокатеблокасодержащего–йблокоднозначноопределяютописаниеидентификатораэлементтаблицыкотороетребуетсянайтиприегоиспользованииПравилонахождениясоответствующегоидентификаторуописаниясостоитвтомчтосначалапросматриваетсятекущийблокзатемсодержащийегоблокитддотехпорпоканебудетнайденоописаниеданногоидентификатораЧислоидентификатороввблокеможетиспользоватьсядляопределенияразмерасегментапамятитребуемогодляхраненияидентификаторовописанныхвданномблоке

Способыпредставленияпромежуточнойпрограммы

ПредставленияпромежуточнойпрограммыПромежуточнаяпрограммадолжнасоднойстороныотражатьсинтаксическуюструктуруисходнойпрограммыасдругойстороныкаждыйоператорпромежуточнойпрограммыдолженотносительнопростотранслироватьсявмашинныйкод

Наиболеераспространеннымиспособамипредставленияпромежуточнойпрограммыявляются

постфикснаяпольскаязапись

префикснаяпольскаязапись

списочныеструктурыпредставляющиедеревья

многоадресныйкодсявноименуемымирезультатамидругоеназвание–тетрада

многоадресныйкодснеявноименуемымирезультатамидругоеназвание–триада

Рассмотримэтиспособыпредставлениянапримереоператораприсваивания

Постфикснаяипрефикснаяформыпольскойзаписиэтогооператораимеютвид

постфикснаяформа

префикснаяформа

ПрименениемоделейсинтаксическиуправляемойтрансляцииСУпереводавразработкеанализаторов

ПрименениемоделейсинтаксическиуправляемойтрансляциидлягенерациикодаиинтерпретацииМоделипереводарассмотренныевглавеможноэффективноиспользоватьвтрансляторахдлягенерациикодапромежуточныхпредставленийпрограммыатакжегенерированияинструкцийдействийболееобщегохарактерачемкодыАссемблеранапримервызовапроцедурнаписанныхнаязыкевысокогоуровня

ОсновнаяидеяэтогоподходазаключаетсявовключениидействийвпроцесссинтаксическогоанализасиспользованиемупомянутыхмоделейМырассмотримкакможноосуществлятьсинтаксическиуправляемыепереводыприпомощипростыхСУсхемиДМПпреобразователейвыполняющихсинтаксическийанализТеоретическимипредпосылкамидляреализацииэтогоподходаявляютсяследующиеположениятеоремы

  1.  всякуюпростуюСУсхемувкоторойвходнаяграмматикаявляется–грамматикойможнореализоватьДМПпреобразователем
  2.  простуюпостфикснуюСУсхемувкоторойграмматикаявляетсяграмматикойможнореализоватьрасширеннымДМПпреобразователем

ОпределениеСУсхемаТназываетсяпостфикснойесликаждоеправилоизимеетвидгдетеэлементперевода–этоцепочкасостоящаяизнетерминаловзакоторымиследуетцепочкавыходныхсимволов

ДлятогочтобыреализоватьпереводопределяемыйпростойСУсхемойТможновоспользоватьсялюбымдетерминированныманализаторомМпостроеннымнаосновевходнойграмматикиэтойсхемымодифицировавалгоритмегоработыследующимобразомПотребуемчтобывпроцессеразборацепочеканализаторформировалвыходизэлементовпереводасхемыТсоответствующихномерамправилразбораТакоймодифицированныйанализаторбудемназыватьтрансляторомРассмотримнаконкретныхпримерахкаконможетбытьреализован

ПримерПостроимпостфикснуюСУсхемудляпереводаарифметическихвыраженийизязыкавкодыассемблераэтопростаяграмматикаграмматикакотораябудетиспользоватьсявСУсхемевкачествевходнойграмматикиБудемсчитатьчтокомпьютеримеетсумматоримагазинДлявыполненияоперацийиспользуютсяследующиекоманды

помещаетзначениеизячейкиХвверхушкумагазинаавсеостальныеэлементымагазинапроталкиваютсявниз

исоответственноскладываютиперемножаютсодержимоедвухверхнихячеекмагазинаубираютэтиячейкиазатемвновьпомещаютрезультатывверхушкумагазинаспроталкиваниемвнизоставшихсяэлементов

Командыразделяютсясимволом«точкасзапятой»Тогдасимволыкомандвместессимволом«точкасзапятой»исимволомХобразуютвыходнойалфавитапостфикснуюСУсхемуТможнопредставитьследующимиправилами

  1.  Е’
  2.  
  3.  ’’
  4.  
  5.  
  6.  ’’–здесьХа

ДалеедляполученияпереводаможновоспользоватьсяанализаторомСоответствующийпримеррассмотренвМырассмотримдругойвариантанализатормоделируемыйалгоритмомАтипа«переноссвертка»дляграмматикиоператорногопредшествованияграмматикаоператорногопредшествованиясмпримерСучетомтогочтоэтотанализаторстроитсядляостовнойграмматикиполученнойизнашаСУсхемапринимаетвид

‘’‘’‘’

АнализаторАдляграмматикибылпостроенвпримереиздесьмысразувоспользуемсяегорезультатамиДлявыходнойцепочкиаааанализаторАвыдаетправыйразборТрансятормодифицированныйанализаторзаменитномераправилкомандамиассемблераНижеприведенатаблицаиллюстрирующаяпотактноеизменениевыходатранслятораисодержимогомашинногомагазинавпроцессеформированияразборавтаблицеоставленытолькотетактывкоторыхАвыдаетномераправил

Номерправила

Выходтранслятора

Содержимоемагазина







Тоже













Такимобразомдлявычислениявыраженияааатрансляторсгенерируеттребуемуюпоследовательностьассемблерныхкоманд

Начало

Упорядочить множество N0={A1An}

Для множества правил вида:

AAi1| ... |Aim|1| ... |p

(βj не начинается с Ak, если ki) выполнить замену по лемме 5.1

i=n

i=i+1, j=1

Заменить правила вида AiAjα на правила:

Ai1α| ... |mα, где Aj1| ... |m – все Aj–правила

0

1

Выход

j=j+1

G=(N′,,P′,S)

Алгоритм 5.5

i=1

Правила замены:

Ai1| ... |p|1Ai| ... |pA′i

A′i1| ... |m|1A′i| ... |mA′i

j=i-1

1

0

3

1

2

ПримерПрименималгоритмклеворекурсивнойграмматикесправилами







Упорядочимтерминалыиперепишемграмматикуввиде







Припреобразованияблоканевыполняютсятаккак–правиланелеворекурсивныДалеевсоответствиисизменяющимисязначениямиивыполнимследующиепреобразования

–выполнимзаменусогласноблокувправилеиполучим–правилаперейдемкблоку

–выполнимпреобразованияА–правилсогласноблокуиполучимправила





переопределимзначенияииперейдемкблоку

–выполнимзаменысогласноблокувправилеиполучимправилаположимивновьперейдемкблоку

–выполнимзаменывправилеиполучимправила



иперейдемкблоку

–выполнимпреобразования–правилсогласноблокуиполучимправила





Возвращаяськисходнымобозначениямнетерминаловграмматикиокончательнополучаемграмматику











ФакторизацияПроцедурафакторизациииспользуетсядляпреобразования–правилграмматикисальтернативнымиправымичастяминачинающимисясоднойитойжецепочки



Методыпостроениядетерминированныхлевыханализатороврассматриваемыевследующейглавенедопускаютналичиятакихправил

Самапроцедурасостоитиздвухэтапов

Цепочкавыноситсязаскобки



причемскобкивтакойзаписиявляютсяметасимволамитенепринадлежатмножествусимволовграмматики

Длявыражениявскобкахвводитсяновыйнетерминалчтоприводиткполучениюправилновойграмматики





 Пустьнапримервнекоторойграмматикеимеютсяправила





Применениемкэтойграмматикепроцедурыфакторизациибудутпостроеныновыеправила







ВлитературеможнонайтиидругиеметодыэквивалентныхпреобразованийпреобразованиякнормальнымформампреобразованиядляразличныхподклассовКСграмматикидр


 

А также другие работы, которые могут Вас заинтересовать

18569. Оптимизация технических объектов в системах автоматизированного проектирования 272.5 KB
  Оптимизация технических объектов в системах автоматизированного проектирования. Данная глава посвящена вопросам постановки и решения задач оптимизации при техническом проектировании. Главное внимание уделяется параметрической оптимизации непрерывных объектов.
18570. Общие сведения об ОС 124.5 KB
  Общие сведения об ОС. Операционная система комплекс системных управляющих и обрабатывающих программ предназначенных для наиболее эффективного использования всех ресурсов ВС и удобства работы с ней. В настоящее время только с помощью ОС можно полностью загружат
18571. ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ САПР 109 KB
  ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ САПР Структура и требования к ТО САПР Техническое обеспечение САПР включает в себя различные технические средства hardware используемые для выполнения автоматизированного проектирования а именно: ЭВМ периферийные устройства сетевое оборуд
18572. Сети ЭВМ и средства телекоммуникационного метода доступа 63 KB
  Сети ЭВМ и средства телекоммуникационного метода доступа Для современного этапа развития средств вычислительной техники характерно использование сравнительно дешевых мини микро и персональных ЭВМ обладающих достаточно большими вычислительными возможностями. По...
18573. Базы данных. Логическая область базы данных 145.5 KB
  Базы данных. Лекция № 1. 1. Предметная область базы: данных сварное соединение стыковое нахлесточное и т.п. Объекты предметной области. Логическая область базы данных цифры записи и т.п.. 2.Характеристика объекта предметной области называется атрибуткоторый прин
18574. НАЗНАЧЕНИЕ, СУЩНОСТЬ И СОСТАВНЫЕ ЧАСТИ ИНФОРМАЦИОННОГО ОБЕСПЕЧЕНИЯ САПР 93.5 KB
  НАЗНАЧЕНИЕ СУЩНОСТЬ И СОСТАВНЫЕ ЧАСТИ ИНФОРМАЦИОННОГО ОБЕСПЕЧЕНИЯ САПР Основное назначение ИО САПР уменьшение объемов информации требуемой в процессе проектирования от разработчика РЭС и исключение дублирования данных в прикладном программном и техническом обе...
18575. УРОВНИ ПРЕДСТАВЛЕНИЯ ДАННЫХ 117.5 KB
  УРОВНИ ПРЕДСТАВЛЕНИЯ ДАННЫХ Существует три уровня представления данных: уровень пользователя предметная область логический и физический. Каждый объект предметной области характеризуется своими атрибутами каждый атрибут имеет имя и значение. Например объект осц
18576. ПРОЕКТИРОВАНИЕ БАЗЫ ДАННЫХ 42.5 KB
  ПРОЕКТИРОВАНИЕ БАЗЫ ДАННЫХ Процесс разработки структуры БД на основании требований пользователя называют проектированием БД ПБД. Результатами ПБД являются структураБД состоящая из логических и физических компонент и руководство для прикладных программистов. Р...
18577. Функции сетевого программного обеспечения 33.5 KB
  Функции сетевого программного обеспечения Принято выделять в ПО АС общесистемное ПО системные среды и прикладное ПО. К общесистемному ПО относят ОС используемых ЭВМ и вычислительных систем а также сетевое ПО типовых телекоммуникационных услуг. Основой системной ср