Производство или правила производства в информатике является правилом перезаписи указания замены символа , который может быть рекурсивно выполняется для генерации новых последовательностей символов. Конечное множество производствявляется основным компонентом спецификации формальной грамматики (в частности, порождающей грамматики ). Остальные компоненты представляют собой конечное множествоиз нетерминальных символов , конечное множество (известное как алфавит)из терминальных символов , который не пересекается с и выдающийся символ это начальный символ .
В неограниченной грамматике продукция имеет вид, где а также - произвольные строки терминалов и нетерминалов, и не может быть пустой строкой . Если это пустая строка, это обозначается символом , или же (а не оставлять правую часть пустой). Итак, производства являются членами декартова произведения.
- ,
где это словарь ,- звездный оператор Клини ,указывает на конкатенацию ,обозначает объединение множеств , аобозначает установленный минус или установленную разницу . Если мы не позволим стартовому символу появиться в (слово справа), мы должны заменить от справа от декартового символа произведения. [1]
Другие типы формальной грамматики в иерархии Хомского накладывают дополнительные ограничения на то, что составляет продукцию. Примечательно, что в контекстно-свободной грамматике левая часть продукции должна быть единственным нетерминальным символом. Итак, продукция имеет вид:
Генерация грамматики
Чтобы сгенерировать строку на языке, нужно начать со строки, состоящей только из одного начального символа , а затем последовательно применять правила (любое количество раз в любом порядке) для перезаписи этой строки. Это останавливается, когда мы получаем строку, содержащую только терминалы. Язык состоит из всех строк, которые могут быть сгенерированы таким образом. Любая конкретная последовательность законных выборов, сделанных во время этого процесса перезаписи, дает одну конкретную строку на языке. Если существует несколько различных способов создания этой единственной строки, то грамматика считается неоднозначной .
Например, предположим, что алфавит состоит из а также , с начальным символом , и у нас есть следующие правила:
- 1.
- 2.
тогда мы начнем с , и можете выбрать правило, которое будет применяться к нему. Если мы выберем правило 1, мы заменим с участием и получим строку . Если мы снова выберем правило 1, мы заменим с участием и получим строку . Этот процесс повторяется до тех пор, пока у нас не останутся только символы алфавита (т.е. а также ). Если теперь мы выберем правило 2, мы заменим с участием и получим строку , и готово. Мы можем записать эту серию вариантов более кратко, используя символы:. Язык грамматики - это набор всех строк, которые могут быть сгенерированы с помощью этого процесса:.
Смотрите также
- Формальная грамматика
- Конечные автоматы
- Генеративная грамматика
- L-система
- Правило перезаписи
- Форма Бэкуса – Наура (компактная форма для написания произведений контекстно-свободной грамматики.)
- Правило структуры фраз
- Постканоническая система (производственные системы Эмиля Поста - модель вычислений.)
Рекомендации
- ^ См. Klaus Reinhardt: Prioritatszahlerautomaten und die Synchronization von Halbspursprachen. Архивировано 17 января 2018 г. в Wayback Machine ; Fakultät Informatik der Universität Stuttgart; 1994 (немецкий)