Терминальные и нетерминальные символы

Категории символов в формальных грамматиках

Строка «собака съела кость» была создана с использованием правил продукций, которые заменяли нетерминальные символы терминальными. ^[1]

В формальных языках терминальные и нетерминальные символы являются лексическими элементами , используемыми для указания правил производства, составляющих формальную грамматику . Терминальные символы являются элементарными символами языка, определенными как часть формальной грамматики. Нетерминальные символы (или синтаксические переменные ) заменяются группами терминальных символов в соответствии с правилами производства.

Терминалы и нетерминалы конкретной грамматики находятся в двух совершенно отдельных наборах .

Терминальные символы

Терминальные символы — это символы, которые могут появляться в выходных данных правил производства формальной грамматики и которые не могут быть изменены с помощью правил грамматики. Рекурсивное применение правил к исходной строке символов обычно приводит к конечной выходной строке, состоящей только из терминальных символов.

Рассмотрим грамматику, определенную двумя правилами. В этой грамматике символ Бявляется терминальным символом и Ψодновременно нетерминальным символом и начальным символом. Правила создания строк следующие:

1. Символ Ψможет статьБΨ
2. Символ Ψможет статьБ

Вот Бтерминальный символ, потому что не существует правила, которое могло бы изменить его во что-то другое. С другой стороны, Ψимеет два правила, которые могут изменить его, поэтому он нетерминальный. Формальный язык , определенный или сгенерированный определенной грамматикой, — это набор строк, которые могут быть созданы грамматикой и которые состоят только из терминальных символов . Диаграмма 1 иллюстрирует строку, которая может быть создана с помощью этой грамматики.

Диаграмма 1. Строка Б Б Б Ббыла сформирована грамматикой, определенной заданными правилами продукций. Эта грамматика может создавать строки с любым количеством символов Б

Нетерминальные символы

Нетерминальные символы — это те символы, которые можно заменить. Их также можно назвать просто синтаксическими переменными . Формальная грамматика включает начальный символ — обозначенный член множества нетерминалов, из которого все строки в языке могут быть получены путем последовательного применения правил производства. Фактически, язык, определяемый грамматикой, — это именно множество терминальных строк, которые могут быть получены таким образом.

Контекстно-свободные грамматики — это те грамматики, в которых левая часть каждого правила производства состоит только из одного нетерминального символа. Это ограничение нетривиально; не все языки могут быть сгенерированы контекстно-свободными грамматиками. Те, которые могут, называются контекстно-свободными языками. Это именно те языки, которые могут быть распознаны недетерминированным push down автоматом . Контекстно-свободные языки являются теоретической основой для синтаксиса большинства языков программирования .

Правила производства

Грамматика определяется правилами продукции (или просто «продукцией»), которые указывают, какие символы могут заменять какие другие символы; эти правила могут использоваться для генерации строк или для их разбора. Каждое такое правило имеет голову , или левую часть, которая состоит из строки, которая может быть заменена, и тело , или правую часть, которая состоит из строки, которая может ее заменить. Правила часто записываются в форме голова → тело ; например, правило a → b указывает, что a может быть заменено на b .

В классической формализации генеративных грамматик, впервые предложенной Ноамом Хомским в 1950-х годах, ^{[2] [3]} грамматика G состоит из следующих компонентов:

• Конечное множество N нетерминальных символов .
• Конечное множество Σ терминальных символов , не пересекающееся с N.
• Конечный набор P правил производства , каждое правило имеет вид

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

где — оператор звезды Клини , а ∪ обозначает объединение множеств , поэтому представляет ноль или более символов, а N означает один нетерминальный символ. То есть каждое правило продукций отображает одну строку символов в другую, где первая строка содержит по крайней мере один нетерминальный символ. В случае, если тело состоит исключительно из пустой строки ^{[примечание 1]} , оно может быть обозначено специальной нотацией (часто Λ , e или ε ), чтобы избежать путаницы. ${\displaystyle {}^{*}}$ ${\displaystyle (\Sigma \cup N)^{*}}$

• Выдающийся символ , являющийся начальным символом . ${\displaystyle S\in N}$

Грамматика формально определяется как упорядоченная четверка . Такая формальная грамматика часто называется в литературе системой переписывания или грамматикой фразовой структуры . ^{[4] [5]} ${\displaystyle \langle N,\Sigma ,P,S\rangle }$

Пример

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

< цифра >  ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' < целое число >  ::= ['-'] < цифра > { < цифра > }

В этом примере символы ( -,0,1,2,3,4,5,6,7,8,9 ) являются терминальными символами, а <digit>и <integer>являются нетерминальными символами. ^{[примечание 2]}

Другой пример:

${\displaystyle {\ce {S -> cAd}}}$

${\displaystyle {\ce {A -> a | ab}}}$

В этом примере символы a,b,c,d являются терминальными символами, а S,A — нетерминальными символами.

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

• Алфавит (официальные языки)
• Иерархия Хомского
• Рекурсивная грамматика

Примечания

1. Он вообще не содержит никаких символов.
2. Этот пример поддерживает строки с ведущими нулями, например «0056» или «0000», а также отрицательные нулевые строки, например «-0» и «-00000».

Ссылки

1. Розен, К. Х. (2012). Дискретная математика и ее приложения. McGraw-Hill. страницы 847-851.
2. Хомский, Ноам (1956). «Три модели описания языка». Труды IRE по теории информации . 2 (3): 113–123. doi :10.1109/TIT.1956.1056813. S2CID  19519474.
3. Хомский, Ноам (1957). Синтаксические структуры . Гаага: Мутон .
4. Гинзбург, Сеймур (1975). Алгебраические и автоматные теоретические свойства формальных языков . Северная Голландия. С. 8–9. ISBN 0-7204-2506-9.
5. Харрисон, Майкл А. (1978). Введение в теорию формального языка . Рединг, Массачусетс: Addison-Wesley Publishing Company. С. 13. ISBN 0-201-02955-3.