Формальная грамматика

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

Структура формального языка

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

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

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

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

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

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

Язык, порожденный грамматикой, определяется как набор всех строк без каких-либо нетерминальных символов, которые могут быть сгенерированы из строки, состоящей из одного начального символа, путем (возможно, повторяющегося) применения ее правил любым возможным способом. Если существуют существенно разные способы генерации одной и той же строки, грамматика называется неоднозначной .

В следующих примерах терминальными символами являются a и b , а начальным символом — S.

Пример 1

Предположим, у нас есть следующие правила производства:

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

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

затем мы начинаем с S и можем выбрать правило, которое будет применяться к нему. Если мы выберем правило 1, мы получим строку aSb . Если затем мы снова выберем правило 1, мы заменим S на aSb и получим строку aaSbb . Если мы теперь выберем правило 2, мы заменим S на ba и получим строку aababb , и все готово. Мы можем записать эту серию выборов более кратко, используя символы: . ${\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}$

Язык грамматики представляет собой бесконечное множество , где повторяется раз (и, в частности , представляет количество раз, когда применялось правило производства 1). Эта грамматика является контекстно-свободной (только отдельные нетерминалы появляются в левой части) и однозначной. ${\displaystyle \{a^{n}bab^{n}\mid n\geq 0\}=\{ba,abab,aababb,aaababbb,\dotsc \}}$ ${\displaystyle a^{k}}$ ${\displaystyle a}$ ${\displaystyle k}$ ${\displaystyle n}$

Примеры 2 и 3

Предположим, что вместо этого действуют следующие правила:

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

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

3. ${\displaystyle aSa\rightarrow b}$

Эта грамматика не является контекстно-свободной из-за правила 3 ​​и неоднозначна из-за множества способов использования правила 2 для генерации последовательностей s . ${\displaystyle S}$

Однако генерируемый им язык представляет собой просто набор всех непустых строк, состоящих из s и/или s. Это легко увидеть: чтобы сгенерировать a из a , дважды используйте правило 2 для генерации , затем дважды правило 1 и один раз правило 3 для создания . Это означает, что мы можем генерировать произвольные непустые последовательности s, а затем заменять каждую из них на или по своему усмотрению. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle S}$ ${\displaystyle SSS}$ ${\displaystyle b}$ ${\displaystyle S}$ ${\displaystyle a}$ ${\displaystyle b}$

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

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

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

3. ${\displaystyle S\rightarrow a}$

4. ${\displaystyle S\rightarrow b}$

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

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

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

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

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

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

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

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

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

Работа грамматики может быть определена в терминах отношений со строками:

• Учитывая грамматику , бинарное отношение (произносится как «G выводится за один шаг») для строк в определяется следующим образом: ${\displaystyle G=(N,\Sigma ,P,S)}$ ${\displaystyle {\underset {G}{\Rightarrow }}}$ ${\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)}$

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

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

Пример

В этих примерах формальные языки указываются с использованием нотации set-builder .

Рассмотрим грамматику , где , , является начальным символом и состоит из следующих правил продукции: ${\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}$

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

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

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

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

Контекстно-свободные грамматики

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

Язык, определенный выше, не является контекстно-свободным языком, и это можно строго доказать с помощью леммы о накачке для контекстно-свободных языков , но, например, язык (по крайней мере 1, за которым следует такое же количество символов) является контекстно-свободным. , как это может быть определено грамматикой с , , начальным символом и следующими производственными правилами: ${\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\}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\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}$

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

Регулярные грамматики

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

Определенный выше язык не является регулярным, но язык (по крайней мере 1 , за которым следует по крайней мере 1 , где числа могут быть разными) является, как его можно определить с помощью грамматики с , , начальным символом и следующими правилами производства : ${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$ ${\displaystyle \left\{a^{n}b^{m}\mid m,n\geq 1\right\}}$ ${\displaystyle a}$ ${\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)}$

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

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

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

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

Рекурсивная грамматика — это грамматика, содержащая рекурсивные правила производства . Например, грамматика контекстно-свободного языка является леворекурсивной, если существует нетерминальный символ A , который можно пропустить через правила производства для создания строки, в которой A является самым левым символом. ^[14] Примером рекурсивной грамматики является предложение внутри предложения, разделенное двумя запятыми. ^[15] Все типы грамматик в иерархии Хомского могут быть рекурсивными.

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

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

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

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

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

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

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

1. Медуна, Александр (2014), Формальные языки и вычисления: модели и их приложения, CRC Press, стр. 233, ISBN 9781466513457. Дополнительную информацию по этой теме см. в разделе «Неразрешимая проблема» .
2. Хомский, Ноам (сентябрь 1956 г.). «Три модели описания языка». IRE Транзакции по теории информации . 2 (3): 113–124. дои : 10.1109/TIT.1956.1056813. S2CID  19519474.
3. Хомский, Ноам (1957). Синтаксические структуры . Гаага: Мутон .
4. Гинзбург, Сеймур (1975). Алгебраические и теоретико-автоматные свойства формальных языков . Северная Голландия. стр. 8–9. ISBN 978-0-7204-2506-2.
5. Харрисон, Майкл А. (1978). Введение в теорию формального языка . Ридинг, Массачусетс: Издательство Addison-Wesley. п. 13. ISBN 978-0-201-02955-0.
6. Формы предложений, Контекстно-свободные грамматики, Дэвид Матушек
7. Грюн, Дик и Джейкобс, Сериэль Х., Методы синтаксического анализа – Практическое руководство , Эллис Хорвуд, Англия, 1990.
8. Эрли, Джей, «Эффективный алгоритм контекстно-свободного анализа», Communications of the ACM , Vol. 13 № 2, стр. 94–102, февраль 1970 г.
9. Кнут, DE (июль 1965 г.). «О переводе языков слева направо». Информация и контроль . 8 (6): 607–639. дои : 10.1016/S0019-9958(65)90426-2.
10. Джоши, Аравинд К. и др. , «Дерево дополнительных грамматик», Journal of Computer Systems Science , Vol. 10 № 1, стр. 136–163, 1975.
11. Костер, Корнелис Х.А., «Аффиксные грамматики», в реализации ALGOL 68 , North Holland Publishing Company, Амстердам, стр. 95-109, 1971.
12. Кнут, Дональд Э., «Семантика контекстно-свободных языков», Теория математических систем , Vol. 2 № 2, стр. 127–145, 1968.
13. Кнут, Дональд Э., «Семантика контекстно-свободных языков (коррекция),» Теория математических систем , Vol. 5 № 1, стр. 95-96, 1971.
14. Заметки по теории формального языка и синтаксическому анализу. Архивировано 28 августа 2017 г. в Wayback Machine , Джеймс Пауэр, факультет компьютерных наук, Национальный университет Ирландии, Мейнут Мейнут, графство Килдэр, Ирландия.JPR02
15. Боренштейн, Сет (27 апреля 2006 г.). «Певчие птицы тоже понимают грамматику». Северо-Западный Вестник . п. 2 – через Newspapers.com.
16. Бирман, Александр, Схема признания TMG , докторская диссертация, Принстонский университет, факультет электротехники, февраль 1970 г.
17. Слиатор, Дэниел Д. и Темперли, Дэви, «Разбор английского языка с помощью грамматики ссылок», Технический отчет CMU-CS-91-196, Компьютерные науки Университета Карнеги-Меллона, 1991.
18. Слиатор, Дэниел Д. и Темперли, Дэви, «Разбор английского языка с помощью грамматики ссылок», Третий международный семинар по технологиям синтаксического анализа , 1993. (Пересмотренная версия приведенного выше отчета.)
19. Форд, Брайан, Анализ Packrat: практический алгоритм линейного времени с обратным отслеживанием , магистерская диссертация, Массачусетский технологический институт, сентябрь 2002 г.

Внешние ссылки