Понятие о формальных системах
Построение и описание языков, использование рекурсии. Пример грамматики, определяющей натуральные числа и целое вещественное тело. Достоинства и недостатки формы метаязыка Бекуса-Наура, разработанного для Алгола. Классификация грамматик по Хомскому.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 08.09.2013 |
| Размер файла | 22,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Лекция
Понятие о формальных системах
1. Основы описания языков
Для построения языка достаточно задать его грамматику.
Алфавит - конечное множество символов применяются в языке
{`A'-`Z', `a'-`z', `0'-`9'}
предложение или цепочка над словарем V-последовательность символов принадлежащих. VЄ(0,1)
Обозначим через V(*) все возможные цепочки над словарем V (имеющих смысл)
Язык L над словарем V-это подмножество из V(*).
Для построения языка используются правила МЕТАЯЗЫКА:
правила подстановки или продукции называется упорядоченная пара (U,X), которая обычно записывается U>X где U-символ, X-непустая цепочка символов. Обозначим продукцию через Р.
Пример грамматики, определяющей натуральные числа.
V={`0','1','2','3','4','5','6','7','8','9',<число>, <чс>,<цифра>}
1)<число>><чс>
2)<чс>><цифра>
3)<чс>><чс><цифра>
4)<цифра>>1
...
13)<цифра>>9
Символы, встречающиеся в левой части правил (И) называется нетерминальным или синтаксическими конструкциями.
Обозначим множества этих символов через N.
Символы, которые не могут быть разделены на более мелкие называются терминальными.
Обозначим множества Т.
N={<число>,<чс>,<цифра>}
Т={`0','1',...,'9'}
Терминальные символы никогда не находится в левой части
V=NхT
Существуют еще начальный или сентенциальный символ S, который обязательно присутствует в левой части хотя бы одного правила и задает начало разбора SЄN
Грамматика - совокупность объектов G=(N,T,S,P) продукции могут использовать рекурсию.
Рекурсия позволяет порождать бесконечное множество объектов при помощи правила.
2. Примеры форм представления грамматики
На практике в качестве метаязыков используются много форм. Большое распределение получила форма Бекуса-Наура -БНФ. Разработана 1959-1961 г. при создании языка АЛГОЛ. Нетерминальные символы даны в <>. Левая и правая части продукции отделяются знаком ::=. Различные варианты подстановок записываются в одном правиле и отделяются, друг от друга отделяются чертой |.
<число>::=<чс>
<чс>::=<цифра>|<чс><цифра>
3. <>::='0'|'1'|'2'|...|'9'
Т. образом вместо 13 продукции БНФ имеет всего 3.
Достоинства: а) простота б) сравнительно компактная запись продукции.
Недостатки: рекурсивные определения повторов, необходимость определений альтернативность (факультативная возможность - элемент, который может отсутствовать.)
Для исправления недостатков была разработана расширенная БНФ (РБНФ).
Рассмотрим пример определения целого вещественного тела.
БНФ.
<цепочка_цифр>::=<цифра>|<цепочка_цифр>
<знак>::=+|-
<число_без_знака>::=<цепочка_цифр>|<цепочка_цифр>.
<число>::=<число_без_знака>|<знак><число_без_знака>
РБНФ.
цепочка_цифр=цифра{цифра}
число_без_знака=цепочка_цифр[`.']
число=число_без_знака|(`+'|'-')число_без_знака
Отличие: нетерминальные символы не заключаются в <>, а терминальные берутся в `'. Для обозначения повторов используются {}. Варианты обозначения |, а факультативные возможности [].
Для данного примера РБНФ позволяет записать:
Число=[(`+'|'-`)]цифра{цифра}[`.']
3. Классификация грамматик по Хомскому
метаязык грамматика рекурсия
Предложим 4-е класса грамматик в зависимости от способа задания продукций.
1) регулярная грамматика
А>ВС
А>С
А,В N, СT
Эта грамматика, ею удобно пользоваться для теоретического описания лексического анализа транслятора. По Хомскому это 3-ий класс, самый строгий.
2) контекстно-свободная
A>
А N, N и T
Удобно использовать при описании трансляторов языков программирования. По Хомскому это 2-ой класс.
3) контекстно-зависимая
X
, X и T
По Хомскому это 1-ый класс.
4) Грамматика без ограничений описывает естественные языки (нет ограничений на продукции). Это класс 0.
Размещено на Allbest.ru
...Подобные документы
Применение правил грамматики. Синтаксический анализатор, нис- и восходящий разбор, полный перебор правил подстановки. Классификация грамматик по Хомскому. Определение языков с помощью автоматов. Форма Бекуса-Наура описания синтаксиса формальных языков.
лекция [270,1 K], добавлен 19.10.2014Особенности и суть языков программирования, способы их задания, цепочки символов и операции над ними. Классификация языков и грамматик, форма Бэкуса-Наура. Определение и свойства регулярных выражений, конечные автоматы и грамматики, описание программы.
курсовая работа [231,5 K], добавлен 23.06.2011Основные понятия теории грамматик простого и операторного предшествования, алгоритмы синтаксического разбора предложения для классов КС-грамматик; разработка дерева вывода для грамматики входного языка в форме Бэкуса-Наура с указанием шагов построения.
лабораторная работа [28,0 K], добавлен 24.07.2012История разработки языка программирования Си. Программа на Си как одна или несколько единиц компиляции (файлов), стадии работы компилятора. Идентификаторы и ключевые слова, типы констант. Форма Бекуса-Наура описания синтаксиса формальных языков.
презентация [257,7 K], добавлен 05.01.2014Теоретические и практические основы грамматик, теория конечных автоматов-распознавателей. Эквивалентные и недостижимые состояния конечных автоматов. Классификация грамматик и порождаемых ими языков. Разработка программного комплекса построения грамматик.
курсовая работа [654,2 K], добавлен 14.11.2010Роль информационных технологий в быту. Теоретические аспекты формальных грамматик и их преобразование, алфавит нетерминалов. Распознаватель для преобразованной грамматики и реализация его в виде программы для проверки текстовых файлов и вводимых цепочек.
курсовая работа [129,4 K], добавлен 15.06.2009Определение и примеры формальной системы. Понятия языка и метаязыка. Интерпретация формальной теории. Понятие изоморфизма в терминах теории формальных систем. Примеры продукционных правил, теория чисел. Исчисление предикатов первого и второго порядка.
лекция [201,4 K], добавлен 19.12.2013Анализ возможностей платформы. Классификация грамматик по Хомскому. Способы задания языков. Разработка алгоритмов выполнения файловых операций на основе спроектированных интерфейсов. Криптосистема с открытым ключом. Свойства электронной цифровой подписи.
дипломная работа [3,6 M], добавлен 24.07.2014Использование рекурсии в предметных областях. Рекурсивные процедуры и функции в программировании. Создание алгоритмов для рисования графических изображений с использованием рекурсии в среде программирования Pascal ABC. Примеры рекурсии в графике.
творческая работа [6,7 M], добавлен 01.02.2014Основные методы описания синтаксиса языков программирования: формальные грамматики, формы Бэкуса-Наура и диаграммы Вирта. Разработка алгоритма решения задачи. Лексический и синтаксический анализатор, семантический анализ. Структурная организация данных.
курсовая работа [680,1 K], добавлен 12.06.2011Разработка формальной грамматики для выражений, содержащих: логические и арифметические операции, константы, идентификаторы, знаки отношений и т.д., ее отладка в соответствии с требованиями метода параллельного предшествования. Разработка сканера.
контрольная работа [45,8 K], добавлен 24.09.2010Организация вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе. Способы программирования алгоритмов с использованием рекурсии. Преимущества и недостатки использования рекурсии.
лабораторная работа [27,8 K], добавлен 28.05.2012Обратная трассировка лучей: ограничения при реализации, достоинства и недостатки. Математические и физические предпосылки алгоритма, блок-схема. Выбор языка программирования. Зависимость времени генерации от глубины рекурсии, количества источников.
курсовая работа [503,0 K], добавлен 27.05.2013Разработка программы для осуществления приведения КС-грамматики к нормальному виду. Особенности преобразования грамматик. Создание алгоритма удаления бесплодных и недостижимых символов, устранения правил с пустой правой частью. Исключение цепных правил.
курсовая работа [1,5 M], добавлен 06.01.2012Построение праволинейной грамматики, автоматной грамматики по полученным результатам. Построение недетерминированного конечного автомата. Сведение недетерминированного конечного автомата к детерминированному. Описание программы и контрольного примера.
курсовая работа [674,9 K], добавлен 13.06.2012Применение грамматических правил на языке Prolog. Использование грамматики для формирования лингвистической информации. Классификация грамматических формальных систем по их порождающей способности. Преобразование правил DCG интерпретатором Prolog.
презентация [72,5 K], добавлен 17.10.2013Исследование понятия рекурсии в программировании. Описание метода, который позволяет разбить задачу на части все меньшего и меньшего размера. Изучение схемы работы рекурсивной процедуры. Способы изображения древовидных структур. Избавление от рекурсии.
презентация [486,1 K], добавлен 22.10.2013Описание синтаксиса и семантики входного языка. Описание типов лексем, определение их синтаксиса. Построение диаграммы лексического анализатора, а также его таблицы, тестирование. Построение КС-грамматики входного языка. Описание промежуточного языка.
курсовая работа [83,0 K], добавлен 23.01.2014Способы применения нейронных сетей для решения различных математических и логических задач. Принципы архитектуры их построения и цели работы программных комплексов. Основные достоинства и недостатки каждой из них. Пример рекуррентной сети Элмана.
курсовая работа [377,4 K], добавлен 26.02.2015Понятие и сущность виртуальных частных сетей (VPN) и история их появления. Принцип работы и общее описание технологии VPN, основы туннелирования. Протоколы управления, их виды и использование. Достоинства, недостатки и перспективы развития сетей VPN.
курсовая работа [986,9 K], добавлен 26.08.2010
