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

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

Продукция или правило продукции в информатике — это правило перезаписи, определяющее замену символа, которая может быть рекурсивно выполнена для генерации новых последовательностей символов. Конечный набор продукций является основным компонентом спецификации формальной грамматики (в частности, генеративной грамматики ). Другие компоненты — это конечный набор нетерминальных символов , конечный набор (известный как алфавит) терминальных символов , который не пересекается с и выделенный символ , который является начальным символом . ${\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 (немецкий)