Язык ДРАКОН и формальная грамматикаЯ предполагаю, что графику языка ДРАКОН можно описать с помощью формальной порождающей грамматики.
Подсказки 1. Терминалами являются иконы языка ДРАКОН.
2. Нетерминалами являются макроиконы языка ДРАКОН. Кроме того, нетерминалами являются шампур-схемы (абстрактные дракон-схемы) , так как они состоят из икон и макроикон с учетом операций заземления лианы и пересадки лианы.
3. Известно, что:
Цитата:
Словами языка, заданного грамматикой, являются все последовательности терминалов, выводимые (порождаемые) из начального нетерминала по правилам вывода.
Применительно к языку ДРАКОН надо говорить не "слова языка, заданного грамматикой", а шампур-схемы, заданные порождающей грамматикой языка ДРАКОН.
Я не знаю получится эта формализация или нет. Приглашаю заинтересованных студентов и аспирантов исследовать эту проблему.
Вы готовы?
Тогда свяжитесь со мной:
vdp2007@bk.ru Цитирую Википедию
http://ru.wikipedia.org/?oldid=78060132Цитата:
Формальная грамматика
Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита.
Различают порождающие и распознающие (или аналитические) грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит ли оно в язык или нет.
Содержание
1 Термины
2 Порождающие грамматики
2.1 Вывод
2.2 Типы грамматик
2.3 Применение
2.4 Пример — арифметические выражения
3 Аналитические грамматики
4 См. также
5 Примечания
6 Литература
Термины
Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII — латинские буквы, цифры и спец. символы.
Нетерминал (нетерминальный символ) — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.
Порождающие грамматики
Словами языка, заданного грамматикой, являются все последовательности терминалов, выводимые (порождаемые) из начального нетерминала по правилам вывода.
Чтобы задать грамматику, требуется задать алфавиты терминалов и нетерминалов, набор правил вывода, а также выделить в множестве нетерминалов начальный.
Итак, грамматика определяется следующими характеристиками:
{\displaystyle \Sigma } \Sigma — набор (алфавит) терминальных символов
N — набор (алфавит) нетерминальных символов
P — набор правил вида: «левая часть» {\displaystyle \rightarrow } \rightarrow «правая часть», где:
«левая часть» — непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал
«правая часть» — любая последовательность терминалов и нетерминалов
S — стартовый (или начальный) символ грамматики из набора нетерминалов.
Вывод
Выводом называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путём замены некоторой подстроки по одному (любому) из правил. Конечной строкой является строка, полностью состоящая из терминалов, и следовательно являющаяся словом языка.
Существование вывода для некоторого слова является критерием его принадлежности к языку, определяемому данной грамматикой.
Типы грамматик
По иерархии Хомского, грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего (но и легче поддающимся анализу):
тип 0. неограниченные грамматики — возможны любые правила
тип 1. контекстно-зависимые грамматики — левая часть может содержать один нетерминал, окруженный «контекстом» (последовательности символов, в том же виде присутствующие в правой части); сам нетерминал заменяется непустой последовательностью символов в правой части.
тип 2. контекстно-свободные грамматики — левая часть состоит из одного нетерминала.
тип 3. регулярные грамматики — более простые, эквивалентны конечным автоматам.
Кроме того, выделяют:
Неукорачивающиеся грамматики. Каждое правило такой грамматики имеет вид {\displaystyle \alpha \rightarrow \beta } \alpha \rightarrow \beta , где {\displaystyle |\alpha |\leqslant |\beta |} |\alpha |\leqslant |\beta |. Длина правой части правила не меньше длины левой[1].
Линейные грамматики. Каждое правило такой грамматики имеет вид {\displaystyle A\rightarrow uBv} A\rightarrow uBv, или {\displaystyle A\rightarrow u} A\rightarrow u, то есть в правой части правила может содержаться не более одного вхождения нетерминала[2].
[b]Применение[/b]
Контекстно-свободные грамматики широко применяются для определения грамматической структуры в грамматическом анализе.
Регулярные грамматики (в виде регулярных выражений) широко применяются как шаблоны для текстового поиска, разбивки и подстановки, в том числе в лексическом анализе.
Пример — арифметические выражения
Рассмотрим простой язык, определяющий ограниченное подмножество арифметических формул, состоящих из натуральных чисел, скобок и знаков арифметических действий.
Стоит заметить, что здесь в каждом правиле с левой стороны от стрелки {\displaystyle \Rightarrow } \Rightarrow стоит только один нетерминальный символ. Такие грамматики называются контекстно-свободными.
Терминальный алфавит:
Sigma = {'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) с помощью перечисленных правил вывода. Для наглядности, стороны каждой замены показаны попарно, в каждой паре заменяемая часть подчеркнута.
ФОРМУЛА {\displaystyle {\stackrel {3}{\to }}} {\stackrel {3}{\to }} (ФОРМУЛА)
(ФОРМУЛА) {\displaystyle {\stackrel {1}{\to }}} {\stackrel {1}{\to }} (ФОРМУЛА ЗНАК ФОРМУЛА)
(ФОРМУЛА ЗНАК ФОРМУЛА) {\displaystyle {\stackrel {4}{\to }}} {\stackrel {4}{\to }} (ФОРМУЛА + ФОРМУЛА)
(ФОРМУЛА + ФОРМУЛА) {\displaystyle {\stackrel {2}{\to }}} {\stackrel {2}{\to }} (ФОРМУЛА + ЧИСЛО)
(ФОРМУЛА + ЧИСЛО) {\displaystyle {\stackrel {5}{\to }}} {\stackrel {5}{\to }} (ФОРМУЛА + ЦИФРА)
(ФОРМУЛА + ЦИФРА) {\displaystyle {\stackrel {7}{\to }}} {\stackrel {7}{\to }} (ФОРМУЛА + 5)
(ФОРМУЛА + 5) {\displaystyle {\stackrel {2}{\to }}} {\stackrel {2}{\to }} (ЧИСЛО + 5)
(ЧИСЛО + 5) {\displaystyle {\stackrel {6}{\to }}} {\stackrel {6}{\to }} (ЧИСЛО ЦИФРА + 5)
(ЧИСЛО ЦИФРА + 5) {\displaystyle {\stackrel {5}{\to }}} {\stackrel {5}{\to }} (ЦИФРА ЦИФРА + 5)
(ЦИФРА ЦИФРА + 5) {\displaystyle {\stackrel {7}{\to }}} {\stackrel {7}{\to }} (1 ЦИФРА + 5)
(1 ЦИФРА + 5) {\displaystyle {\stackrel {7}{\to }}} {\stackrel {7}{\to }} (1 2 + 5)