Грамматика ID/LP

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

Например, типичное правило построения фразы, такое как ${\ce {S -> NP \; VP}}$ , что указывает на то, что S-узел доминирует над NP-узлом и VP-узлом и что NP предшествует VP в поверхностной строке. В грамматиках ID/LP это правило будет указывать только на доминирование и оператор линейного приоритета, например: $NP\prec VP$ , тоже будет дано.

Идея впервые стала известна как часть грамматики обобщенной фразовой структуры ; ^[1]^[2] подход ID/LP Grammar также используется в грамматике структуры фраз, управляемой головой , ^[3] лексическая функциональная грамматика и другие унификационные грамматики .

Текущая работа в рамках Минималистской программы также пытается провести различие между доминированием и упорядочением. Например, в недавних работах Ноама Хомского предположено, что, хотя иерархическая структура является результатом операции построения синтаксической структуры Merge , линейный порядок не определяется этой операцией, а является просто результатом экстернализации (устного произношения, или, в в случае языка жестов — ручное подписание). ^[4]^[5]^[6]

Определение доминирования и приоритета

Немедленное доминирование

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

Например, контекстно-свободное правило $A\rightarrow B\ C\ D$ , показывает, что узел с меткой A (материнский узел) немедленно доминирует над узлами с метками B, C и D (дочерние узлы), а узлы с метками B, C и D могут немедленно доминировать узлом с меткой A.

Узел с меткой A немедленно доминирует над узлами B, C и D, а узел с меткой B немедленно доминирует над C' и D'. А также доминирует над С' и D', но не сразу.

Линейный приоритет

Линейный приоритет — это порядок отношений сестринских узлов. Ограничения LP определяют, в каком порядке могут появляться сестринские узлы под одной материнской платой. Узлы, которые появляются раньше в строках, предшествуют своим сестрам. ^[2] ЛП можно отобразить в правилах построения фраз в виде $A\rightarrow B\ C\ D$ это означает, что B предшествует C предшествует D, как показано в дереве ниже.

Правило, имеющее ограничения ID, но не LP, записывается с запятыми между дочерними узлами, например $A\rightarrow B,\ C,\ D$ . Поскольку для дочерних узлов не существует фиксированного порядка, вполне возможно, что все три показанных здесь дерева генерируются по этому правилу.

Альтернативно, эти отношения могут быть выражены через операторы линейного приоритета, такие как $B\prec C$ , что означает, что каждый раз, когда B и C являются сестрами, B должно предшествовать C. ^[2]^[7]

что если К отношениям LP можно применить принцип транзитивности, который означает, $B\prec C$ и $C\prec D$ , затем $B\prec D$ также. Отношения LP асимметричны: если B предшествует C, C никогда не может предшествовать B. Отношения LP, в которых не может быть промежуточных узлов, называются непосредственным приоритетом, тогда как отношения LP, в которых могут быть промежуточные узлы (те, которые получены из принципа транзитивности), являются Говорят, что он имеет слабый приоритет. ^[8]

Грамматичность в грамматиках ID/LP

Чтобы строка была грамматической в грамматике ID/LP, она должна принадлежать локальному поддереву , которое соответствует хотя бы одному правилу ID и всем операторам LP грамматики. Если каждая возможная строка, сгенерированная грамматикой, соответствует этому критерию, то это грамматика ID/LP. Кроме того, чтобы грамматику можно было записать в формате ID/LP, она должна обладать свойством исчерпывающего постоянного частичного упорядочения (ECPO): а именно, чтобы по крайней мере часть отношений ID/LP в одном правиле соблюдалась во всех других правилах. правила. ^[2] Например, набор правил:

(1) $A\rightarrow B\ C\ D$

(2) $B\rightarrow D\ C\ A$

не обладает свойством ECPO, поскольку (1) говорит, что C всегда должно предшествовать D, а (2) говорит, что D всегда должно предшествовать C.

Преимущества грамматик ID/LP

Поскольку операторы LP применяются независимо от контекста правила ID, они позволяют нам делать обобщения по всей грамматике. ^[2]^[7] Например, учитывая утверждение LP $V\prec DP$ , где V является главой VP, это означает, что в любом предложении в любом предложении V всегда будет появляться перед своей сестрой DP. ^[7] в любом контексте, как показано в следующих примерах.

Люси выиграла гонку.

Ава посоветовала Саре прочитать книгу.

Это можно обобщить до правила, действующего для всего английского языка. $X\prec YP$ , где X — начало любой фразы, а YP — ее дополнение . Грамматики, не относящиеся к ID/LP, не способны делать такие обобщения по всей грамматике и поэтому должны повторять ограничения порядка для каждого отдельного контекста. ^[7]

Отделение требований LP от правил ID также объясняет феномен свободного порядка слов в естественном языке. Например, в английском языке можно поставить наречия до или после глагола, и обе строки будут грамматическими. ^[7]

Джон внезапно вскрикнул. Джон внезапно вскрикнул .

Традиционное правило PS потребует двух отдельных правил, но это можно описать одним правилом ID/LP. $VP\rightarrow V,AdvP$ Это свойство грамматик ID/LP позволяет упростить межлингвистические обобщения, описывая специфические языковые различия в порядке составляющих с помощью операторов LP отдельно от правил ID, которые аналогичны для разных языков. ^[7]

Разбор грамматик ID/LP

Для анализа грамматик ID/LP используются два алгоритма синтаксического анализа: анализатор Эрли и алгоритм Шибера. ^[9]

Эрли Парсер в грамматиках ID/LP

Правила ID и LP накладывают ограничения на строки предложений; ^[9] при работе с большими строками, ^[9] ограничения этих правил могут привести к тому, что анализируемая строка станет бесконечной, что затруднит синтаксический анализ. Earley Parser решает эту проблему, изменяя ^[10] формат грамматики ID/LP в контекстно-свободную грамматику (CFG), разделяющий грамматику ID/LP на упорядоченную контекстно-свободную грамматику (CFG) и неупорядоченную контекстно-свободную грамматику (UCFG). Это позволяет двум алгоритмам более эффективно анализировать строки; ^[9] в частности, Earley Parser использует метод отслеживания точек, который следует линейному пути, установленному правилами LP. ^[9] В CFG правила LP не допускают повторяющихся составляющих в анализируемой строке, но UCFG допускает повторяющиеся составляющие в анализируемой строке. ^[9] Если грамматика ID/LP преобразуется в UCFG, то правила LP не доминируют в процессе анализа, однако все равно следуют методу отслеживания точек.

Анализ Эрли в CFG

После того как грамматика ID/LP будет преобразована в эквивалентную форму в CFG, алгоритм проанализирует строку. Позволять $\mathrm {X}$ стоять на старте и $\alpha ,\beta ,\iota$ обозначают элементы строки, а также представляют синтаксические категории . Затем алгоритм анализирует строку и определяет следующее:

Исходное положение точки; обычно он начинается с крайнего левого элемента строки.
Текущее положение точки; это предсказывает следующий элемент.
Изготовление готовой струны. ^[9]

(1) $\mathrm {X} \longrightarrow \cdot \alpha \beta \iota$

(2) $\mathrm {X} \longrightarrow \alpha \cdot \beta \iota$ ( $\beta$ прогнозируется)

(3) $\mathrm {X} \longrightarrow \alpha \beta \iota \cdot$

Проанализированные строки затем используются вместе для формирования списка синтаксического анализа. ^[10] например:

$\mathrm {I} _{0}\ldots \mathrm {I} _{n}$ ^[10]

список которых поможет определить, завершен ли производственный элемент ( $\mathrm {X} \longrightarrow \alpha \beta \iota$ ) принимается в основной строке. Для этого он проверяет, найдены ли созданные отдельные строки в списке синтаксического анализа. Если одна или все отдельные строки не найдены в списке анализа, то вся строка завершится ошибкой. Если одна или все отдельные строки найдены в списке анализа, то будет принята вся строка. ^[10]

Эрли-парсинг в UCFG

UCFG является подходящим эквивалентом для преобразования грамматики ID/LP в целях использования анализатора Earley. ^[9] Этот алгоритм читает строки аналогично тому, как он анализирует CFG, однако в этом случае порядок элементов не соблюдается; что приводит к отсутствию соблюдения правил LP. Это позволяет повторять некоторые элементы в анализируемых строках, а UCFG принимает пустые мультинаборы вместе с заполненными мультинаборами в своих строках. ^[9] Например:

Исходное положение точки; оно находится между пустым и заполненным множеством.
Текущая позиция точки, которая предсказывает следующий набор; элемент, который передала точка, переместится в пустой набор.
Изготовление готовой струны. В этом случае положение двух наборов в исходной позиции поменяется местами; заполненное множество находится на левом краю, а пустое множество — на правом. ^[9]

(1) $\mathrm {X} \longrightarrow \{\}\cdot \{\alpha ,\beta ,\iota \}$

(2) $\mathrm {X} \longrightarrow \{\alpha \}\cdot \{\beta ,\iota \}$ ( $\{\beta ,\iota \}$ прогнозируются)

(3) $\mathrm {X} \longrightarrow \{\alpha ,\beta ,\iota \}\cdot \{\}$

При анализе строки, содержащей несколько неупорядоченных элементов, Earley Parser обрабатывает ее как перестановку Y! и генерирует каждую строку индивидуально вместо использования одной строки для представления повторяющихся анализируемых строк. ^[9] Всякий раз, когда точка перемещается над одним элементом, алгоритм начинает генерировать анализируемые строки элементов на правом краю в случайных позициях до тех пор, пока в наборе правого края больше не останется элементов. Пусть X ₀ представляет исходную строку, а X ₁ — первую проанализированную строку; например:

$\mathrm {X} _{0}:[\mathrm {X} \longrightarrow \{\}\cdot \{t,v,w,z\},0]$

$\mathrm {X} _{1}:[\mathrm {X} \longrightarrow \{t\}\cdot \{v,w,z\},0]$

строка X ₁ выдаст 3! = 6, разные анализируемые строки набора правых ребер:

(1) $[\mathrm {X} \longrightarrow t.vwz,0]$ (4) $[\mathrm {X} \longrightarrow t.zvw,0]$

(2) $[\mathrm {X} \longrightarrow t.vzw,0]$ (5) $[\mathrm {X} \longrightarrow t.wvz,0]$

(3) $[\mathrm {X} \longrightarrow t.zwv,0]$ (6) $[\mathrm {X} \longrightarrow t.wzv,0]$

Earley Parser применяет каждую строку к отдельным правилам грамматики. ^[9] и это приводит к очень большим наборам. Большие наборы частично приводят к преобразованию грамматики ID/LP в эквивалентную грамматику, однако анализ всей грамматики ID/LP с самого начала затруднен. ^[9]

Алгоритм Шибера

Основа алгоритма Шибера ^[9] основан на Earley Parser для CFG, ^[10] однако он не требует преобразования грамматики ID/LP в другую грамматику. ^[10] для того, чтобы быть разобранным. Правила ID можно анализировать в отдельной форме, S → _ID {V, NP, S}, из правил LP, V < S. ^[10] Шибер сравнил анализ CFG с упорядоченной строкой грамматики ID/LP, а Бартон сравнил анализ UCFG с неупорядоченной строкой грамматики ID/LP.

Прямой анализ упорядоченной грамматики ID/LP

Непосредственный анализ грамматики ID/LP генерирует список наборов, который будет определять, будет ли создание строки принято или ошибочно. Алгоритм состоит из 6 шагов (используемые символы также могут обозначать синтаксические категории):

Для всех правил идентификатора добавьте $[S,\mathrm {T} ,\beta ,0]$ к начальному элементу в списке разбора, $\mathrm {I} _{0}$ . ^[10]
Если все элементы в $\mathrm {I} _{0}$ , $[\mathrm {Z} ,\lambda ,\theta ,0]$ и элементы, $[\mathrm {A} ,\alpha ,\{Z\}\cup \beta ,0]$ , из $\mathrm {I} _{0}$ не позволяет предшествовать Z $\beta$ , $Z\nprec \beta$ , и Z не является элементом $\beta$ , $Z\not \in \beta$ ; затем следующая строка, $[\mathrm {A} ,\alpha Z,\beta ,0]$ можно добавить в $\mathrm {I} _{0}$ .
Если все предметы, $[\mathrm {A} ,\alpha ,\{Z\}\cup \beta ,0]$ , являются элементами $\mathrm {I} _{0}$ , затем $Z\nprec \beta$ , и $Z\not \in \beta$ и все $Z\longrightarrow _{\mathrm {ID} }\lambda$ то в этот список можно добавить следующий элемент, $[Z,T,\lambda ,0]$ .
На этом этапе будет построен сет-лист, $\mathrm {I} _{n}$ , более. Каждый предмет, $[A,\alpha ,\{q\}\cup \beta ,i]$ , это элемент $\mathrm {I} _{n-1}$ и где $q=q_{n}$ , $q\nprec \beta$ и $q\not \in \beta$ затем добавляется следующий элемент: $[A,\alpha q,\beta ,i]$ , к $\mathrm {I} _{n}$ .
Если предметы, $[Z,\lambda ,\theta ,i]$ , являются элементами $\mathrm {I} _{n}$ и предметы, $[A,\alpha \{Z\}\cup \beta ,k]$ , являются элементами $\mathrm {I} _{i}$ где $Z\nprec \beta$ , и $Z\not \in \beta$ ; строка, $[A,\alpha Z,\beta ,k]$ , добавляется к $\mathrm {I} _{n}$ .
Если предметы, $[A,\alpha ,\{Z\}\cup \beta ,i]$ , является элементом $\mathrm {I} _{n}$ где $Z\nprec \beta$ , и $Z\not \in \beta$ ; строка, $[Z,T,\lambda ,n]$ , добавляется к $\mathrm {I} _{n}$ .

Шаги 2-3 повторяются до конца. ^[10] до тех пор, пока новые элементы не перестанут добавляться, а затем перейдите к шагу 4. Шаги 5–6 также полностью повторяются. ^[10] до тех пор, пока в сет-лист не будет добавлено больше новых элементов. Строка будет принята, если строка ведет себя или напоминает продукцию, $[S,\alpha ,\theta ,0]$ является элементом $\mathrm {I} _{n}$ . ^[10] Например:

S\longrightarrow _{\mathrm {ID} }\{C,D,F\}

C\longrightarrow _{\mathrm {ID} }\{c\}

D\longrightarrow _{\mathrm {ID} }\{d\}

F\longrightarrow _{\mathrm {ID} }\{f\}

C\prec D

Таблица 1.0
Сет-листы	Предметы
$\mathrm {I} _{0}$	$[S,T,\{C,D,F\},0],$ $[C,T,\{c\},0],$ $[F,T,\{f\},0]$
$\mathrm {I} _{1}$	$[C,c,\emptyset ,0],$ $[S,C,\{D,F\},0],$ $[D,T,\{d\},1],$ $[F,T,\{f\},1]$
$\mathrm {I} _{2}$	$[F,f,\emptyset ,1],$ $[S,CF,\{D\},0],$ $[D,T,\{d\},2]$
$\mathrm {I} _{3}$	$[D,d,\emptyset ,2],$ $[S,CDF,\emptyset ,0]$

Полное производство $\mathrm {I} _{3},$ $[S,CDF,\emptyset ,0],$ принимается и создает следующую производственную строку: $[_{S}[_{C}c][_{D}d][_{F}f]]$ . ^[10]

Прямой анализ неупорядоченной грамматики ID/LP

Неупорядоченная грамматика ID/LP использует описанный выше шестишаговый алгоритм для анализа строк. Заметная разница заключается в постановке каждого сет-листа; есть одна строка, которая представляет множество отдельных строк в одном списке. ^[9] В таблице ниже показан список настроек Таблицы 1.0. $[S,T,\{C,D,F\},0],$ в неупорядоченной грамматике:

Таблица 2.0
Сет-лист	Предметы
$\mathrm {I} _{0}$	$[S,T,C\cdot d,f,\emptyset ,0]$
$\mathrm {I} _{1}$	$[S,T\cdot c,d,f,\emptyset ,0]$
$\mathrm {I} _{2}$	$[S,T,C,d\cdot F,\emptyset ,0]$
$\mathrm {I} _{3}$	$[S,T,C,D,F\cdot \emptyset ,0]$

Полная производственная цепочка, $[S,T,C,D,F\cdot \emptyset ,0],$ в результате получается строка, аналогичная упорядоченной грамматике ID/LP; однако порядок элементов в строке не соблюдается. Окончательная строка принимается, если она соответствует элементам исходной строки.

Обратите внимание, что неупорядоченная версия грамматики ID/LP содержит гораздо меньше строк, чем UCFG; Алгоритм Шибера использует одну строку для представления нескольких разных строк для повторяющихся элементов. Оба алгоритма могут одинаково анализировать упорядоченные грамматики, однако алгоритм Шибера кажется более эффективным. ^[9] при анализе неупорядоченной грамматики.

См. также

Ссылки

^ Газдар, Джеральд; Пуллум, Джеффри К. (1981). «Подкатегоризация, порядок составляющих и понятие «голова» ». В М. Моортгате; Хвд Хюлст; Т. Хукстра (ред.). Область применения лексических правил . стр. 107–124. ISBN 9070176521 .
^ Jump up to: ^а ^б ^с ^д ^и Газдар, Джеральд; Юэн Х. Кляйн; Джеффри К. Пуллум; Иван А. Саг (1985). Грамматика обобщенной структуры фразы . Оксфорд: Блэквелл и Кембридж, Массачусетс: Издательство Гарвардского университета. ISBN 0-674-34455-3 .
^ Дэниелс, Майк; Мёрерс, Детмар (2004). «GIDLP: грамматический формат для HPSG на основе линеаризации» (PDF) . Материалы одиннадцатой Международной конференции по грамматике фразовых структур, управляемых головой . дои : 10.21248/hpsg.2004.5 . S2CID 17009554 .
^ Хомский, Ноам (2007). «Биолингвистические исследования: дизайн, развитие, эволюция». Международный журнал философских исследований . 15 (1): 1–21. дои : 10.1080/09672550601143078 . S2CID 144566546 .
^ Хомский, Ноам (2011). «Язык и другие когнитивные системы. Что особенного в языке?». Изучение и развитие языка . 7 (4): 263–278. дои : 10.1080/15475441.2011.584041 . S2CID 122866773 .
^ Бервик, Роберт С.; и др. (2011). «Возвращение к бедности стимулов» . Когнитивная наука . 35 (7): 1207–1242. дои : 10.1111/j.1551-6709.2011.01189.x . ПМИД 21824178 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж Беннетт, Пол (1995). Курс грамматики обобщенной фразовой структуры . Лондон: UCL Press. ISBN 1-85728-217-5 .
^ Дэниэлс, М. (2005). Обобщенная грамматика ID/LP: формализм для анализа грамматик HPSG на основе линеаризации . (Электронная диссертация или диссертация). Получено с https://etd.ohiolink.edu/.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п Бартон-младший, Дж. Эдвард (1985). «О сложности разбора ID/LP» . Компьютерная лингвистика . 11 (4): 205–218 – через Ассоциацию компьютерной лингвистики.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л Шибер, Стюарт М. (1983). «Прямой анализ грамматик ID/LP» . Языкознание и философия . 7 (2): 1–30 – через SRI International.

[1] Газдар, Джеральд; Пуллум, Джеффри К. (1981). «Подкатегоризация, порядок составляющих и понятие «голова» ». В М. Моортгате; Хвд Хюлст; Т. Хукстра (ред.). Область применения лексических правил . стр. 107–124. ISBN 9070176521 .

[:0-2] Jump up to: ^а ^б ^с ^д ^и Газдар, Джеральд; Юэн Х. Кляйн; Джеффри К. Пуллум; Иван А. Саг (1985). Грамматика обобщенной структуры фразы . Оксфорд: Блэквелл и Кембридж, Массачусетс: Издательство Гарвардского университета. ISBN 0-674-34455-3 .

[3] Дэниелс, Майк; Мёрерс, Детмар (2004). «GIDLP: грамматический формат для HPSG на основе линеаризации» (PDF) . Материалы одиннадцатой Международной конференции по грамматике фразовых структур, управляемых головой . дои : 10.21248/hpsg.2004.5 . S2CID 17009554 .

[4] Хомский, Ноам (2007). «Биолингвистические исследования: дизайн, развитие, эволюция». Международный журнал философских исследований . 15 (1): 1–21. дои : 10.1080/09672550601143078 . S2CID 144566546 .

[5] Хомский, Ноам (2011). «Язык и другие когнитивные системы. Что особенного в языке?». Изучение и развитие языка . 7 (4): 263–278. дои : 10.1080/15475441.2011.584041 . S2CID 122866773 .

[6] Бервик, Роберт С.; и др. (2011). «Возвращение к бедности стимулов» . Когнитивная наука . 35 (7): 1207–1242. дои : 10.1111/j.1551-6709.2011.01189.x . ПМИД 21824178 .

[:1-7] Jump up to: ^а ^б ^с ^д ^и ^ж Беннетт, Пол (1995). Курс грамматики обобщенной фразовой структуры . Лондон: UCL Press. ISBN 1-85728-217-5 .

[8] Дэниэлс, М. (2005). Обобщенная грамматика ID/LP: формализм для анализа грамматик HPSG на основе линеаризации . (Электронная диссертация или диссертация). Получено с https://etd.ohiolink.edu/.

[:3-9] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п Бартон-младший, Дж. Эдвард (1985). «О сложности разбора ID/LP» . Компьютерная лингвистика . 11 (4): 205–218 – через Ассоциацию компьютерной лингвистики.

[:2-10] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л Шибер, Стюарт М. (1983). «Прямой анализ грамматик ID/LP» . Языкознание и философия . 7 (2): 1–30 – через SRI International.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]