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

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

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

Символы терминалов

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

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

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

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

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

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

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

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

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

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

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

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

где

{}^{*}

— Клини звездный оператор

, а \cup

обозначает объединение множеств , поэтому

(\Sigma \cup N)^{*}

представляет ноль или более символов, а

N

означает один нетерминальный символ. То есть каждое продукционное правило отображается из одной строки символов в другую, где первая строка содержит хотя бы один нетерминальный символ. В случае, если тело состоит исключительно из пустой строки ^{[примечание 1]}, его можно обозначать специальными обозначениями (часто

Λ

,

e

или

ε

), чтобы избежать путаницы.

Выдающийся символ $S\in N$ это стартовый символ .

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

Пример

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

<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> являются нетерминальными символами. ^{[примечание 2]}

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

{\ce {S -> cAd}}

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

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

См. также

Примечания

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

Ссылки

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

[4] Он вообще не содержит символов.

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

[1] Розен, К.Х. (2012). Дискретная математика и ее приложения. МакГроу-Хилл. страницы 847-851

[Chomsky1956-2] Хомский, Ноам (1956). «Три модели описания языка». IRE Транзакции по теории информации . 2 (3): 113–123. дои : 10.1109/TIT.1956.1056813 . S2CID 19519474 .

[Chomsky1957-3] Хомский, Ноам (1957). Синтаксические структуры . Гаага: Мутон .

[5] Гинзбург, Сеймур (1975). Алгебраические и теоретико-автоматные свойства формальных языков . Северная Голландия. стр. 8–9. ISBN 0-7204-2506-9 .

[6] Харрисон, Майкл А. (1978). Введение в теорию формального языка . Ридинг, Массачусетс: Издательство Addison-Wesley. стр. 13 . ISBN 0-201-02955-3 .

[1]

[2]

[3]

[примечание 1]

[4]

[5]

[примечание 2]