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

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

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

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

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

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

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

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

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

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

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

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

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

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

Конечное множество ${displaystyle N}$ из нетерминальные символы.
Конечное множество ${displaystyle Sigma}$ из терминальные символы это непересекающийся из ${displaystyle N}$ .
Конечное множество ${displaystyle P}$ из правила производства, каждое правило вида

{displaystyle (Сигма-чашка N) ^ {*} N (Сигма-чашка N) ^ {*} ightarrow (Сигма-чашка N) ^ {*}}

где

{displaystyle {} ^ {*}}

это Клини звезда оператор и

{displaystyle cup}

обозначает установить союз, так

{displaystyle (чашка сигмы N) ^ {*}}

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

{displaystyle N}

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

{displaystyle Lambda}

,

{displaystyle e}

или

{displaystyle epsilon}

) во избежание путаницы.

Выдающийся символ ${displaystyle Sin N}$ это начальный символ.

Грамматика формально определяется как упорядоченная четверка ${displaystyle }$ . Такую формальную грамматику часто называют система перезаписи или грамматика фразовой структуры в литературе.^[3]^[4]

пример

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

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

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

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

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

S -> cAd

А -> а | ab

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

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

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

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

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

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

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

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

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

[1]

[2]

[3]

[4]