Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Март 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) ( |
В информатике , терминальные и нетерминальные символы являются лексическими элементами , используемых при определении в правиле производства , составляющее формальную грамматику . Терминальные символы - это элементарные символы языка, определенные формальной грамматикой. Нетерминальные символы (или синтаксические переменные ) заменяются группами терминальных символов в соответствии с правилами продукции.
Терминалы и нетерминалы конкретной грамматики - это два непересекающихся множества .
Терминальные символы [ править ]
Терминальные символы - это буквальные символы, которые могут появляться в выходных данных правил продукции формальной грамматики и которые не могут быть изменены с помощью правил грамматики. Рекурсивное применение правил к исходной строке символов обычно заканчивается окончательной выходной строкой, состоящей только из оконечных символов.
Рассмотрим грамматику, определяемую двумя правилами. Использование графических знаков, взаимодействующих друг с другом:
- Символ
ר
может статьди
- Символ
ר
может статьд
Вот д
символ терминала, потому что не существует правила, которое бы изменило его на что-то другое. С другой стороны, ר
есть два правила, которые могут его изменить, поэтому он нетерминальный. Формальный язык определен или генерируются с помощью конкретной грамматики это набор строк , которые могут быть произведены с помощью грамматики и состоит только из терминальных символов .
Нетерминальные символы [ править ]
Нетерминальные символы - это те символы, которые можно заменить. Их также можно назвать просто синтаксическими переменными . Формальная грамматика включает в себя начальный символ , обозначенный член набора нетерминалов, из которого все строки в языке могут быть получены путем последовательного применения производственных правил. Фактически, язык, определяемый грамматикой, - это в точности набор терминальных строк, которые могут быть получены таким образом.
Бесконтекстные грамматики - это те грамматики, в которых левая часть каждого производственного правила состоит только из одного нетерминального символа. Это ограничение нетривиально; не все языки могут быть созданы с помощью контекстно-свободных грамматик. Те, что могут, называются контекстно-свободными языками. Это как раз те языки, которые может распознать недетерминированный автомат нажатия . Контекстно-свободные языки являются теоретической основой синтаксиса большинства языков программирования .
Правила производства [ править ]
Грамматика определяется производственными правилами (или просто «продукцией»), которые определяют, какие символы могут заменять какие другие символы; эти правила могут использоваться для генерации строк или их синтаксического анализа. У каждого такого правила есть голова , или левая сторона, которая состоит из строки, которую можно заменить, и тело , или правая часть, которая состоит из строки, которая может ее заменить. Часто правила записываются в виде голова → тело ; например, правило a → b указывает, что a можно заменить на b .
В классической формализации порождающих грамматик, впервые предложенной Ноамом Хомским в 1950-х годах [1] [2], грамматика G состоит из следующих компонентов:
- Конечное множество из нетерминальных символов .
- Конечное множество из терминальных символов , который не пересекается с .
- Конечное множество из продукционных правил , каждое правило вида
- где - оператор звезды Клини и обозначает объединение множеств , поэтому представляет ноль или более символов и означает один нетерминальный символ. То есть каждое правило продукции преобразует одну строку символов в другую, где первая строка содержит по крайней мере один нетерминальный символ. В том случае, если тело состоит только из пустой строкой -ie, что он не содержит ни одного символа на все это может быть обозначено с помощью специальной записи (часто , или ) для того , чтобы избежать путаницы.
- Выдающийся символ, который является стартовым символом .
Грамматика формально определяется как упорядоченная четверка . Такую формальную грамматику в литературе часто называют системой переписывания или грамматикой структуры фраз . [3] [4]
Пример [ править ]
Например, следующее представляет собой целое число (которое может быть подписано), выраженное в варианте формы Бэкуса – Наура :
< цифра > :: = '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. CS1 maint: обескураженный параметр ( ссылка )
- ^ Харрисон, Майкл А. (1978). Введение в теорию формального языка . Ридинг, Массачусетс: издательство Addison-Wesley Publishing Company. С. 13 . ISBN 0-201-02955-3. CS1 maint: обескураженный параметр ( ссылка )