___________________________________________________________
11. Алгоритм LL(1) разбора.
Алгоритм. Принадлежит ли данная грамматика LL (1) -грамматике?
Вход. Некоторая произвольная грамматика.
Выход. «ДА» если данная грамматика является LL (1)-грамматикой, «НЕТ» в - противном случае.
Метод.
Прежде всего, нужно установить, какие нетерминалы могут генерировать пустую строку. Для этого создадим одномерный массив, где каждому нетерминалу соответствует один элемент. Любой элемент массива может принимать одно из трех значений: YES, NO, UNDECIDED. Вначале все элементы имеют значение UNDECIDED. Мы будем просматривать грамматику столько раз, сколько потребуется для того, чтобы каждый элемент принял значение YES или NO.
При первом просмотре исключаются все порождающие правила, содержащие терминалы. Если это приведет к исключению всех порождающих правил для какого-либо нетерминала, соответствующему элементу массива присваивается значение NO. Затем для каждого порождающего правила с е в правой части тому элементу массива, который соответствует нетерминалу в левой части, присваивается значение YES, и все порождающие правила для этого нетерминала исключаются из грамматики.
Если требуются дополнительные просмотры (т.е. значения некоторых элементов массива все еще имеют значение UNDECIDED), выполняются следующие действия.
1) Каждое порождающее правило, имеющее такой символ в правой части, который не может генерировать пустую цепочку (о чем свидетельствует значение соответствующего элемента массива), исключается из грамматики. В том случае, когда для нетерминала в левой части исключенного правила не существует других порождающих правил, значение элемента массива, соответствующего этому нетерминалу, устанавливается на NO.
2) Каждый нетерминал в правой части порождающего правила, который может генерировать пустую строку, стирается из правила. В том случае, когда правая часть правила становится пустой, элементу массива, соответствующему нетерминалу в левой части, присваивается значение YES, и все порождающие правила для этого нетерминала исключаются из грамматики.
Этот процесс продолжается до тех пор, пока за полный просмотр грамматики не изменится ни одно из значений элементов массива.
12. Компиляторы С++.
Компилятор -программа считыв. текст прогри написан на 1 языке и трансформ. его в эквив. текст на др языке. попутно компилятор выдает сообщения об ошибках.
Borland C++ - среда программирования (IDE) на языках Си и C++ для DOS, Windows и Windows NT. Потомок Turbo C. Его отладчик Turbo Debugger был написан для защищённого режима DOS.
C++ Builder - программный продукт, инструмент быстрой разработки приложений (RAD), интегрированная среда программирования (IDE), система, используемая программистами для разработки программного обеспечения на языке C++.
Intel C++ compiler - оптимизирующий компилятор, разрабатываемый фирмой Intel для процессоров семейств x86, x86-64 и IA-64. Главным достоинством компилятора являются выполняемые им высокоуровневые, а также целевые оптимизации под процессоры Intel. Компилятор работает под ОС Linux, Windows, Mac OS X.
Microsoft Visual C++ - интегрированная среда разработки приложений на языке C++, разработанная фирмой Microsoft и поставляемая либо как часть комплекта Microsoft Visual Studio, либо отдельно в виде бесплатного функционально ограниченного комплекта Visual C++ Express Edition. Сменила интегрированную среду разработки Microsoft QuickC.
13. LR- анализаторы. Построение таблиц LR- разбора.
В информатике LR-анализатор — синтаксический анализатор для исходных кодов программ, написанных на некотором языке программирования, который читает входной поток слева (Left) направо и производит наиболее правую (Right) продукцию контекстно-свободной грамматики. Используется также термин LR(k)-анализатор, где k выражает количество непрочитанных символов предпросмотра во входном потоке, на основании которых принимаются решения при анализе. Обычно k равно 1 и часто опускается.
_______________________
При построении LR-таблиц разбора нам необходимо ссылаться на конкретную позицию в правиле, поэтому в правилах вводится понятие «конфигурация ». Например, в грамматике
1) S ® · real IDLIST
2) IDLIST ® IDLIST, ID
3) IDLIST ® ID
4) ID ® A | B | C | D
точка соответствует конфигурации (1,0), т.е. правило 1) позиция 0; конфигурация (1,1) соответствует точке, появляющейся сразу после real в правиле 1), а (2,0) – точке появляющейся перед IDLIST в правой части правила 2). Так, конфигурация (2,2) показывает, что правая часть правила 2) распознана по запятую включительно.
Состояние в таблице разбора примерно соответствует конфигурациям в грамматике с той разницей, что конфигурации, которые неразличимы для анализатора, представляются одним и тем же состоянием. Например, если (1,0) соответствует состоянию 1, а (1,1) - состоянию 2, то в вышеприведенной грамматике (2,0), (3,0) и (4,0) будут также соответствовать состоянию 2. В этом случае говорят, что множество конфигураций
образуют замыкание (1,1).
Из заданного состояния, не соответствующего концу правила, можно перейти в другое состояние, введя терминальный или нетерминальный символ. Это состояние называется преемником первоначального состояния. Чтобы построить таблицу разбора, необходимо прежде найти все состояния в грамматике. Поэтому, начиная с конфигурации (1,0), последовательно выполним операции замыкания и образования приемника до тех пор, пока все конфигурации не окажутся включенными в какое-либо состояние. Там, где ряд конфигураций содержится в одном замыкании, каждая из них будет соответствовать одному и тому же состоянию. Новая конфигурация, которая получается при операции образования преемника, называется базовой. Если за базовой конфигурацией следует нетерминал, то все конфигурации, соответствующие помещению точки слева от каждой правой части для данного нетерминала, сконцентрируются в замыкании этой базовой конфигурации. В приведенной грамматике можно выделить семь состояний, которые описываются следующим образом (табл. 5.2).
Таблица 5.2 – Состояния грамматики
| Состояние | База | Замыкание |
| (1,0) (1,1) (4,1) (3,1) {(2,1), (1,2)} (2,2) (2,3) | {(1,0)} {(1,1), (2,0), (3,0), (4,0)} {(4,1)} {(3,1)} {(2,1), (1,2)} {(2,2), (4,0)} {(2,3)} |
Эти состояния расположены в грамматике следующим образом:
1) S ® 1 real 2 IDLIST 5
2) IDLIST ® 2 IDLIST 5 , 6 ID 7
3) IDLIST ® 2 ID 4
4) ID ® (2,6) A | B | C | D 3
Заметим, что конфигурация может соответствовать более чем одному состоянию, и в базе может быть более одной конфигурации, если преемники двух конфигураций в одном и том же замыкании неразличимы. Например, за конфигурациями (1,1) и (2,0) следует IDLIST, что делает (1,2) и (2,1) неразличимыми, пока не осуществится операция замыкания. Число состояний в анализаторе соответствует числу множеств неразличимых конфигураций в грамматике. Причина того, что два и более состояния соответствуют одной конфигурации, раскрывается в ходе разбора.
Действия анализатора со сдвигом аналогичны операции получения преемника. Поэтому действия со сдвигом в таблицу разбора могут вноситься на основании информации о размещении состояний в грамматике (табл. 5.3).
Таблица 5.3.
| Состояние | S | IDLIST | ID | real | «,» | A B C D | ^ |
| S5 | S4 | S2 | S6 | S3 S3 |
Например, правило 2) означает «из состояния 2 при чтении IDLIST перейти в состояние 5», «из состояния 5 при чтении запятой перейти в состояние 6» и т.д.
Задача внесения приведения в таблицу разбора нетривиальна. Однако, единственные состояния, в которых приведения возможны, - это состояния, соответствующие окончаниям правил (в нашей грамматике 3, 4, 5, и 7). Поэтому мы можем внести R4 во все столбцы состояния 3, R3 - во все столбцы состояния 4, R1 – во все столбцы состояния 5 и R2 – во все столбцы состояния 7. Однако в состоянии 5 в одном столбце уже имеется элемент сдвига. Таким образом, возникает конфликт сдвиг/приведение. Состояние 5 называется неадекватным. Разрешить эту проблему можно просматривая символы, которые показали бы приведение в состояние 5, а не сдвиг. Из правил 1) и 2) следует, что такими символами могут быть только «^» и «,», а приведение возможно лишь в том случае, если символ окажется «^», в то время как анализатор осуществит сдвиг в состояние 6, если следующим символом будет «,». Поэтому вносим R1 в пятую строку столбца, соответствующего знаку «^». Этим действием неадекватность снимается (табл. 5.4).
Таблица 5.4.
| Состояние | S | IDLIST | ID | real | «,» | A B C D | ^ |
| R4 R3 R2 | S5 R4 R3 R2 | S4 R4 R3 R2 | S2 R4 R3 R2 | R4 R3 S6 R2 | S3 R4 R3 S3 R2 | R4 R3 R1 R2 |
Аналогичным образом, рассмотрев предварительные символы, можно исключить из таблицы все лишние приведения. В результате таблица разбора приобретает вид табл. 5.5.
Таблица 5.5.
| Состояние | S | IDLIST | ID | real | «,» | A B C D | ^ |
| HALT | S5 | S4 | S2 | R4 R3 S6 R2 | S3 S3 | R4 R3 R1 R2 |
14. Опишите, как может быть реализован оператор case или switch в том языке, с которым вы знакомы.
15. Алгоритм LR- разбора.
16. Опишите, как может быть реализован оператор if в том языке, с которым вы знакомы.
17. Организация распределения памяти на базе стека.
1) Стек
Структура данных, в которой доступ к элементам организован по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.
Расп.памяти: в стек записываются адреса переменных, получается их адрес. Этот адрес прога использует. если рекурсивно - опят новые переменные в стеке и адреса. т.е
n = [start+1]
m=[start+2]
В стеке только адреса на кучу. [прога]->[cтек-адреса на кучу]->[куча здесь так: +;адрес начала;адрес конца]
18. Критерии производительности компиляторов.
19. Таблица символов
представляются объекты.
типа как: [id;имя;тип ->ссылка на таблицу типов]
В процессе работы компилятор хранит информацию об объектах программы в специальных таблицах символов. Как правило, информация о каждом объекте состоит из двух основных элементов: имени объекта и описания объекта. Информация об объектах программы должна быть организована таким образом, чтобы поиск ее был по возможности быстрее, а требуемая память по возможности меньше.
Кроме того, со стороны языка программирования могут быть дополнительные требования к организации информации. Имена могут иметь определенную область видимости. Например, поле записи должно быть уникально в пределах структуры (или уровня структуры), но может совпадать с именем объекта вне записи (или другого уровня записи). В то же время имя поля может открываться оператором присоединения, и тогда может возникнуть конфликт имен (или неоднозначность в трактовке имени). Если язык имеет блочную структуру, то необходимо обеспечить такой способ хранения информации, чтобы, во-первых, поддерживать блочный механизм видимости, а во-вторых - эффективно освобождать память при выходе из блока. В некоторых языках (например, Аде) одновременно (в одном блоке) могут быть видимы несколько объектов с одним именем, в других такая ситуация недопустима.
Мы рассмотрим некоторые основные способы организации таблиц символов в компиляторе: таблицы идентификаторов, таблицы расстановки, двоичные деревья и реализацию блочной структуры.
20. Языки промежуточных представлений кода.
Дерево, построенное синтаксическим анализатором, используется для того, чтобы получить перевод входной программы. Этот перевод может быть программой в машинном коде, но чаще всего он бывает программой на промежуточном языке, таком как ассемблер или трехадресный код (из операторов, содержащих не более 3 идентификаторов).
Если требуется, чтобы компилятор произвел существенную опти-мизацию кода, то предпочтительно использовать трехадресный код, т.к. он не использует промежуточные регистры, привязанные к кон-кретному типу машин.
Программа для.NET Framework, написанная на любом поддерживаемом языке программирования, сначала переводится компилятором в единый для.NET понятный человеку низкоуровневый язык Common Intermediate Language (CIL) (ранее назывался Microsoft Intermediate Language, MSIL). Затем компилятор производит перевод CIL-кода в объектный байт-код (в терминах.NET получается сборка, англ. assembly), а уже байт-код либо исполняется виртуальной машиной CLR, либо транслируется утилитой NGen.exe в исполняемый код для конкретного целевого процессора. Использование виртуальной машины предпочтительно, так как избавляет разработчиков от необходимости заботиться об особенностях аппаратной части. В случае использования виртуальной машины CLR, встроенный в неё JIT-компилятор «на лету» (just in time — компиляция на лету) преобразует промежуточный байт-код в машинные коды нужного процессора. Современная технология динамической компиляции позволяет достигнуть высокого уровня быстродействия. Виртуальная машина CLR также сама заботится о базовой безопасности, управлении памятью и системе исключений, избавляя разработчика от части работы.
псевдоко́д — машинно-независимый код низкого уровня, генерируемый транслятором и исполняемый интерпретатором. Большинство инструкций байт-кода эквивалентны одной или нескольким командам ассемблера. Трансляция в байт-код занимает промежуточное положение между компиляцией в машинный код и интерпретацией.
Байт-код называется так, потому что длина каждого кода операции — один байт, но длина кода команды различна. Каждая инструкция представляет собой однобайтовый код операции от 0 до 255, за которым следуют такие параметры, как регистры или адреса памяти. Это в типичном случае, но спецификация байт-кода значительно различается в разных языках.
Программа на байт-коде обычно выполняется интерпретатором байт-кода (обычно он называется виртуальной машиной, поскольку подобен компьютеру). Преимущество — в портируемости, т. е. один и тот же байт-код может исполняться на разных платформах и архитектурах. То же самое преимущество дают интерпретируемые языки. Однако, поскольку байт-код обычно менее абстрактный, более компактный и более «компьютерный», чем исходный код, эффективность байт-кода обычно выше, чем чистая интерпретация исходного кода, предназначенного для правки человеком. По этой причине многие современные интерпретируемые языки на самом деле транслируют в байт-код и запускают интерпретатор байт-кода. К таким языкам относятся Perl, PHP, Ruby (начиная с версии 1.9) и Python. Программы на Java обычно передаются на целевую машину в виде байт-кода, который перед исполнением транслируется в машинный код «на лету» — с помощью JIT-компиляции. В стандарте открытых загрузчиков Open Firmware фирмы Sun Microsystems байт-код представляет операторы языка Forth.
В то же время возможно создание процессоров, для которых данный байт-код является непосредственно машинным кодом (такие процессоры существуют, например, для Java и Forth).
Также некоторый интерес представляет p-код (p-code), который похож на байт-код, но физически может быть менее лаконичным и сильно варьироваться по длине инструкции. Он работает на очень высоком уровне, например «напечатать строку» или «очистить экран». P-код повсеместно используется в СУБД и некоторых реализациях BASIC и Паскаля.
Программы на Java транслируются в байт-код, выполняемый виртуальной машиной Java (JVM) — программой, обрабатывающей байтовый код и передающей инструкции оборудованию как интерпретатор.
Достоинство подобного способа выполнения программ — в полной независимости байт-кода от операционной системы и оборудования, что позволяет выполнять Java-приложения на любом устройстве, для которого существует соответствующая виртуальная машина. Другой важной особенностью технологии Java является гибкая система безопасности благодаря тому, что исполнение программы полностью контролируется виртуальной машиной. Любые операции, которые превышают установленные полномочия программы (например, попытка несанкционированного доступа к данным или соединения с другим компьютером) вызывают немедленное прерывание.
21. Таблица видов (типов).
[id;тип;имя]
id - адрес на которую ссылается данные с таблицы символов.
22. Сравнение JAVA и.NET.
Если Вы знакомы с Java, архитектура платформ покажется Вам похожей, особенно на высоком уровне.
Приложение на Java компилируется в байт-код, на.NET в промежуточный язык MSIL (Microsoft Intermediate Language). Для работы приложения на Java требуется поставить на клиента JRE (Java Runtime Environment), для работы.NET требуется наличие CLR (Common Language Runtime).
И с той, и с другой платформой поставляется обширная библиотека базовых классов, готовых к использованию.
Теперь о некоторых отличиях, больших и не очень.
Библиотеки.
1)В.NET ставится один.NET Framework SDK.
2)Если говорить про разработку приложений для настольных компьютеров и для серверов, в Java для этого используются разные пакеты разработчиков - J2SE и J2EE.
Сервера приложений.
1)Достаточно серверной операционной системы. Веб-сервер и поддержка COM+ входят в стандартные возможности Windows 2000 Server/Advanced Server/Datacenter, Windows.NET
2)Для полноценного использования возможностей J2EE Вам необходимо воспользоваться сервером приложений (бесплатным или купленным).
Отдельно хочется выделить одну из ключевых возможностей архитектурного решения.NET, которое позволяет говорить о его уникальности. Корпорация Microsoft с первых дней представления.NET заявила, что дает разработчику свободу выбора языка. И это не пустые слова.
Технология предоставляемая в Microsoft.NET намного проще в использовании и более прозрачна, чем ранее используемые средства интеграции объектов в разных средах (COM, CORBA, Java RMI). Суть нового решения в том, что программный код всех языков, поддерживаемых.NET, компилируется не в родной код платформы, а в промежуточный код. Данный промежуточный код фактически является ассемблером, но в отличии от традиционного ассемблера для x86 платформы является объектно-ориентированным и поддерживает несколько высокоуровневых конструкций.
Скептики при таких заявлениях сразу стали утверждать, что языков-то, видимо, будет раз-два и обчелся. Но если бы мы верили скептикам, мы бы игнорировали многие технологии. Вряд ли мы поверили бы кому-то в возможности запускать один и тот же код на java в абсолютно различных программных средах. Креативные личности и компании не подвели разработчиков и сейчас под.NET есть порядка 20-ти языков, включая версии для Visual Basic, C++, Java, COBOL, Pascal и другие.
Размеры нашей публикации не позволяют углубляться более детально во все особенности каждого архитектурного решения. Оба решения красивы, оба достойны внимания и оба обладают индивидуальностью при том, что они похожи.
Интеграция бизнес-приложений.
В этой области решение о выборе платформы может быть принято только после детального анализа существующей инфраструктуры и требований к ее изменению (созданию новой). Тем более, что зачастую вопрос выбора технологии не стоит, в связи с огромными потерями при создании системы с нуля.
Вместе с выходом.NET компания Microsoft предоставило возможность интегрировать самые современные решения с существующим кодом, скажем на COBOL. И это безусловно даст новой технологии огромный рынок. Полная поддержка XML позволяет говорить об идеальной среде для создания B2B приложений. А одна из передовых разработок компании Microsoft - BizTalk Server позволяет максимально использовать возможности этой среды, при этом осуществляя связь с легаси системами (например, включая поддержку EDI).
Война за будущее. Веб сервисы.
Здесь первенство несомненно принадлежит Майкрософт. С другой стороны J2EE сейчас тоже имеет API, позволяющее оперировать SOAP запросами и полноценно работать с веб-сервисами.
Но не стоит забывать, что.NET - это экс "Next Generation Web Services" (одна из первых марок новой технологии). XML технологии были у всех на уме, когда проектировался.NET. Именно по этой причине работа с Xml в.NET намного проще, а иногда вообще не требует от программиста усилий.
Представив новую технологию для работы с данными в.NET - ADO.NET, ориентированную на создание сервисов и веб-приложений (disconnected model), нам представили и встроенную Xml интеграцию. JDBC же таких простых способов работы с XML и XSD не имеет.
Примерно то же самое можно сказать и про XML сериализацию/десериализацию, работа с которой в.NET стала проще за счет использования концепции атрибутивного программирования (в Java отсутствуют атрибуты как элемент языка, а следовательно и как элемент стандартной платформы).
Таким образом сервисы можно делать на разных платформах - выбор в деле вкуса и потребности бизнеса.
Надо заметить, что как и обещано сервисы обеспечивают работу в многородной среде - мы сами использовали.NET веб-сервисы из Java и Perl (и vice versa).
Сравнивая C# и Java.
Честно говоря тема эта кажется мне несколько заезженной, потому весьма коротко для тех, кто не в курсе.
C# (произносится "си шарп") - это основной язык новой платформы, он создавался параллельно с созданием.NET для максимально удобного использования всех возможностей платформы.
Мне довелось писать парсеры обоих языков, так что грамматику и того и другого я знаю достаточно хорошо. Оба языка имеют много различий и в то же время достаточно похожи. В C# больше языковых конструкций, а значит дает больше гибкости для реализации задач. В то же время, на мой взгляд, создателям языка удалось сохранить стройность концепции и сделать красивый язык.
Скажем, в Java остались примитивные типы, так как их наличие достаточно критично по быстродействию. Создатели C# же обошли эту проблему предоставив возможности использовать примитивные типы в качестве объектов (так называемая упаковка/распаковка).
В C# было введено понятие делегата. Если упростить - это объектно-ориентированный указатель на функцию. Таким образом использование обратных вызовов и событий стало намного проще и понятнее.
В C# введено понятие свойства (в Java beans тоже реализуются свойства, но там это вопрос соглашения об именовании функций, в C# же это компилируемая языковая конструкция). Реализация свойств весьма проста и удобна в использовании.
Индексаторы позволяют использовать коллекции при помощи привычного по работе с массивами синтаксиса "[]".
Если добавить сюда концепцию события на уровне поддержки компилятора - становится понятно, почему язык так удобен для разработки компонент. Недаром одним из основных архитекторов C# был Хайлсберг, известный всем по огромному вкладу в Delphi.
Есть еще два основных момента, про которые мы расскажем - это поддержка XML комментариев (очень удобно, XML расширяем в отличии от javadoc формата) и стандартизация языка.
В остальном - советую посмотреть следующие темы: деструкторы, статические конструкторы, внутренние классы, неуправляемый код, переопределение операторов (в том числе приведения типов).
23. Распределение памяти.
Расп памяти - компилятор должен знать как выделять память под проги. 1)Выделение памяти под пер 2) иниц. переменной 3) осв памяти
Дин расп памяти идет: стек или куча.
24. Сравнение LL и LR методов синтаксического разбора.
25. Промежуточный код..
26. Основные задачи сканера.
27. Генерация кода для конструкций ветвления.
28. Способы организации таблицы символов в блочно структурированных языках.
1)Информацию о типе (виде) идентификаторов синтаксический ана-лизатор хранит с помощью таблицы символов. Этими таблицами так-же пользуются генератор кода для хранения адресов значений во время прогона. В языках, имеющих конечное число типов (видов), ин-формацией о типе может быть простое целое число, представляющее этот тип, а в языках имеющих потенциально бесконечное число типов (С++, Pascal и др.), - указатель на таблицу видов, элементами которо-го являются структуры, представляющие вид.
Как уже отмечалось, для простых языков (Fortran, Basic и др.), имеющих конечное число типов, каждый из них может быть представ-лен целым числом. Например, тип integer - посредством 1, а тип real – посредством 2. В этом случае таблица символов имеет вид массива с элементами
Identifier, type.
В языках, имеющих ограничение на число литер в идентификаторе, обычно в таблице символов хранятся сами идентификаторы, а не ка-кое-либо их представление, полученное посредством лексического анализа.
С таблицей символов ассоциируются следующие действия.
1) Идентификатор, встречающийся впервые, помещается в табли-цу символов, его тип определяется по соответствующему опи-санию.
2) Если встречается идентификатор, который уже помещен в таб-лицу, его тип определяется по соответствующей записи в таб-лице.
В соответствии с этой моделью идентификаторы будут появляться в таблице в том же порядке, в каком они впервые встречаются в про-грамме. Всякий раз, когда анализатору встречается идентификатор, он проверяет, есть ли уже этот идентификатор в таблице, и при его отсут-ствии в конец таблицы вносится соответствующая запись. Если иден-тификатора в таблице нет, то требуется ее полный просмотр; но даже в тех случаях, когда идентификатор находится в таблице, поиск в среднем охватывает ее половину. Такой поиск в таблице обычно называют линейным. Естественно, что при больших размерах таблицы этот процесс может оказаться длительным.
Если бы идентификаторы были расположены в алфавитном поряд-ке, то поиск осуществлялся бы гораздо быстрее за счет последователь-ного деления таблицы пополам (двоичный поиск), однако на сортировку записей по порядку каждый раз при добавлении новой записи уходило бы очень много времени, что существенно снижает достоинства этого метода. Поэтому при создании таблицы символов и поиска в ней обычно используется метод хеширования.
Для многих языков программирования в общем случае число воз-можных идентификаторов хотя и конечно, но очень велико.
В общем случае для таблицы символов используется массив из большего числа элементов, чем максимальное число ожидаемых иден-тификаторов в программе, и определяется отображение каждого воз-можного идентификатора на элемент массива (функция хеширования). Это отображение не является, конечно, отображением один к одному, а множество идентификаторов отображается на один и тот же элемент массива. Всякий раз при появлении идентификатора проверяется наличие записи в соответствующем элементе массива. При отсутствии записи этот идентификатор еще не находится в таблице символов, и можно сделать соответствующую запись. Если этот элемент не пустой, проверяется, соответствует ли запись в нем данному идентификатору, и когда выясняется, что соответствия нет, точно так же исследуется следующий элемент и т.д. до тех пор, пока не обнаружится пустой элемент или запись. Таким образом, таблица символов просматривается линейно, начиная с записи, полученной с помощью функции отображения, до тех пор, пока не встретится сам идентификатор или пустой элемент, указывающий на то, что для этого идентификатора записи не существует. Такой массив называется таблицей хеширования, функция отображения – функцией хеширования. Таблица хеширования обрабатывается циклично, т.е., если поиск не завершен к моменту достижения конца таблицы, он должен быть продолжен с ее начала.
Самая простая функция хеширования подразумевает использование первой буквы каждого идентификатора для его отображения на элемент 26-элементного массива. Идентификаторы, начинающиеся с А, отображаются на первый элемент массива, начинающиеся с В – на второй и т.д. После встречи с идентификаторами
CAR DOG CAB ASS EGG
таблица примет вид табл.7.1; позиции идентификаторов зависят от порядка их внесения в таблицу.
Если идентификатор не может быть внесен в ту позицию, которая задается функцией хеширования, происходит так называемый кон-фликт. Чем больше таблица (и меньше число идентификаторов, отра-жающихся на каждую запись), тем меньше вероятность конфликтов. При наличии в программе только вышеперечисленных идентификато-ров и использовании рассмотренной функции хеширования таблица заполнялась бы неравномерно, и имела бы место кластеризация. Функция хеширования, которая зависела бы от последней литеры идентификатора, вероятно, меньше бы способствовала кластеризации. Конечно, чем сложнее функция, тем больше времени требуется для ее вычисления при внесении в таблицу идентификатора или при поиске конкретного идентификатора в таблице. Поэтому выбор функции хе-ширования – важная задача при построении компиляторов.
29. Генерация кода для цикла for.
30. Варианты реализации компиляторов.
31. Генерация кода для цикла while.
32. Стратегии выделения памяти
33. Генерация кода для цикла repeat.
34. Метод рекурсивного спуска.
35. Действия компилятора при обработке конструкций присваивания, при входе в блок и выходе из блока.
36. Отслеживание информации об области видимости.
37. Генерация кода для вычисления выражения: вставка действий в синтаксис.
38. LL(1) языки.Проблемы, связанные с определением свойств LL(1).