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

Метод замены символов

Производственное или производственное правило в информатике — это правило перезаписи , определяющее замену символов, которая может выполняться рекурсивно для создания новых последовательностей символов. Конечный набор продукций является основным компонентом спецификации формальной грамматики (в частности, порождающей грамматики ). Другие компоненты — это конечный набор нетерминальных символов , конечный набор (известный как алфавит) терминальных символов , который не пересекается с, и выделенный символ , который является начальным символом . ${\displaystyle P}$ ${\displaystyle N}$ ${\displaystyle \Sigma }$ ${\displaystyle N}$ ${\displaystyle S\in N}$

В неограниченной грамматике продукция имеет вид , где и — произвольные строки терминалов и нетерминалов и не может быть пустой строкой . Если это пустая строка, это обозначается символом или (вместо того, чтобы оставлять правую часть пустой). Таким образом, произведения являются членами декартова произведения. ${\displaystyle u\to v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \epsilon }$ ${\displaystyle \lambda }$

${\displaystyle V^{*}NV^{*}\times V^{*}=(V^{*}\setminus \Sigma ^{*})\times V^{*}}$,

где - словарь , - оператор звезды Клини , указывает на конкатенацию , обозначает объединение множеств и обозначает минус или разность множеств . Если мы не допускаем появления начального символа (слова справа), нам придется заменить его на в правой части символа декартового произведения. ^[1] ${\displaystyle V:=N\cup \Sigma }$ ${\displaystyle {}^{*}}$ ${\displaystyle V^{*}NV^{*}}$ ${\displaystyle \cup }$ ${\displaystyle \setminus }$ ${\displaystyle v}$ ${\displaystyle V^{*}}$ ${\displaystyle (V\setminus \{S\})^{*}}$

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

${\displaystyle N\to (N\cup \Sigma )^{*}}$

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

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

Например, предположим, что алфавит состоит из и с начальным символом , и у нас есть следующие правила: ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle S}$

1. ${\displaystyle S\rightarrow aSb}$

2. ${\displaystyle S\rightarrow ba}$

затем мы начинаем с и можем выбрать правило, которое будет применяться к нему. Если мы выберем правило 1, мы заменим на и получим строку . Если мы снова выберем правило 1, мы заменим его на и получим строку . Этот процесс повторяется до тех пор, пока у нас не останутся только символы алфавита (т. е. и ). Если мы теперь выберем правило 2, мы заменим на и получим строку и все готово. Мы можем записать эту серию выборов более кратко, используя символы: . Язык грамматики — это набор всех строк, которые могут быть сгенерированы с помощью этого процесса: . ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle aSb}$ ${\displaystyle aSb}$ ${\displaystyle S}$ ${\displaystyle aSb}$ ${\displaystyle aaSbb}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle S}$ ${\displaystyle ba}$ ${\displaystyle aababb}$ ${\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}$ ${\displaystyle \{ba,abab,aababb,aaababbb,\dotsc \}}$

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

• Формальная грамматика
• Конечные автоматы
• Генеративная грамматика
• L-система
• Переписать правило
• Форма Бэкуса – Наура (компактная форма для записи произведений контекстно-свободной грамматики.)
• Правило построения фразы
• Пост-каноническая система (Продукционные системы Эмиля Поста - модель вычислений.)

Рекомендации

1. См. Клаус Рейнхардт: Prioritatszahlerautomaten und die Synchronization von Halbspursprachen. Архивировано 17 января 2018 г. в Wayback Machine ; Факультет информатики университета Штутгарта; 1994 (немецкий)