Презентация на тему "Семантическийанализ"

Содержание

• 
  Слайд 1

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

• 
  Слайд 2

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

  2 С целью упрощения синтаксических анализаторов большинство из них основано на контекстно-свободных грамматиках (тип 2). Однако большинство языков программирования содержат те или иные контекстно-зависимые элементы (тип 1). Например, во многих языках идентификаторы не могут применяться, если они не описаны, также имеются ограничения в отношении способов употребления в программе значений различных типов.

• 
  Слайд 3
  

  3 Алгоритмы анализа, основанные на контекстно-зависимых грамматиках, имеют низкую эффективность (как по времени работы, так и по используемой памяти). Поэтому на практике они не используются. Все реально существующие трансляторы выполняют анализ исходной программы в два этапа: 1) синтаксический анализ на основе распознавателя для одного из классов КС-грамматик; 2) семантический анализ.

• 
  Слайд 4
  

  4 Основная задача семантического анализа – определить, соответствует ли программа семантическим соглашениям языка. На этапе семантического анализа выполняется несколько типов проверок. Конкретный состав проверяемых соглашений зависит от семантики языка.

• 
  Слайд 5
  

  5 Проверка соответствия типов Необходимо убедиться в том, что: – арифметические операторы применяются к операндам допустимого типа; Пример. double a,b,c; a=6.25; b=2.25; c=a%b;

• 
  Слайд 6
  

  6 – при присваивании тип переменной соответствует типу арифметического выражения; Пример. int a; double b,c; a=b+c; На этапе проверке соответствия типов также выявляется необходимость выполнения неявных преобразований.

• 
  Слайд 7
  

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

• 
  Слайд 8
  

  8 Проверка правильности употребления имен Необходимо убедиться в том, что: – используемый идентификатор был ранее объявлен и находится в области видимости; – отсутствует повторное объявление идентификаторов (например, в операторах case, enum); Пример. int a; for(a=1;a

• 
  Слайд 9
  

  9 Проверка правильности передачи управления Необходимо убедиться, что осуществляется допустимая передача управления. Пример. В C-подобных языках программирования оператор break передает управление за пределы наиболее вложенной инструкции while, for или switch; если же таковые отсутствуют, то выводится сообщение об ошибке.

• 
  Слайд 10
  

  10 Проверка элементарных смысловых норм, не связанных со входным языком – каждая объявленная переменная или константа должна хотя бы один раз использоваться в программе; – каждая переменная должна быть определена до ее первого использования при любом ходе выполнения программы (т.е. первому использованию переменной должно всегда предшествовать присвоение ей какого-либо значения);

• 
  Слайд 11
  

  11 – результат функции должен быть определен при любом ходе ее выполнения; – операторы ветвления и выбора должны предусматривать возможность хода выполнения программы по каждой из своих ветвей; – операторы цикла должны предусматривать возможность завершения цикла; – каждый оператор в исходной программе должен иметь возможность хотя бы один раз выполниться.

• 
  Слайд 12
  

  12 Способы организации семантического анализа Входными данными для семантического анализа служат: – таблица идентификаторов; – результаты разбора синтаксических конструкций входного языка (синтаксическое дерево программы). Результаты семантического анализа фиксируются в какой-либо внутренней форме представления программы, чаще всего в виде атрибутированного синтаксического дерева.

• 
  Слайд 13
  

  13 Реализация проверки правильности употребления имен Определяющей (описывающей) реализацией идентификатора называет синтаксическая конструкция, содержащая объявление идентификатора, например: int a; Все остальные конструкции, содержащие идентификатор, являются прикладными (использующими) реализациями, например: a=4 или a+b или read(a)

• 
  Слайд 14
  

  14 Многие современные языки высокого уровня обладают следующими свойствами: –определяющая реализация идентификатора появляется (текстуально) раньше любой прикладной реализации; –при наличии прикладной реализации идентификатора соответствующая определяющая реализация разыскивается в наименьшем включающем блоке, в котором содержится этот идентификатор; – в одном и том же блоке идентификатор не может описываться более одного раза

• 
  Слайд 15
  

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

• 
  Слайд 16
  

  16 Структура таблицы идентификаторов должна соответствовать блочной структуре программы { int a,b; { char c,d; } { floate,f; } }

• 
  Слайд 17
  

  17 Во многих языках программирования один и тот же идентификатор может использоваться в различных частях программы для представления различных объектов. В таких случаях структура программы помогает различать эти объекты, например: { int a; ... } ... { char a; ... }

• 
  Слайд 18
  

  18 В качестве структуры данных для таблицы идентификаторов очень удобен стек, каждым элементом которого служит элемент этой таблицы. При встрече с описанием соответствующий элемент таблицы идентификаторов помещается в вершину стека. Перед занесением необходимо проверить, нет ли в последнем блоке (С/C++) или во всем стеке (Java) идентификатора с таким же именем.

• 
  Слайд 19
  

  19 При выходе из блока все элементы таблицы идентификаторов, соответствующие описаниям в этом блоке, удаляются из стека. Указатель же стека возвращается в положение, которое он имел при вхождении в блок. В результате в любой момент разбора элементы таблицы, соответствующие всем текущим идентификаторам, находятся в стеке, а связанные с ним прикладные и определяющие реализации идентификаторов требуют поиска в стеке в направлении от вершины к дну стека.

• 
  Слайд 20
  

  20 { // блок 1 int a,b; // ... { // блок 2 float c,d; // ... { // блок 3 double e,f; // ... } } } блок 1 блок 2 блок 3 Для удобства организации поиска и обработки стек может содержать граничные элементы, соответствующие началу каждого блока

• 
  Слайд 21
  

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

• 
  Слайд 22
  

  22 Перед занесением идентификатора необходимо проверить, нет ли в последнем списке (С/C++) или во всей структуре (Java) идентификатора с таким же именем. При выходе из блока удаляется список идентификаторов, соответствовавший данному блоку.

• 
  Слайд 23
  

  23 { // блок 1 int a,b; // ... { // блок 2 float c,d; // ... { // блок 3 double e,f; // ... } } }

• 
  Слайд 24
  

  24 Реализация проверки совместимости типов в арифметическом выражении Исходными данными для анализа является синтаксическое дерево арифметического выражения, результатом – атрибутированное синтаксическое дерево.

• 
  Слайд 25
  

  25 Каждая вершина синтаксического дерева выражения должна помечаться соответствующим ей типом. Для этого используется алгоритм полного обхода графа в глубину.

• 
  Слайд 26
  

  26 Тип каждой вершины определяется следующим образом: 1. Для "листьев", соответствующих константам, тип определяется на основании результатов лексического анализа. 2. Для "листьев", соответствующих идентификаторам, тип определяется на основаниисемантического анализа (исходя из содержимого таблицы идентификаторов).

• 
  Слайд 27
  

  27 3. Для внутренних вершин, соответствующих арифметическим операциям, тип определяется в соответствии с правилами языка программирования для каждой конкретной операции отдельно. Если комбинация типов операндов для анализируемой операции является недопустимой, то семантический анализатор должен завершить работу с ошибкой.

• 
  Слайд 28
  

  28 float float float int int int double double double

• 
  Слайд 29

  Фаза оптимизации

• 
  Слайд 30
  

  30 Необязательной фазой трансляции перед работой генератора кода может быть фаза оптимизации. На этой фазе делается попытка преобразовать промежуточный код в такой вид, по которому может быть получен более эффективный целевой код. Основные критерии оптимизации: – используемые ресурсы (память); – быстродействие; – объем кода.

• 
  Слайд 31
  

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