- •3. Опорный конспект лекций
- •3.1. Введение, определение языка
- •3.1.1. Элементы теории языка и их грамматика. Символы, цепочки и операции над ними
- •Формальное определение языка
- •3.1.3. Отношения и операции над ними
- •3.1.4. Требования, предъявляемые к грамматикам
- •Способы представления синтаксиса языка. Задание бесконечного текста конечными средствами. Проблема разбора. Классификация языков
- •3.2. Сканеры (лексические анализаторы)
- •3.2.1. Автоматные грамматики и диаграмма состояний
- •Регулярные выражения и конечные автоматы
- •Недетерминированные конечные автоматы
- •3.3. Грамматики простого предшествования
- •3.3.1. Простые предшествования.
- •Отношения предшествования и их вычисление
- •Операторное предшествование
- •Вычисление отношений операторного предшествования. Алгоритм разбора на основе операторного предшествования
- •3.3.5. Предшествование более высокого порядка
- •3.3.6. Способ представления грамматики в оп
- •3.3.7. Предшествование более высокого порядка
- •3.3.8. Ограниченный контекст
- •Определение 1:1 ограниченного контекстного распознавателя
- •Алгоритм 1:1 ограниченного контекстного преобразователя
- •Примеры разбора цепочек по алгоритму 1:1 ограниченного контекстного преобразователя
- •Определение m: n - ограниченного контекста
- •3.4. Автоматы с магазинной памятью, [ мп-автомат ]
- •Операции над магазином:
- •Операции над состоянием:
- •Операции над входной цепочкой:
- •Автомат задаётся:
- •Варианты мп-автоматов (доопределение)
- •Эквивалентность мп-автоматов и кс-грамматик
- •Мп, работающий снизу вверх
- •Формальное определение для левой свертки
- •Восходящий распознаватель
- •Детерминированный мп-автомат
- •Проблема зацикливания
- •3.4.1. Общие методы синтаксического анализа.
- •Вопросы для самопроверки
- •Нисходящий разбор
- •Нисходящий преобразователь (распознаватель)
- •Моделирование мп –преобразователя. Нисходящий анализ с возвратом Синтез процедуры
- •Нисходящий разбор в терминах грамматик
- •Алгоритм нисходящего разбора
- •Пример:
- •Алгоритм восходящего разбора
- •3.4.2. Польская запись, тетрады, триады, деревья.
- •Перевод индексной записи в тетрады
- •3.5. Теория перевода
- •3.5.1. Формализмы определения перевода
- •3.5.2. Синтаксически управляемый перевод
- •3.5.3. Конечные преобразователи. (Простейший транслятор)
- •3.5.4. Преобразователи с магазинной памятью
- •Лабораторная работа №7 Поиск основы в грамматиках простого предшествования
- •5. Контроль знаний
- •Глоссарий
Лабораторная работа №7 Поиск основы в грамматиках простого предшествования
Краткие сведения из теории
При использовании метода «Простого предшествования» в текущей сентенциальной форме осуществляется поиск основы, которая в соответствии с правилами этой грамматики приводится к нетерминальному символу, стоящему в левой части. Будем искать основу сентенциальной формы, двигаясь слева направо и рассматривать одновременно два соседних символа. Пусть имеется цепочка … RS … . Здесь возможны ситуации:
оба символа принадлежат основе (правой части правила)(U: = …RS…)
R≐S (одновременно)
U
… R S …
R принадлежит основе, а S – нет (U:=…WS…; W=>+…R)
R⋗S (R раньше S) U
W
… R S
S принадлежит основе, а R – нет (U: = …RW…; W=>+S…)
R⋖S (R позже S) U
W
R S …
Пример
Имеется грамматика G(Z).
Z: = bMb;
M: = (L|a;
L: = Ma).
Z
b M b
( L
M a )
a
Если между какой-либо парой символов определено более чем одно отношение, использование матрицы невозможно. Если отношение единственно, то можно утверждать, что основой сентенциальной формы S1…Sn является подцепочка Si…Sj, для которой выполнено условие:
…Si-1⋖ Si ≐ Si+1 ≐ … ≐ Sj-1 ≐ Sj ⋗ Sj+1…
Для принятия решения о том, действительно ли рассматриваемая часть сентенциальной формы является основой, используют по одному символу слева и справа от неё. Если S1 – начальный символ основы и вместе с тем первый символ рассматриваемого предложения (сентенциальной формы), то символа S0 не существует. Для фиксации этого факта, заключают предложение между некоторыми символами, не являющимися символами грамматики: Sj ⋗ # или # ⋖ Sj.
Алгоритм
Если грамматика является грамматикой простого предшествования, то
для поиска основы каждой ее сентенции надо просматривать элементы сентенции слева направо и найти самую левую пару символов xj и xj+1, такую что xj .>xj+1.
Окончанием основы сентенции будет xj.
Далее просматривать элементы сентенции справа налево, начиная с символа xj до тех пор, пока не будет найдена самая правая пара символов xi-1 и xi, такая что xi-1 <. xi.
Заголовком основы будет символ xi. Таким образом, будет найдена основа сентенции, имеющая вид xi xi+1…xj-1 xj.
Схема поиска основы сентенции грамматики представлена на рисунке.
На основе отношений предшествования строят матрицу предшествования грамматики. Строки и столбцы матрицы предшествования помечаются символами грамматики. Пустые клетки матрицы указывают на то, что данные символы не связаны отношением предшествования.
5. Контроль знаний
Вопросы:
К теме 3.1.
Дайте определения следующим понятиям: язык, алфавит, грамматика, терминальный символ, нетерминальный символ, начальный символ, цепочка.
Для чего нужен начальный символ?
Что такое формальный и неформальный языки? Для чего нужно формализовать язык?
Что называют сентенциальной формой?
Что такое фраза и простая фраза?
Что называется произведением отношений и транзитивным замыканием?
Какие требования предъявляются к грамматикам?
Что такое синтаксическое дерево? Приведите пример.
Что означает неоднозначность грамматики? Как она проявляется?
Какие алгоритмы разбора синтаксических деревьев вы знаете? В чем они заключаются?
Какие 4 основных класса языков выделил Хомский?
К теме 3.2.
Что такое сканер и синтаксический анализатор?
Что включают в себя символы исходного языка?
Что такое диаграмма состояний и как она строится?
В чем заключается алгоритм распознавания на основе диаграммы состояний?
Что значит детерминированный конечный автомат?
Что значит недетерминированный конечный автомат?
К темам 3.3 - 3.5.
Что такое основа и для чего она нужна?
Какие виды простых предшествований вам известны?
Каким образом осуществляется алгоритм разбора на основе простого предшествования?
Каким образом осуществляется алгоритм разбора на основе операторного предшествования?
Что такое первичные фразы и для чего их используют?
Какие существуют способы представления грамматики в оперативной памяти?
В чем преимущества ограниченного контекстного преобразователя перед техникой предшествования?
Определите основную суть работы по алгоритму 1:1 ограниченного контекстного преобразователя.
Какие элементы входят в таблицу, используемую при разборе цепочек по алгоритму 1:1 ограниченного контекстного преобразователя.
Что используется при составлении таблицы для 1:1 ограниченного контекстного преобразователя.
Какая цепочка считается правильной?
Укажите основное отличие алгоритма 1:1 ограниченного контекстного преобразователя от m:n контекстного преобразователя.
Что такое стратификация?
Что называется основой сентенциальной формы в грамматике предшествования более высокого порядка.
Что такое грамматика n:m предшествования?
Опишите алгоритм разбора по грамматике n:m предшествования.
Дайте определение левой свертки.
В чем заключается работа восходящего распознавателя?
Какой автомат называется детерминированным (недетерминированным)?
При каких условиях конфигурация автомата называется зацикливающейся?
21.LL(k)-грамматики. Предсказывающие алгоритмы разбора.