Терминальные и нетерминальные символы - Terminal and nonterminal symbols

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\ Displaystyle (\ Sigma \ чашка N) ^ {*} N (\ Sigma \ cup N) ^ {*} \ rightarrow (\ Sigma \ cup N) ^ {*}}$

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

• Выдающийся символ, который является стартовым символом .${\ displaystyle S \ in N}$

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

Пример

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

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

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

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

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

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

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

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

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

Примечания

использованная литература