Построение синтаксического дерева на основе алгоритма рекурсивного спуска. Метод рекурсивного спуска

Синтаксический анализ 2 Содержание 1. LL(1) грамматика 2. Построение синтаксического дерева на основе алгоритма рекурсивного спуска 3. Метод рекурсивного спуска 4. Рекурсивный спуск с возвратами 5. Расположение грамматики в памяти 6. Практическое задание 7. Задание на Лабораторную работу №2 2 LL(1) - грамматики 3 Методы нисходящего синтаксического анализа с одним символом предпросмотра • Для каждого терминала, который находится в левой части нескольких правил, необходимо найти такие непересекающиеся множества символов предпросмотра, чтобы каждое множество содержало символы, соответствующие точно одной возможной правой части. • Выбор конкретного правила для замены данного терминала будет определяться символом предпросмотра и множеством, к которому принадлежит данный символ. 4 Множество первых порождаемых символов • Множество символов предпросмотра, соотнесенных с применением определенного правила, называется ее множеством первых порождаемых символов(director symbol set). 5 Важные категории символов • Стартовый символ для данного нетерминала определяется как любой символ (например, терминал), который может появиться в начале строки, генерируемой нетерминалом. • Символ-последователь для данного нетерминала определяется как любой символ (терминал или нетерминал), который может следовать за нетерминалом в любой сентенциальной форме. 6 • Вычисление множества стартовых символов может быть достаточно трудоемким и вычислительно сложным процессом, и оно всегда выполняется в процессе генерации программы синтаксического анализа, а не при каждом запуске этой программы. 7 Пример • Пусть, например, для нетерминала Т грамматика содержит только два правила: • T::=aG | bG • В этом случае имеем следующие множества стартовых символов: Правило T=:: aG T=::bG Множество стартовых символов {a} {b} 8 • В общем случае, если правило начинается с терминала, множество стартовых символов просто состоит из этого терминала. • Если правило не начинается с терминала, то для него все равно нужно вычислить множество стартовых символов 9 ПРИМЕР (продолжение) • Имеются следующие правила для нетерминала R: R::=BG |CH • Множество стартовых символов нельзя определить «с ходу» • Пусть имеются следующие правила для нетерминала B: • B=:: cD |TV • Тогда можно заключить, что множеством стартовых символов для правила R=:: BG будет {a,b,c}, состоящих из всех стартовых для B 10 Нетерминалы, которые генерируют пустые строки • Множество первых порождаемых символов правила выбираются как множество всех терминалов, которые, выступая как символы предпросмотра, указывают на использование данного правила. • A ::= BC • B::=ε • Множество первых порождаемых символов будет включать • Все символы-последователи А • Стартовые символы B и C • Если и B и C будут генерировать пустые строки, то на использование данной продукции будут указывать символы предпросмотра, являющие последователям А и B и С 11 ПРИМЕР Правило S=:: Ty T=::AB T=::sT A=::aA A=::ε B=::bB B=::ε Множество первых порождаемых символов S – начальный символ грамматики {a, b, y} {s} {a} {b, y} {b} {y} B=::ε равно {y} поскольку y может следовать за B b и y могут следовать за А, если B генерирует пустую строку 12 LL(1)-грамматика • Можно определить как грамматику, в которой для каждого нетерминала, появляющегося в левой части нескольких правил, множества первых порождаемых символов всех правил, в которых появляется этот нетерминал, являются непересекающимися. • L (left – чтение слева направо) L (Leftmost) использование левых порождений, а 1 – один символ предпросмотра. 13 Детерминированный анализ • Если вычислены все множества первых порождаемых символов для всех возможных правых частей правил, то языки, которые описываются LL(1)-грамматикой всегда анализируются детерминировано, т.е. без необходимости отменять правило после его применения (возврат) 14 Недетерминированный анализ • Недетерминированных нисходящий анализ, основанный на откате (backtracking), уже не считается эффективной процедурой, хотя в начале эры компиляторов он широко использовался в языках подобных FORTRAN 15 Грамматика LL(k) • Грамматики LL(k), требующие k символов предпросмотра для различения альтернативных правых частей, также уже не считаются практичными с точки зрения синтаксического анализа 16 LL(1)-языки и LL(1)-грамматики (1) • LL(1)-язык – это язык, который можно сгенерировать посредством LL(1)грамматики. • Для любого LL(1)-языка возможен нисходящий синтаксический анализ с одним символом предпросмотра. • Существует алгоритм определения, относится ли грамматика к классу LL(1), поэтому грамматику можно проверить на “LL(1)-ность», прежде чем создавать на ее основе программу синтаксического анализа. • Но не существует алгоритма определения, относится ли данный язык к классу LL(1), то есть имеет ли он LL(1)-грамматику. 17 LL(1)-языки и LL(1)-грамматики (1) • Не LL(1)-грамматика может иметь или не иметь эквивалентную LL(1)-грамматику, генерирующую тот же язык, и не существует алгоритма, который для данной произвольной грамматики определит, являются ли генерируемы ею язык LL(1) или нет. • Имеются грамматики, не являющиеся LL(1), которые генерируют LL(1)-языки, т.е. грамматики имеют эквивалентные LL(1)грамматики. • Грамматики часто нужно преобразовывать, прежде чем использовать с методами нисходящего синтаксического анализа. 18 ПОСТРОЕНИЕ СИНТАКСИЧЕСКОГО ДЕРЕВА на основе АЛГОРИТМА РЕКУРСИВНОГО СПУСКА 19 Синтаксическое дерево • представляет собой упорядоченное, укорененное дерево, что представляет собой синтаксическую структуру строки в соответствии с некоторой контекстно-свободной грамматикой • Синтаксическое дерево состоит из узлов и ветвей. • Корень – начальный нетерминальный символ • Нетерминальные символы – узлы • Терминальные символы – листья 20 Пример построения синтаксического дерева для LL(1) грамматики (top-down) • ::= • ::= | + • ::= | * • ::= NUM | () • 3*(1+2)+4 21 Построение дерева 22 Метод рекурсивного спуска 23 Метод рекурсивного спуска • Может применяться только к LL(1) –грамматикам • Но, грамматику можно преобразовать и привести к LL(1) грамматике 24 Метод рекурсивного спуска – основные принципы • Процессор грамматического разбора состоит из отдельных процедур для каждого нетерминала, определенного в грамматике. • Процедура ищет подстроку, которая может быть интерпретирована как нетерминал. • Процедура может вызывать другие подобные процедуры или саму себя рекурсивно. 25 Общая идея метода • Для каждого нетерминала U создается по одной рекурсивной процедуре. • • • • ::= ::= | + ::= | * ::= NUM | () • Каждая такая процедура осуществляет разбор фраз, выводимых из U и, возможно, вызывает другие процедуры 26 Пример ::= :=|IFTHEN [ЕLSE] :: = i [()] :: = {+ } :: = {* } :: = | () Процедуры (функции) • STATE • VAR • EXP • TERM • FACTOR Дополнительные процедуры SCAN (лексический анализатор) ERROR – вызывается при возникновении ошибки 27 Входные данные: • Считанные лексемы (токены, символы) из SCAN (лексического анализатора) - лексема и ее тип. 28 Алгоритм. Процедура STATE 1. Первая считанная лексема из SCAN записывается в переменную token 2. Вызывается процедура STATE (соответствует нетерминалу ) 3. Если первый символ (лексема,токен) = IF, тогда сканируем следующий символ и запускаем процедуру EXP; 4. Если следующий символ (за ) != THEN тогда ERROR (ошибка) в противном случае сканируем следующий символ и запускаем процедуру STATE 5. Если следующий символ за ELSE тогда сканируем следующий символ и запускаем процедуру STATE 6. Иначе (1) 1) вызываем процедуру VAR 2) считываем следующий символ. Если он не равен “ :=“, то ERROR (ошибка) иначе считываем следующий символ Вызываем процедуру EXP 29 Алгоритм. Процедура STATE 30 Алгоритм. Процедура VAR 1. Если тип символа не равен ‘i’ тогда ERROR (ошибка) Иначе 2. Считываем следующий символ SCAN 3. Если следующий символ равен ‘(‘ тогда считываем следующий символ SCAN. Вызываем процедуру EXP 4. Если следующий символ неравен ‘)’ тогда ERROR (ошибка) иначе вызов процедуры SCAN 31 Алгоритм. Процедура VAR 32 Алгоритм процедуры EXP 1. Вызов процедуры TERM 2. Пока token = ‘+’ считываем очередной символ и вызываем процедуру TERM 33 Алгоритм процедуры EXP 34 Алгоритм процедуры TERM 1. Вызов процедуры FACTOR 2. Пока token=‘*’ считываем очередной символ и вызываем процедуру TERM 35 Алгоритм процедуры TERM 36 Алгоритм процедуры FACTOR 1. Если token=‘(‘ тогда считываем следующий символ SCAN и вызываем процедуру EXP; 2. Если token не равен ‘)’ тогда ERROR (ошибка) иначе считываем следующий символ SCAN 3. Иначе (1) вызываем процедуру VAR 37 Алгоритм процедуры FACTOR 38 Не все грамматики для этого подходят, Поэтому требуется преобразование грамматики 39 О применимости метода рекурсивного спуска (1) Метод рекурсивного спуска применим в том случае, если каждое правило грамматики для символа UN имеет вид: • либо U→, где (T+N)* и это единственное правило вывода для этого нетерминала; • либо U→a11 | a22 | ... | an n, где aiT для всех i = 1,2,...,n; ai  aj для i  j; и i(T+N)*, т. е. если для нетерминала U правил вывода несколько, то они должны начинаться с терминалов, причем все эти терминалы должны быть различными. Если правила вывода имеют такой вид, то рекурсивный спуск может быть реализован по вышеизложенной схеме. 40 О применимости метода рекурсивного спуска (1) Сформулированное выше условие не является необходимым. Метод рекурсивного спуска представляет собой одну из возможных реализаций нисходящего анализа с прогнозируемым выбором альтернатив. Прогнозируемый выбор означает, что по грамматике можно заранее предсказать, какую альтернативу нужно будет выбрать на очередном шаге вывода в соответствии с текущим символом (т.е. первым символом из еще не прочитанной части входной цепочки). РС-метод неприменим, если такой выбор неоднозначен. Например, для грамматики G: S→A|B A → aA | d B → aB | b РС-метод неприменим, поскольку, если первый прочитанный символ есть ‘а’, то выбор альтернативы правила вывода из S неоднозначен. РС-метод неприменим к неоднозначным грамматикам, так как на каком-либо шаге анализа выбор альтернативы вывода обязательно будет неоднозначным. 41 Рекурсивный спуск в возвратом 42 Рекурсивный спуск с возвратами Чтобы иметь возможность применить метод рекурсивного спуска, мы должны преобразовать грамматику к виду, описанному выше. Это сложный и неприятный процесс. Поэтому зачастую используется следующий прием, называемый рекурсивным спуском с возвратами. 43 Рекурсивный спуск с возвратами – основной принцыа Для этого лексический анализатор представляется в виде объекта, у которого есть также копирующий конструктор, позволяющий во всех ситуациях, где может возникнуть неоднозначность, запоминать текущее состояние лексического анализатора (т.е. заводим копию лексического анализатора ). Если первый вариант разбора заканчивается неудачей, то мы восстанавливаем состояние лексического анализатора и пытаемся заново разобрать тот же самый фрагмент с помощью следующего варианта грамматики и т.д. Если все варианты разбора заканчиваются неудачно, то мы сообщаем об ошибке. Такой метод разбора медленнее, чем рекурсивный спуск без возвратов, но взамен удается сохранить грамматику в ее оригинальном виде и сэкономить усилия программиста. 44 Расположения грамматики в памяти 45 Методы расположения грамматики в памяти • Грамматика: Z::=E + T | T • В виде одномерного массива Z E + T • указатель | T # E признак конца T ... • В виде списка E + T • В виде структуры NAME DEF ALT SUC DEF – Указатель на первый символ в правой части правила для этого символа. Ноль, если терминал ALT – Указатель на первый символ в правой части альтернативного правила для этого символа SUC – Указатель на следующий тер\нетер. 46 Методы расположения грамматики в памяти. Синтаксический граф Грамматика: E ::= E T|T T ::= TF|F F ::= i | (E) ::= +| ::= *|/ 47 Методы расположения грамматики в памяти. Синтаксический граф E E AOP T 0 0 + - i 0 0 0 0 0 0 AOP T 0 0 T F T MOP F 0 0 MOP F ( 0 0 * / E ) 0 0 0 0 0 0 E 48 Практическое задание 49 Задание на лабораторную работу №2 50 Преобразования грамматик Проблема возможности построения грамматики, к которой применим метод рекурсивного спуска (РС), эквивалентной грамматике, не удовлетворяющей критерию применимости РС-метода, является алгоритмически неразрешимой проблемой. 1) Если в грамматике есть нетерминалы, правила вывода которых леворекурсивны, т.е. имеют вид A → A1 | ... | An | 1 | ... | m, //A → A |  где i  (T  N)+, j  (T  N)*, i = 1, 2, ..., n; j =1, 2 ,..., m, то непосредственно применять РС-метод нельзя. Левую рекурсию всегда можно заменить правой: A → 1A’ | ... | mA’ // A → A’ A’ → 1A’ | ... | nA’ |  // A’ → A’ |  Будет получена грамматика, эквивалентная данной, т.к. из нетерминала A попрежнему выводятся цепочки вида j {i}, где i = 1,2,...,n; j = 1,2,...,m. 51 2) Если в грамматике есть нетерминал, у которого несколько правил вывода, и среди них есть правила, начинающиеся нетерминальными символами, т.е. имеют вид: A → B11 | ... | Bnn | a11 | ... | amm // A → B | С B1 → 11 | ... | 1k // B → 1 | 2 ... // С → 1 | 2 Bn → n1 | ... | np , где Bi  N; aj  T; i, j, ij  (T  N)*, то можно заменить вхождения нетерминалов Bi их правилами вывода в надежде, что правила вывода из нетерминала A станут удовлетворять требованиям метода рекурсивного спуска: A → 111 | ... | 1k1 | ... | n1n | ... | npn | a11 | ... | amm // A → 1 | 12 | 1 | 2 52 3) Если в грамматике есть нетерминал, у которого несколько правил вывода начинаются одинаковыми терминальными символами, т.е. имеют вид A → a1 | a2 | ... | an | 1 | ... |m , // A → a1 | a2 |  где a  T; i,  j  (T  N)*, то непосредственно применять РС-метод нельзя. Можно преобразовать правила вывода данного нетерминала, объединив правила с общими началами в одно правило: A → aA’ | 1 | ... |m // A → aA’ |  A’ → 1 | 2 | ... | n // A’ → 1 | 2 Будет получена грамматика, эквивалентная данной. 53 4) Если в правилах вывода грамматики есть пустая альтернатива, т.е. есть правила вида A → a11 | ... | ann |  , то метод рекурсивного спуска может оказаться неприменимым. Мы помним, что такая грамматика называется укорачивающей и она практически не применяется (грамматика типа 0 по Хомскому). В теории вычислимости алгоритмически неразрешимой задачей называется задача, имеющая ответ да или нет для каждого объекта из некоторого множества входных данных, для которой (принципиально) не существует алгоритма, который бы, получив любой возможный в качестве входных данных объект, останавливался и давал правильный ответ после конечного числа шагов. 54 Проблема алгоритмической неразрешимости достаточно серьезна. На практике это означает, что если ставится проблема построения алгоритма, имеющего общий (универсальный) характер, например, автоматического синтеза программ по описанию произвольной задачи, то скорее всего такая проблема не может быть решена. Но если проблему ограничить, не ориентируясь на синтез программ для произвольных задач, а очертить более узкий круг задач и задать простые правила описания таких задач, то, вероятно, проблема может быть решена. 55