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

редактировать

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

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

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

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

Содержание

1 История
2 Вводный пример
3 Формальное определение
- 3.1 Синтаксис грамматик
- 3.2 Некоторые математические конструкции относительно формальных грамматик
- 3.3 Пример
4 The Chomsky иерархия
- 4.1 Контекстно-свободные грамматики
- 4.2 Регулярные грамматики
- 4.3 Другие формы генеративных грамматик
- 4.4 Рекурсивные грамматики
5 Аналитические грамматики
6 См. также
7 Ссылки
8 Внешние ссылки

История

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

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

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

Например, предположим, что алфавит состоит из a и b, начальным символом является S, и у нас есть следующая продукция правила:

S → a S b {\ displaystyle S \ rightarrow aSb}

S \ rightarrow aSb

S → b a {\ displaystyle S \ rightarrow ba}

S \ rightarrow ba

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

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

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

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

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

(Σ ∪ N) ∗ N (Σ ∪ N) ∗ → (Σ ∪ N) ∗ {\ displaystyle (\ Sigma \ cup N) ^ {*} N (\ Sigma \ cup N) ^ { *} \ rightarrow (\ Sigma \ cup N) ^ {*}}

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

где

∗ {\ displaystyle {*}}

{*}

- это оператор звезды Клини, а

∪ {\ displaystyle \ cup}

\ cup

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

Λ {\ displaystyle \ Lambda}

\ Lambda

, e или

ϵ {\ displaystyle \ epsilon}

\ epsilon

), чтобы избежать путаницы.

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

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

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

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

Дана грамматика $G = (N, Σ, P, S) {\ displaystyle G = (N, \ Sigma, P, S)}$ $G = (N, \ Sigma, P, S)$ , двоичное отношение $⇒ G {\ displaystyle {\ underset {G} {\ Rightarrow}}}$ ${\ underset {G} {\ Rightarrow}}$ (произносится как «G выводится за один шаг») в строках в $(Σ ∪ N) ∗ {\ displaystyle (\ Sigma \ cup N) ^ {*}}$ $(\ Sigma \ cup N) ^ {{*}}$ определяется следующим образом:
$x ⇒ G y ⟺ ∃ u, v, p, q ∈ (Σ ∪ N) ∗: (x = upv) ∧ (p → q ∈ P) ∧ (y = uqv) {\ displaystyle x {\ underset {G} {\ Rightarrow}} y \ iff \ существует u, v, p, q \ in (\ Sigma \ cup N) ^ {*} :( x = upv) \ wedge (p \ rightarrow q \ in P) \ wedge (y = uqv)}$ ${\ displaystyle x {\ underset {G} {\ Rightarrow}} y \ iff \ существует 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}}}}$ ${\ overset {*} {\ underset {G} {\ Rightarrow}}}$ (произносится как G, производный от нуля или более шагов) определяется как рефлексивный тра nситивное замыкание из $⇒ G {\ displaystyle {\ underset {G} {\ Rightarrow}}}$ ${\ underset {G} {\ Rightarrow}}$
сентенциальная форма является членом $(Σ ∪ N) ∗ {\ displaystyle (\ Sigma \ cup N) ^ {*}}$ $(\ Sigma \ cup N) ^ {*}$ , который может быть получен за конечное число шагов из начального символа $S {\ displaystyle S}$ $S$ ; то есть сентенциальная форма является членом ${w ∈ (Σ ∪ N) ∗ ∣ S ⇒ G ∗ w} {\ displaystyle \ left \ {w \ in (\ Sigma \ cup N) ^ {*} \ mid S {\ overset {*} {\ underset {G} {\ Rightarrow}}} w \ right \}}$ $\ left \ {w \ in (\ Sigma \ cup N) ^ {*} \ mid S {\ overset {*} {\ underset {G} {\ Rightarrow}}} w \ right \}$ . Сентенциальная форма, которая не содержит нетерминальных символов (т.е. является членом $Σ ∗ {\ displaystyle \ Sigma ^ {*}}$ $\ Sigma ^ {*}$ ), называется предложением.
язык $G {\ displaystyle G}$ $G$ , обозначаемый как $L (G) {\ displaystyle {\ boldsymbol {L}} (G)}$ ${\ boldsymbol {L}} (G)$ , определяется как все те предложения, которые могут быть получены за конечное число шагов от начального символа $S {\ displaystyle S}$ $S$ ; то есть множество ${w ∈ Σ ∗ ∣ S ⇒ G ∗ w} {\ displaystyle \ left \ {w \ in \ Sigma ^ {*} \ mid S {\ overset {*} {\ underset {G } {\ Rightarrow}}} w \ right \}}$ $\ left \ {w \ in \ Sigma ^ {* } \ mid S {\ overset {*} {\ underset {G} {\ Rightarrow}}} w \ right \}$ .

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

Пример

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

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

S → a B S c {\ displaystyle S \ rightarrow aBSc}

S \ rightarrow aBSc

S → a b c {\ displaystyle S \ rightarrow abc}

S \ rightarrow abc

В a → a B {\ displaystyle Ba \ rightarrow aB}

Ba \ rightarrow aB

B b → bb {\ displaystyle Bb \ rightarrow bb}

Bb \ rightarrow bb

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

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

$S ⇒ 2 abc {\ displaystyle {\ boldsymbol {S}} {\ underset {2} {\ Rightarrow}} {\ boldsymbol {abc}}}$ ${\ boldsymbol {S}} {\ underset {2} {\ Rightarrow}} {\ boldsymbol {abc}}$
$S ⇒ 1 a BS c ⇒ 2 a B abcc ⇒ 3 aa B bcc ⇒ 4 aabbcc {\ displaystyle {\ begin {align} {\ 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 \ конец {выровнен}}}$ ${\ begin {выровнено } {\ boldsymbol {S}} {\ underset {1} {\ Rightarrow}} {\ boldsymbol {aBSc}} \\ {\ underset {2} {\ Rightarrow}} aB {\ bold символ {abc}} c \\ {\ underset {3} {\ Rightarrow}} a {\ boldsymbol {aB}} bcc \\ {\ underset {4} {\ Rightarrow}} aa {\ boldsymbol {bb} } cc \ end {align}}$
$S ⇒ 1 a BS c ⇒ 1 a B a BS cc ⇒ 2 a B a B abccc ⇒ 3 aa BB abccc ⇒ 3 aa B a B bccc ⇒ 3 aaa BB bccc ⇒ 4 aaa B bbccc ⇒ 4 aaabbbccc {\ displaystyle {\ begin {align} {\ 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} {\ Right arrow}} 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 {align}}}$ ${\ begin {align} {\ 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 {\ подмножество {4} {\ Rightarrow}} aaa {\ boldsymbol {bb}} bccc \ end {align}}$

(Примечание к обозначениям:

P ⇒ i Q {\ displaystyle P {\ underset {i} {\ Rightarrow}} Q}

P {\ underset {i} {\ Rightarrow}} Q

читает: «Строка P генерирует строку Q посредством производства i», и сгенерированная часть каждый раз выделяется жирным шрифтом.)

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

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

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

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

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

S → a S b {\ displaystyle S \ rightarrow aSb}

S \ rightarrow aSb

S → ab {\ displaystyle S \ rightarrow ab}

S \ rightarrow ab

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

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

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

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

$S → a A {\ displaystyle S \ rightarrow aA}$ $S \ rightarrow aA$
$A → a A {\ displaystyle A \ rightar строка aA}$ $A \ rightarrow aA$
$A → b B {\ displaystyle A \ rightarrow bB}$ $A \ rightarrow bB$
$B → b B {\ displaystyle B \ rightarrow bB}$ $B \ rightarrow bB$
$B → ϵ {\ displaystyle B \ rightarrow \ epsilon}$ $B \ rightarrow \ epsilon$

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

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

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

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

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

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

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

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

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

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

См. Также

Ссылки

^Медуна, Александр (2014), Формальные языки и вычисления: модели и их приложения, CRC Press, стр. 233, ISBN 9781466513457. Подробнее об этом см. неразрешимая проблема.
^«Биография Панини». www-history.mcs.st-andrews.ac.uk. Архивировано из оригинала 15.08.2018.
^McElvenny J (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.
^Sentential Forms, Context-Free Grammars, Дэвид Матушек
^Grune, Dick Jacobs, Ceriel H., Методы синтаксического анализа - Практическое руководство, Эллис Хорвуд, Англия, 1990.
^Эрли, Джей, «Эффективный алгоритм анализа без контекста,« Связь ACM, Vol. 13 No. 2, pp. 94-102, February 1970.
^Knuth, D.E. (июль 1965). «О переводе языков слева направо» (PDF). Информация и контроль. 8 (6): 607–639. DOI : 10.1016 / S0019-9958 (65) 90426-2. Архивировано из оригинального (PDF) 15 марта 2012 г. Дата обращения 29 мая 2011 г. CS1 maint: ref = harv (ссылка )
^Джоши, Аравинд К. и др., «Грамматики дополнительных деревьев,« Журнал компьютерных систем », том 10, № 1, стр. 136–163, 1975.
^Костер, Корнелис Х.А.,« Грамматики присоединения », в реализации Алгола 68, North Holland Publishing Company, Амстердам, стр. 95-109, 1971.
^Кнут, Дональд Э. "Семантика контекстно-свободных языков," Теория математических систем, том 2, № 2, pp. 127-145, 1968.
^Кнут, Дональд Э., «Семантика контекстно-свободных языков (исправление)», «Теория математических систем», том 5, № 1, стр. 95-96, 1971.
^Заметки по теории и синтаксическому анализу формального языка, Джеймс Пауэр, факультет компьютерных наук Ирландского национального университета, Мэйнут Мейнут, графство Килдэр, Ирландия.
^Боренштейн, Сет (27 апреля 2006 г.). " Певчие птицы тоже понимают грамматику ". Northwest Herald. Стр. 2 - через Newspapers.com.
^Бирман, Александр, The TMG Recognit ion Schema, докторская диссертация, Принстонский университет, кафедра электротехники, февраль 1970 г.
^Слейатор, Дэниел Д. и Темперли, Дэви, «Анализ английского языка с помощью грамматики ссылок,« Технические Отчет CMU-CS-91-196, Компьютерные науки Университета Карнеги-Меллона, 1991.
^Слеатор, Дэниел Д. и Темперли, Дэви, «Анализ английского языка с помощью грамматики ссылок», Третий международный семинар по технологиям синтаксического анализа, 1993 г. (пересмотренный вариант) версия вышеприведенного отчета.)
^Форд, Брайан, Парсинг Packrat: практический алгоритм линейного времени с возвратом, магистерская диссертация, Массачусетский технологический институт, сентябрь 2002 г.