Восходящий синтаксический анализ. Стековая реализация ПС-анализа.

Поскольку синтаксический анализатор обычно использует контекстно-

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

 

Реализация в виде массива

Достоинства такой организации:

· Быстрое выделение памяти под таблицу символов (происходит один раз при объявлении массива)

· Экономия места за счет отсутствия необходимости хранить информацию о размещении других элементов массива

· Простота реализации методов ускоренного поиска, имитации стека и т.д.

Недостатки:

· При трансляции небольших программ и малом количестве идентификаторов – неэффективное использование памяти, т.к. большая частьмассива остается незанятой

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

·

Реализация в виде цепочной структуры (связанного списка)

Достоинством такой организации является наиболее полное использование ресурсов памяти.

Недостатки:

1. Выделение памяти осуществляется значительно медленнее, т.к. производится отдельно под каждый элемент.

2. Дополнительные затраты памяти, поскольку хранятся ссылки на последующий и, возможно, предыдущий элемент

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

 

Конечные автоматы

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

 

Конечный автомат формально определяется пятью характеристиками:

-конечным множеством состояний (K)

-конечным входным алфавитом (Σ)

-множеством переходов (δ)

-начальным состоянием (S 0 ∈ K)

-множеством последних состояний (f ∈ K)

M = (K, Σ, δ, S 0, f).

Пример: Состояниями автомата являются А и В, входным алфавитом –

{0,1}, начальным состоянием – А, множеством последних состояний – { A }, а

переходами

δ (А, 0) = А,

δ (А, 1) = В,

δ (В, 0) = В,

δ (В, 1) = А.

Эти переходы означают, что при чтении 0 в состоянии А управление передается в состояние А и т.д. При чтении строки

 

0 1 0 0 1 0 1 1

 

управление последовательно передается в следующем порядке через состояния:

А, А, В, В, В, А, А, В, А.

Так как А есть последнее состояние, строка принимается конечным автоматом, однако при чтении строки

 

0 0 1 1 1

 

автомат проходит через состояния

А, А, А, В, А, В

 

поскольку В не является последним состоянием, эта строка не принимается, т.е. она не принадлежит языку, принимаемому этим автоматом.

 

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

 

Переходы можно представить с помощью таблицы (таблица 6.1) и схематически (рис.6.1).

 

Таблица 6.1

 

 

Рис.6.1. Переходы детерминированного конечного автомата.