В теории формальных языков , а грамматика (если контекст не задан, часто называют формальной грамматики для ясности) описывает , как формировать строки из языка в алфавите , которые действительны в зависимости от языка синтаксиса . Грамматика не описывает значение строк или то, что с ними можно делать в любом контексте - только их форму. Формальная грамматика определяется как набор продукционных правил для строк в формальном языке.
Теория формального языка, дисциплина, изучающая формальные грамматики и языки, является разделом прикладной математики . Его приложения находят в теоретической информатике , теоретической лингвистике , формальной семантике , математической логике и других областях.
Формальная грамматика - это набор правил для перезаписи строк, а также «начальный символ», с которого начинается перезапись. Поэтому грамматика обычно рассматривается как генератор языка. Однако иногда его также можно использовать в качестве основы для « распознавателя » - функции в вычислениях, которая определяет, принадлежит ли данная строка языку или является грамматически неверной. Для описания таких распознавателей в теории формального языка используются отдельные формализмы, известные как теория автоматов . Один из интересных результатов теории автоматов заключается в том, что невозможно разработать распознаватель для некоторых формальных языков. [1] Синтаксический анализ - это процесс распознавания высказывания (строки в естественных языках) путем разбиения его на набор символов и анализа каждого из них на соответствие грамматике языка. В большинстве языков значения высказываний структурированы в соответствии с их синтаксисом - практика, известная как композиционная семантика . В результате первый шаг к описанию значения высказывания на языке - это разбить его по частям и посмотреть на его анализируемую форму (известную как дерево синтаксического анализа в информатике и как его глубокая структура в порождающей грамматике ).
История
Панините трактат «S Astadyayi дает формальные правила и определение производства для описания формальной грамматики санскрита . [2] Существуют различные варианты использования терминов «форма» и «формализм», которые со временем менялись, в зависимости от полей, с которыми контактировал соответствующий автор. Исторический обзор концепции дан в [3].
Вводный пример
Грамматика в основном состоит из набора производственных правил , правил переписывания для преобразования строк. Каждое правило определяет замену определенной строки (ее левой части ) другой (ее правой части ). Правило может быть применено к каждой строке, содержащей ее левую часть, и создает строку, в которой вхождение этой левой части заменено ее правой частью.
В отличие от системы полутхуэ , которая полностью определяется этими правилами, грамматика дополнительно различает два вида символов: нетерминальные и конечные символы; каждая левая часть должна содержать хотя бы один нетерминальный символ. Он также выделяет специальный нетерминальный символ, называемый начальным символом .
Язык, сгенерированный грамматикой, определяется как набор всех строк без каких-либо нетерминальных символов, которые могут быть сгенерированы из строки, состоящей из одного начального символа, путем (возможно, повторного) применения его правил любым возможным способом. Если есть существенно разные способы создания одной и той же строки, грамматика называется неоднозначной .
В следующих примерах, терминал символы и Ь , а символ пуска S .
Пример 1
Предположим, у нас есть следующие производственные правила:
- 1.
- 2.
затем мы начинаем с S и можем выбрать правило, которое будет применяться к нему. Если мы выберем правило 1, мы получим строку aSb . Если мы затем снова выберем правило 1, мы заменим S на aSb и получим строку aaSbb . Если теперь мы выберем правило 2, мы заменим S на ba и получим строку aababb , и все готово. Мы можем записать эту серию вариантов более кратко, используя символы:.
Язык грамматики - бесконечное множество , где является повторяется раз (и в частности, представляет количество раз, когда применялось правило 1). Эта грамматика не зависит от контекста (только отдельные нетерминалы отображаются слева) и однозначна.
Примеры 2 и 3
Предположим, что правила таковы:
- 1.
- 2.
- 3.
Эта грамматика не является контекстно-свободной из-за правила 3 и неоднозначна из-за множества способов использования правила 2 для генерации последовательностей с.
Однако генерируемый им язык - это просто набор всех непустых строк, состоящих из s и / или с. Это легко увидеть: чтобы сгенерировать из , дважды используйте правило 2, чтобы сгенерировать , затем правило 1 дважды и правило 3 один раз, чтобы произвести . Это означает, что мы можем сгенерировать произвольные непустые последовательностиs, а затем замените каждый из них на или же как нам угодно.
В качестве альтернативы тот же самый язык может быть создан с помощью контекстно-свободной однозначной грамматики; например, обычная грамматика с правилами
- 1.
- 2.
- 3.
- 4.
Формальное определение
Синтаксис грамматик
В классической формализации порождающих грамматик, впервые предложенной Ноамом Хомским в 1950-х годах [4] [5], грамматика G состоит из следующих компонентов:
- Конечное множество Н из нетерминальных символов , то есть не пересекаются со строками , образованных из G .
- Конечное множество из терминальных символов , которая пересекается с N .
- Конечное множество Р из продукционных правил , каждое правило вида
- где - звездный оператор Клини и обозначает объединение множеств . То есть каждое производственное правило преобразуется из одной строки символов в другую, где первая строка («заголовок») содержит произвольное количество символов при условии, что по крайней мере один из них является нетерминальным. В случае, если вторая строка («тело») состоит исключительно из пустой строки, т. Е. Вообще не содержит символов, она может быть обозначена специальным обозначением (часто , e или ) во избежание путаницы.
- Выдающийся символ это начальный символ , также называемый символом предложения .
Грамматика формально определяется как кортеж . Такую формальную грамматику в литературе часто называют системой переписывания или грамматикой структуры фраз . [6] [7]
Некоторые математические конструкции относительно формальных грамматик
Работа грамматики может быть определена в терминах отношений на строках:
- Учитывая грамматику , бинарное отношение (произносится как «G происходит за один шаг») на струнах в определяется:
- Соотношение (произносится как G вытекает в ноль или более шагов ) определяется как рефлексивном транзитивного замыкания из
- а сентенциальная форма является членом который может быть получен за конечное число шагов из начального символа ; то есть сентенциальная форма является членом. Формула предложения, не содержащая нетерминальных символов (т. Е. Является членом) называется предложением . [8]
- язык из, обозначаемый как , определяется как все те предложения, которые могут быть получены за конечное число шагов из начального символа ; то есть набор.
Обратите внимание, что грамматика фактически является системой полу-Туэ , точно так же переписывая строки; единственное отличие состоит в том, что мы выделяем определенные нетерминальные символы, которые должны быть перезаписаны в правилах перезаписи, и заинтересованы только в перезаписи от назначенного начального символа к строкам без нетерминальных символов.
Пример
В этих примерах формальные языки указаны с использованием нотации построителя множеств .
Учитывайте грамматику где , , - начальный символ, а состоит из следующих производственных правил:
- 1.
- 2.
- 3.
- 4.
Эта грамматика определяет язык где обозначает строку из n последовательныхс. Таким образом, язык - это набор строк, состоящих из 1 или более's, за которым следует такое же количество 's, за которым следует такое же количество с.
Некоторые примеры образования строк в находятся:
- (Примечание к обозначениям: читает "Строка P генерирует строку Q посредством продукции i ", и сгенерированная часть каждый раз выделяется жирным шрифтом.)
Иерархия Хомского
Когда Ноам Хомский впервые формализовал порождающие грамматики в 1956 году [4], он классифицировал их по типам, теперь известным как иерархия Хомского . Разница между этими типами заключается в том, что они имеют все более строгие производственные правила и поэтому могут выражать меньше формальных языков. Двумя важными типами являются контекстно-свободные грамматики (Тип 2) и обычные грамматики (Тип 3). Языки, которые можно описать с помощью такой грамматики, называются контекстно-свободными языками и обычными языками соответственно. Хотя эти два ограниченных типа грамматик гораздо менее мощны, чем неограниченные грамматики (тип 0), которые фактически могут выражать любой язык, который может быть принят машиной Тьюринга , используются, потому что синтаксические анализаторы для них могут быть эффективно реализованы. [9] Так , например, все обычные языки могут быть признаны конечным автоматом , и полезных подмножества контекстно-свободными грамматик существует хорошо известные алгоритмы , чтобы генерировать эффективные анализаторы LL и LR парсер для признания соответствующих языков этих грамматики генерируют .
Бесконтекстные грамматики
Контекстно-свободная грамматика является грамматикой , в которой левая сторона каждого правила производства состоит только из одного нетерминального символа. Это ограничение нетривиально; не все языки могут быть созданы с помощью контекстно-свободных грамматик. Те, которые могут, называются контекстными языками .
Язык определенный выше не является контекстно-свободным языком, и это можно строго доказать с помощью леммы о перекачке для контекстно-свободных языков , но, например, язык (не менее 1 за которым следует такое же количество 's) не зависит от контекста, так как это может быть определено грамматикой с участием , , начальный символ и следующие производственные правила:
- 1.
- 2.
Контекстно-свободный язык можно распознать в время ( см. обозначение Big O ) с помощью такого алгоритма, как распознаватель Эрли . То есть для каждого контекстно-свободного языка можно построить машину, которая принимает строку в качестве входных данных и определяет в время, является ли строка членом языка, где - длина строки. [10] Детерминированные контекстно-свободные языки - это подмножество контекстно-свободных языков, которые можно распознать за линейное время. [11] Существуют различные алгоритмы, нацеленные либо на этот набор языков, либо на какое-то его подмножество.
Обычные грамматики
В обычных грамматиках левая часть снова представляет собой только один нетерминальный символ, но теперь правая часть также ограничена. Правая сторона может быть пустой строкой, или одним конечным символом, или одним конечным символом, за которым следует нетерминальный символ, но ничего больше. (Иногда используется более широкое определение: можно разрешить более длинные строки терминалов или одиночные нетерминалы без чего-либо еще, что упрощает обозначение языков, но при этом определяет тот же класс языков.)
Язык определенное выше не является регулярным, но язык (не менее 1 за которым следует как минимум 1 , где числа могут быть разными) есть, как это может быть определено грамматикой с участием , , начальный символ и следующие производственные правила:
Все языки, созданные с помощью обычной грамматики, могут быть распознаны в время с помощью конечного автомата. Хотя на практике регулярные грамматики обычно выражаются с помощью регулярных выражений , некоторые формы регулярных выражений, используемые на практике, строго не генерируют регулярные языки и не демонстрируют линейное распознавание из-за этих отклонений.
Другие формы порождающих грамматик
Многие расширения и вариации исходной иерархии формальных грамматик Хомского были разработаны как лингвистами, так и компьютерными специалистами, как правило, либо для увеличения их выразительной силы, либо для облегчения их анализа или синтаксического анализа. Некоторые формы разработанных грамматик включают:
- Смежные с деревом грамматики увеличивают выразительность обычных порождающих грамматик, позволяя правилам перезаписи работать с деревьями синтаксического анализа, а не только со строками. [12]
- Грамматики присоединения [13] и грамматики атрибутов [14] [15] позволяют дополнить правила перезаписи семантическими атрибутами и операциями, полезными как для увеличения выразительности грамматики, так и для создания практических инструментов языкового перевода.
Рекурсивные грамматики
Рекурсивная грамматика - это грамматика, которая содержит рекурсивные производственные правила . Например, грамматика для контекстно-свободного языка является леворекурсивной, если существует нетерминальный символ A, который может быть пропущен через производственные правила для получения строки с A в качестве крайнего левого символа. [16] Пример рекурсивной грамматики - предложение в предложении, разделенное двумя запятыми. [17] Все типы грамматик в иерархии Окое могут быть рекурсивными. [ необходима цитата ]
Аналитические грамматики
Хотя существует огромное количество литературы по алгоритмам синтаксического анализа , большинство этих алгоритмов предполагают, что анализируемый язык изначально описывается с помощью порождающей формальной грамматики, и что цель состоит в том, чтобы преобразовать эту порождающую грамматику в работающий синтаксический анализатор. Строго говоря, порождающая грамматика никоим образом не соответствует алгоритму, используемому для синтаксического анализа языка, и различные алгоритмы имеют разные ограничения на форму производственных правил, которые считаются правильно сформированными.
Альтернативный подход состоит в том, чтобы формализовать язык в первую очередь в терминах аналитической грамматики, которая более точно соответствует структуре и семантике синтаксического анализатора языка. Примеры формализмов аналитической грамматики включают следующее:
- Language Machine напрямую реализует неограниченные аналитические грамматики. Правила подстановки используются для преобразования ввода для получения результатов и поведения. Система также может создавать lm-диаграмму , которая показывает, что происходит, когда применяются правила неограниченной аналитической грамматики.
- Язык синтаксического анализа сверху вниз (TDPL): крайне минималистичный формализм аналитической грамматики, разработанный в начале 1970-х годов для изучения поведения синтаксических анализаторов сверху вниз . [18]
- Грамматики ссылок : форма аналитической грамматики, разработанная для лингвистики , которая выводит синтаксическую структуру, исследуя позиционные отношения между парами слов. [19] [20]
- Грамматики синтаксического анализа (PEG): более недавнее обобщение TDPL, разработанное с учетом практических потребностей в выразительности языков программирования и разработчиков компиляторов . [21]
Смотрите также
- Абстрактное синтаксическое дерево
- Адаптивная грамматика
- Неоднозначная грамматика
- Форма Бэкуса – Наура (БНФ)
- Категориальная грамматика
- Конкретное синтаксическое дерево
- Расширенная форма Бэкуса – Наура (EBNF)
- Грамматическая структура
- L-система
- Ложбан
- Постканоническая система
- Грамматика формы
- Правильная формула
Рекомендации
- ^ Медуна, Александр (2014), Формальные языки и вычисления: модели и их приложения , CRC Press, стр. 233, ISBN 9781466513457. Для получения дополнительной информации см. Неразрешимую проблему .
- ^ "Биография Панини" . www-history.mcs.st-andrews.ac.uk . Архивировано из оригинала на 2018-08-15.
- ^ МакЭлвенни Дж (2019). МакЭлвенни Дж (ред.). Форма и формализм в лингвистике (pdf) . Берлин: Language Science Press. DOI : 10.5281 / zenodo.2654375 . ISBN 978-3-96110-182-5.
- ^ а б Хомский, Ноам (сентябрь 1956). «Три модели для описания языка». Сделки IRE по теории информации . 2 (3): 113–124. DOI : 10.1109 / TIT.1956.1056813 .
- ^ Хомский, Ноам (1957). Синтаксические структуры . Гаага: Мутон .
- ^ Гинзбург, Сеймур (1975). Алгебраические и теоретико-автоматные свойства формальных языков . Северная Голландия. С. 8–9. ISBN 978-0-7204-2506-2.
- ^ Харрисон, Майкл А. (1978). Введение в теорию формального языка . Ридинг, Массачусетс: издательство Addison-Wesley Publishing Company. п. 13. ISBN 978-0-201-02955-0.
- ^ Формы предложения , контекстно-свободные грамматики, Дэвид Матушек
- ^ Grune, Dick & Jacobs, Ceriel H., Разбор Techniques - Практическое руководство , Эллис Хорвуд, Англия, 1990.
- ^ Эрли, Джей, " Эффективный алгоритм анализа без контекста ", Связь ACM , Vol. 13 No. 2, pp. 94-102, февраль 1970.
- ^ Кнут, DE (июль 1965 г.). «О переводе языков слева направо» (PDF) . Информация и контроль . 8 (6): 607–639. DOI : 10.1016 / S0019-9958 (65) 90426-2 . Архивировано из оригинального (PDF) 15 марта 2012 года . Проверено 29 мая 2011 года .
- ^ Джоши, Аравинд К. и др. , " Грамматики дополнительных деревьев ", Журнал компьютерных систем , Vol. 10 No. 1, pp. 136-163, 1975.
- ↑ Костер, Корнелис Х.А., «Аффиксные грамматики», в « Реализация Алгола 68» , издательство North Holland Publishing Company, Амстердам, с. 95-109, 1971.
- ^ Кнут, Дональд Э., " Семантика контекстно-свободных языков ", Математическая теория систем , Vol. 2 No. 2, pp. 127-145, 1968.
- ^ Кнут, Дональд Э., "Семантика контекстно-свободных языков (исправление)", " Математическая теория систем" , Vol. 5 № 1, стр 95-96, 1971.
- ^ Заметки по теории формального языка и синтаксическому анализу , Джеймс Пауэр, факультет компьютерных наук Национального университета Ирландии, Мейнут Мейнут, графство Килдэр, Ирландия. JPR02
- ^ Боренштейн, Сет (27 апреля 2006 г.). «Певчие птицы тоже разбираются в грамматике» . Северо-западный вестник . п. 2 - через Newspapers.com.
- ↑ Бирман, Александр, Схема распознавания TMG , докторская диссертация, Принстонский университет, кафедра электротехники, февраль 1970 г.
- ^ Слеатор, Дэниел Д. и Темперли, Дэви, « Анализ английского языка с помощью грамматики ссылок », Технический отчет CMU-CS-91-196, Компьютерные науки Университета Карнеги-Меллона, 1991.
- ^ Sleator, Daniel D. & Темперли, Дэви, "Синтаксический английский с Link Grammar," Третий международный семинар по PARSING технологий , 1993. (пересмотренный вариант вышеупомянутого доклада.)
- ^ Форд, Брайан, Packrat Parsing: Практический алгоритм линейного времени с возвратом , магистерская диссертация, Массачусетский технологический институт, сентябрь 2002 г.