Jump to content

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

(Перенаправлено с Нетерминала )
Строка «собака съела кость» была создана с использованием правил производства, которые заменяли нетерминальные символы терминальными. [1]

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

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

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

[ редактировать ]

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

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

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

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

Схема 1. Строка Б Б Б Б была сформирована грамматикой, определенной заданными правилами производства. Эта грамматика может создавать строки с любым количеством символов Б.

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

[ редактировать ]

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

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

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

[ редактировать ]

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

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

  • Конечное множество N символов нетерминальных .
  • Конечное множество Σ , терминальных символов не пересекающееся с N .
  • Конечное множество P правил производства , каждое правило вида
где Клини звездный оператор , а ∪ обозначает объединение множеств , поэтому представляет ноль или более символов, а N означает один нетерминальный символ. То есть каждое продукционное правило отображается из одной строки символов в другую, где первая строка содержит хотя бы один нетерминальный символ. В случае, если тело состоит исключительно из пустой строки [примечание 1] , его можно обозначать специальными обозначениями (часто Λ , e или ε ), чтобы избежать путаницы.
  • Выдающийся символ это стартовый символ .

Грамматика формально определяется как упорядоченная четверка . Такую формальную грамматику часто называют системой переписывания или грамматикой фразовой структуры . в литературе [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]

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

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

См. также

[ редактировать ]

Примечания

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


  1. ^ Розен, К.Х. (2012). Дискретная математика и ее приложения. МакГроу-Хилл. страницы 847-851
  2. ^ Хомский, Ноам (1956). «Три модели описания языка». IRE Транзакции по теории информации . 2 (3): 113–123. дои : 10.1109/TIT.1956.1056813 . S2CID   19519474 .
  3. ^ Хомский, Ноам (1957). Синтаксические структуры . Гаага: Мутон .
  4. ^ Гинзбург, Сеймур (1975). Алгебраические и теоретико-автоматные свойства формальных языков . Северная Голландия. стр. 8–9. ISBN  0-7204-2506-9 .
  5. ^ Харрисон, Майкл А. (1978). Введение в теорию формального языка . Ридинг, Массачусетс: Издательство Addison-Wesley. стр. 13 . ISBN  0-201-02955-3 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 276b879d01af74259e5b07f8d3c13232__1721223780
URL1:https://arc.ask3.ru/arc/aa/27/32/276b879d01af74259e5b07f8d3c13232.html
Заголовок, (Title) документа по адресу, URL1:
Terminal and nonterminal symbols - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)