Презентация на тему "Синтаксическийанализ"

Содержание

• 
  Слайд 1

  Синтаксическийанализ

• 
  Слайд 2

  Синтаксический анализ

  2 Синтаксический анализ (распознавание, разбор, parsing) является обязательной фазой в работе любого транслятора. Синтаксический анализ преследует две цели: – определить принадлежность цепочки символов языку; – выявить структуру этой цепочки.

• 
  Слайд 3
  

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

• 
  Слайд 4
  

  4 Успешное восстановление дерева вывода для заданной цепочки означает, что цепочка есть правильное предложение языка, порождаемого некоторой грамматикой. Наоборот, если для некоторой цепочки символов дерево вывода построить невозможно, это значит, что цепочка не принадлежит языку, порождаемому грамматикой.

• 
  Слайд 5
  

  5 Свойства синтаксического дерева – Корень дерева помечен стартовым символом грамматики. – Каждый лист дерева помечен терминальным символом или . – Каждый внутренний узел помечен нетерминальным символом. – Если нетерминальный символ A помечает некоторый внутренний узел, и его дочерние узлы имеют метки Х1, Х2, ..., Хn, тограмматика содержит правило вида А  Х1Х2...Хn, где Х1, Х2, ..., Хn могут быть как терминальными, так и нетерминальными символами.

• 
  Слайд 6
  

  6 Пример. Фрагмент синтаксического дерева while (a!=b) if (a>b) a-=b; else b-=a; 

• 
  Слайд 7
  

  7 Методы синтаксического анализа Большинство методов синтаксического анализа делится на два типа: – нисходящие (сверху вниз); – восходящие (снизу вверх). Это связано с порядком, в котором строятся узлы дерева разбора.

• 
  Слайд 8
  

  8 Особенности нисходящих методов разбора – Построение синтаксического дерева начинается от корня по направлению к листьям. – Удобны для "ручного" программирования синтаксического анализатора.

• 
  Слайд 9
  

  9 Особенности восходящих методов разбора – Построение синтаксического дерева начинается от листьев по направлению к дереву. – Могут быть использованы для более широкого класса грамматик и схем трансляции. – Обычно используются при автоматизированном построении трансляторов.

• 
  Слайд 10
  

  10 Общий алгоритм методов нисходящего синтаксического анализа Построение синтаксического дерева начинается с корня, помеченного стартовым нетерминалом, и осуществляется многократным выполнением следующих двух шагов: 1. В узле, помеченном нетерминальным символом А, выбираем одно из порождающих правил для А и строим дочерние узлы для символов из правой части правила. 2. Находим следующий узел, в котором должно быть построено поддерево.

• 
  Слайд 11
  

  11 Основные отличия между методами нисходящего анализа заключаются в том, каким образом происходит выбор порождающего правила и как происходит переход к следующему узлу.

• 
  Слайд 12
  

  12 Метод рекурсивного спуска Анализ методом рекурсивного спуска представляет собой способ нисходящего синтаксического анализа, при котором выполняется ряд рекурсивных процедур для обработки входного потока лексем.

• 
  Слайд 13
  

  13 При выборе порождающего правила для нетерминального символа применяется метод проб и ошибок: 1. делается попытка применить порождающее правило; 2. в случае неуспешной попытки выполняется откат и, затем, переход, к другим порождающим правилам для данного нетерминального символа. Попытка использования порождающего правила считается неуспешной, если после нее невозможно завершить дерево, соответствующее входной последовательности лексем.

• 
  Слайд 14
  

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

• 
  Слайд 15
  

  15 2а) Если правило содержит терминальный символ, то процедура должна убедиться в правильности очередной лексемы. 2б) Если правило содержит нетерминальный символ, то процедура должна обратиться к соответствующим распознающим процедурам для анализа части входной последовательности. 3. В случае успешного окончания работы процедуры текущей становится первая лексема, следующая во входной последовательности за данной конструкцией языка. 4. В случае ошибочного завершения работы процедуры анализа, текущей по прежнему является исходная лексема.

• 
  Слайд 16
  

  16 Пример. Шаблон процедуры синтаксического анализадля нетерминального символа "Оператор" boolean Оператор(Узел) { // попытки применить возможные порождающие правила if ( ПростойОператор(Узел) ) return true; if (СоставнойОператор(Узел) ) return true; if ( УсловныйОператор(Узел) ) return true; if ( ОператорЦиклаСПредусловием(Узел) ) return true; if ( ОператорЦиклаСПостусловием(Узел) ) return true; if ( ОператорЦиклаСПараметром(Узел) ) return true; . . . // ошибочное завершение return false; } Параметр "узел" указывает на текущую вершину, используемую для построения синтаксического дерева

• 
  Слайд 17
  

  17 Пример. Шаблон процедуры синтаксического анализадля нетерминального символа "Условный оператор" boolean УсловныйОператор(Узел) { Позиция = СписокЛексем.ТекущаяПозиция; ТекущийУзел = new УзелУсловныйОператор; if ( СписокЛексем.СледующаяЛексема == ЛЕКСЕМА_IF) if ( СписокЛексем.СледующаяЛексема == ЛЕКСЕМА_( )if ( Условие(ТекущийУзел.Условие) ) if ( СписокЛексем.СледующаяЛексема == ЛЕКСЕМА_) )if ( Оператор(ТекущийУзел.Оператор1) ) { ОператорElse(ТекущийУзел.Оператор2); return true; } // ошибочное завершение Узел = Пусто; СписокЛексем.ТекущаяПозиция = Позиция; return false; }

• 
  Слайд 18
  

  18 Предиктивный анализ Для некоторых грамматик языков программирования допускается построение детерминированных синтаксических анализаторов, использующих метод предиктивного (предсказывающего) анализа. Основное отличие метода предиктивного анализа от метода рекурсивного спуска заключается в том, что на основе анализа нескольких стартовых лексем входной последовательности можно однозначно выбрать порождающее правило грамматики.

• 
  Слайд 19
  

  19 Метод предиктивного анализа допустимо применять для LL(k)-грамматик. LL(k)-грамматикой называется контекстно-свободная грамматика (тип 2), в которой выбор правила в ходе левостороннего вывода однозначно определяется не более чем k очередными символами входной цепочки, считываемой слева направо. Самым удобным для реализации оказываются синтаксические анализаторы, основанные на LL(1)-грамматиках.

• 
  Слайд 20
  

  20 Рассмотрим правило вида A. Определение 1.Множеством FIRST() будем называть множество терминальных символов, которые могут появиться в качестве первого символа последовательностей, полученных из . Если  представляет собой  или может порождать , то  также принадлежит FIRST().

• 
  Слайд 21
  

  21 Определение 2.Множеством FOLLOW(A) будем называть множество терминальных символов, которые могут появиться в непосредственно справа за A в некоторой сентенциальной форме грамматики, т.е. aFOLLOW(A), еслисуществует вывод вида SAa Если A может являться крайним правым символом некоторой сентенциальной формы, то  также принадлежит FOLLOW(A).

• 
  Слайд 22
  

  22 Критерий принадлежности грамматики к классу LL(1)-грамматик Контекстно-свободная грамматика принадлежит к классу LL(1)-грамматик тогда и только тогда, когда для любых правил вида A, A, принадлежащих грамматике, множества FIRST() и FIRST() не имеют общих элементов: FIRST() FIRST() =  и если  FIRST(), то FOLLOW(A) FIRST() = 

• 
  Слайд 23
  

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

• 
  Слайд 24
  

  24 1. Исходя из текущей лексемы принимает решение, какое порождающее правило должно быть использовано. Если сканируемый символ принадлежит множеству FIRST(), применяется правило с правой частью . Правило с  в правой части используется в случае, когда текущий сканируемый символ не принадлежит никакому множеству FIRST() для всех возможных правых частей.

• 
  Слайд 25
  

  25 2. Имитирует правую часть порождающего правила. Каждый нетерминальный символ, содержащийся в правиле, заменяется на вызов процедуры, соответствующей этому нетерминалу. Каждый терминальный символ, содержащийся в правиле, приводит к чтению следующей лексемы из входного потока. Если прочитанная лексема не соответствует терминальному символу, то вызывается процедура обработки ошибки.

• 
  Слайд 26
  

  26 Пример. Синтаксический анализ арифметических выражений Пусть грамматика арифметических выражений описывается следующими правилами: expr term moreterms moreterms '–' expr | '+' expr |  term const | ident

• 
  Слайд 27
  

  27 Процедура анализа нетерминального символа "expr" void expr() { term(); moreterms(); }

• 
  Слайд 28
  

  28 Процедура анализа нетерминального символа "term" void term() { if (currentLexem.type==CONST) { checkLexem(CONST); } else if (currentLexem.type==IDENT) { checkLexem(IDENT); } else { error(); } }

• 
  Слайд 29
  

  29 Процедура анализа нетерминального символа "moreterm" void moreterms() { if (currentLexem.type==OP_ADD) { checkLexem(OP_ADD); expr(); } else if (currentLexem.type==OP_SUB) { checkLexem(OP_SUB); expr(); } else { /* допускается пустая цепочка */ } }

• 
  Слайд 30
  

  30 Процедура проверки типа терминального символа void checkLexem(int type) { if (currentLexem.type==type) { currentLexem=nextLexem(); } else { error(); } }

• 
  Слайд 31
  

  31 Восходящий синтаксический анализ Одним из распространенных алгоритмов восходящего синтаксического анализа является алгоритм «сдвиг – свертка». Основная идея алгоритма заключается в том, что процедура-распознаватель просматривает входную последовательность лексем слева направо и по возможности заменяет некоторую цепочку символов (как терминальных, так и нетерминальных) новым нетерминальным символом в соответствии с порождающими правилами грамматики.

• 
  Слайд 32
  

  32 Процедура замены цепочки символов в соответствии с порождающим правилом носит название «свертка», процедура считывания очередной лексемы – «сдвиг» («перенос»).

• 
  Слайд 33
  

  33 Пример. Анализ выражения b*b–4*a*cв соответствии с грамматикой арифметических выражений: E  E + F | E – F | F * T | F / T | ( E ) | Ident | Const F  F * T | F / T | ( E ) | Ident | Const T  ( E ) | Ident | Const

• 
  Слайд 34
  

  34 сдвиг b Ident свертка (2)F сдвиг b * F * сдвиг b * b F * Ident свертка (3)F * T свертка (1)E сдвиг b * b – E – сдвиг b * b – 4 E – Const свертка (2)E – F сдвиг b * b – 4 * E – F * сдвиг b * b – 4 * aE – F * Ident

• 
  Слайд 35
  

  35 свертка (3) E – F * T свертка (2) E – F сдвиг b * b – 4 * a * E – F* сдвиг b * b – 4 * a * c E – F * Ident свертка (3)E – F * T свертка (2)E – F свертка (1)E

• 
  Слайд 36
  

  36 На каждом шаге работы распознаватель должен решать следующие задачи: 1. Какую процедуру необходимо выполнить: сдвиг или свертку? 2. Если выполнять свертку, то какую цепочку выбрать для поиска правил? (какой длины?) 3. Если существует несколько правил с одинаковой правой частью, то какое из них выбрать? 

• 
  Слайд 37
  

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

• 
  Слайд 38
  

  38 Описание алгоритма «сдвиг–свертка» Входные данные:  = a1a2…ai…aN – входная цепочка терминальных символов (лексем) N – количество лексем Pj, j = 1..M – порождающие правила

• 
  Слайд 39
  

  39 Внутренние переменные idx – индекс текущей лексемы правила стек1 – список, который используется для хранения считанных лексем и заменяющих их нетерминальных символов. стек2 – список, который используется для запоминания примененных правил.

• 
  Слайд 40
  

  40 Начальное состояние idx =0 стек1 – пустой стек2 – пустой

• 
  Слайд 41
  

  41 Функция 1 (сдвиг – возврат) Если idx==N, Если стек1 содержит единственный символ (стартовый символ грамматики), То успешный выход из функции. Иначе прекратить алгоритм, сгенерировать ошибку. Выполнить сдвиг (idx++ , поместить в стек1 лексемуaidx). Вызвать функцию 2. Если успешно, то успешный выход из функции. Реализовать возврат сдвига (извлечь из стека1 лексему, idx––) Выход из функции – неуспешно.

• 
  Слайд 42
  

  42 Функция 2 (свертка – возврат) если idx==Nи стек1 содержит единственную лексему (стартовый символ), то успешный выход из функции. Нц. Цикл по порождающим правилам Pj. Проверить, можно ли выполнить свертку по правилу Pj. Если можно: Выполнить свертку (извлечь нужное количество символов из стека1, занести в стек1 новый нетерминал, в стек2 занести правило Pj). Вызвать функцию 2. Если успешно, то успешный выход из функции. Реализовать возврат свертки (извлечь правило из стека2, извлечь из стека1 нетерминал, вернуть в стек1 правую часть правила). Кц Вызывать функцию 1. Если успешно, то успешный выход из функции. Выход из функции – неуспешный

• 
  Слайд 43
  

  43 Конечное состояние В случае успешного завершения работы алгоритма стек2 – содержит последовательность правил грамматики, необходимых для построения синтаксического дерева анализируемой строки.

• 
  Слайд 44
  

  44 Область применимости алгоритмов типа «сдвиг–свертка» Исходная грамматика – не должна содержать циклов (правил вида AA); – не должна содержать -правил (правил вида A); – желательно отсутствие цепных правил (правил вида AB, где А и В – нетерминальные символы).

• 
  Слайд 45
  

  45 Пример. Исключение из грамматики цепных правил Исходная грамматика арифметических выражений E  E + F | E – F | F F  F * T | F / T | T T  ( E ) | Ident | Const Преобразованная грамматика E  E + F | E – F | F * T | F / T | ( E ) | Ident | Const F  F * T | F / T | ( E ) | Ident | Const T  ( E ) | Ident | Const