Эффективный синтаксический анализ
Рассмотрим два приведенных ниже предложения.
Have the students in section 2 of Computer Science 101 take the exam. Have the students in section 2 of Computer Science 101 taken the exam?
Даже несмотря на то, что первые 10 слов в этих предложениях совпадают, они имеют очень сильно отличающиеся друг от друга деревья синтаксического анализа, поскольку первое из них представляет собой команду, а второе — вопрос. При использовании алгоритма синтаксического анализа, действующего слева направо, пришлось бы принять предположение о том, является ли первое слово частью предложения, представляющего собой команду или вопрос, но нельзя было бы подтвердить правильность этого предположения по меньшей мере до обработки одиннадцатого слова, "take" или "taken". Если предположение, принятое в этом алгоритме, оказывается неправильным, то приходится осуществлять полный возврат вплоть до первого слова. Такого рода возврат является неизбежным, но для повышения эффективности алгоритма синтаксического анализа следует предотвратить повторный анализ словосочетания "the students in section 2 of Computer Science 101" как NP после каждого возврата.
В этом разделе будет разработан алгоритм синтаксического анализа, в котором исключен указанный источник неэффективности. В его основе лежит идея, представляющая собой пример динамического программирования — после проведения анализа каждой подстроки сохранять результаты, чтобы не нужно было проводить ее повторный анализ в дальнейшем. Например, обнаружив, что словосочетание "the students in section 2 of Computer Science 101" относится к типу NP, можно зарегистрировать этот результат в структуре данных, известной под названием диаграммы. Алгоритмы, поддерживающие эти функции, называются диаграммными синтаксическими анализаторами. Поскольку в данном случае мы имеем дело с контекстно-свободными грамматиками, то любое словосочетание, обнаруженное в контексте одной ветви пространства поиска, вполне может применяться и в любой другой ветви пространства поиска.
Диаграмма для последовательности из п строк включает в себя п+1 вершину и целый ряд ребер, которые соединяют вершины. На рис. 22.2 показана диаграмма с шестью вершинами (обозначенными кружками) и тремя ребрами (обозначенными линиями). Например, ребро со следующей меткой:
[0, 5, S —> NP VP •]
означает, что словосочетание NP, за которым следует VP, объединяются, составляя узел S, который охватывает строку от вершины 0 до вершины 5. Символ • в обозначении ребра3 отделяет то, что было найдено до тех пор, от того, что осталось найти. Ребра с символами • в конце называются полными ребрами. Например, следующее ребро:
[0, 2, S —> NP • VP]
указывает, что словосочетание NP охватывает строку от вершины 0 до вершины 2 (первые два слова) и что если бы мы смогли найти словосочетание VP, чтобы продолжить это ребро, то получили бы словосочетание S. Ребра, подобные этому, в которых точка не достигла конца, называются неполными ребрами, и принято говорить, что для этого ребра требуется найти словосочетание VP.
Алгоритм диаграммного синтаксического анализатора показан в листинге 22.4. Его основная идея такова, что в нем объединяются лучшие свойства нисходящего и восходящего синтаксического анализа. Процедура Predictor выполняет нисходящий анализ; она создает записи в диаграмме, которые указывают, какие символы желательно найти и в каких местах. Процедура Scanner — это процедура восходящего анализа, которая начинает работу со слов, но использует любое слово только для продления существующей записи в диаграмме. По аналогии с ней процедура
Extender формирует составляющие дерева синтаксического анализа в направлении снизу вверх, но только для продления существующей записи в диаграмме.
Листинг 22.4. Алгоритм диаграммного синтаксического анализатора, где S — начальный символ, S1 — новый нетерминальный символ, a chart [j] — список ребер, которые оканчивается в вершине j. Словосочетания, обозначенные греческими буквами, согласуются с некоторой строкой, имеющей длину от нуля и больше символов
function Chart-Parse(words, grammar) returns диаграмма chart
chart <— массив [ 0...Length (words) ] пустых списков
Add-Edge( [0,0,5' -> • S] )
for i <— from 0 to Length (words) do
Scanner(i, words[i]) return chart
procedure Add-Edge(edge)
I * Добавить ребро к диаграмме и проверить, позволяет ли оно
продлить или предсказать другое ребро */ if ребро edge не находится в диаграмме chart[End(edge)] then добавить ребро edge к диаграмме chart[End(edge)] if ребро edge не содержит ничего после точки
then Extender(edge) else Predictor(edge)
procedure Scanner(j, word)
/* Для каждого ребра, ожидающего в данный момент появления слова
заданной категории, выполнить продление этого ребра */ for each [i, j, A —> a • В P] in chart [j] do
if слово word относится к категории В then Add-Edge ( [ i , j+1, A -> a В • p] )
procedure Predictor ( [i , j, A —> a • В P] )
/* Добавить к диаграмме любые правила для В, которые могут
помочь продлить это ребро */ for each (В —> у) in Rewrites-For (В, grammar) do Add-Edge([j,j,В -> • у])
procedure Extender([j,k,В —> у •])
/* Проверить, какие ребра могут быть продлены с помощью этого ребра */
ев <— ребро, которое является входным для этой процедуры for each [i,j,A—> ос • В' Р] in chart [j] do if В = В' then
Add-Edge([i,k,A -» a eB • 0])
Для запуска всего алгоритма воспользуемся таким приемом: добавим к диаграмме ребро [0,0,5' —> • S], где S— начальный символ грамматики, а 5' - новый символ, который был только что предложен. Вызов процедуры Add-Edge вынуждает процедуру Predictor ввести ребра, соответствующие правилам, применение которых может привести к получению S, т.е. [ S —> NP VP]. Затем осуществляется поиск первой составляющей этого правила, NP, и добавление правил, соответствующих каждому способу получения какого-то подходящего словосочетания NP. В конечном итоге процедура предсказателя Predictor добавляет в режиме нисходящего синтаксического анализа все возможные ребра, которые могут использоваться в процессе создания окончательного словосочетания S.
После завершения работы предсказателя применительно к словосочетанию S' алгоритм входит в цикл, в котором вызывается процедура Scanner для каждого слова в предложении. Если слово, находящееся в позиции j, является членом такой категории В, которая отыскивается для некоторого ребра в позиции j, то данное ребро продлевается, а слово отмечается как экземпляр категории В. Обратите внимание на то, что каждый вызов процедуры Scanner приводит к рекурсивному вызову процедур Predictor и Extender, в результате чего происходит чередование нисходящей и восходящей обработки.
Другой компонент восходящей обработки4, процедура Extender, принимает на входе некоторое полное ребро с левой частью В и использует его для продления любого неполного правила в диаграмме, которая оканчивается там, где начинается полное ребро, если для этого неполного правила требуется категория В.
4 По традиции применяемая нами процедура Extender именуется Completer. Но последнее название может сбить с толку, поскольку эта процедура не пополняет ребра — она принимает на входе полное ребро и продлевает неполные ребра.
На рис. 22.3 и в табл. 22.3 показаны диаграмма и трассировка процесса синтаксического анализа с помощью этого алгоритма предложения "I feel it" (которое является положительным ответом на вопрос "Do you feel a breeze?" — "Вы чувствуете ветерок?"). В этой диаграмме зарегистрированы тринадцать ребер (обозначенных метками от а до л?), включая пять полных ребер (показанных над вершинами диаграммы) и восемь неполных ребер (показанных под вершинами). Обратите внимание на то, как действуют в цикле процедуры предсказания Predictor, сканирования Scanner и продления Extender. Например, в процедуре предсказания используется тот факт, что для ребра а должен быть выполнен поиск словосочетания S, чтобы можно было разрешить сделать предсказание о том, что должно появиться словосочетание NP (ребро Ь), а затем словосочетание Pronoun (ребро с). После этого процедура сканирования распознает, что в нужном месте находится словосочетание Pronoun (ребро d), а процедура продления объединяет неполное ребро Ь с полным ребром d для получения нового ребра, е.
Этот алгоритм диаграммного синтаксического анализатора позволяет предотвратить формирование большого класса ребер, которые пришлось бы исследовать при использовании простой восходящей процедуры. Рассмотрим предложение: "The ride the horse gave was wild" (Скачка, на которую пустилась эта лошадь, была дикой). Процедура восходящего синтаксического анализа отметила бы словосочетание "ride the horse" (скакать на лошади) как VP, а затем отбросила бы все дерево синтаксического анализа, обнаружив, что такой вариант анализа не складывается в общее словосочетание S. Но в языке ?0 не разрешается, чтобы словосочетание VP следовало за словом "the", поэтому данный алгоритм диаграммного синтаксического анализатора никогда не предсказал бы наличие в этой точке словосочетания VP и поэтому избежал бы напрасного расходования времени на формирование здесь составляющей VP. Алгоритмы, которые действуют слева направо и предотвращают формирование таких невозможных составляющих, называются синтаксическими анализаторами по левому углу, поскольку они формируют дерево синтаксического анализа, начинающееся с начального символа грамматики и продолжающееся вниз к самому левому слову предложения (к левому углу). Ребро добавляется к диаграмме, только если оно может послужить для продления этого дерева синтаксического анализа (соответствующий пример приведен на рис. 22.4).
Этот диаграммный синтаксический анализатор характеризуется только полиномиальными затратами времени и пространства. Он требует О (кп2) пространства для хранения ребер, где п — количество слов в предложении, а к — константа, которая зависит от грамматики. Если алгоритм не может продолжать дальнейшее формирование ребер, он останавливается, поэтому известно, что работа данного алгоритма всегда завершается (даже при наличии леворекурсивных правил). В действительности он требует времени О (л3) даже в наихудшем случае, а это — самые лучшие показатели, которые могут быть достигнуты при использовании контекстно-свободных грамматик. Узким местом алгоритма Chart-Parse является процедура Extender, которая должна предпринять попытку продления каждого из 0( л) неполных ребер, оканчивающихся в позиции j, с помощью каждого из О(л) полных ребер, начинающихся с позиции j, для каждого из п+1 различных значений j. Перемножая эти числа, получаем значение О (л3). Полученные результаты довольно парадоксальны — как может алгоритм с затратами времени О (л3) возвратить ответ, в котором может содержаться экспоненциальное количество деревьев синтаксического анализа? Рассмотрим один пример; следующее предложение: Fall leaves fall and spring leaves spring
является неоднозначным, поскольку в нем каждое слово (кроме "and") может быть либо существительным, либо глаголом, a "fall" и "spring" могут быть также прилагательными. В целом этому предложению могут соответствовать четыре приведенных ниже варианта5 синтаксического анализа.
Если имеется л неоднозначных сочетающихся друг с другом фрагментов предложения, то может быть предусмотрено 2П способа6 выбора вариантов синтаксического анализа для этих фрагментов предложения. Как избежать экспоненциального роста затрат времени на обработку при использовании данного алгоритма диаграммного синтаксического анализатора? По сути на этот вопрос можно дать два ответа. Первый ответ состоит в том, что сам алгоритм Chart-Parse фактически представляет собой не синтаксический анализатор, а распознаватель. Если в диаграмме имеется полное ребро в форме [ 0, л, S —> а •], это означает, что какое-то словосочетание S распознано. Восстановление дерева синтаксического анализа из информации, заданной в этом ребре, не рассматривается как часть функций алгоритма Chart-Parse, но может быть выполнено с его помощью. Обратите внимание на то, что в последней операции процедуры Extender строка а формируется как список ребер ев, а не просто как список имен категорий. Поэтому, чтобы преобразовать ребро в дерево синтаксического анализа, достаточно выполнить рекурсивный просмотр составляющих ребер, преобразовав каждое ребро [i,j,x —> а •] в дерево [X: а]. Такой процесс является несложным, но позволяет получить только одно дерево синтаксического анализа.
5 Вариант синтаксического анализа [S: Fall [VP: leaves fall] ] эквивалентен предложению "Autumn abandons autumn" (Осень покидает осень).
6 Может возникнуть также 0(п\) неоднозначных вариантов, связанных с тем способом, как компоненты соединяются друг с другом, например (хи (У и Z)) или ((хи Y) и Z). Но это — другая проблема, которая весьма успешно исследована в [256].
Второй ответ состоит в том, что если требуются все возможные варианты синтаксического анализа, то придется глубже разобраться в этой диаграмме. Во время преобразования ребра [i,j,X —> а •] в дерево [X: а] можно будет проверить, есть ли какие-либо другие ребра в форме [i,j,X —> Р •]. Если они имеются, то эти ребра должны сформировать дополнительные варианты синтаксического анализа. Определив все эти варианты, необходимо будет продумать вопрос, что с ними делать. Можно просто перечислить все варианты, а это означает, что указанный выше парадокс будет разрешен и потребуется экспоненциальное количество времени для составления списка всех вариантов синтаксического анализа. Еще один подход может состоять в том, чтобы еще немного продолжить эту работу и представить варианты синтаксического анализа в виде структуры, называемой упакованным лесом, который выглядит примерно так:
[NP: Fall leaves][VP: fall] [S: [S: { [Np: Fall][T/P: leaves fall] > ] and
[NP: spring leaves][VP: spring] [S: i [NP: spring] [VP: leaves spring] > ]]
Идея этого способа представления состоит в том, что каждый узел дерева синтаксического анализа может быть либо обычным узлом дерева, либо множеством узлов дерева. Это позволяет возвратить из программы некоторое представление экспоненциального количества вариантов синтаксического анализа за счет полиномиальных затрат пространства и времени. Безусловно, если п=2, то разницы между 2П и 2п нет, но при больших значениях п такое представление обеспечивает значительную экономию. К сожалению, этот простой подход на основе упакованного леса не позволяет учесть все 0{п\) вариантов неоднозначности, касающиеся того, как могут быть связаны между собой различные составляющие. Максвелл и Каплан [1002] показали, что некоторый более сложный способ представления, основанный на принципах систем поддержки истинности, позволяет упаковывать деревья еще плотнее.