Конфликты в процессе ПС-анализа.

Существуют контекстно-свободные грамматики, для которых ПС-анализ не применим. Любой ПС-анализатор для такой грамматики может достичь конфигурации, в которой синтаксический анализатор по информации о содержимом стека и об очередном входном символе не в состоянии решить, должен ли использоваться перенос или свертка (конфликт перенос/свертка, shift/reduce conflict), либо какая из нескольких возможных сверток должна применяться (конфликт свертка/свертка,reduce/reduce conflict). Сейчас мы рассмотрим несколько примеров синтаксических конструкций, приводящих к построению таких грамматик. Технически эти грамматики не входят в класс LR(k)-грамматик, мы говорим о них как о не-LR-грамматиках. k в LR(k) означает количество символов входного потока, следующих за текущим, которые синтаксический анализатор может при необходимости просмотреть, не перенося в стек. Практически используемые грамматики в основном принадлежат классу LR(1).

Пример 12.d

Неоднозначная грамматика не может быть LR-грамматикой. Рассмотрим классический случай грамматики "кочующегоelse":

stmt ® if expr then stmt

| if expr then stmt else stmt

| other

Если ПС-анализатор находится в конфигурации

Стек Вход

$... if expr then stmt else... $

то мы не можем сказать, является ли подстрока if expr then stmt основой, независимо от того, что находится в стеке под нею. Здесь возникает конфликт перенос/свертка – в зависимости от того, что следует за else во входном потоке, верным решением может оказаться свертка if expr then stmt в stmt, а может – перенос else и поиск еще одного stmt для завершения альтернативы if expr then stmt else stmt. Таким образом, мы не можем сказать, что следует использовать в данном случае – перенос или свертку, а значит, грамматика не является LR(1)-грамматикой. Более того, никакая неоднозначная грамматика не может быть LR(k)-грамматикой ни при каком k.

Следует отметить, однако, что ПС-анализ может быть легко адаптирован к разбору некоторых неоднозначных грамматик вроде приведенной выше. При построении такого синтаксического анализатора для грамматики, содержащей две приведенные выше про­дукции, мы получим конфликт переноса/свертки – переноcе else или свертки stmt ® if expr then stmt. Если мы разрешим конфликт в пользу переноса, синтаксический анализатор будет работать нормально.

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

Пример 12.e

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

(1)	stmt	id(parameter_list)
(2)	stmt	expr:= expr
(3)	parameter_list	parameter_list, parameter
(4)	parameter_list	parameter
(5)	parameter	id
(6)	expr	id(expr_list)
(7)	expr	id
(8)	expr_list	expr_list, expr
(9)	expr_list	expr

Инструкция, начинающаяся с А(I,J), будет передана синтаксическому анализатору как поток символов id (id, id). После переноса первых трех символов в стек ПС-анализатор окажется в конфигурации

Стек Вход

... id (id, id...

Очевидно, что символ id на вершине стека должен быть свернут, но какой продукцией? Правильный выбор – продукция(5), если А – процедура, и (7), если А – массив. Содержимое стека не может подсказать, чем является А; для принятия решения мы должны использовать информацию из таблицы символов, которая была занесена туда при объявлении А.

Одно из решений состоит в замене символа id в продукции (1) на procid и использовании более интеллектуального лексического анализатора, который возвращает procid при распознавании идентификатора, представляющего собой имя процедуры. Такой способ требует от лексического анализатора обращения к таблице символов перед тем, как вернуть символ.

Если мы внесем эти изменения, то при обработке А(I,J) синтаксический анализатор может оказаться либо в конфигурации, приведенной ранее, либо в следующей:

Стек Вход

... procid (id, id...

В первом случае выбираем свертку по продукции (7); в последнем – по продукции (5). Обратите внимание, что выбор определяется третьим от вершины символом в стеке, который даже не участвует в свертке. Для управления разбором ПС-анализ может использовать информацию "из глубин" стека.

 

Работа с таблицей символов.

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

Когда описывается идентификатор, например,

int a;

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

a=4 или a+b или read(a)

здесь имеются прикладные реализации a.

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

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

{

int a;

...

}

...

{

char a;

...

}

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

Многие современные языки высокого уровня обладают следующими свойствами:

Определяющая реализация идентификатора появляется (текстуально) раньше любой прикладной реализации.

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

В одном и том же блоке идентификатор не может описываться более одного раза.

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

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

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

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

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

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

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

Недостатки:

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

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

 

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

 

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

Недостатки:

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

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

На практике также встречается комбинация этих подходов.

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

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

Рассмотренный метод проиллюстрирован на flash-ролике