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

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

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

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

История [ править ]

Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Февраль 2018 г. )

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

Вводный пример [ править ]

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

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

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

В следующих примерах, терминал символы и Ь , а символ пуска 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-х годах ^[4]^[5], грамматика G состоит из следующих компонентов:

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

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

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

{*}

\cup

\Lambda

\epsilon

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

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

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

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

С учетом грамматики бинарное отношение (произносится как «G происходит за один шаг») в строках в определяется следующим образом: $G=(N,\Sigma ,P,S)$ ${\underset {G}{\Rightarrow }}$ $(\Sigma \cup N)^{*}$
$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 происходит в ноль или более стадий ) определяется как рефлексивном транзитивного замыкания из ${\overset {*}{\underset {G}{\Rightarrow }}}$ ${\underset {G}{\Rightarrow }}$
а сентенциальная форма - это член, который может быть получен за конечное число шагов от начального символа ; то есть сентенциальная форма является членом . Сентенциальная форма, не содержащая нетерминальных символов (т.е. являющаяся членом ), называется предложением . ^[8] $(\Sigma \cup N)^{*}$ $S$ $\left\{w\in (\Sigma \cup N)^{*}\mid S{\overset {*}{\underset {G}{\Rightarrow }}}w\right\}$ $\Sigma ^{*}$
язык из , обозначается как , определяются как все те предложения , которые могут быть получены в конечном числе шагов из начального символа ; то есть набор . $G$ ${\boldsymbol {L}}(G)$ $S$ $\left\{w\in \Sigma ^{*}\mid S{\overset {*}{\underset {G}{\Rightarrow }}}w\right\}$

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

Пример [ править ]

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

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

1.

S\rightarrow aBSc

2.

S\rightarrow abc

3.

Ba\rightarrow aB

4.

Bb\rightarrow bb

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

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

${\boldsymbol {S}}{\underset {2}{\Rightarrow }}{\boldsymbol {abc}}$
${\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}}$
${\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

», и сгенерированная часть каждый раз выделяется жирным шрифтом.)

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

Иерархия Хомского [ править ]

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

Бесконтекстные грамматики [ править ]

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

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

1.

S\rightarrow aSb

2.

S\rightarrow ab

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

Обычные грамматики [ править ]

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

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

$S\rightarrow aA$
$A\rightarrow aA$
$A\rightarrow bB$
$B\rightarrow bB$
$B\rightarrow \epsilon$

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

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

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

Смежные с деревом грамматики увеличивают выразительность обычных порождающих грамматик, позволяя правилам перезаписи работать с деревьями синтаксического анализа, а не только со строками. ^[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.
^ McElvenny J (2019). МакЭлвенни Дж (ред.). Форма и формализм в лингвистике (pdf) . Берлин: Language Science Press. DOI : 10.5281 / zenodo.2654375 . ISBN 978-3-96110-182-5.
^ a b Хомский, Ноам (сентябрь 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.
↑ Knuth, 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
^ Borenstein, Сет (27 апреля 2006). «Певчие птицы тоже разбираются в грамматике» . Северо-западный вестник . п. 2 - через Newspapers.com.
↑ Бирман, Александр, Схема распознавания TMG , докторская диссертация, Принстонский университет, кафедра электротехники, февраль 1970 г.
^ Слеатор, Дэниел Д. и Темперли, Дэви, « Анализ английского языка с помощью грамматики ссылок », Технический отчет CMU-CS-91-196, Компьютерные науки Университета Карнеги-Меллона, 1991.
^ Sleator, Daniel D. & Темперли, Дэви, "Синтаксический английский с Link Grammar," Третий международный семинар по PARSING технологий , 1993. (пересмотренный вариант вышеупомянутого доклада.)
^ Форд, Брайан, Packrat Parsing: Практический алгоритм линейного времени с возвратом , магистерская диссертация, Массачусетский технологический институт, сентябрь 2002 г.

Внешние ссылки [ править ]

[1] Медуна, Александр (2014), Формальные языки и вычисления: модели и их приложения , CRC Press, стр. 233, ISBN 9781466513457. Подробнее об этом см. В разделе « Неразрешимая проблема» .

[2] "Биография Панини" . www-history.mcs.st-andrews.ac.uk . Архивировано из оригинала на 2018-08-15.

[mcelvenny-3] McElvenny J (2019). МакЭлвенни Дж (ред.). Форма и формализм в лингвистике (pdf) . Берлин: Language Science Press. DOI : 10.5281 / zenodo.2654375 . ISBN 978-3-96110-182-5.

[Chomsky1956-4] Хомский, Ноам (сентябрь 1956 г.). «Три модели для описания языка». Сделки IRE по теории информации . 2 (3): 113–124. DOI : 10.1109 / TIT.1956.1056813 .

[Chomsky1957-5] Хомский, Ноам (1957). Синтаксические структуры . Гаага: Мутон .

[6] Гинзбург, Сеймур (1975). Алгебраические и теоретико-автоматные свойства формальных языков . Северная Голландия. С. 8–9. ISBN 978-0-7204-2506-2.

[7] Харрисон, Майкл А. (1978). Введение в теорию формального языка . Ридинг, Массачусетс: издательство Addison-Wesley Publishing Company. п. 13. ISBN 978-0-201-02955-0.

[8] Формы предложения , контекстно-свободные грамматики, Дэвид Матушек

[Grune&Jacobs1990-9] Grune, Dick & Jacobs, Ceriel H., Разбор Techniques - Практическое руководство , Эллис Хорвуд, Англия, 1990.

[Earley1970-10] Эрли, Джей, " Эффективный алгоритм анализа без контекста ", Связь ACM , Vol. 13 No. 2, pp. 94-102, февраль 1970.

[11] Knuth, DE (июль 1965 г.). «О переводе языков слева направо» (PDF) . Информация и контроль . 8 (6): 607–639. DOI : 10.1016 / S0019-9958 (65) 90426-2 . Архивировано из оригинального (PDF) 15 марта 2012 года . Проверено 29 мая 2011 года .

[JoshiEtAl1975-12] Джоши, Аравинд К. и др. , " Грамматики дополнительных деревьев ", Журнал компьютерных систем , Vol. 10 No. 1, pp. 136-163, 1975.

[Koster1971-13] Костер, Корнелис Х.А., «Аффиксные грамматики», в « Реализация Алгола 68» , издательство North Holland Publishing Company, Амстердам, с. 95-109, 1971.

[Knuth1968-14] Кнут, Дональд Э., " Семантика контекстно-свободных языков ", Математическая теория систем , Vol. 2 No. 2, pp. 127-145, 1968.

[Knuth1971-15] Кнут, Дональд Э., «Семантика контекстно-свободных языков (исправление)», « Математическая теория систем» , Vol. 5 № 1, стр 95-96, 1971.

[16] Заметки по теории формального языка и синтаксическому анализу , Джеймс Пауэр, факультет компьютерных наук Национального университета Ирландии, Мейнут Мейнут, графство Килдэр, Ирландия. JPR02

[17] Borenstein, Сет (27 апреля 2006). «Певчие птицы тоже разбираются в грамматике» . Северо-западный вестник . п. 2 - через Newspapers.com.

[Birman1970-18] Бирман, Александр, Схема распознавания TMG , докторская диссертация, Принстонский университет, кафедра электротехники, февраль 1970 г.

[Sleater&Temperly1991-19] Слеатор, Дэниел Д. и Темперли, Дэви, « Анализ английского языка с помощью грамматики ссылок », Технический отчет CMU-CS-91-196, Компьютерные науки Университета Карнеги-Меллона, 1991.

[Sleater&Temperly1993-20] Sleator, Daniel D. & Темперли, Дэви, "Синтаксический английский с Link Grammar," Третий международный семинар по PARSING технологий , 1993. (пересмотренный вариант вышеупомянутого доклада.)

[21] Форд, Брайан, Packrat Parsing: Практический алгоритм линейного времени с возвратом , магистерская диссертация, Массачусетский технологический институт, сентябрь 2002 г.

[1]