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

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

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

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

История

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

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

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

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

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

В следующих примерах, терминал символы и Ь , а символ пуска 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 а ^ {к}}$${\ 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 из , дважды используйте правило 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-х годах, грамматика G состоит из следующих компонентов:

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

${\ Displaystyle (\ Sigma \ чашка N) ^ {*} N (\ Sigma \ cup N) ^ {*} \ rightarrow (\ Sigma \ cup N) ^ {*}}$

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

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

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

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

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

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

  ${\ displaystyle x {\ underset {G} {\ Rightarrow}} y \ iff \ существует u, v, p, q \ in (\ Sigma \ cup N) ^ {*} :( x = upv) \ wedge (p \ rightarrow q \ in P) \ клин (y = uqv)}$

• отношение (читается как G происходит в ноль или более стадий ) определяется как рефлексивном транзитивного замыкания из${\ Displaystyle {\ overset {*} {\ underset {G} {\ Rightarrow}}}}$${\ Displaystyle {\ underset {G} {\ Rightarrow}}}$
• а сентенциальная форма - это член, который может быть получен за конечное число шагов от начального символа ; то есть сентенциальная форма является членом . Сентенциальная форма, не содержащая нетерминальных символов (т.е. являющаяся членом ), называется предложением .${\ Displaystyle (\ Sigma \ чашка 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 \ чашка \ Sigma, P)}$${\ displaystyle S}$

Пример

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

Рассмотрим грамматику , где , , является символом начала, и состоит из следующих правил производства: ${\ displaystyle G}$${\ Displaystyle N = \ влево \ {S, B \ вправо \}}$${\ 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 а ^ {п}}$${\ displaystyle a}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle c}$

Вот несколько примеров образования строк в : ${\ Displaystyle L (G)}$

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

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

Когда Ноам Хомский впервые формализовал порождающие грамматики в 1956 году, он классифицировал их по типам, которые теперь известны как иерархия Хомского . Разница между этими типами заключается в том, что они имеют все более строгие правила производства и, следовательно, могут выражать меньше формальных языков. Двумя важными типами являются контекстно-свободные грамматики (Тип 2) и обычные грамматики (Тип 3). Языки, которые можно описать с помощью такой грамматики, называются контекстно-свободными языками и обычными языками соответственно. Хотя эти два ограниченных типа грамматик гораздо менее мощны, чем неограниченные грамматики (тип 0), которые фактически могут выражать любой язык, который может быть принят машиной Тьюринга , используются, потому что синтаксические анализаторы для них могут быть эффективно реализованы. Например, все регулярные языки могут быть признаны конечного автомата и полезные подмножества контекстно-свободных грамматик существуют хорошо известные алгоритмы для генерации эффективных парсеров 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 = \ влево \ {S \ вправо \}}$${\ Displaystyle \ Sigma = \ влево \ {а, б \ вправо \}}$${\ displaystyle S}$

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

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

Контекстно-свободный язык может быть распознан во времени ( см. Нотацию Big O ) с помощью такого алгоритма, как распознаватель Эрли . То есть для каждого контекстно-свободного языка может быть построена машина, которая принимает строку в качестве входных данных и определяет во времени, является ли строка членом языка, где - длина строки. Детерминированные контекстно-свободные языки - это подмножество контекстно-свободных языков, которые можно распознать за линейное время. Существуют различные алгоритмы, нацеленные либо на этот набор языков, либо на какое-то его подмножество. ${\ Displaystyle О (п ^ {3})}$ ${\ Displaystyle О (п ^ {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 = \ влево \ {S, A, B \ right \}}$${\ Displaystyle \ Sigma = \ влево \ {а, б \ вправо \}}$${\ 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 О (п)}$

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

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

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

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

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

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

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

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

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

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

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

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