Категориальная грамматика - Categorial grammar

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

Основы

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

Категориальная грамматика имеет некоторые общие черты с просто типизированное лямбда-исчисление.В то время как лямбда-исчисление имеет только один тип функции ${ displaystyle A rightarrow B}$ , категориальная грамматика обычно имеет два типа функций: один применяется слева, а другой - справа. Например, простая категориальная грамматика может иметь два типа функций ${ Displaystyle B / A , !}$ и ${ displaystyle A backslash B}$ .Первый, ${ Displaystyle B / A , !}$ , это тип фразы, которая приводит к фразе типа ${ Displaystyle B , !}$ когда за ним (справа) следует фраза типа ${ Displaystyle А , !}$ .Второй, ${ Displaystyle A обратная косая черта B , !}$ , это тип фразы, которая приводит к фразе типа ${ Displaystyle B , !}$ когда предшествует (слева) фраза типа ${ Displaystyle А , !}$ .

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

Первый и самый простой вид категориальной грамматики называется базовой категориальной грамматикой или иногда AB-грамматикой (после Айдукевич и Бар-Гилель Дан набор примитивных типов. ${ displaystyle { text {Prim}} , !}$ , позволять ${ displaystyle { text {Tp}} ({ text {Prim}}) , !}$ быть набором типов, построенным из примитивных типов. В основном случае это наименьший набор такой, что ${ displaystyle { text {Prim}} substeq { text {Tp}} ({ text {Prim}})}$ и если ${ displaystyle X, Y in { text {Tp}} ({ text {Prim}})}$ тогда ${ displaystyle (X / Y), (Y обратная косая черта X) in { text {Tp}} ({ text {Prim}})}$ .Думайте об этом как о чисто формальных выражениях, свободно генерируемых из примитивных типов; любая семантика будет добавлена позже. Некоторые авторы предполагают фиксированный бесконечный набор примитивных типов, используемых всеми грамматиками, но, делая примитивные типы частью грамматики, вся конструкция остается конечной.

Базовая категориальная грамматика - это кортеж ${ displaystyle ( Sigma, { text {Prim}}, S, треугольникleft)}$ куда ${ Displaystyle Sigma , !}$ конечный набор символов, ${ displaystyle { text {Prim}} , !}$ - конечный набор примитивных типов, и ${ displaystyle S in { text {Tp}} ({ text {Prim}})}$ .

Соотношение ${ Displaystyle треугольникleft}$ это лексика, которая связывает типы с символами ${ Displaystyle ( треугольникleft) substeq { text {Tp}} ({ text {Prim}}) times Sigma}$ .Поскольку лексикон конечен, его можно определить, перечислив набор пар, например ${ displaystyle ТИП треугольникleft { текст {символ}}}$ .

Такая грамматика английского языка может иметь три основных типа. ${ displaystyle (N, NP, { text {и}} S) , !}$ , присвоение считать существительные тип ${ Displaystyle N , !}$ , завершите существительные фразы типа ${ Displaystyle NP , !}$ , и предложения типа ${ Displaystyle S , !}$ .Затем прилагательное мог иметь тип ${ Displaystyle N / N , !}$ , потому что, если за ним следует существительное, тогда вся фраза будет существительным. Аналогично определитель имеет тип ${ Displaystyle NP / N , !}$ , потому что он образует законченную именную фразу, когда за ней следует существительное. глаголы иметь тип ${ displaystyle NP backslash S}$ , а переходные глаголы типа ${ displaystyle (NP обратная косая черта S) / NP}$ . Тогда строка слов является предложением, если она имеет общий тип. ${ Displaystyle S , !}$ .

Например, возьмем строку «плохой мальчик все устроил». Теперь "the" и "that" являются определяющими, "мальчик" и "беспорядок" - существительные, "bad" - прилагательное, "made" - переходный глагол, поэтому лексикон будет { ${ Displaystyle NP / N треугольникleft { text {the}}}$ , ${ displaystyle NP / N треугольникleft { text {that}}}$ , ${ Displaystyle N треугольникleft { text {мальчик}}}$ , ${ Displaystyle N треугольникleft { текст {беспорядок}}}$ , ${ displaystyle N / N треугольникleft { text {bad}}}$ , ${ Displaystyle (НП обратная косая черта S) / НП треугольникleft { текст {made}}}$ }.

и последовательность типов в строке

${ displaystyle {{ text {the}} atop {NP / N,}} {{ text {bad}} atop {N / N,}} {{ text {boy}} atop {N, }} {{ text {made}} atop {(NP backslash S) / NP,}} {{ text {that}} atop {NP / N,}} {{ text {mess}} наверху {N}}}$

теперь найдите функции и соответствующие аргументы и уменьшите их в соответствии с двумя правила вывода ${ Displaystyle X leftarrow X / Y, ; Y}$ и ${ Displaystyle X leftarrow Y, ; Y обратная косая черта X}$ :

${ Displaystyle. qquad NP / N, ; N / N, ; N, ; (NP обратная косая черта S) / NP, ; underbrace {NP / N, ; N}}$
${ Displaystyle. qquad NP / N, ; N / N, ; N, ; underbrace {(NP backslash S) / NP, quad NP}}$
${ displaystyle. qquad NP / N, ; underbrace {N / N, ; N}, qquad (NP backslash S)}$
${ Displaystyle. qquad underbrace {NP / N, ; quad N}, ; qquad (NP backslash S)}$
${ displaystyle. qquad qquad underbrace {NP, ; qquad (NP backslash S)}}$
${ Displaystyle. qquad qquad qquad quad ; ; ; S}$

Дело в том, что результат ${ Displaystyle S , !}$ означает, что строка является предложением, а последовательность сокращений показывает, что она должна быть проанализирована как (((плохой мальчик)) (сделал (тот беспорядок))).

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

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

Исчисление Ламбека

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

Для исчисления Ламбека существует оператор конкатенации типов ${ Displaystyle звезда , !}$ , так что ${ displaystyle { text {Prim}} substeq { text {Tp}} ({ text {Prim}})}$ и если ${ displaystyle X, Y in { text {Tp}} ({ text {Prim}})}$ тогда ${ displaystyle (X / Y), (X обратная косая черта Y), (X star Y) in { text {Tp}} ({ text {Prim}})}$ .

Исчисление Ламбека состоит из нескольких правил вывода, которые определяют, как утверждения включения типов могут быть получены. В следующих правилах латинские буквы верхнего регистра обозначают типы, а греческие буквы верхнего регистра обозначают последовательности типов. Секвенция формы ${ Displaystyle X leftarrow Gamma}$ можно прочитать: строка имеет тип ${ Displaystyle X , !}$ если он состоит из конкатенации строк каждого из типов в ${ Displaystyle Gamma , !}$ . Если тип интерпретируется как набор строк, то ${ displaystyle leftarrow}$ можно интерпретировать как ${ Displaystyle supseteq , !}$ , то есть «включает как подмножество». Горизонтальная линия означает, что включение над линией означает включение под линией.

Процесс начинается с правила Аксиомы, которое не имеет предшественников и просто говорит, что любой тип включает себя.

${ Displaystyle (Аксиома) quad {{} над X leftarrow X}}$

Правило Cut гласит, что включения могут быть составлены.

${ displaystyle (Cut) quad {Z leftarrow Delta X Delta ' qquad X leftarrow Gamma over Z leftarrow Delta Gamma Delta'}}$

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

Цель	Источник
${ Displaystyle ( обратная косая черта leftarrow) quad {Y leftarrow X Gamma над X обратная косая черта Y leftarrow Gamma}}$	${ displaystyle ( leftarrow backslash) quad {Z leftarrow Delta Y Delta ' qquad X leftarrow Gamma over Z leftarrow Delta Gamma (X backslash Y) Delta'}}$
${ Displaystyle (/ leftarrow) quad {Y leftarrow Gamma X над Y / X leftarrow Gamma}}$	${ Displaystyle ( leftarrow /) quad {Z leftarrow Delta Y Delta ' qquad X leftarrow Gamma over Z leftarrow Delta (Y / X) Gamma Delta'}}$
${ displaystyle ( star leftarrow) quad {X leftarrow Gamma qquad Y leftarrow Gamma ' над X star Y leftarrow Gamma Gamma'}}$	${ displaystyle ( leftarrow star) quad {Z leftarrow Delta XY Delta ' over Z leftarrow Delta (X star Y) Delta'}}$

Например, вот вывод от «повышения типа», который гласит, что ${ Displaystyle (B / A) обратная косая черта B leftarrow A}$ . Справа указаны названия правил и используемые замены.

${ displaystyle { dfrac {{ dfrac {} {B leftarrow B}} qquad { dfrac {} {A leftarrow A}}} { dfrac {B leftarrow (B / A), ; ; A} {(B / A) backslash B leftarrow A}}} qquad { begin {matrix} { mbox {(Axioms)}} qquad qquad qquad qquad qquad qquad qquad qquad qquad {} {( leftarrow /) , , [Z = Y = B, X = A, Gamma = (A), Delta = Delta '= ()]} {( backslash leftarrow) , , [Y = B, X = (B / A), Gamma = (A)]} qquad qquad qquad {} end {matrix}}}$

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

Напомним, что контекстно-свободная грамматика это 4-кортеж:

${ Displaystyle G = (V, , Sigma, , :: =, , S)}$ куда

1. ${ Displaystyle V ,}$ конечный набор нетерминалы или же переменные.

2. ${ Displaystyle Sigma ,}$ конечный набор терминальные символы.

3. ${ displaystyle :: = ,}$ конечный набор правила производства, то есть конечное отношение ${ Displaystyle (:: =) substeq V раз (V чашка Sigma) ^ {*}}$ .

4. ${ Displaystyle S ,}$ - начальная переменная.

С точки зрения категориальных грамматик, контекстно-свободная грамматика может рассматриваться как исчисление с набором аксиом специального назначения для каждого языка, но без операторов построения типов и правил вывода, кроме Cut.

В частности, учитывая неконтекстную грамматику, как указано выше, определите категориальную грамматику ${ displaystyle ({ text {Prim}}, , Sigma, , треугольникleft, , S)}$ куда ${ displaystyle { text {Prim}} = V cup Sigma}$ ,и ${ displaystyle { text {Tp}} ({ text {Prim}}) = { text {Prim}} , !}$ . Пусть есть аксиома ${ Displaystyle {х leftarrow х}}$ за каждый символ ${ Displaystyle х в В чашка Sigma}$ , аксиома ${ displaystyle {X leftarrow Gamma}}$ для каждого правила производства ${ Displaystyle Х :: = Гамма , !}$ , словарная статья ${ Displaystyle {с треугольникleft s}}$ для каждого терминального символа ${ displaystyle s in Sigma}$ и Cut для единственного правила. Эта категориальная грамматика генерирует тот же язык, что и данный CFG.

Конечно, это не базовая категориальная грамматика, поскольку у нее есть особые аксиомы, которые зависят от языка; то есть он не лексикализован, а также вообще не использует непримитивные типы.

Чтобы показать, что любой контекстно-свободный язык может быть создан с помощью базовой категориальной грамматики, вспомним, что любой контекстно-свободный язык может быть создан с помощью контекстно-независимой грамматики. Нормальная форма Грейбаха.

Грамматика находится в нормальной форме Грейбаха, если каждое производственное правило имеет вид ${ Displaystyle A :: = sA_ {0} ldots A_ {N-1}}$ , где заглавные буквы - переменные, ${ displaystyle s in Sigma}$ ,и ${ displaystyle N geq 0}$ , то есть правая часть продукции - это один терминальный символ, за которым следует ноль или более (нетерминальных) переменных.

Теперь, имея CFG в нормальной форме Грейбаха, определите базовую категориальную грамматику с примитивным типом для каждой нетерминальной переменной. ${ displaystyle { text {Prim}} = V , !}$ , и с записью в лексиконе ${ Displaystyle A / A_ {N-1} / ldots / A_ {0} треугольникleft s}$ , для каждого производственного правила ${ Displaystyle A :: = sA_ {0} ldots A_ {N-1}}$ Достаточно легко увидеть, что эта базовая категориальная грамматика генерирует тот же язык, что и исходный CFG. Обратите внимание, что лексикон этой грамматики обычно присваивает несколько типов каждому символу.

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

Показать обратное, что каждый язык, созданный грамматикой Ламбека, является контекстно-независимым, гораздо сложнее. Это была открытая проблема в течение почти тридцати лет, с начала 1960-х годов примерно до 1991 года, когда это было доказано Пентусом.

Основная идея, учитывая грамматику Ламбека, ${ displaystyle ({ text {Prim}}, , Sigma, , треугольникleft, , S)}$ построить контекстно-свободную грамматику ${ Displaystyle (V, , Sigma, , :: =, , S)}$ с одинаковым набором терминальных символов, одинаковым начальным символом, с переменными некоторых (не всех) типов ${ Displaystyle V подмножество { текст {Tp}} ({ text {Prim}}) , !}$ , и с производственным правилом ${ Displaystyle T :: = { текст {s}} , !}$ для каждой записи ${ Displaystyle Т треугольникleft { текст {s}}}$ в лексиконе и правилах производства ${ Displaystyle T :: = Gamma , !}$ для определенных секвентов ${ Displaystyle T leftarrow Gamma}$ которые выводимы в исчислении Ламбека.

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

Обозначение

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

В логике стрелки обычно указывают слева направо. В этой статье это соглашение изменено для согласования с нотацией контекстно-свободных грамматик, где единственный нетерминальный символ всегда находится слева. Мы используем символ ${ displaystyle :: =}$ в производственном правиле, как в Форма Бэкуса-Наура. Некоторые авторы используют стрелку, которая, к сожалению, может указывать в любом направлении, в зависимости от того, считается ли грамматика порождающей или распознающей язык.

Некоторые авторы по категориальным грамматикам пишут ${ Displaystyle B обратная косая черта A}$ вместо ${ displaystyle A backslash B}$ . Используемое здесь соглашение следует Ламбеку и алгебре.

Исторические заметки

Основные идеи категориальной грамматики восходят к работе А. Казимеж Айдукевич (в 1935 г.) и Иегошуа Бар-Гилель (в 1953 г.). В 1958 г. Иоахим Ламбек представил синтаксическое исчисление который формализовал функцию конструкторы типов наряду с различными правилами сочетания функций. Это исчисление является предшественникомлинейная логика в том, что это субструктурная логика. Грамматика Монтегю использует специальную синтаксическую систему для английского языка, основанную на принципах категориальной грамматики. Несмотря на то что Монтегю Работа иногда считается синтаксически неинтересной, она способствовала повышению интереса к категориальной грамматике, связывая ее с весьма успешным формальным подходом к естественному языку семантика. Недавние исследования категориальной грамматики были сосредоточены на улучшении синтаксического охвата. Одним из формализмов, которому в последние годы уделяется значительное внимание, является Steedman и Сабольчи с комбинаторно-категориальная грамматика который основан на комбинаторная логика изобретен Моисей Шёнфинкель и Хаскелл Карри.

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

Некоторые определения

Вывод: Вывод - это двоичное дерево, которое кодирует доказательство.
Дерево синтаксического анализа: Дерево синтаксического анализа отображает производную, показывая синтаксическую структуру предложения.
Функтор и аргумент: В приложении с правой (левой) функцией узел типа A B (B / A) называется функтором, а узел типа A называется аргументом.
Структура функтора – аргумента^{[требуется разъяснение ]}

Уточнения категориальной грамматики

Были предложены различные изменения категориальной грамматики для улучшения синтаксического покрытия. Некоторые из наиболее распространенных из них перечислены ниже.

Функции и подкатегории

Большинство систем категориальной грамматики подразделяют на категории. Самый распространенный способ сделать это - пометить их Особенности, Такие как человек, Пол, номер, и напряженный. Иногда таким образом помечаются только атомарные категории. В грамматике Монтегю традиционно разделяют категории функций, используя соглашение о множественных косых чертах, поэтому А / Б и А // Б будут две разные категории функций с левым применением, которые принимают одни и те же аргументы, но могут различаться другими функциями, принимающими их в качестве аргументов.

Состав функций

Правила композиции функций включены во многие категориальные грамматики. Примером такого правила может быть правило, разрешающее конкатенацию составляющих типа А / Б с одним из типов ДО Н.Э создать новую составляющую типа Кондиционер. Семантика такого правила будет просто включать состав задействованных функций. Состав функций важен для категориального учета соединение и экстракция, особенно в том, что касается таких явлений, как поднятие правого узла. Введение функциональной композиции в категориальную грамматику приводит ко многим видам деривационной неоднозначности, которые бессмысленны в том смысле, что они не соответствуют семантическая двусмысленность.

Соединение

Многие категориальные грамматики включают типичное правило конъюнкции общей формы X CONJ X → X, куда Икс это категория. Соединение обычно применяется к нестандартным компонентам, возникающим в результате повышения типа или функционального состава.

Прерывность

Грамматика расширена для обработки языковых явлений, таких как прерывистые идиомы, пропуски и извлечение.

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

дальнейшее чтение

Майкл Мортгат, Логика категориального типа, Глава 2 в J. van Benthem и A. ter Meulen (ред.) Справочник по логике и языку. Эльзевир, 1997 г., ISBN 0-262-22053-9
Войцех Бушковски, Математическая лингвистика и теория доказательств, Глава 12 в J. van Benthem and A. ter Meulen (ред.) Справочник по логике и языку. Эльзевир, 1997 г., ISBN 0-262-22053-9
Герхард Ягер (2005). Анафора и типовая логическая грамматика. Springer. ISBN 978-1-4020-3904-1.
Глин Моррилл (2010). Категориальная грамматика: логический синтаксис, семантика и обработка. Издательство Оксфордского университета. ISBN 978-0-19-958986-9.
Ричард Мут; Кристиан Реторе (2012). Логика категориальных грамматик: дедуктивный анализ синтаксиса и семантики естественного языка. Springer Verlag. ISBN 978-3-642-31554-1.