Вычислительные Машины и Системы Математическое Обеспечение Вычислительных Систем Разработка формальной грамматики



Скачать 64.34 Kb.
Дата30.12.2012
Размер64.34 Kb.
ТипЛабораторная работа


Федеральное агентство по образованию

Московский Институт Радиотехники Электроники и Автоматики (Технический Университет)
Вычислительные Машины и Системы

Математическое Обеспечение Вычислительных Систем

Разработка формальной грамматики
Лабораторная работа

Выполнил:

Студент группы ВЕ-11-05 Исаков Андрей Владимирович







Проверил:

Доцент

Котович Леонид Леонидович



Москва

2009

Оглавление


Оглавление 2

Введение 3

Постановка задачи 5

Описание грамматики: 5

Реализация программы 5

Листинг программы: 5

Результат работы программы: 6



Введение


Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавитa. Различают порождающие и распознающие (или аналитические) грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит оно в язык или нет.




Термины

  • Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII — латинские буквы, цифры и спец. символы.

  • Нетерминал (нетерминальный символ) — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.

Порождающие грамматики

Словами языка, заданного грамматикой, являются все последовательности терминалов, выводимые (порождаемые) из начального нетерминала по правилам вывода.


Чтобы задать грамматику, требуется задать алфавиты терминалов и нетерминалов, набор правил вывода, а также выделить в множестве нетерминалов начальный.

Итак, грамматика определяется следующими характеристиками:

  • Σ — набор (алфавит) терминальных символов

  • N — набор (алфавит) нетерминальных символов

  • R — набор правил вида: «левая часть» «правая часть», где:

    • «левая часть» — непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал

    • «правая часть» — любая последовательность терминалов и нетерминалов

  • S — стартовый (начальный) символ из набора нетерминалов.

Вывод

Выводом называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путем замены некоторой подстроки по одному из правил. Конечной строкой является строка, полностью состоящая из терминалов, и следовательно являющаяся словом языка.

Существование вывода для некоторого слова является критерием его принадлежности к языку, определяемому данной грамматикой.

Типы грамматик

По иерархии Хомского, грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего (но и легче поддающимся анализу):

Применение

Пример — арифметические выражения

Рассмотрим простой язык, определяющий ограниченное подмножество арифметических формул, состоящих из натуральных чисел, скобок и знаков арифметических действий. Стоит заметить, что здесь в каждом правиле с левой стороны от стрелки стоит только один нетерминальный символ. Такие грамматики называются контекстно-свободными.

Терминальный алфавит:

Σ={'0','1','2','3','4','5','6','7','8','9','+','-','*','/','(',')'}.

Нетерминальный алфавит:

{ ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА }

Правила:

1. ФОРМУЛА ФОРМУЛА ЗНАК ФОРМУЛА (формула есть две формулы, соединенные знаком)

2. ФОРМУЛА ЧИСЛО (формула есть число)

3. ФОРМУЛА ( ФОРМУЛА ) (формула есть формула в скобках)

4. ЗНАК + | - | * | / (знак есть плюс или минус или умножить или разделить)

5. ЧИСЛО ЦИФРА (число есть цифра)

6. ЧИСЛО ЧИСЛО ЦИФРА (число есть число и цифра)

7. ЦИФРА 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (цифра есть 0 или 1 или ... 9 )

Начальный нетерминал:

ФОРМУЛА


Вывод:

Выведем формулу (12+5) с помощью перечисленных правил вывода. Для наглядности, стороны каждой замены показаны попарно, в каждой паре заменяемая часть подчеркнута.

ФОРМУЛА ( ФОРМУЛА )

( ФОРМУЛА ) ( ФОРМУЛА ЗНАК ФОРМУЛА )

( ФОРМУЛА ЗНАК ФОРМУЛА ) (ФОРМУЛА + ФОРМУЛА )

( ФОРМУЛА + ФОРМУЛА ) ( ФОРМУЛА + ЧИСЛО )

( ФОРМУЛА + ЧИСЛО ) ( ФОРМУЛА + ЦИФРА )

( ФОРМУЛА + ЦИФРА ) ( ФОРМУЛА + 5)

( ФОРМУЛА + 5) ( ЧИСЛО + 5 )

( ЧИСЛО + 5 ) ( ЧИСЛО ЦИФРА + 5)

( ЧИСЛО ЦИФРА + 5 ) ( ЦИФРА ЦИФРА + 5)

( ЦИФРА ЦИФРА + 5 ) ( 1 ЦИФРА + 5)

(1 ЦИФРА + 5) ( 1 2 + 5)
Аналитические грамматики

Порождающие грамматики - не единственный вид грамматик, однако наиболее распространенный в приложениях к программированию. В отличие от порождающих грамматик, аналитическая (распознающая) грамматика задает алгоритм, позволяющий определить, принадлежит ли данное слово языку. Например, любой регулярный язык может быть распознан при помощи грамматики, задаваемой конечным автоматом, а любая контекстно-свободная грамматика — с помощью автомата со стековой памятью. Если слово принадлежит языку, то такой автомат строит его вывод в явном виде, что позволяет анализировать семантику этого слова.

Постановка задачи


  1. Описать произвольно выбранную формальную грамматику

  2. Разработать программу, которая выводит все строки, порождаемые описанной грамматикой


В качестве грамматики используется грамматика порождающая строки, состоящие из символов ‘a’ и ‘b’. Причем строка должная начинаться с символа ‘a’ и заканчиваться символом ‘b’. Символы не должны чередоваться. Количество символов ‘a’ должно равняться количеству символов ‘b’.

Пример:

ab

aabb

aaabbb

Описание грамматики:


G = (N, T, P, S)

N – множество нетерминальных символов;

Т – множество терминальных символов;

Р – правила преобразования;

S – стартовый символ;
G = ( {S}, {a, b}, {S  aSb | ab}, S)

Реализация программы


Для реализации выбрана среда разработки Microsoft Visual Studio 2008.

Листинг программы:


#include "stdafx.h"

#include

#include

int _tmain(int argc, _TCHAR* argv[])

{

int k = 0;

std::cout<<"Enter the number repeats\n";

std::cin>>k;

std::string s = "ab";

for (int i = 0; i < k; i++)

{

std::cout<
s = 'a' + s + 'b';

}

return 0;

}

Результат работы программы:





Похожие:

Вычислительные Машины и Системы Математическое Обеспечение Вычислительных Систем Разработка формальной грамматики iconПрограмма учебной дисциплины «вычислительные машины, системы и сети» Направление подготовки
Вычислительные машины, системы и сети ” призвана познакомить студента, обучающегося по направлению 220700 “Автоматизация технологических...
Вычислительные Машины и Системы Математическое Обеспечение Вычислительных Систем Разработка формальной грамматики iconПринципы и решения по совершенствованию эффективности функционирования операционных систем и приложений микропроцессорных карт 05. 13. 11 математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей
Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей
Вычислительные Машины и Системы Математическое Обеспечение Вычислительных Систем Разработка формальной грамматики iconСпецкурсы кафедры Компьютерных систем фит нгу
Математическое обеспечение современных высокопроизводительных вычислительных систем (2-2) (экзамен)
Вычислительные Машины и Системы Математическое Обеспечение Вычислительных Систем Разработка формальной грамматики iconПрограммы подготовки бакалавра по направлению 230100 Вычислительные машины, комплексы, системы и сети
«Информатика и вычислительная техника», профиль «Вычислительные машины, комплексы, системы и сети»
Вычислительные Машины и Системы Математическое Обеспечение Вычислительных Систем Разработка формальной грамматики iconИсследование и разработка алгоритмов параллельного дедуктивного вывода на графовых структурах
Специальность 05. 13. 11 – Математическое и программное обеспечение вычислительных машин, комплексов
Вычислительные Машины и Системы Математическое Обеспечение Вычислительных Систем Разработка формальной грамматики iconИсследование и разработка алгоритмов обобщения на основе теории приближенных множеств
Специальность 05. 13. 11 – Математическое и программное обеспечение вычислительных машин, комплексов
Вычислительные Машины и Системы Математическое Обеспечение Вычислительных Систем Разработка формальной грамматики iconНовые эффективные методы энтропийного кодирования медиаданных 05. 13. 11 "Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей"
Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей”
Вычислительные Машины и Системы Математическое Обеспечение Вычислительных Систем Разработка формальной грамматики iconУчебно-методический комплекс по дисциплине «Алгоритмическое обеспечение информационных систем» (наименование дисциплины) для специальности(ей)
Учебно-методический комплекс (умк) составлен на основании гос впо и учебного плана Улгту специальности (направления) 23010165 «Вычислительные...
Вычислительные Машины и Системы Математическое Обеспечение Вычислительных Систем Разработка формальной грамматики iconВопросы кандидатского экзамена 05. 13. 11 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»
Вопросы кандидатского экзамена 05. 13. 11 Математическое и программное обеспечение вычислительных машин
Вычислительные Машины и Системы Математическое Обеспечение Вычислительных Систем Разработка формальной грамматики iconСписок экзаменационных вопросов по курсу «Системное программное обеспечение»
Понятие формальной грамматики и языка. Выводимость. Язык, порождаемый грамматикой
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org