- •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. Контроль знаний
- •Глоссарий
3. Опорный конспект лекций
3.1. Введение, определение языка
Современный этап развития общества характеризуется возрастающей ролью информационной сферы, представляющей собой совокупность информации, информационной инфраструктуры, субъектов, осуществляющих сбор, формирование, распространение и использование информации, а также системы регулирования возникающих при этом общественных отношений. Методы и средства, используемые при синтезе процедур преобразования информации, возникающих в процессе взаимодействия перечисленных выше структур, получили название информационные технологии. Слово информация своими корнями уходит в древнюю Грецию и означает объясняю, излагаю, слово технология оттуда же и означает искусство, мастерство, умение, т.е. умение описать сущности окружающей действительности и их предикаты. Решение этой проблемы как в те далекие времена, так и по сей день осуществляется с помощью звуковых или символьных средств. Теперь можно сформулировать понятие “язык” как стихийно возникшую систему звуков, а затем и символов (письменность). Последовательность дискретных звуков (цепочка символов) определяют некоторую сущность действительного мира и отношений между субъектами. Автоматизация, поглотившая человечество во всех сферах его деятельности не обошла и информационные процессы, являющиеся фундаментом жизнедеятельности человека. На сегодняшний день в качестве абонентов, взаимодействующих друг с другом, рассматривают не только биологические субъекты, а также компоненты технической системы, реализующие ее функциональное назначение, т.е. субъекты живой и неживой природы. Эти системы могут излагать свое состояние на разных языках, т.е. алфавит и правила построения цепочек языка различны. Вычислительная машина излагает свое состояние в бинарном алфавите, чтобы понять ее необходимо выполнить перевод с машинного языка на язык другого абонента, причем этот перевод должен быть однозначен. Естественный язык не однозначен, т.е. возникает необходимость в построении формального языка однозначно определяющего состояние каждого абонента.
Все мы с детства привыкли использовать язык для передачи информации другим людям. Мы говорим какую-либо фразу, например «Красивый дом стоит у берега моря» и уверенны, что наш собеседник нас понимает. Если же мы скажем: «Моря у дом красивый стоит берега», то вряд ли нас кто-нибудь поймет, хотя мы использовали те же самые слова, что и в первом предложении. Мы не задумываемся над тем, каким образом наш мозг провел разбор данного предложения и заключил, что оно правильное и несет некий смысл или неправильное и никакого смысла не несет. А если подумать над
этой проблемой, то можно представить следующую схему разбора этого предложения:
Итак: Красивый дом стоит у берега моря.
Выполним его разбор.
Необходима некоторая система правил построения предложения, которая могла бы однозначно определить местоположение того или иного слова в предложении.
<предложение> := <подлежащее> <сказуемое> ;
<подлежащее> := <определение> <существительное> ← нетерминальные символы;
<сказуемое> := <глагол> <дополнение>;
<глагол> := стоит ← терминальные символы;
<дополнение> := у берега моря;
<существительное> := дом;
<определение> := красивый.
Наиболее распространенным способом формального описания синтаксиса языков программирования являются нормальные формы Бэкуса-Наура (БНФ). Синтаксис задается с помощью формул
<Идентификатор>::=<Буква>|< Идентификатор >< Буква >|<Идентификатор><Цифра>.
Последовательности знаков, заключенные в скобки <>, представляют собой переменные, значениями которых являются последовательности символов, знаки := и | (последний со значением “ИЛИ”) – это связки. Любой знак, который не является переменной или связкой, обозначает самого себя (и класс знаков, ему подобных). Соединение знаков И (ИЛИ), переменных в формуле, означает соединение обозначаемых последовательностей. Таким образом, вышеприведенная формула задает рекурсивное правило для образования имен из букв и цифр.
Любой язык (русский, английский, французский и т.д.) включает в себя алфавит и систему правил построения предложений, а вообще язык можно определить как систему дискретных звуков, необходимых для описания внешнего мира. Предложения языка записываются в виде последовательности символов из некоторого алфавита. Такие символы будем называть терминальными символами или терминалами, а последовательности терминалов – терминальными цепочками. Но для того, чтобы компьютер правильно сделал разбор предложения, оказалось недостаточно этих двух понятий – терминал и система правил. Поэтому были введены еще два понятия: начальный символ и нетерминальный символ или нетерминал.
Если терминальные символы – символы, из которых нет дальнейшего вывода, то нетерминальные символы – символы, из которых возможен дальнейший вывод цепочки.
Начальный символ – общая запись всех возможных конструкций языка, построенных из элементов данного алфавита по определенным правилам, образующим систему правил; т.е. начальным символом может быть предложение, слово, число и т.д.
Для чего нужен начальный символ? С него начинается построение синтаксического дерева, т.е. в вышерассмотренном примере <предложение> и будет являться начальным символом. Существует два варианта разбора синтаксических деревьев: сверху вниз и снизу вверх. При разборе сверху вниз мы получим множество конструкций, каждую из которых нужно будет сравнить с введенной, и если ни одна из полученных конструкций не совпадет с введенной, то можно утверждать, что введена неправильная конструкция. Это очень долгий и трудоемкий вариант. При разборе снизу вверх мы введенную конструкцию преобразуем согласно правилам, т.е. отыскиваем правые части правил и заменяем их левыми частями, в результате чего мы должны получить начальный символ, если по окончании разбора начальный символ не получен, то можно сделать вывод, что введена неправильная конструкция.
Учитывая вышеизложенное, вычислительную среду формально можно представить в виде следующих правил:
<ВС>:=<АС><ПС>, <ПС>:=<ОС><ПИ>, где
ВС - вычислительная среда, ас - аппаратные средства;
пс - программные средства; ос - операционная система;
пи - программный интерфейс;
«: =» - «это есть» по определению.