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

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

Терминалы и нетерминалы конкретной грамматики представляют собой два непересекающихся набора.

• 1 Терминальные символы
• 2 Нетерминальные символы
• 3 Правила производства
• 4 Пример
• 5 См. Также
• 6 Ссылки

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

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

1. Символ רможет стать ди
2. Символ רможет стать д

Здесь 94- терминал символ, потому что не существует правила, которое изменило бы его на что-то другое. С другой стороны, רимеет два правила, которые могут его изменить, поэтому он нетерминальный. Формальный язык, определенный или генерируемый определенной грамматикой, представляет собой набор строк, которые могут быть созданы грамматикой и которые состоят только из терминальных символов.

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

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

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

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

• Конечное множество $N\; \{\backslash \; displaystyle\; N\}$нетерминальных символов.
• Конечный набор $\Sigma \; \{\backslash \; displaystyle\; \backslash \; Sigma\}$терминальных символов, который не пересекается с $N\; \{\backslash \; displaystyle\; N\}$.
• Конечный набор $P\; \{\backslash \; displaystyle\; P\}$производственных правил, каждое правило имеет форму

$(\Sigma \; \cup \; N)\; \ast \; N\; (\; \Sigma \; \cup \; N)\; \ast \; \to \; (\Sigma \; \cup \; N)\; \ast \; \{\backslash \; displaystyle\; (\backslash \; Sigma\; \backslash \; cup\; N)\; ^\; \{*\}\; N\; (\backslash \; Sigma\; \backslash \; cup\; N)\; ^\; \{*\}\; \backslash \; rightarrow\; (\backslash \; Sigma\; \backslash \; cup\; N)\; ^\; \{*\; \}\}$

где $\ast \; \{\backslash \; displaystyle\; \{\}\; ^\; \{*\}\}$- оператор звезды Клини, а $\cup \; \{\backslash \; displaystyle\; \backslash \; cup\}$обозначает объединение множества, поэтому $(\Sigma \; \cup \; N)\; \ast \; \{\backslash \; displaystyle\; (\backslash \; Sigma\; \backslash \; cup\; N)\; ^\; \{*\}\}$представляет ноль или более символов, а $N\; \{\backslash \; displaystyle\; N\}$означает один нетерминальный символ. То есть каждое производственное правило преобразуется из одной строки символов в другую, где первая строка содержит по крайней мере один нетерминальный символ. В случае, если тело состоит исключительно из пустой строки, т. Е. Вообще не содержит символов, его можно обозначить специальным обозначением (часто $\Lambda \; \{\backslash \; displaystyle\; \backslash \; Lambda\}$, $e\; \{\backslash \; displaystyle\; e\}$или $ϵ\; \{\backslash \; displaystyle\; \backslash \; epsilon\}$) во избежание путаницы.

• Выделенный символ $S\; \in \; N\; \{\backslash \; displaystyle\; S\; \backslash \; in\; N\}$, это начальный символ.

Грамматика формально определяется как упорядоченная четверка . Такую формальную грамматику часто называют системой переписывания или грамматика структуры фразы в литературе.

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

:: = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9 ':: = [' - '] {}

В этом примере символ s (-, 0,1,2,3,4,5,6,7,8,9) - терминальные символы, а и - нетерминальные символы.

Примечание. В этом примере поддерживаются строки с ведущими нулями, например «0056» или «0000», а также строки с отрицательными нулями, например «-0» и «-00000».

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

S ->cAd

A ->a | ab

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

• Рекурсивная грамматика