|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Лабораторная работа 3. Синтаксический анализ. Восходящий разбор. Метод простого предшествования
Цель работы Изучение принципов работы синтаксического анализатора на осно ве метода простого предшествования. Теоретические положения Метод простого предшествования основан на том, что между двумя соседними символами Si и Si+1 приводимой строки могут существовать только три отношения: 1) Si< *Si+1 - отношение верно, если символ Si+1 - самый левый символ некоторой основы; 2) Si*> Si+1 - отношение верно, когда Si - символ, являющийся самым правым в некоторой основе; 3) Si*=Si+1 - верно, если Si и Si+1 принадлежат одной основе. Отношения < *, *>, *= называются отношениями предшествования. Отношения предшествования являются отношениями порядка, т. е. они зависят от порядка следования символов Si и Si+1. Если имеется от ношение Si*> Si+1 - это не означает, что Si+1< *Si, или Si*=Si+1 - не означает, что Si+1*=Si. Если для каждой пары символов грамматики существует не более, чем одно отношение предшествования, то на каждом шаге синтаксического анализа можно выделить основу. Основой называется самая левая группа символов Si... Sj, связанных отношениями предшествования вида: Si< *Si*=Si+1*=... *=Sj*=Sj*> Sj. Грамматика предшествования. Пусть U, C, D - нетерминальные символы; x, y, z, w - любые цепочки. Грамматикой предшествования называется такая грамматика класса 2, которая отвечает следующим двум требованиям: 1) Для каждой упорядоченной пары терминальных и нетерминальных символов выполняется не более, чем одно из трех отношений предшествования, определяемых следующим образом: Si*=Sj, если существует правило U:: =xSiSjy; Si< *Sj, если существует правило U:: =xSiDy и существует вывод из D цепочки Sjz (D-> *Sjz); Si*> Sj, если существует правило U:: =xCSjy и существует вывод C=> *zSi, либо существует правило U:: =xCDy и существуют выводы C=> *zSi, D=> *Sjw. 2) Разные порождающие правила имеют разные правые части. Например, правило для списка идентификаторов id_list:: =id|id_list, id, и правило для множителя F:: =id|(E) имеют одинаковые правые части, но разные левые. Распознаватель простого предшествования. Алгоритм разбора, основанный на отношениях предшествования, заключается в следующем: символы входной строки поочередно переписываются в стек до тех пор, пока между символом на вершине стека Sj и очередным символом входной строки Si не появится отношение *>, т. е. Sj*> Si. Это признак того, что в стеке находится основа. Стек в этом случае просматривается в направлении от вершины к началу до тех пор, пока между двумя очередными символами стека Sk-1 и Sk непоявится отношение < *, т. е. Sk-1 < * Sk. В этом случае часть стека от вершины Sj до символа Sk является основой. После этого среди порождающих правил отыскивается правило U:: = Sk... Sj, и последовательность символов в стеке Sk... Sj заменяется на найденный символ U, который становится текущим. Далее процесс повторяется аналогично. Матрица предшествования. Матрица предшествования формируется на предварительном этапепроектирования транслятора и должна содержать отношения предшествования между символами грамматики. Обозначим L(U) - множество самых левых символов относительно нетерминала U. Формально это множество определяется следующим образом: L(U)={S|если существует правило U=> *Sz}, где S – символ грамматики. Это множество можно определить рекурсивно: L(U)={S|если (существует правило U:: =S... ) или (существует правило U:: =U'... и S принадлежит L(U'))}. Аналогично определяется множество R(U). С использованием множеств R(U) и L(U) отношения предшествова ния определяются следующим образом: Si *= Sj < => если существует правило U:: =... SiSj... Si< *Sj< => если существует правило U:: =... SiD… и Sj принадлежит L(D) Si*> Sj< => если существует правило U:: =... СSj... и Si принадлежит R(C) где С, D-нетерминальные символы. Построение L(U) и R(U) включает несколько шагов: 1)Для каждого нетерминального символа грамматики отыскивается правило, в левой части которого находится символ U. В множество L(U) включаются все самые левые символы правых частей правил для U. В множество R(U) включаются все правые символы из правил для U. 2) Рассматривается полученное множество L(U). Если оно содержит нетерминальные символы U', U'',..., то левые символы для U', U'',... включаются в L(U). Если R(U) содержит нетерминальный символ U1, U2,..., то в R(U) включаются все правые символы для U1, U2,... 3)Пункт 2 выполняется до тех пор, пока множества L(U) и R(U) не перестанут изменяться. Построение матрицы предшествования. 1)Отыскивается отношение *= в соответствии с записанным прави лами грамматики. Отношения < * отыскиваются путем просмотра правых частей правил с использованием формулы для определения данного отношения. Аналогичным образом отыскивается отношение *>. Пример построения матрицы предшествования приведен на рис. 4. 3. Из матрицы предшествования видно, что данная грамматика не является грамматикой предшествования, так как существует неоднозначность отношений предшествования. Неоднозначность отношений предшествования для данной грамматики является следствием того, что в методе простого предшествования используется минимальный контекст. Для устранения неоднозначности отношений предшествования следует использовать более глубокий контекст. Так, в контексте... (Е)... справедливо отношение (*= Е и возможна прямая редукция: (Е)=> E. В контексте... (Е+Т)... между ( и Е выполняется отношение < * и будет редукция: Е+Т=> E. В контексте... +T*F... между + и Т выполняется отношение < * и, следовательно, будет редукция Т*F=> T. В данном случае формально неоднозначность отношений предшест вования вытекает из того, что, например, ( и Е встречаются рядом в правой части, а, с другой стороны, Е принадлежит L(E), то есть L(E) рекурсивно для символа Е. Избежать неоднозначность отношений предшествования можно, используя, например, метод стратификации(отделения), который устраняет рекурсивность множества L(U) или R(U) для тех символов U, для которых отношения предшествования неоднозначны. Например, после введения новых правил: E:: =E' E':: =E+T|T, множество левых символов для Е будет таким L(E)={E', T, F, (, id}. Аналогично вводя стратификацию для символа T можно записать грамматику G2[Z] целиком: Z:: =#E E:: =E' E':: =E'+T|T T:: =T' T':: =T'*F|F F:: =(E)|id. После такого преобразования грамматики множества L(U) и R(U) и матрица предшествования примут вид:
Задание на работу
Варианты заданий такие же как в лабораторной работе N 3. Дополнительно к заданию на каждый вариант добавляется возможность использования функций в подмножестве языка программирования. 4. Контрольные вопросы 1) Какие требования предъявляются к грамматике предшествования 2) Как модифицировать процедуру построения множеств L(U) и R(U) для одношагового процесса? Каким образом должна выглядеть грамматика? 3) Почему появляется неоднозначность отношений предшествования? 4) Каков порядок заполнения матрицы предшествования? 5) Поясните методы устранения неоднозначности отношений предшествования. 6) Как работает распознаватель простого предшествования?
Лабораторная работа 4. Структуры данных в трансляторах Цель работы Ознакомление и освоение приемов работы с различными информационными структурами используемыми в трансляторах. Теоретические положения Данные обычно разделяются на две главные группы - скаляры и структуры. К скалярам относятся числа, коды, флаги, слова. К структурам - массивы, стеки, таблицы, сети, очереди и пр. Структуры формируются из скалярных данных, сгруппированных в соответствии с определенными отношениями. Причем следует различать структуры данных и структуры хранения. Структуры данных - это организованные совокупности данных, определяемые правилами, которые устанавливают отношения между элементами. В общем случае каждый элемент структуры в свою очередь может быть некоторой структурой. Таким образом, взаимоотношения между терминальными элементами данных могут иметь очень сложный вид. Отношения между элементами информационной структуры организуются различными способами. Иногда структуры данных называют логическими структурами, чтобы акцентировать то обстоятельство, что структуры данных воспринимаются пользователем не совсем так, как данные расположены в памяти. Способ хранения структур данных в памяти называется структурой хранения. При проектировании трансляторов наиболее часто используются такие структуры данных, как строка, массив, очередь, стек, двоичное дерево и ориентированный граф. Строка - это одномерный набор данных одного типа, каждый из которых имеет своего предшественника и последователя (за исключением первого и последнего элемента строки). Доступ к i - тому элементу возможен только после просмотра предыдущих i-1 элементов. Массив - набор элементов одного типа, с каждым из которых связан упорядоченный набор целых чисел, называемых индексами, которые однозначно определяют место элемента в массиве. Каждому элементу массива может соответствовать один, два, три и более индексов, в таком случае говорят об одномерном, двумерном, трехмерном и т. д. массиве, n - мерным массивом будет называться массив, у которого элемент определяется n индексами. Таблица - массив структур, причем чаще всего - массив одномерный. Индекс указывает на структуру, обычно на ключевой элемент структуры. Между индексом и ключом структуры существует зависимость, что позволяет быстро находить нужную структуру (строку таблицы). Таблицы бывают либо упорядочены ( в возрастающем или убывающем порядке значения ключа), либо между индексом и ключом структуры устанавливается функциональная зависимость ( подбирается функция преобразования ключа в индекс ). Последний способ доступа называется хешированием, а функция - хеш-функцией. Очередь - одномерный динамически изменяемый массив элементов некоторого типа. Новый элемент в очередь добавляется всегда к одному и тому же концу массива ( к i+1, если в массиве уже было i элементов) обрабатывается ( удаляется из очереди) элемент с другого конца очереди, т. е. с первого. Таким образом, для обработки элементов очереди используется принцип FIFO (первым пришел, первым ушел). Стек - структура данных, которая отличается от очереди тем, что для его элементов используется принцип обработки LIFO (последним пришел, первым ушел). Дерево - структура данных, состоящая из набора вершин, каждая из которых содержит не только данные, но и указатели на вершины нижнего уровня. Данные могут иметь любой вид, а указатели представляют собой адрес нижестоящей вершины. Указателей может быть любое количество. Если указателей у каждой вершины не больше двух- дерево называется бинарным. Единственная вершина самого верхнего уровня называется " корнем". Терминальные вершины в этом случае называют листьями. На каждую вершину кроме корня указывает лишь одна вершина верхнего уровня. Поэтому существует единственный путь от корня до вершины. Листья представляют собой элементы внешние по от- ношению к дереву. С помощью деревьев легко устанавливаются иерархические отношения между данными. Ориентированный граф – это структура подобная дереву, но отличающаяся от дерева тем, что на каждую вершину может указывать более чем одна вершина. Причем вершина может иметь указатель на себя. Если в таком пути есть другие вершины, то путь называют " циклом", если в таком пути вершин других нет, то его называют петлей. Конкретные структуры данных могут быть представлены в памяти ЭВМ различными способами и хранятся в виде так называемых структур хранения. Способы представления различаются временем доступа к различным элементам, допустимым объемом, возможностями модификации элементов данных, эффективностью использования ОП. На практике применяются следующие структуры хранения - вектор, список и сеть. Вектор - это набор соседних элементов хранения одинакового размера, расположенных в памяти рядом. Для получения адреса элемента i нужно к адресу начала массива прибавить (i-1)*l, где l - длина элемента (записи). Чаще всего вектор можно описать как одномерный массив. Список - это набор элементов, каждый из которых состоит из двух полей. Одно поле содержит запись или указатель на запись, второе - указатель на следующий элемент списка. Списки позволяют легко включать новые элементы между любыми уже имеющимися путем корректировки указателей. Элементы списков могут произвольно располагаться в памяти ЭВМ. Двунаправленные списки состоят из элементов с двумя указателями - на предыдущий и последующий элементы. Такой вариант используется в том случае, если доступ к данным производится в обоих направлениях. Списки одно- и двунаправленные полезны в тех случаях, когда требуется связать воедино группу данных, либо упорядочить данные, без их физического перемещения. В программах списки могут быть описаны в виде массивов структур, либо в виде одномерных массивов. Сети похожи на списки, но имеют в отличие от списков несколько указателей на другие элементы сети. В одном из полей элемента хранения помещается элемент данных или указатель на элемент данных. Сети лучше, чем другие структуры хранения, приспособлены для отображения деревьев, в том числе и бинарных, а также ориентированных графов. Организация таблиц В значительной мере на производительность транслятора оказывает влияние используемый способ организации таблиц. К наиболее простым можно отнести неупорядоченные таблицы, в которых записи размещаются последовательно без пропусков. Такие таблицы легко составляются, но доступ к записи с данным значением ключа возможен последовательным просмотром всех записей таблицы от начала вектора, на который отображается таблица, при этом средняя длина поиска для таблицы, содержащей N записей, составляет N/2 просмотров. Неупорядоченные таблицы неэффективны по времени доступа к данным. Однако если таблица невелика, то можно использовать данный способ хранения, т. к. включить запись в такую таблицу достаточно просто. Иногда структуру размещения записей в таблице организуют в виде бинарного дерева. В такой таблице записи снабжаются двумя указателями, один из которых указывает на запись с меньшим ключом, другой - на запись с большим ключом. Средняя длина поиска в сбалансированной древовидной таблице будет равна ]log2 N+2[, где N-количество записей. Использование памяти в древовидных таблицах ухудшается за счет введения указателей. Для уменьшения времени поиска используются упорядоченные таблицы. Обычно записи в таблицы упорядочиваются по значению ключа. В этом случае для поиска записей используют " двоичный поиск". Двоичный поиск состоит в последовательном делении таблицы на две части и определении того, в какой половине содержится запись с искомым ключом. Последующему делению подвергается часть, содержащая ключ и т. д.. Хеш-таблицы. Наиболее эффективной является организация таблиц с прямым доступом. При этом для N записей с различными значениями ключей подбирается функция f(i), где i - значение ключа. Функция f(i) называется функцией расстановки, для каждого i она возвращает уникальное целое значение в диапазоне между 1 и М, где М> =N. Поэтому доступ к записи с ключом х возможен путем вычисления f(x). По значению X=f(x) выбирается из вектора отображения длиной М соответствующий элемент с номером Х. Описанный способ доступа называется хешированным, а функция расстановки хеш-функцией. Задание на работу Разработать согласно варианту задания пример информационной структуры. Определить процедуры создания, ведения и корректировки соответствующей структуры. Разработать и отладить программное обеспечение этих процедур. Варианты заданий приведены в таблице. Таблица. Варианты заданий
4.4 Контрольные вопросы 1) Какие бывают типы упорядоченных таблиц? 2) Как вычислить среднюю длину поиска в древовидной таблице? 3) Что влияет на использование таблиц с вычисляемыми входами? 4) Какие методы используются для преодоления коллизий? 5) В чем заключается принцип линейного рехеширования? 6) Для чего используются при построении таблиц цепочки переполнения записей?
Популярное:
|
Последнее изменение этой страницы: 2016-05-03; Просмотров: 1172; Нарушение авторского права страницы