фазой в работе любого транслятора.
Синтаксический анализ преследует две цели:
– определить
принадлежность цепочки символов языку;– выявить структуру этой цепочки.
- Главная
- Разное
- Бизнес и предпринимательство
- Образование
- Развлечения
- Государство
- Спорт
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Религиоведение
- Черчение
- Физкультура
- ИЗО
- Психология
- Социология
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Что такое findslide.org?
FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Обратная связь
Email: Нажмите что бы посмотреть
Презентация на тему Синтаксическийанализ
Содержание
- 2. Синтаксический анализ Синтаксический анализ (распознавание, разбор, parsing) является
- 3. Синтаксический анализ Структуру цепочки обычно представляют с помощью
- 4. Синтаксический анализ Успешное восстановление дерева вывода для заданной
- 5. Синтаксический анализСвойства синтаксического дерева– Корень дерева помечен стартовым
- 6. Синтаксический анализПример. Фрагмент синтаксического дереваwhile (a!=b) if (a>b) a-=b; else b-=a;
- 7. Синтаксический анализМетоды синтаксического анализа Большинство методов синтаксического анализа
- 8. Синтаксический анализ Особенности нисходящих методов разбора– Построение синтаксического дерева
- 9. Синтаксический анализ Особенности восходящих методов разбора– Построение синтаксического дерева
- 10. Синтаксический анализ Общий алгоритм методов нисходящего синтаксического анализа Построение
- 11. Синтаксический анализ Основные отличия между методами нисходящего анализа
- 12. Синтаксический анализМетод рекурсивного спуска Анализ методом рекурсивного спуска
- 13. Синтаксический анализ При выборе порождающего правила для нетерминального
- 14. Синтаксический анализ Для каждого нетерминального символа грамматики записывается
- 15. Синтаксический анализ 2а) Если правило содержит терминальный символ, то
- 16. Синтаксический анализПример. Шаблон процедуры синтаксического анализа для
- 17. Синтаксический анализПример. Шаблон процедуры синтаксического анализа для
- 18. Синтаксический анализПредиктивный анализ Для некоторых грамматик языков программирования
- 19. Синтаксический анализ Метод предиктивного анализа допустимо применять для
- 20. Синтаксический анализ Рассмотрим правило вида A.Определение 1. Множеством
- 21. Синтаксический анализОпределение 2. Множеством FOLLOW(A) будем называть
- 22. Синтаксический анализ Критерий принадлежности грамматики к классу LL(1)-грамматик Контекстно-свободная
- 23. Синтаксический анализСтруктура предиктивного анализатора Предиктивный анализатор содержит набор
- 24. Синтаксический анализ1. Исходя из текущей лексемы принимает решение,
- 25. Синтаксический анализ2. Имитирует правую часть порождающего правила. Каждый нетерминальный
- 26. Синтаксический анализПример. Синтаксический анализ арифметических выражений Пусть грамматика
- 27. Синтаксический анализПроцедура анализа нетерминального символа "expr" void expr() { term(); moreterms(); }
- 28. Синтаксический анализПроцедура анализа нетерминального символа "term" void term() { if (currentLexem.type==CONST) { checkLexem(CONST); } else if (currentLexem.type==IDENT) { checkLexem(IDENT); } else { error(); } }
- 29. Синтаксический анализПроцедура анализа нетерминального символа "moreterm" void moreterms()
- 30. Синтаксический анализПроцедура проверки типа терминального символа void checkLexem(int type) { if (currentLexem.type==type) { currentLexem=nextLexem(); } else { error(); } }
- 31. Синтаксический анализВосходящий синтаксический анализ Одним из распространенных алгоритмов
- 32. Синтаксический анализ Процедура замены цепочки символов в соответствии
- 33. Синтаксический анализПример. Анализ выражения b*b–4*a*c в соответствии
- 34. Синтаксический анализ сдвиг b Ident свертка (2) F сдвиг b * F * сдвиг b * b F
- 35. Синтаксический анализ свертка (3) E – F * T свертка
- 36. Синтаксический анализ На каждом шаге работы распознаватель должен
- 37. Синтаксический анализ Поскольку каждая из этих задач имеет
- 38. Синтаксический анализОписание алгоритма «сдвиг–свертка» Входные данные: = a1
- 39. Синтаксический анализВнутренние переменные idx – индекс текущей лексемы
- 40. Синтаксический анализНачальное состояние idx = 0 стек1 – пустой стек2 – пустой
- 41. Синтаксический анализФункция 1 (сдвиг – возврат)Если idx==N,
- 42. Синтаксический анализФункция 2 (свертка – возврат)если idx==N
- 43. Синтаксический анализКонечное состояние В случае успешного завершения работы
- 44. Синтаксический анализОбласть применимости алгоритмов типа «сдвиг–свертка» Исходная грамматика
- 45. Скачать презентацию
- 46. Похожие презентации
Синтаксический анализ Синтаксический анализ (распознавание, разбор, parsing) является обязательной фазой в работе любого транслятора. Синтаксический анализ преследует две цели:– определить принадлежность цепочки символов языку;– выявить структуру этой цепочки.
Слайд 2
Синтаксический анализ
Синтаксический анализ (распознавание, разбор, parsing) является обязательной
фазой в работе любого транслятора.
принадлежность цепочки символов языку;– выявить структуру этой цепочки.
Слайд 3
Синтаксический анализ
Структуру цепочки обычно представляют с помощью графа,
называемого синтаксическим деревом (деревом вывода, деревом разбора).
Термин дерево вывода
указывает на то, что данный граф отображает последовательность вывода цепочки символов из начального символа грамматики.Термин дерево разбора указывает на то, что данное дерево строится в процессе анализа (разбора) заранее заданной цепочки.
Слайд 4
Синтаксический анализ
Успешное восстановление дерева вывода для заданной цепочки
означает, что цепочка есть правильное предложение языка, порождаемого некоторой
грамматикой.Наоборот, если для некоторой цепочки символов дерево вывода построить невозможно, это значит, что цепочка не принадлежит языку, порождаемому грамматикой.
Слайд 5
Синтаксический анализ
Свойства синтаксического дерева
– Корень дерева помечен стартовым символом
грамматики.
– Каждый лист дерева помечен терминальным символом или .
– Каждый внутренний
узел помечен нетерминальным символом.– Если нетерминальный символ A помечает некоторый внутренний узел, и его дочерние узлы имеют метки Х1, Х2, ..., Хn, то грамматика содержит правило вида А Х1Х2...Хn, где Х1, Х2, ..., Хn могут быть как терминальными, так и нетерминальными символами.
Слайд 6
Синтаксический анализ
Пример. Фрагмент синтаксического дерева
while (a!=b) if (a>b)
a-=b; else b-=a;
Слайд 7
Синтаксический анализ
Методы синтаксического анализа
Большинство методов синтаксического анализа делится
на два типа:
– нисходящие (сверху вниз);
– восходящие (снизу вверх).
Это связано с
порядком, в котором строятся узлы дерева разбора.
Слайд 8
Синтаксический анализ
Особенности нисходящих методов разбора
– Построение синтаксического дерева начинается
от корня по направлению к листьям.
– Удобны для "ручного" программирования
синтаксического анализатора.
Слайд 9
Синтаксический анализ
Особенности восходящих методов разбора
– Построение синтаксического дерева начинается
от листьев по направлению к дереву.
– Могут быть использованы для
более широкого класса грамматик и схем трансляции. – Обычно используются при автоматизированном построении трансляторов.
Слайд 10
Синтаксический анализ
Общий алгоритм методов нисходящего синтаксического анализа
Построение синтаксического
дерева начинается с корня, помеченного стартовым нетерминалом, и осуществляется
многократным выполнением следующих двух шагов:1. В узле, помеченном нетерминальным символом А, выбираем одно из порождающих правил для А и строим дочерние узлы для символов из правой части правила.
2. Находим следующий узел, в котором должно быть построено поддерево.
Слайд 11
Синтаксический анализ
Основные отличия между методами нисходящего анализа заключаются
в том, каким образом происходит выбор порождающего правила и
как происходит переход к следующему узлу.
Слайд 12
Синтаксический анализ
Метод рекурсивного спуска
Анализ методом рекурсивного спуска представляет
собой способ нисходящего синтаксического анализа, при котором выполняется ряд
рекурсивных процедур для обработки входного потока лексем.
Слайд 13
Синтаксический анализ
При выборе порождающего правила для нетерминального символа
применяется метод проб и ошибок:
1. делается попытка применить порождающее
правило;2. в случае неуспешной попытки выполняется откат и, затем, переход, к другим порождающим правилам для данного нетерминального символа.
Попытка использования порождающего правила считается неуспешной, если после нее невозможно завершить дерево, соответствующее входной последовательности лексем.
Слайд 14
Синтаксический анализ
Для каждого нетерминального символа грамматики записывается отдельная
распознающая процедура.
При этом анализ входной последовательности лексем осуществляется
по следующему алгоритму:1. Перед началом работы процедуры текущей является первая лексема анализируемой конструкции языка.
2. В процессе работы распознающая процедура считывает все лексемы, относящиеся к данной конструкции.
Слайд 15
Синтаксический анализ
2а) Если правило содержит терминальный символ,
то процедура должна
убедиться в правильности
очередной лексемы.
2б) Если правило содержит нетерминальный символ,
то процедура
должна обратиться к соответствующим
распознающим процедурам для анализа части
входной последовательности. 3. В случае успешного окончания работы процедуры текущей становится первая лексема, следующая во входной последовательности за данной конструкцией языка.
4. В случае ошибочного завершения работы процедуры анализа, текущей по прежнему является исходная лексема.
Слайд 16
Синтаксический анализ
Пример. Шаблон процедуры синтаксического анализа для нетерминального
символа "Оператор"
boolean Оператор(Узел) {
// попытки применить возможные порождающие правила
if
( ПростойОператор(Узел) ) return true;if ( СоставнойОператор(Узел) ) return true;
if ( УсловныйОператор(Узел) ) return true;
if ( ОператорЦиклаСПредусловием(Узел) ) return true;
if ( ОператорЦиклаСПостусловием(Узел) ) return true;
if ( ОператорЦиклаСПараметром(Узел) ) return true;
. . .
// ошибочное завершение
return false;
}
Параметр "узел" указывает на текущую вершину, используемую для построения синтаксического дерева
Слайд 17
Синтаксический анализ
Пример. Шаблон процедуры синтаксического анализа для нетерминального
символа "Условный оператор"
boolean УсловныйОператор(Узел) {
Позиция = СписокЛексем.ТекущаяПозиция;
ТекущийУзел = new
УзелУсловныйОператор;if ( СписокЛексем.СледующаяЛексема == ЛЕКСЕМА_IF )
if ( СписокЛексем.СледующаяЛексема == ЛЕКСЕМА_( ) if ( Условие(ТекущийУзел.Условие) )
if ( СписокЛексем.СледующаяЛексема == ЛЕКСЕМА_) ) if ( Оператор(ТекущийУзел.Оператор1) ) {
ОператорElse(ТекущийУзел.Оператор2);
return true;
}
// ошибочное завершение
Узел = Пусто;
СписокЛексем.ТекущаяПозиция = Позиция;
return false;
}
Слайд 18
Синтаксический анализ
Предиктивный анализ
Для некоторых грамматик языков программирования допускается
построение детерминированных синтаксических анализаторов, использующих метод предиктивного (предсказывающего) анализа.
Основное
отличие метода предиктивного анализа от метода рекурсивного спуска заключается в том, что на основе анализа нескольких стартовых лексем входной последовательности можно однозначно выбрать порождающее правило грамматики.
Слайд 19
Синтаксический анализ
Метод предиктивного анализа допустимо применять для LL(k)-грамматик.
LL(k)-грамматикой
называется контекстно-свободная грамматика (тип 2), в которой выбор правила
в ходе левостороннего вывода однозначно определяется не более чем k очередными символами входной цепочки, считываемой слева направо.Самым удобным для реализации оказываются синтаксические анализаторы, основанные на LL(1)-грамматиках.
Слайд 20
Синтаксический анализ
Рассмотрим правило вида A.
Определение 1.
Множеством FIRST() будем
называть множество терминальных символов, которые могут появиться в качестве
первого символа последовательностей, полученных из .Если представляет собой или может порождать , то также принадлежит FIRST().
Слайд 21
Синтаксический анализ
Определение 2.
Множеством FOLLOW(A) будем называть множество терминальных
символов, которые могут появиться в непосредственно справа за A
в некоторой сентенциальной форме грамматики, т.е. aFOLLOW(A), если существует вывод видаSAa
Если A может являться крайним правым символом некоторой сентенциальной формы, то также принадлежит FOLLOW(A).
Слайд 22
Синтаксический анализ
Критерий принадлежности грамматики к классу LL(1)-грамматик
Контекстно-свободная грамматика
принадлежит к классу LL(1)-грамматик тогда и только тогда, когда
для любых правил вида A, A, принадлежащих грамматике, множества FIRST() и FIRST() не имеют общих элементов:FIRST() FIRST() =
и если FIRST(), то
FOLLOW(A) FIRST() =
Слайд 23
Синтаксический анализ
Структура предиктивного анализатора
Предиктивный анализатор содержит набор процедур,
соответствующих каждому анализируемому нетерминальному символу. Каждая такая процедура решает
две задачи.
Слайд 24
Синтаксический анализ
1. Исходя из текущей лексемы принимает решение, какое
порождающее правило должно быть использовано.
Если сканируемый символ принадлежит множеству
FIRST(), применяется правило с правой частью . Правило с в правой части используется в случае, когда текущий сканируемый символ не принадлежит никакому множеству FIRST() для всех возможных правых частей.
Слайд 25
Синтаксический анализ
2. Имитирует правую часть порождающего правила.
Каждый нетерминальный символ,
содержащийся в правиле, заменяется на вызов процедуры, соответствующей этому
нетерминалу.Каждый терминальный символ, содержащийся в правиле, приводит к чтению следующей лексемы из входного потока. Если прочитанная лексема не соответствует терминальному символу, то вызывается процедура обработки ошибки.
Слайд 26
Синтаксический анализ
Пример. Синтаксический анализ арифметических выражений
Пусть грамматика арифметических
выражений описывается следующими правилами:
expr term moreterms
moreterms '–'
expr | '+' expr | term const | ident
Слайд 27
Синтаксический анализ
Процедура анализа нетерминального символа "expr"
void expr() {
term();
moreterms();
}
Слайд 28
Синтаксический анализ
Процедура анализа нетерминального символа "term"
void term() {
if
(currentLexem.type==CONST) {
checkLexem(CONST);
} else
if (currentLexem.type==IDENT) {
checkLexem(IDENT);
} else {
error();
}
}
Слайд 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
Синтаксический анализ
Процедура проверки типа терминального символа
void checkLexem(int type)
{
if (currentLexem.type==type) {
currentLexem=nextLexem();
} else {
error();
}
}
Слайд 31
Синтаксический анализ
Восходящий синтаксический анализ
Одним из распространенных алгоритмов восходящего
синтаксического анализа является алгоритм «сдвиг – свертка».
Основная идея алгоритма
заключается в том, что процедура-распознаватель просматривает входную последовательность лексем слева направо и по возможности заменяет некоторую цепочку символов (как терминальных, так и нетерминальных) новым нетерминальным символом в соответствии с порождающими правилами грамматики.
Слайд 32
Синтаксический анализ
Процедура замены цепочки символов в соответствии с
порождающим правилом носит название «свертка», процедура считывания очередной лексемы
– «сдвиг» («перенос»).
Слайд 33
Синтаксический анализ
Пример. Анализ выражения b*b–4*a*c в соответствии с
грамматикой арифметических выражений:
E E + F | E
– F | F * T | F / T | ( E ) | Ident | ConstF F * T | F / T | ( E ) | Ident | Const
T ( E ) | Ident | Const
Слайд 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 * a E – F * Ident
Слайд 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
Синтаксический анализ
На каждом шаге работы распознаватель должен решать
следующие задачи:
1. Какую процедуру необходимо выполнить: сдвиг или свертку?
2.
Если выполнять свертку, то какую цепочку выбрать для поиска правил? (какой длины?)3. Если существует несколько правил с одинаковой правой частью, то какое из них выбрать?
Слайд 37
Синтаксический анализ
Поскольку каждая из этих задач имеет неоднозначное
решение, то при реализации алгоритма на каждом шаге запоминаются
все предпринятые действия, для того чтобы иметь возможность вернуться назад и выполнить все действия по другому. Этот процесс повторяется до тех пор, пока не будут перебраны все возможные варианты.
Слайд 38
Синтаксический анализ
Описание алгоритма «сдвиг–свертка»
Входные данные:
= a1 a2
… ai … aN – входная цепочка терминальных символов
(лексем)N – количество лексем
Pj, j = 1..M – порождающие правила
Слайд 39
Синтаксический анализ
Внутренние переменные
idx – индекс текущей лексемы правила
стек1
– список, который используется для хранения считанных лексем и
заменяющих их нетерминальных символов.стек2 – список, который используется для запоминания примененных правил.
Слайд 41
Синтаксический анализ
Функция 1 (сдвиг – возврат)
Если idx==N,
Если
стек1 содержит единственный символ (стартовый символ грамматики), То успешный
выход из функции.Иначе прекратить алгоритм, сгенерировать ошибку.
Выполнить сдвиг (idx++ , поместить в стек1 лексему aidx).
Вызвать функцию 2. Если успешно, то успешный выход из функции.
Реализовать возврат сдвига (извлечь из стека1 лексему, idx – –)
Выход из функции – неуспешно.
Слайд 42
Синтаксический анализ
Функция 2 (свертка – возврат)
если idx==N и
стек1 содержит единственную лексему (стартовый символ), то успешный выход
из функции.Нц. Цикл по порождающим правилам Pj.
Проверить, можно ли выполнить свертку по правилу Pj.
Если можно:
Выполнить свертку (извлечь нужное количество символов из стека1, занести в стек1 новый нетерминал, в стек2 занести правило Pj).
Вызвать функцию 2. Если успешно, то успешный выход из функции.
Реализовать возврат свертки (извлечь правило из стека2, извлечь из стека1 нетерминал, вернуть в стек1 правую часть правила).
Кц
Вызывать функцию 1. Если успешно, то успешный выход из функции.
Выход из функции – неуспешный
Слайд 43
Синтаксический анализ
Конечное состояние
В случае успешного завершения работы алгоритма
стек2 – содержит последовательность правил грамматики, необходимых для построения
синтаксического дерева анализируемой строки.
Слайд 44
Синтаксический анализ
Область применимости алгоритмов типа «сдвиг–свертка»
Исходная грамматика
– не
должна содержать циклов (правил вида AA);
– не должна содержать -правил
(правил вида A); – желательно отсутствие цепных правил (правил вида AB, где А и В – нетерминальные символы).
