Синтаксический уровень

Синтаксис рассматривает правила построения и отдельные разновидности словосочетаний и предложений.

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

На сегодняшний день наиболее широко используются следующие формализмы:

рекурсивная сеть переходов (Recursive Transitive Network – RTN); расширенная сеть переходов (Augmented Transitive Network – ATN),; контекстно-свободная грамматика (Context-Free Grammar – CFG) и различные её расширения: КСГ с управляющими символами, атрибутная КСГ, КСГ с ограничивающими условиями, транслирующая грамматика; грамматика обобщенной структуры фразы (General Phrase Structure Grammar – GPSG); грамматика головной структуры фразы (Head-Driven Phrase Structure Grammar – HPSG); грамматика определенных выражений (Definite Clause Grammar – DCG; функционально-унификационная грамматика (Functional Unification Grammar – FUG; лексико-функциональная грамматика (Lexical Functional Grammar); грамматика деревьев примыкания (Tree-Adjoining Grammar – TAG) .

Для работы с этими грамматиками используют различные методы распознавания и разбора текста. Они делятся два основных вида: детерминированные и недетерминированные. В детерминированных методах на каждом шаге алгоритма существует только один вариант интерпретации обработанной части цепочки. Такие методы, при подстановке цепочки вместо нетерминала, из всех возможных выражений выбирают только одно. Это позволяет исключить многозначные прочтения входных символов и значительно уменьшает общее время работы алгоритма и его требования к памяти. Алгоритмы этой группы являются самим быстрыми, их наихудшее время работы ограничено O(n). К таким методам относится, например, метод магазинного автомата.

Недетерминированные методы допускают несколько вариантов интерпретации отдельных частей цепочки (или всей цепочки), но строка считается правильной, только если существует единственный вариант её интерпретации. За счет того, что допускается несколько вариантов прочтения текущего символа и решение о правильности или неправильности одной из ветвей анализа принимается не сразу, а по мере поступления дополнительной информации, данные методы значительно медленнее. Их наихудшее время работы как правило ограничено O(n2) или O(n3). Недетерминированные методы делятся на табличные и автоматные. К табличным методам относятся:

метод Коке-Касами-Янгера (Cocke-Kasami-Younger) – первый метод табличного разбора. Использует грамматики в нормальной форме Хомского или линейные грамматики в нормальной форме. Для первых худшее время работы ограничено O(n3), для вторых – O(n2). Алгоритм двунаправленный (разбор слева-направо и справа-налево), анализ производится снизу-вверх. К достоинствам алгоритма относится простота реализации и достаточно хорошее время работы (на линейных грамматиках). К недостаткам – вертикальная однонаправленность алгоритма и его избыточность, так как алгоритм действует локально, не учитывая контекста. Из-за этого в матрицу распознавания часто добавляются символы, которые далее не в состоянии развить анализ и порождают большое количество тупиковых ветвей;

метод Эрли (Earley) – работа метода Эрли основана на использовании метасимвола «·», не входящего в V (полный словарь грамматики), и точечных правил (dotted rule), вида A®a·b, где a, bÎ V*. Метасимвол «·» является маркером, показывающим, какие символы данного правила уже были обработаны (до маркера), а какие еще нет. Наихудшее время работы ограничено O(n3). Данный алгоритм может быть усложнен, введением дополнительного протоколирования, и тогда наихудшее время его работы будет ограничено лишь O(n2). Алгоритм двунаправленный, анализ производится снизу-вверх. К достоинствам данного алгоритма относится хорошее время работы и относительная простота реализации. Недостатки такие же, как и у метода Коке-Касами-Янгера;

метод Валианта (Valiant) – данный алгоритм является самым сложным, среди табличных методов, и из-за этого никогда не был практически реализован. Он интересен тем, что для произвольной грамматики дает наихудшее время анализа ограниченное O(n2.87), что лучше, чем у конкурирующих методов;

метод головного анализа (Head-driven) – базируется на использовании покрывающей грамматики. Дополнительно к грамматике определяются символы tr, 1£ tr £ pr (где pr – длина r-того правила) являющиеся индексами головного элемента в правилах. С головных элементов и начинаются анализы правой части (а не с самого левого символа, как в традиционных методах). Худшее время работы данного алгоритма ограничено О(n2). Алгоритм двунаправленный, анализ производится снизу-вверх с дополнительной вертикальной фильтрацией сверху-вниз. К достоинствам данного алгоритма относится высокая скорость работы, достигнутая за счет понижения избыточности анализа, так как применение головных элементов позволяет ограничить количество символов, вставляемых в матрицу распознавания, но при этом сохранить полноту анализа. К недостаткам относится однонаправленное вертикальное направление анализа – только снизу-вверх;

метод островного анализа (Island-driven) – метод схож с алгоритмом головного анализа, но распознавание цепочки начинается с динамически выбираемых точек (островов), заранее не определенных в грамматике.

Данный метод также использует покрывающую грамматику GI. Если G= (N, S, P, S) это контекстно-свободная грамматика, то её островное покрытие GI= (IG(I), S, PI, IS) также является контекстно-свободной грамматикой, правила PI которой разделены на три множества:

для каждого правила Pr в P, предсказывающее множество PI(0) содержит продукции вида Ir(0,0)® e и Ir(pr, pr)® e;

проецирующие множество PI(1) определяется как:

для любого правила вида Dr® Zr,1 из P, правило IDr® XI принадлежит PI(1), где XI= IZr,1 если Zr,1ÎN и XI= Zr,1, если Zr,1Î S;

для каждого правила вида Dr® Zr,1… Zr,pr из P, pr>1, и для каждого 1£ S£ pr, тогда правило Ir(S-1,S) ® XI,S принадлежит PI(1), где XI,S= IZr,s если Zr,sÎN и XI= Zr,s, если Zr,sÎ S;

распространяющее множество PI(2) определяется следующим образом. Для каждого правила Dr® Zr,1…Zr,pr из P, pr>1:

для каждого символа Ir(s,t) и для каждого u, s< u< t: Ir(s,t) ® Ir(s,t-1) XI,t; Ir(s,t)® YI,SIr(s+1,t); Ir(s,t)® Ir(s,u) Ir(u,t) принадлежит PI(2), где XI,t= IZr,t если Zr,tÎN; XI,t= Zr,t, если Zr,tÎ S и YI,S= Zr,s+1 если Zr,s+1Î S;

для каждого u, 0< y< pr, правила IDr® Ir(0, pr-1) XI, IDr® YDr Ir(1, pr), IDr® Ir(0, u) Ir(u, pr) принадлежат PI(2), с аналогичными пункту 1 условиями для символов XI, YIÎ(IG(I) È S) по отношению к Zr,pr и Zr,1.

Алгоритм включает в себя два основных шага: распространение влево и распространение вправо, которые объединяют два смежных анализа, в соответствии с правилами из Pi(2). Правила из Pi(1) используются в шагах инициализации и проецирования, которые, соответственно, пытаются активировать анализы на выбранных островах, или на уже построенных конституентах, которые содержат по крайней мере один остров. Далее, шаг предсказания использует продукции из Pi(0) для предсказаний сверху-вниз конституентов, необходимых для анализа. За исключением шага инициализации, все остальные действия над элементами матрицы распознавания Т могут производится в произвольном порядке. Порядок обработки элементов матрицы Т во время остальных шагов также не имеет значения. Алгоритм также использует процедуру синхронизации, которая обрабатывает случаи конфликтов между анализами сверху-вниз справа-налево и слева-направо.

Далее в тексте мы будем называть элементы, имеющие вид Ir(s,t), частичными анализами, а элементы вида IA – полными анализами. Два частичных анализа Ir(s,t) и Ir(t+1,u), которые располагаются слева-направо во входной строке, называются конкурирующими за общий конституент, если существует полный анализ Iz(r,t+1), который покрывает в точности участок между Ir(s,t) и Ir(t+1,u). Такая ситуация возможна только в случае, если в строке выбрано более одного острова, которые были найдены в правой части правил из Pr.

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

каждый полный анализ, целиком находящийся в пределах левой подстроки, может быть объединен только с частичным анализом слева от себя; в тоже время, каждый полный анализ, целиком находящийся в пределах правой строки, может быть объединен только с частичным анализом справа от себя;

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

каждый полный анализ, который покрывает остров, не может быть объединен с частичным анализом;

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

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

Недетерминированные автоматные методы [86] делятся на:

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

метод стека древесных структур – происходит не дублирование, а ветвление анализов. Так как обработанная часть цепочки уже не изменится, то она может быть совместно использована процессами;

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

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