Рассмотрим два приведенных ниже предложения.

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 показана диаграмма с шестью вершинами (обозначенными кружками) и тремя ребрами (обозначенными линиями). Например, ребро со следующей меткой:

означает, что словосочетание ΝΡ, за которым следует VP, объединяются, составляя узел S, который охватывает строку от вершины 0 до вершины 5. Символ · в обозначении ребра3 отделяет то, что было найдено до тех пор, от того, что осталось найти. Ребра с символами · в конце называются полными ребрами. Например, следующее ребро: