Понятие о формальных системах
Основы описания языков программирования при помощи грамматики. Синтаксические конструкции. Формы представления грамматики. Описание формы Бекуса-Наура, достоинства и недостатки. Классификация грамматик по Хомскому как трансляторов языков программирования.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 09.10.2013 |
| Размер файла | 24,0 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История разработки языка программирования Си. Программа на Си как одна или несколько единиц компиляции (файлов), стадии работы компилятора. Идентификаторы и ключевые слова, типы констант. Форма Бекуса-Наура описания синтаксиса формальных языков.
презентация [257,7 K], добавлен 05.01.2014Основные методы описания синтаксиса языков программирования: формальные грамматики, формы Бэкуса-Наура и диаграммы Вирта. Разработка алгоритма решения задачи. Лексический и синтаксический анализатор, семантический анализ. Структурная организация данных.
курсовая работа [680,1 K], добавлен 12.06.2011Система дистанционного обучения Distance Learning Belarus и лабораторный практикум курса "Разработка трансляторов для языков программирования", его перенос в интерактивную среду обучения. Описание работы программы и её взаимодействия с пользователями.
курсовая работа [588,5 K], добавлен 03.11.2012Теоретические и практические основы грамматик, теория конечных автоматов-распознавателей. Эквивалентные и недостижимые состояния конечных автоматов. Классификация грамматик и порождаемых ими языков. Разработка программного комплекса построения грамматик.
курсовая работа [654,2 K], добавлен 14.11.2010Основные концепции языков программирования, механизмы типизации данных. Описание языков программирования и методов трансляции. Конечные автоматы и преобразователи. Общие методы синтаксического анализа. Формальные методы описания языкового перевода.
курс лекций [5,5 M], добавлен 04.12.2013Классификация языков программирования. Использование циклических конструкций и выполнение итерационных процессов. Алгоритмические структуры циклов языков C, C++, Java, C#. Особенности современных языков программирования высокого уровня и их применение.
курсовая работа [345,6 K], добавлен 13.11.2009Рассмотрение общих сведений и уровней языков программирования. Ознакомление с историей развития, использования языков программирования. Обзор достоинств и недостатков таких языков как Ассемблер, Паскаль, Си, Си++, Фортран, Кобол, Бейсик, SQL, HTML, Java.
курсовая работа [759,5 K], добавлен 04.11.2014Понятия языка программирования, разновидности и характеристика языков. Исторический обзор их создания и применения. Классификация, примеры использования. Характеристики языков программирования с точки зрения элементов объектной модели, их популярность.
реферат [463,6 K], добавлен 07.09.2009Особенности способов описания языков программирования. Язык программирования как способ записи программ на ЭВМ в понятной для компьютера форме. Характеристика языка Паскаль, анализ стандартных его функций. Анализ примеров записи арифметических выражений.
курсовая работа [292,0 K], добавлен 18.03.2013Характеристики и свойства языков программирования. Исследование эволюции объектно-ориентированных языков программирования. Построение эволюционной карты механизмов ООП. Разработка концептуальной модели функционирования пользовательского интерфейса.
курсовая работа [2,6 M], добавлен 17.11.2014Машинные коды и ассемблер. Первые языки программирования высокого уровня. Язык программирования FORTRAN. Достоинства и недостатки ALGOL. Научные и бухгалтерские программы. Основные принципы, которые соблюдались при создании языка программирования Basic.
курсовая работа [407,4 K], добавлен 21.06.2014Сущность и функции языков программирования, их эволюция и оценка популярности различных видов. Особенности компьютерных программ, разработанных на компилируемом, интерпретируемом или смешанном языке. Основные классы и иерархия языков программирования.
презентация [873,4 K], добавлен 23.01.2013Характеристика базовых конструкций языков программирования. Изучение истории их развития и классификации. Определение основных понятий языков программирования. Описание основных операторов, которые используются в языках программирования высокого уровня.
курсовая работа [400,6 K], добавлен 10.11.2016Понятия структурного программирования и алгоритма решения задачи. Краткая история развития языков программирования от машинных до языков ассемблера и языков высокого уровня. Процедурное программирование на C#. Методы и программы для моделирования.
учебное пособие [1,7 M], добавлен 26.10.2010Основные понятия теории грамматик простого и операторного предшествования, алгоритмы синтаксического разбора предложения для классов КС-грамматик; разработка дерева вывода для грамматики входного языка в форме Бэкуса-Наура с указанием шагов построения.
лабораторная работа [28,0 K], добавлен 24.07.2012Развитие и классификация языков программирования. Методические рекомендации по изучению языков программирования. Основные понятия объектно-ориентированного программирования. Создание электронного учебного пособия с помощью языка гипертекстовой разметки.
курсовая работа [331,1 K], добавлен 06.09.2011Характеристика языков программирования: краткая история, хронология. Основные виды языков программирования: ассемблер; бейсик. Создание и использование формул в Excel. Применение операторов в формулах. Использование функций в Excel. Сайт дома отдыха.
отчет по практике [139,1 K], добавлен 03.06.2011Классификация электронных средств обучения, преимущества их использования, рекомендации по созданию. Требования к структуре и содержанию учебного материала. Особенности изучения языков программирования на уроках информатики. Среда программирования Delphi.
дипломная работа [770,2 K], добавлен 12.09.2015
