Приведение грамматики к виду LL(1). Лабораторнаяработа 2
 Скачать 79.5 Kb.
|
Л А Б О Р А Т О Р Н А Я Р А Б О Т А № 2Приведение грамматики к виду LL(1) Цель – поиск направляющих символов сконструированной КС-грамматики языка и преобразование ее к виду LL(1).
Рассмотрим более подробно группу КС-грамматик, так как они являются наиболее универсальными и поэтому более пригодны в качестве основы для описания языков программирования, а, следовательно, и для фазы синтаксического анализа ( разбора ) компиляции. КС-грамматики, в свою очередь, делятся на три класса:
Появление данной классификации КС-грамматик связано со следующей проблемой. Попытаемся на основе грамматики - - осуществить вывод (разбор) предложения аb + cd + e (рис.1). Разбирать это предложение, в принципе, можно в любом порядке. Это может быть как левый вывод, т.е. последовательная подстановка самых левых НТ-символов правила. Это может быть правый вывод, т.е. последовательная подстановка самых правых НТ-символов правила на каждом шаге вывода. Также вывод может осуществляться и в смешанном порядке. Стратегия вывода ощутимо влияет на эффективность процесса. Каким бы ни был порядок вывода, отдельные шаги состоят из попыток подыскать правило подстановки, подходящее для рассматриваемого участка строки. Так, например, пройдя с самого начала по первым альтернативам правил мы бы сделали вывод о невозможности дальнейшего разбора указанного предложения и неминуемо бы совершили возврат ко второй альтернативе первого правила.  Рис. 1. Вывод (разбор) предложения аb + cd + e Таким образом, чем сложнее грамматика, тем более долгим и запутанным становится алгоритм разбора предложения. Следовательно, конструируемая грамматика должна обладать некоторыми специальными свойствами, позволяющими осуществлять детерминированный ( безвозвратный ) вывод любого предложения. Именно такими свойствами обладают S, Q, LL(1)-грамматики. S-грамматика КС-грамматика называется S-грамматикой (разделенной или простой) тогда и только тогда, когда выполняются следующие два условия:
Грамматика : 1.
3.
является S-грамматикой, так как отвечает условиям принадлежности. Можно заметить, что на основе грамматики такого вида легко построить вывод любого предложения, потому что на любом шаге возможно спрогнозировать, какое из предложений нужно использовать. Такой прогноз осуществляется благодаря тому, что в начале правой части каждого правила находится терминальный символ. А так как для разных альтернатив одного правила Т-символы различны, то всегда можно выбрать необходимый.Множество символов, позволяющих сделать правильный выбор правила, называется множеством выбора или множеством направляющих символов. Направляющие символы являются единственно допустимыми символами на каждом шаге анализа. Для s-грамматик это множество составляет множество непосредственно первых терминальных символов: НАПР(i) = НПерв (i) Q-грамматики КС-грамматика называется Q-грамматикой тогда и только тогда, когда выполняются следующие два условия:
Приведенная ниже грамматика отвечает поставленным условиям. От S-грамматики она отличается только наличием пустой строки (-строки). -строка может использоваться при разборе предложения в двух случаях:
Множества направляющих символов для Q-грамматики: НАПР(i) = НПерв(i) , для непустых правил, След(i) , для -правил. Таким образом, для пустой строки тоже существует множество символов выбора, так называемых символов-следователей, на основании которого возможно применение -правила в двух описанных выше условиях. Например, выведем из приведенной Q-грамматики цепочку aacbb, которая принадлежит языку, определяемому данной грамматикой (рис.2). Для данной КС-грамматики с начальным символом  Рис. 2. Вывод цепочки, принадлежащей языку Анализируя пример, можно установить, что после нетерминала могут идти только Т-символы a и b, т.е. СЛЕД ( ) = {a,b}. LL(1)-грамматика LL(1)-грамматика обобщает классы Q и S-грамматик. LL(1)-грамматика обеспечивает нисходящий детерминированный анализ предложений слева направо, получает L-вывод и использует один предварительно просматриваемый символ анализируемой строки для выбора правила на очередном шаге вывода. LL(1)-грамматика включает в себя свойства Q и S-грамматик. Новым же ее элементом является то, что правая часть правил может начинаться как с Т- и НТ-символов. Направляющими символами LL(1)-грамматик являются НАПР(i) = ПЕРВТ(i), для непустых правил, СЛЕД(i), для пустых правил. КС-грамматика называется LL(1)-грамматикой тогда и только тогда, когда множества выбора различных альтернатив одного и того же правила не пересекаются. Первыми терминальными символами считаются такие Т-символы, которые являются первыми (левыми), во всех возможных предложениях, выводимых из данного правила с использованием любых правил грамматики. Пример: Грамматика Направ. символы
Наиболее трудным является вопрос поиска символов-следователей для LL(1)-грамматики, так как он осложняется присутствием в качестве начала правой части правила НТ-символа. Идеология поиска СЛЕД(i) для LL(1)-грамматики остается такой же, как и для Q-грамматики: символы, следующие за НТ-символом, включающим -строку на любом шаге вывода, являются символами-следователями для -строки. Определим СЛЕД(3): правило 3 является альтернативой для НТ-символа Таким же образом ищется символ-следователь для -строки НТ-символа <ТSP>. На основании определения LL(1)-грамматик можно также вывести три необходимых ( но недостаточных ) условия принадлежности грамматики к классу LL(1):
<В> - ...); 3. Отсутствие альтернативных правил, начинающихся НТ- или Т- символами. Нарушение этих условий приведет к пересечению направляющих символов альтернативных правил грамматики. Преобразование грамматики Обычно для языка программирования дается формальное описание синтаксиса языка с использованием БНФ и ее модификаций или синтаксических диаграмм. Такое описание, ориентированное на прикладного программиста, в принципе, определяет КС-грамматику языка, но весьма далекую от LL(1) грамматики. Поэтому при разработке компилятора приходится готовить эквивалентную грамматику, обладающую нужными свойствами. Это можно сделать неформальным преобразованием правил, т.е. исходя из общей структуры конструкции, записать новые порождающие правила. Однако такой путь при недостаточном понимании структуры языка может привести к ситуации, когда новая грамматика порождает язык, отличающийся от исходного. Другой способ преобразования – формальный, гарантирующий эквивалентность грамматик. Правила преобразования грамматик к виду LL(1)
Если правило грамматики имеет вид - где е - элемент списка, , - разделитель, то его необходимо преобразовать с помощью введения дополнительного НТ-символа и -строки к виду - , где
Как правило, левые рекурсии и леворекурсивные циклы встречаются при описании арифметических выражений: - - т.е. в том случае, когда необходимо получить цепочку любой длины. К примеру, a + a – a + a ... Правило преобразования таких структур схоже с п.1: в начальной структуре ( Правая часть же для - + - - -
Если несколько альтернатив для одного НТ-символа имеют одинаковое начало, то преобразование правила выглядит следующим образом: <S1> - b - aSc - c
Такая замена не изменяет LL(1)-свойств грамматики и может проводиться для всех вхождений НТ-символа в правые части правил или только для некоторых. 4.1. Исключение одиночного правила Если в грамматике имеется одиночное правило -..., то оно может быть исключено, если все вхождения <Р> в правые части правил заменить правой частью одиночного правила. Исключение целесообразно при единственном вхождении в правые части правил грамматики ( лишний НТ-символ грамматики ). |