Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
шпорки.docx
Скачиваний:
0
Добавлен:
01.04.2025
Размер:
353 Кб
Скачать
☆
  1. Восходящие методы синтаксического разбора. Метод перенос-свертка.

Условия реализации метода:

  1. Магазинные символы МП-автомата – терминалы и нетерминалы КС – грамматики, дополненные маркером дна 

  2. Входные символы автомата - терминальные символы, дополненные маркером конца цепочки -| .

  3. Управление автоматом задается управляющей таблицей. Элементами таблицы являются операции ПЕРЕНОС , ОТВЕРГНУТЬ или вызывают процедуру ОПОЗНАТЬ для каждой комбинации магазинного символа и входного символа.

  4. Каждая процедура ОПОЗНАТЬ просматривает несколько верхних символов магазина и либо выбирает одну из операций СВЕРТКА (i) - для i-го правила грамматики, либо выполняет операцию ДОПУСТИТЬ, либо операцию отвергнуть.

  5. Управляющая таблица задает выбор процедуры ОПОЗНАТЬ когда наверху магазина находится основа, в остальных случаях выбирается операция ПЕРЕНОС.

Метод распознает LR грамматики не содержащие аннулирующие правила <A>→ .

Принцип переноса:

Управляющая таблица строится по следующему правилу . Операция ПЕРЕНОС для магазинного символа <В> и терминала a вносится в таблицу когда выполняется одно из условий:

1) имеется правило <A>→  =<B> ,  - цепочка из терминальных и нетерминальных символов , a FIRST () ;

2) если вместо <В> стоит маркер дна магазина и a FIRST (S), где S – стартовый нетерминал грамматики.

Принцип свертывания:

В управляющей таблице ячейка на пересечении магазинного символа <В> и терминала a обеспечивает вызов процедуры ОПОЗНАТЬ в следующих случаях:

  1. для правила <A>→ <B> терминал a NEXT (<A>)

  2. если <B> является стартовым нетерминал грамматики a = -|

Эти правила задают построение двух таблиц, таблицы переносов и таблицы свертываний.

  1. Задачи семантического анализа. Семантические соглашения.

Статическая проверка (Static Checking)

Выполняется на этапе компиляции.

Типы проверок:

    1. Проверка типов: проверяется совместимость типов при выполнении операций и других действий. Самое сложное

      1. Эквивалентность по типу

A: array[1..10] of integer

B: array[1..10] of integer

A и B эквивалентны. Но могут быть более сложные ситуации с собственными типами.

      1. Эквивалентность по структуре

В FORTRAN можно присваивать массивы: A:=B

Типы:

      1. Базовые (integer, real, char, Boolean)

      2. Выражение типа (пользовательские) – на основе базовых типов конструируются более сложные типы

        1. Массив – конечное множество однотипных элементов – array[T,I]

        2. Декартово произведение – многомерный массив TxT.

Например, H: array[1..n] of array[1..k] of integer

        1. Запись – конструкция, предполагающая объединение типов разного вида

record((num x integer)(lex x array[T,I]))

        1. Указатель – указатель на некоторую переменную, в которой хранится тип

pointer(T)

        1. Функция – позволяет от одних типов переходить к другим – F: T1xT2 T3

Например, Sin(x): real real

    1. Проверка управления: передача управления за пределы языковых конструкций (условие, цикл, конкатенация) должна производиться в место, которое является корректным с точки зрения языка. Например, в Си: break.

    2. Проверка единственности. Например, в case несколько пунктов с пересекающимися множествами

    3. Проверка имен. Например, проверка меток: каждая метка должна встретиться минимум 2 раза

Динамическая проверка (Dynamic Checking)

Выполняется на этапе выполнения.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]