Формальная грамматика
Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавитa. Различают порождающие и распознающие (или аналитические) грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит оно в язык или нет.
Термины
- Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII — латинские буквы, цифры и спец. символы.
- Нетерминал (нетерминальный символ) — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.
Порождающие грамматики
Словами языка, заданного грамматикой, являются все последовательности терминалов, выводимые (порождаемые) из начального нетерминала по правилам вывода.
Чтобы задать грамматику, требуется задать алфавиты терминалов и нетерминалов, набор правил вывода, а также выделить в множестве нетерминалов начальный.
Итак, грамматика определяется следующими характеристиками:
- <math>\Sigma</math> — набор (алфавит) терминальных символов
- N — набор (алфавит) нетерминальных символов
- P — набор правил вида: «левая часть» <math>\rightarrow</math> «правая часть», где:
- «левая часть» — непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал
- «правая часть» — любая последовательность терминалов и нетерминалов
- S — стартовый (начальный) символ из набора нетерминалов.
Вывод
Выводом называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путем замены некоторой подстроки по одному из правил. Конечной строкой является строка, полностью состоящая из терминалов, и следовательно являющаяся словом языка.
Существование вывода для некоторого слова является критерием его принадлежности к языку, определяемому данной грамматикой.
Типы грамматик
По иерархии Хомского, грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего (но и легче поддающимся анализу):
- тип 0. неограниченные грамматики — возможны любые правила
- тип 1. контекстно-зависимые грамматики — левая часть может содержать один нетерминал, окруженный «контекстом» (последовательности символов, в том же виде присутствующие в правой части); сам нетерминал заменяется непустой последовательностью символов в правой части.
- тип 2. контекстно-свободные грамматики — левая часть состоит из одного нетерминала.
- тип 3. регулярные грамматики — более простые, эквивалентны конечным автоматам.
Применение
- Контекстно-свободные грамматики широко применяются для определения грамматической структуры в грамматическом анализе.
- Регулярные грамматики (в виде регулярных выражений) широко применяются как шаблоны для текстового поиска, разбивки и подстановки, в т.ч. в лексическом анализе.
Пример — арифметические выражения
Рассмотрим простой язык, определяющий ограниченное подмножество арифметических формул, состоящих из натуральных чисел, скобок и знаков арифметических действий. Стоит заметить, что здесь в каждом правиле с левой стороны от стрелки <math>\Rightarrow</math> стоит только один нетерминальный символ. Такие грамматики называются контекстно-свободными.
Терминальный алфавит:
<math>\Sigma</math>={'0','1','2','3','4','5','6','7','8','9','+','-','*','/','(',')'}.
Нетерминальный алфавит:
{ ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА }
Правила:
1. ФОРМУЛА <math>\Rightarrow\!\,</math> ФОРМУЛА ЗНАК ФОРМУЛА (формула есть две формулы, соединенные знаком) 2. ФОРМУЛА <math>\Rightarrow\!\,</math> ЧИСЛО (формула есть число) 3. ФОРМУЛА <math>\Rightarrow\!\,</math> ( ФОРМУЛА ) (формула есть формула в скобках) 4. ЗНАК <math>\Rightarrow\!\,</math> + | - | * | / (знак есть плюс или минус или умножить или разделить) 5. ЧИСЛО <math>\Rightarrow\!\,</math> ЦИФРА (число есть цифра) 6. ЧИСЛО <math>\Rightarrow\!\,</math> ЧИСЛО ЦИФРА (число есть число и цифра) 7. ЦИФРА <math>\Rightarrow\!\,</math> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (цифра есть 0 или 1 или ... 9 )
Начальный нетерминал:
ФОРМУЛА
Вывод:
Выведем формулу (12+5) с помощью перечисленных правил вывода. Для наглядности, стороны каждой замены показаны попарно, в каждой паре заменяемая часть подчеркнута.
- ФОРМУЛА <math>\Rightarrow_3\!\,</math> ( ФОРМУЛА )
- ( ФОРМУЛА ) <math>\Rightarrow_1\!\,</math> ( ФОРМУЛА ЗНАК ФОРМУЛА )
- ( ФОРМУЛА ЗНАК ФОРМУЛА ) <math>{\Rightarrow_4\!\,}</math> (ФОРМУЛА + ФОРМУЛА )
- ( ФОРМУЛА + ФОРМУЛА ) <math>{\Rightarrow_2\!\,}</math> ( ФОРМУЛА + ЧИСЛО )
- ( ФОРМУЛА + ЧИСЛО ) <math>{\Rightarrow_5\!\,}</math> ( ФОРМУЛА + ЦИФРА )
- ( ФОРМУЛА + ЦИФРА ) <math>{\Rightarrow_7\!\,}</math> ( ФОРМУЛА + 5)
- ( ФОРМУЛА + 5) <math>{\Rightarrow_2\!\,}</math> ( ЧИСЛО + 5 )
- ( ЧИСЛО + 5 ) <math>{\Rightarrow_6\!\,}</math> ( ЧИСЛО ЦИФРА + 5)
- ( ЧИСЛО ЦИФРА + 5 ) <math>{\Rightarrow_5\!\,}</math> ( ЦИФРА ЦИФРА + 5)
- ( ЦИФРА ЦИФРА + 5 ) <math>{\Rightarrow_7\!\,}</math> ( 1 ЦИФРА + 5)
- (1 ЦИФРА + 5) <math>{\Rightarrow_7\!\,}</math> ( 1 2 + 5)
Аналитические грамматики
Порождающие грамматики - не единственный вид грамматик, однако наиболее распространенный в приложениях к программированию. В отличие от порождающих грамматик, аналитическая (распознающая) грамматика задает алгоритм, позволяющий определить, принадлежит ли данное слово языку. Например, любой регулярный язык может быть распознан при помощи грамматики, задаваемой конечным автоматом, а любая контекстно-свободная грамматика — с помощью автомата со стековой памятью. Если слово принадлежит языку, то такой автомат строит его вывод в явном виде, что позволяет анализировать семантику этого слова.
См. также
Источники
- Гладкий А. В. Формальные грамматики и языки. — М.: Наука, 1973.
- Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. - Новосибирск: НГУ. - 1995. - 112 с.
- Хомский Н., Миллер Дж. Введение в формальный анализ естественных языков // Кибернетический сборник / Под ред. А.А.Ляпунова и О.Б.Лупанова. — М.: Мир, 1965.
Формула | Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её. |
bs:Formalna gramatika ca:Gramàtica formal cs:Formální gramatika de:Formale Grammatik el:Τυπική γραμματική en:Formal grammar es:Gramática formal et:Formaalne grammatika fi:Formaali kielioppi fr:Grammaire formelle gl:Gramática formal hr:Formalna gramatika hu:Formális nyelvtan it:Grammatica formale ja:形式文法 ko:형식 문법 nl:Formele grammatica no:Formell grammatikk pl:Gramatyka formalna pt:Gramática formal sh:Formalna gramatika sr:Формална граматика sv:Formell grammatik uk:Формальні граматики zh:形式文法
Если вам нравится SbUP.com Сайт, вы можете поддержать его - BTC: bc1qppjcl3c2cyjazy6lepmrv3fh6ke9mxs7zpfky0 , TRC20 и ещё....