|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Теоретическая часть. В процессе синтаксического анализа предложения исходной программы распознаются как языковые конструкции
В процессе синтаксического анализа предложения исходной программы распознаются как языковые конструкции, описываемые используемой грамматикой. Этот процесс можно рассматривать как построение дерева грамматического разбора для транслируемых предложений. Все методы грамматического разбора в соответствии с порядком построения дерева можно разбить на два больших класса: 1. восходящие; 2. нисходящие. Восходящие методы (методы "снизу-вверх") начинают создание дерева с конечных узлов дерева и пытаются объединить их построением узлов всё более и более высокого уровня до тех пор, пока не будет достигнут корень дерева. Нисходящие методы (методы "сверху-вниз") начинают построение с корня дерева грамматического разбора и пытаются так его наращивать, чтобы последующие узлы соответствовали синтаксису анализируемого предложения. В пределах названных классов разработано множество конкретных методов грамматического разбора, которые применяются к грамматикам, удовлетворяющим определённым требованиям. В настоящей работе предлагается разработать блоки синтаксического анализатора, в котором реализуется один из нисходящих методов анализа, называемый рекурсивным спуском. Синтаксический анализатор, основанный на этом методе, состоит из отдельных процедур для распознавания нетерминальных символов, определённых в грамматике. Каждая такая процедура ищет во входном потоке лексем подстроку, которой может быть поставлен в соответствие нетерминальный символ, распознаваемый с помощью данной процедуры. В процессе своей работы процедура может обратиться к другим подобным процедурам для поиска других нетерминальных символов или даже рекурсивно вызвать саму себя. Если эта процедура интерпретирует входную подстроку как соответствующий нетерминальный символ, то она заканчивает свою работу, передаёт в вызвавшую её программу или процедуру признак успешного завершения и устанавливает указатель текущей лексемы на первую лексему после распознанной подстроки. Если же процедура не может найти подстроку, которая могла бы быть интерпретирована как требуемый нетерминальный символ, она заканчивается с признаком неудачного завершения и выдает соответствующее диагностическое сообщение. В общем случае для любого нетерминального символа в грамматике может существовать несколько альтернативных описаний. В связи с этим каждая процедура анализатора дополнительно на основании анализа очередной входной лексемы должна определять, какую альтернативу использовать в качестве следующей. Для иллюстрации данного метода рассмотрим следующую грамматику. 1. <оператор>::=<переменная>:=<выражение> 2. <переменная>::=ИМЯ | ИМЯ(<выражение>) 3. <выражение>:: =<терм> | <выражение>+<терм> 4. <терм>::=<множитель> | <терм>*<множитель> 5. < множитель>:: =< переменная> | (<выражение>) Здесь ИМЯ - терминальный символ, представляемый как последовательность букв и цифр, начинающихся с буквы. Попытка написания полного набора процедур для этой грамматики наталкивается на трудность, связанную с тем, что ряд правил грамматики (третье и четвертое) имеют альтернативы, в описания которых входят нетерминальные символы левой части этих правил. Подобные правила, как и грамматики их содержащие, называются леворекурсивными. Реализация таких правил приводит к множественному рекурсивному вызову соответствующих процедур, что ведёт к зацикливанию программы синтаксического анализатора. Для исключения левой рекурсии правил грамматики используется несколько методов. Один из них, называемый итерацией, заключается в итеративном представлении правых частей леворекурсивных правил с помощью метасимволов {...}. Эта запись означает, что конструкция, заключённая в фигурные скобки, может либо отсутствовать, либо повторяться один или большее число раз. Тогда 1. < оператор>::=<переменная>:=<выражение> 2. < переменная>::=ИМЯ | ИМЯ(<выражение>) 3. < выражение>::=<терм>{+<терм>} 4. < терм>:: =<множитель> {*<множитель>} 5. <множитель>:: =<переменная> | (<выражение>) Согласно новым определениям процедура, соответствующая, например, нетерминальному символу <выражение>, сначала вызывает процедуру для анализа нетерминального символа <терм>, затем она должна проверить в строке лексем наличие любого, но конечного числа конструкций вида "+<терм>". В результате трудности в реализации леворекурсивных правил устраняются. При этом в целом преобразованная грамматика не теряет свойство обычной рекурсивности. Рассмотрим в качестве примера набор процедур синтаксического анализа методом рекурсивного спуска для правил модифицированной грамматики. Процедуры написаны на упрощенном ПАСКАЛЕ и сопровождаются комментариями, пояснявшими логику их работы. PROCEDURE INSTRUCT; Процедура для нетерминала <оператора> BEGIN. VARIABLE; Анализируется наличие переменной. IF NXTSYMB<>’:=’ Проверяется наличие символа ": =" THEN ERROR и затем анализируется выражение. ELSE BEGIN SCAN; EXPR END END; PROCEDURE VARIABLE; Процедура для нетерминала <переменная>. BEGIN IF NXTSYMB<>'буква’ Переменная должна начинаться с буквы. THEN ERROR ELSE BEGIN SCAN; Взять символ, следующий за первой бук WHILE NXTSYMB=’буква’ вой. Читать символы, пока они являются OR NXTSYMB='цифра' DO буквами или цифрами. SCAN; IF NXTSYMB =’(‘ THEN Если символ, следующий за последней бук- BEGIN SCAN; EXPR; вой иди цифрой, есть открывающаяся ско- IF NXTSYMB<>')' бка, перейти к разбору выражения и про- THEN ERROR верить, следует ли за выражением эакры- ELSE SCAN ваюшаяся скобка. Занести в NXTSYMB сим- END вол, следующий за обработанной констру- END кцией. END; PROCEDURE EXPR; Процедура для нетерминала < выражение>. BEGIN TERM; Выражение должно начинаться термом. WHILE NXTSYMB=' +' DO После этого проверяется наличие конеч- BEGIN SCAN; ного числа конструкций вида "+<терм>". TERM END END; PROCEDURE TERM; Процедура для нетерминала <терм> ана- BEGIN FACTOR; логична предыдущей процедуре. WHILE NXTSYMB=' *' DO BEGIN SCAN; FACTOR END END; PROCEDURE FACTOR; Процедура для нетерминала <множитель>. BEGIN По первому символу выбирается альтер IF NXTSYMB=’(' THEN натива. Если это открывающаяся скобка, BEGIN SCAN; EXPR; то анализируется выражение, которое IF NXTSYMB<>')' должно заканчиваться закрывающейся THEN ERROR скобкой. Если первый символ не скобка, ELSE SCAN то анализируется переменная. END ELSE VARIABLE END; В представленных процедурах используются вся глобальная переменная NXTSYMB и несколько дополнительных процедур. Переменная NXTSYMB всегда содержит ту лексему, которая должна обрабатываться следующей. Процедура SCAN читает эту лексему из таблицы кодов лексем и помешает её в NXTSYMB. Процедура ERROR вызывается в тех случаях, когда обнаруживется ошибка. Она формирует и выдаёт сообщение об ошибке на стандартные устройства вывода и возвращает управление обратно. Синтаксический анализ начинается с обращения к процедуре SCAN, которая помещает самую первую лексему анализируемого текста в NXTSYMB, после чего вызывается процедура INSTRUCT, соответствующая корневому символу модифицированной грамматики. В процессе работы этой процедуры последовательно могут быть вызваны другие процедуры анализатора.
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.008 сек.) |