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

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

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

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

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

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

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

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

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

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

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

В следующих примерах, терминал символы и Ь , а символ пуска S .

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

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

1.

S\rightarrow aSb

2.

S\rightarrow ba

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

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

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

Предположим, что правила таковы:

1.

S\rightarrow a

2.

S\rightarrow SS

3.

aSa\rightarrow b

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

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

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

1.

S\rightarrow aS

2.

S\rightarrow bS

3.

S\rightarrow a

4.

S\rightarrow b

Формальное определение [ править ]

Синтаксис грамматик [ править ]

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

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

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

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

{*}

\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.
^ МакЭлвенни Дж (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 г.
^ Sleator, Daniel D. & Темперли, Дэви, " Синтаксический английский с Link Grammar ," Технический отчет CMU-CS-91-196, Университет КарнегиМеллона Computer Science, 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] МакЭлвенни Дж (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] Sleator, Daniel D. & Темперли, Дэви, " Синтаксический английский с Link Grammar ," Технический отчет CMU-CS-91-196, Университет КарнегиМеллона Computer Science, 1991.

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

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

[1]