Что такое «Производство» на простом английском языке?

Question

Я могу прочитать в Википедии формальное определение Production, однако, когда вы начинаете читать эту статью, в ней делается предположение о предварительном знании.

Википедия определяет его следующим образом:

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

Это предполагает, что я знаю и понимаю, что правилоперезаписи. Я этого не делаю, и если я нажму ссылку, я получу еще одно техническое объяснение.

Может ли кто-нибудь объяснить мне на простом английском языке, что такое Производство на самом деле?

Примечание: Я сделал много попыток понять это, но я не думаю, что я преуспел. Из того, что я могу сказать, он переписывает данную строку в терминах правил грамматики. Не уверен, что я прав.

Answer 1

Чтобы объяснить, что такое производство, я хотел бы сначала представить немного контекста.

Дракон книги утверждает, что контекст свободная грамматика имеет 4 компонента:

• набор терминальных символов (лексем)
• набор нетерминальными символов (синтаксических переменных)
• набор производств вида: без термина -> последовательность терминалов и нетерминалов
• не-терминальный символ обозначен как начальный символ

Также говорится, что синтаксический анализ представляет собой проблему взятия строки терминалов (исходный код) и выяснение, какие шаги необходимы для получения этой строки терминалов из символа начала грамматики.

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

Например, давайте сделаем простую грамматику для представления произвольно длинных последовательностей окончания a с помощью b. В 4 компонент этой грамматики будут:

• Терминалы: а, б
• нетерминалов: S, X
• Правило: S -> X, X -> аХ, X - > абы
• символ Начала: S

из описания я дал выше «aaaab» должен быть выводим из этой грамматики. Посмотрим, справится ли это. Мы начинаем с символа начала, а затем применяем постановки до тех пор, пока а) не получим окончательную последовательность, б) мы исчерпаем все возможности без успеха (это означает, что последовательность не является «грамматически правильной»).

S 
X (after applying S --> X) 
aX (after applying X --> aX) 
aaX (after applying X --> aX) 
aaaX (after applying X --> aX) 
aaaab (after applying X --> ab) 

И все готово, мы получили исходную последовательность. Итак, как вы можете видеть, мы повторно написали нетерминальные символы, применяя правила (один из них мы применили рекурсивно), которые трансформировали последовательность в новую последовательность символов на каждом шаге, и мы сделали это до тех пор, пока не получим окончательную последовательность.

Answer 2

Правило перезаписи - это метод замены подтерм формулы с другими терминами. В своей основной форме они состоят из набора объектов, а также отношений о том, как преобразовать эти объекты.

Пример правила перезаписи может выглядеть следующим образом:

A → B 

Теперь, как для того, что это на самом деле делает! Вы прямо на вашу записку, возьмите, например, список вещей (и 2 правила перезаписи):

X, Y, Z 
X → Y 
Y → Z 

Что бы привести:

Z, Z, Z 

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

X, Y, Z 
X → aX 

Используя правило таким образом, становится возможным применить рекурсию (создать новые последовательности), как это будет держать замену себя:

aX, Y, Z 
aaX, Y, Z 
aaaX, Y, Z 

Что касается вопрос, который вы задаете, можно сказать: «Правило производства является правилом замены для формул, в которых используется рекурсия для создания новых последовательностей».