Формальная грамматика - Formal grammar - Wikipedia

В формальная теория языка, а грамматика (когда контекст не указан, часто называется формальная грамматика для ясности) описывает, как формировать строки из языка алфавит которые действительны в соответствии с языком синтаксис. Грамматика не описывает значение строк или что с ними можно сделать в любом контексте - только в их форме. Формальная грамматика определяется как набор правила производства за струны на формальном языке.

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

Формальная грамматика - это набор правил для перезаписи строк, а также «начальный символ», с которого начинается перезапись. Поэтому грамматика обычно рассматривается как генератор языка. Однако иногда его также можно использовать в качестве основы для "распознаватель "- вычислительная функция, которая определяет, принадлежит ли данная строка языку или является грамматически неверной. Для описания таких распознавателей в теории формального языка используются отдельные формализмы, известные как теория автоматов. Один из интересных результатов теории автоматов заключается в том, что невозможно разработать распознаватель для некоторых формальных языков.^[1]Парсинг это процесс распознавания высказывания (строки в естественных языках) путем разбиения его на набор символов и анализа каждого из них с точки зрения грамматики языка. В большинстве языков значения высказываний структурированы в соответствии с их синтаксисом - практика, известная как композиционная семантика. В результате первый шаг к описанию значения высказывания на языке - это разбить его по частям и посмотреть на его анализируемую форму (известную как его дерево синтаксического анализа в информатике, и как ее глубокая структура в порождающая грамматика ).

История

Панини трактат Астадяй дает формальные производственные правила и определения для описания формальной грамматики санскрит.^[2] Существуют различные варианты использования терминов «форма» и «формализм», которые со временем менялись, в зависимости от полей, с которыми контактировал соответствующий автор. Исторический обзор концепции дан в ^[3]

Вводный пример

Грамматика в основном состоит из набора правил преобразования строк. (Если оно Только состоит из этих правил, это было бы система полутхуэ.) Чтобы сгенерировать строку на языке, нужно начать со строки, состоящей только из одного начальный символ. В правила производства затем применяются в любом порядке, пока строка, которая не содержит ни начального символа, ни назначенного нетерминальные символы производится. Производственное правило применяется к строке путем замены одного вхождения левой части производственного правила в строке правой частью этого производственного правила (ср. работа теоретического Машина Тьюринга ). Язык, сформированный грамматикой, состоит из всех отдельных строк, которые могут быть созданы таким образом. Любая конкретная последовательность производственных правил в начальном символе дает отдельную строку на языке. Если существуют существенно разные способы создания одной и той же строки, грамматика называется двусмысленный.

Например, предположим, что алфавит состоит из а и б, начальный символ S, и у нас есть следующие производственные правила:

1. ${\displaystyle S\rightarrow aSb}$

2. ${\displaystyle S\rightarrow ba}$

тогда мы начнем с S, и можете выбрать правило, которое будет применяться к нему. Если мы выберем правило 1, мы получим строку aSb. Если мы затем снова выберем правило 1, мы заменим S с aSb и получим строку aaSbb. Если теперь мы выберем правило 2, мы заменим S с ба и получим строку aababb, и готово. Мы можем описать эту серию вариантов более кратко, используя символы: ${\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}$. Тогда язык грамматики - это бесконечное множество ${\displaystyle \{a^{n}bab^{n}\mid n\geq 0\}=\{ba,abab,aababb,aaababbb,\dotsc \}}$, куда ${\displaystyle a^{k}}$ является ${\displaystyle a}$ повторяется ${\displaystyle k}$ раз (и ${\displaystyle n}$ в частности, представляет собой количество раз, когда применялось правило производства 1).

Формальное определение

Основная статья: Неограниченная грамматика

Синтаксис грамматик

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

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

${\displaystyle (\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}}$

куда ${\displaystyle {*}}$ это Клини звезда оператор и ${\displaystyle \cup }$ обозначает установить союз. То есть каждое производственное правило преобразуется из одной строки символов в другую, где первая строка («заголовок») содержит произвольное количество символов при условии, что по крайней мере один из них является нетерминальным. В случае, если вторая струна («тело») состоит исключительно из пустой строкой - т.е. что он вообще не содержит символов - его можно обозначать специальными обозначениями (часто ${\displaystyle \Lambda }$, е или же ${\displaystyle \epsilon }$) во избежание путаницы.

• Выдающийся символ ${\displaystyle S\in N}$ это начальный символ, также называемый символ предложения.

Грамматика формально определяется как кортеж ${\displaystyle (N,\Sigma ,P,S)}$. Такую формальную грамматику часто называют система перезаписи или грамматика фразовой структуры в литературе.^[6][7]

Некоторые математические конструкции относительно формальных грамматик

Функционирование грамматики можно определить в терминах отношений на строках:

• Учитывая грамматику ${\displaystyle G=(N,\Sigma ,P,S)}$, бинарное отношение ${\displaystyle {\underset {G}{\Rightarrow }}}$ (произносится как «G происходит за один шаг») на струнах в ${\displaystyle (\Sigma \cup N)^{*}}$ определяется:

  ${\displaystyle x{\underset {G}{\Rightarrow }}y\iff \exists u,v,p,q\in (\Sigma \cup N)^{*}:(x=upv)\wedge (p\rightarrow q\in P)\wedge (y=uqv)}$

• Соотношение ${\displaystyle {\overset {*}{\underset {G}{\Rightarrow }}}}$ (произносится как G выводится за ноль или более шагов) определяется как рефлексивное переходное замыкание из ${\displaystyle {\underset {G}{\Rightarrow }}}$
• а сентенциальная форма является членом ${\displaystyle (\Sigma \cup N)^{*}}$ который может быть получен за конечное число шагов из начального символа ${\displaystyle S}$; то есть сентенциальная форма является членом ${\displaystyle \left\{w\in (\Sigma \cup N)^{*}\mid S{\overset {*}{\underset {G}{\Rightarrow }}}w\right\}}$. Сентенциальная форма, не содержащая нетерминальных символов (т. Е. Является членом ${\displaystyle \Sigma ^{*}}$) называется приговор.^[8]
• то язык из ${\displaystyle G}$, обозначенный как ${\displaystyle {\boldsymbol {L}}(G)}$, определяется как все те предложения, которые могут быть получены за конечное число шагов из начального символа ${\displaystyle S}$; то есть набор ${\displaystyle \left\{w\in \Sigma ^{*}\mid S{\overset {*}{\underset {G}{\Rightarrow }}}w\right\}}$.

Обратите внимание, что грамматика ${\displaystyle G=(N,\Sigma ,P,S)}$ эффективно система полутхуэ ${\displaystyle (N\cup \Sigma ,P)}$, точно так же переписывая строки; единственная разница в том, что мы выделяем конкретные нетерминальный символы, которые должны быть перезаписаны в правилах перезаписи, и интересны только перезаписи от назначенного начального символа ${\displaystyle S}$ к строкам без нетерминальных символов.

Пример

Для этих примеров формальные языки указаны с помощью обозначение построителя множеств.

Учитывайте грамматику ${\displaystyle G}$ куда ${\displaystyle N=\left\{S,B\right\}}$, ${\displaystyle \Sigma =\left\{a,b,c\right\}}$, ${\displaystyle S}$ - начальный символ, а ${\displaystyle P}$ состоит из следующих производственных правил:

1. ${\displaystyle S\rightarrow aBSc}$

2. ${\displaystyle S\rightarrow abc}$

3. ${\displaystyle Ba\rightarrow aB}$

4. ${\displaystyle Bb\rightarrow bb}$

Эта грамматика определяет язык ${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$ куда ${\displaystyle a^{n}}$ обозначает строку п последовательный ${\displaystyle a}$с. Таким образом, язык - это набор строк, состоящих из 1 или более ${\displaystyle a}$'s, за которым следует такое же количество ${\displaystyle b}$'s, за которым следует такое же количество ${\displaystyle c}$с.

Некоторые примеры образования строк в ${\displaystyle L(G)}$ находятся:

• ${\displaystyle {\boldsymbol {S}}{\underset {2}{\Rightarrow }}{\boldsymbol {abc}}}$
• ${\displaystyle {\begin{aligned}{\boldsymbol {S}}&{\underset {1}{\Rightarrow }}{\boldsymbol {aBSc}}\\&{\underset {2}{\Rightarrow }}aB{\boldsymbol {abc}}c\\&{\underset {3}{\Rightarrow }}a{\boldsymbol {aB}}bcc\\&{\underset {4}{\Rightarrow }}aa{\boldsymbol {bb}}cc\end{aligned}}}$
• ${\displaystyle {\begin{aligned}{\boldsymbol {S}}&{\underset {1}{\Rightarrow }}{\boldsymbol {aBSc}}{\underset {1}{\Rightarrow }}aB{\boldsymbol {aBSc}}c\\&{\underset {2}{\Rightarrow }}aBaB{\boldsymbol {abc}}cc\\&{\underset {3}{\Rightarrow }}a{\boldsymbol {aB}}Babccc{\underset {3}{\Rightarrow }}aaB{\boldsymbol {aB}}bccc{\underset {3}{\Rightarrow }}aa{\boldsymbol {aB}}Bbccc\\&{\underset {4}{\Rightarrow }}aaaB{\boldsymbol {bb}}ccc{\underset {4}{\Rightarrow }}aaa{\boldsymbol {bb}}bccc\end{aligned}}}$

(Примечание к обозначениям: ${\displaystyle P{\underset {i}{\Rightarrow }}Q}$ читает "Строка п генерирует строку Q посредством производства я", а созданная часть каждый раз выделяется жирным шрифтом.)

Иерархия Хомского

Основная статья: Иерархия Хомского

Когда Ноам Хомский первые формализованные порождающие грамматики в 1956 г.,^[4] он разделил их на типы, теперь известные как Иерархия Хомского. Разница между этими типами в том, что они имеют все более строгие производственные правила и, следовательно, могут выражать меньше формальных языков. Два важных типа: контекстно-свободные грамматики (Тип 2) и регулярные грамматики (Тип 3). Языки, которые можно описать с помощью такой грамматики, называются контекстно-свободные языки и обычные языки, соответственно. Хотя гораздо менее мощный, чем неограниченная грамматика (Тип 0), который фактически может выражать любой язык, который может быть принят Машина Тьюринга, эти два ограниченных типа грамматик используются чаще всего, потому что для них можно эффективно реализовать синтаксические анализаторы.^[9] Например, все обычные языки можно распознать по конечный автомат, а для полезных подмножеств контекстно-свободных грамматик существуют хорошо известные алгоритмы для генерации эффективных Парсеры LL и Парсеры LR для распознавания соответствующих языков, которые генерируют эти грамматики.

Бесконтекстные грамматики

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

Язык ${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$ определенный выше не является контекстно-независимым языком, и это можно строго доказать с помощью лемма о прокачке для контекстно-свободных языков, но например язык ${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$ (не менее 1 ${\displaystyle a}$ за которым следует такое же количество ${\displaystyle b}$'s) не зависит от контекста, так как это может быть определено грамматикой ${\displaystyle G_{2}}$ с ${\displaystyle N=\left\{S\right\}}$, ${\displaystyle \Sigma =\left\{a,b\right\}}$, ${\displaystyle S}$ начальный символ и следующие правила производства:

1. ${\displaystyle S\rightarrow aSb}$

2. ${\displaystyle S\rightarrow ab}$

Контекстно-свободный язык можно распознать в ${\displaystyle O(n^{3})}$ время (видеть Обозначение Big O ) с помощью такого алгоритма, как Алгоритм Эрли. То есть для каждого контекстно-свободного языка можно построить машину, которая принимает на вход строку и определяет в ${\displaystyle O(n^{3})}$ время, является ли строка членом языка, где ${\displaystyle n}$ - длина строки.^[10] Детерминированные контекстно-свободные языки - это подмножество контекстно-свободных языков, которые можно распознать за линейное время.^[11] Существуют различные алгоритмы, нацеленные либо на этот набор языков, либо на какое-то его подмножество.

Обычные грамматики

В регулярные грамматики, левая часть снова представляет собой только один нетерминальный символ, но теперь правая часть также ограничена. Правая сторона может быть пустой строкой, или одним терминальным символом, или одним терминальным символом, за которым следует нетерминальный символ, но ничего больше. (Иногда используется более широкое определение: можно разрешить более длинные строки терминалов или одиночные нетерминалы без чего-либо еще, делая языки легче обозначить при этом все еще определяя тот же класс языков.)

Язык ${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$ определенное выше не является регулярным, но язык ${\displaystyle \left\{a^{n}b^{m}\mid m,n\geq 1\right\}}$ (не менее 1 ${\displaystyle a}$ за которым следует как минимум 1 ${\displaystyle b}$, где числа могут быть разными) равно, как это может быть определено грамматикой ${\displaystyle G_{3}}$ с ${\displaystyle N=\left\{S,A,B\right\}}$, ${\displaystyle \Sigma =\left\{a,b\right\}}$, ${\displaystyle S}$ начальный символ и следующие правила производства:

1. ${\displaystyle S\rightarrow aA}$
2. ${\displaystyle A\rightarrow aA}$
3. ${\displaystyle A\rightarrow bB}$
4. ${\displaystyle B\rightarrow bB}$
5. ${\displaystyle B\rightarrow \epsilon }$

Все языки, созданные с помощью обычной грамматики, можно распознать в ${\displaystyle O(n)}$ время на конечный автомат. Хотя на практике обычные грамматики обычно выражаются с помощью обычные выражения, некоторые формы регулярных выражений, используемые на практике, строго не генерируют регулярные языки и не демонстрируют линейную производительность распознавания из-за этих отклонений.

Другие формы порождающих грамматик

Многие расширения и вариации исходной иерархии формальных грамматик Хомского были разработаны как лингвистами, так и компьютерными специалистами, как правило, либо для увеличения их выразительной силы, либо для облегчения их анализа или анализа. Некоторые формы разработанных грамматик включают:

• Грамматики, примыкающие к дереву повысить выразительность обычных порождающих грамматик, позволяя правилам перезаписи оперировать разбирать деревья а не просто струны.^[12]
• Аффикс грамматики^[13] и грамматики атрибутов^[14][15] позволяют дополнять правила перезаписи семантическими атрибутами и операциями, полезными как для повышения выразительности грамматики, так и для создания практических инструментов языкового перевода.

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

Не путать с Рекурсивный язык.

Рекурсивная грамматика - это грамматика, которая содержит производственные правила, которые рекурсивный. Например, грамматика для контекстно-свободный язык является леворекурсивный если существует нетерминальный символ А которые можно пропустить через производственные правила, чтобы получить строку с А как крайний левый символ.^[16] Пример рекурсивной грамматики - предложение в предложении, разделенное двумя запятыми.^[17] Все типы грамматик в Иерархия окое может быть рекурсивным.^{[нужна цитата ]}

Аналитические грамматики

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

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

• Языковая машина непосредственно реализует неограниченные аналитические грамматики. Правила подстановки используются для преобразования ввода для получения результатов и поведения. Система также может производить lm-диаграмма, который показывает, что происходит, когда применяются правила неограниченной аналитической грамматики.
• Язык синтаксического анализа сверху вниз (TDPL): крайне минималистский формализм аналитической грамматики, разработанный в начале 1970-х годов для изучения поведения нисходящие парсеры.^[18]
• Грамматики ссылок: форма аналитической грамматики, разработанная для лингвистика, который определяет синтаксическую структуру, исследуя позиционные отношения между парами слов.^[19][20]
• Анализ грамматик выражений (PEG): более недавнее обобщение TDPL, разработанное для практических выразительность потребности язык программирования и компилятор писатели.^[21]

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

• Абстрактное синтаксическое дерево
• Адаптивная грамматика
• Неоднозначная грамматика
• Форма Бэкуса – Наура (БНФ)
• Категориальная грамматика
• Конкретное синтаксическое дерево
• Расширенная форма Бэкуса – Наура (EBNF)
• Грамматическая структура
• L-система
• Ложбан
• Постканоническая система
• Грамматика формы
• Правильная формула

Рекомендации

1. Медуна, Александр (2014), Формальные языки и вычисления: модели и их приложения, CRC Press, стр. 233, г. ISBN  9781466513457. Подробнее об этом см. неразрешимая проблема.
2. "Биография Панини". www-history.mcs.st-andrews.ac.uk. Архивировано из оригинал на 2018-08-15.
3. МакЭлвенни Дж (2019). МакЭлвенни Дж (ред.). Форма и формализм в лингвистике (pdf). Берлин: Language Science Press. Дои:10.5281 / zenodo.2654375. ISBN  978-3-96110-182-5.
4. Хомский, Ноам (сентябрь 1956). «Три модели для описания языка». Сделки IRE по теории информации. 2 (3): 113–124. Дои:10.1109 / TIT.1956.1056813.
5. Хомский, Ноам (1957). Синтаксические структуры. Гаага: Mouton.
6. Гинзбург, Сеймур (1975). Алгебраические и теоретико-автоматные свойства формальных языков. Северная Голландия. С. 8–9. ISBN  978-0-7204-2506-2.
7. Харрисон, Майкл А. (1978). Введение в теорию формального языка. Ридинг, Массачусетс: издательство Addison-Wesley Publishing Company. п. 13. ISBN  978-0-201-02955-0.
8. Формы предложения, Контекстно-свободные грамматики, Дэвид Матушек
9. Грун, Дик и Джейкобс, Сериэль Х., Методы синтаксического анализа - Практическое руководство, Эллис Хорвуд, Англия, 1990 год.
10. Эрли, Джей "Эффективный алгоритм анализа без контекста," Коммуникации ACM, Vol. 13 No. 2, pp. 94-102, февраль 1970.
11. Кнут, Д. Э. (Июль 1965 г.). «О переводе языков слева направо» (PDF). Информация и контроль. 8 (6): 607–639. Дои:10.1016 / S0019-9958 (65) 90426-2. Архивировано из оригинал (PDF) 15 марта 2012 г.. Получено 29 мая 2011.
12. Джоши, Аравинд К., и другие., "Грамматики для дерева," Журнал компьютерных систем науки, Vol. 10 No. 1, pp. 136-163, 1975.
13. Костер, Корнелис Х. А., «Грамматики аффиксов», в Реализация Алгола 68, North Holland Publishing Company, Амстердам, стр. 95-109, 1971.
14. Кнут, Дональд Э. "Семантика контекстно-свободных языков," Математическая теория систем, Vol. 2 No. 2, pp. 127-145, 1968.
15. Кнут, Дональд Э., «Семантика контекстно-свободных языков (исправление)», Математическая теория систем, Vol. 5 № 1, стр 95-96, 1971.
16. Заметки по теории формального языка и синтаксическому анализу Джеймс Пауэр, факультет компьютерных наук Ирландского национального университета, Мейнут Мейнут, графство Килдэр, Ирландия.JPR02
17. Боренштейн, Сет (27 апреля 2006 г.). "Певчие птицы тоже разбираются в грамматике". Northwest Herald. п. 2 - через Newspapers.com.
18. Бирман Александр, Схема распознавания TMG Докторская диссертация, Принстонский университет, факультет электротехники, февраль 1970 г.
19. Слейтор, Дэниел Д. и Темперли, Дэви "Разбор английского языка с помощью грамматики ссылок, "Технический отчет CMU-CS-91-196, Компьютерные науки Университета Карнеги-Меллона, 1991.
20. Слейтор, Дэниел Д. и Темперли, Дэви, «Анализ английского языка с помощью грамматики ссылок», Третий международный семинар по технологиям парсинга, 1993. (Доработанная версия вышеприведенного отчета.)
21. Форд, Брайан, Парсинг Packrat: практический алгоритм линейного времени с возвратом, Магистерская работа, Массачусетский технологический институт, сентябрь 2002 г.

внешняя ссылка