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

Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Март 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{\ displaystyle {} ^ {*}}

{\ Displaystyle \ чашка}

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

{\ displaystyle N}

{\ displaystyle \ Lambda}

{\ displaystyle e}

{\ displaystyle \ epsilon}

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

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

Пример [ править ]

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

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

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

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

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

S -> cAd

А -> а | ab

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

См. Также [ править ]

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

Ссылки [ править ]

^ Хомский, Ноам (1956). «Три модели описания языка». Сделки IRE по теории информации . 2 (2): 113–123. DOI : 10.1109 / TIT.1956.1056813 .
^ Хомский, Ноам (1957). Синтаксические структуры . Гаага: Мутон .
^ Гинзбург, Сеймур (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. DOI : 10.1109 / TIT.1956.1056813 .

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

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

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

[1]