Производство (информатика) - Production (computer science)

Производство или правила производства в информатике является правилом перезаписи указания замены символа , который может быть рекурсивно выполняется для генерации новых последовательностей символов. Конечное множество продукций является основным компонентом спецификации формальной грамматики (в частности, порождающей грамматики ). Остальные компоненты представляют собой конечное множество из нетерминальных символов , конечное множество (известное как алфавит) из терминальных символов , которая пересекается с и отмеченным символом , который является начальным символом .

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

,

где - словарь , - оператор звезды Клини , обозначает конкатенацию , обозначает объединение множеств и обозначает множество минус или разность множеств . Если мы не допускаем появления начального символа в (слово в правой части), мы должны заменить его на в правой части декартового символа произведения.

Другие типы формальной грамматики в иерархии Хомского накладывают дополнительные ограничения на то, что составляет продукцию. В частности, в контекстно-свободной грамматике левая часть продукции должна быть единственным нетерминальным символом. Итак, продукция имеет вид:

Генерация грамматики

Чтобы сгенерировать строку на языке, нужно начать со строки, состоящей только из одного начального символа , а затем последовательно применять правила (любое количество раз в любом порядке) для перезаписи этой строки. Это останавливается, когда мы получаем строку, содержащую только терминалы. Язык состоит из всех строк, которые могут быть сгенерированы таким образом. Любая конкретная последовательность законных выборов, сделанных во время этого процесса перезаписи, дает одну конкретную строку на языке. Если существует несколько разных способов создания этой единственной строки, то грамматика называется неоднозначной .

Например, предположим, что алфавит состоит из и с начальным символом , и у нас есть следующие правила:

1.
2.

затем мы начинаем с и можем выбрать правило, которое будет применяться к нему. Если мы выбираем правило 1, мы заменяем его на и получаем строку . Если мы снова выберем правило 1, мы заменим его на и получим строку . Этот процесс повторяется до тех пор, пока у нас не останутся только символы алфавита (например, и ). Если теперь мы выберем правило 2, мы заменим на и получим строку , и все готово. Мы можем написать эту серию вариантов более кратко, используя символы: . Язык грамматики есть множество всех строк , которые могут быть получены с помощью этого процесса: .

Смотрите также

Ссылки

  1. ^ См. Klaus Reinhardt: Prioritatszahlerautomaten und die Synchronization von Halbspursprachen. Архивировано 17 января 2018 г. в Wayback Machine ; Fakultät Informatik der Universität Stuttgart; 1994 (немецкий)