Методы и алгоритмы трансляции естественно-языковых запросов к базе данных в SQL-запросы. Найханова Л.В - 17 стр.

комбинация надчерков: N . Число надчерков при этом означает уровень проекции данной
составляющей. Существенно ограничение максимального количества штрихов двумя:
первый соответствует частично построенной группе, например, глагольной группе вместе
со своими актантами, введение подлежащего (максимальная проекция второго уровня)
превращает глагольную группу в законченную пропозицию. Таким образом, вся
синтаксическая структура состоит из комбинации поддеревьев.
      Многие теории (примерно с начала 80-х годов) перешли от описания грамматики в
терминах правил к описанию ограничений (licensing rules), накладываемых на
сформированность (well-formedness) частей выражения. При таком способе описания языка
синтаксис языка не задается, различные ограничения в явном виде друг с другом не
связаны. Анализ (или синтез) при этом является попыткой найти представление,
одновременно удовлетворяющее всем ограничениям, причем возможные варианты
конструкций строятся параллельно (или псевдо-параллельно). Представители этого
направления связывают популярность таких грамматик с тем, что правила (КС или КЗ)
описывают структурные свойства лингвистических конструкций, в то время как
ограничения на сформированность являются более общими принципами, определяющими
эти конструкции. В частности, это приводит к большей независимости правил от
конкретных конструкций (нужно написать меньше правил для описания сравнимых
элементов грамматики языка) и возможности описания в грамматике свойств лексических
единиц.
      Существует два способа применения синтаксических правил: снизу вверх и сверху
вниз. В первом случае применяются правила, заменяющие структуру, описанную в правой
части, символом, представленным в левой части. Во втором случае доказывается
выводимость данного предложения из начального символа S. Часто оказывается
возможным применить правила несколькими способами при анализе снизу вверх.
      В синтаксическом анализе существуют две стандартные стратегии применения
правил при возможности альтернативного выбора: поиск "в ширину" и поиск "в глубину".
В первом случае запоминаются все возможные варианты, и каждый из них разворачивается
параллельно (или по очереди в случае последовательного анализа), при неудаче какого-
либо варианта разбора соответствующий вариант удаляется из набора возможностей. Во
втором случае, при анализе "в глубину", выбирается одна из альтернатив, а при неудаче
построения разбора происходит возврат на точку последней альтернативы и выбор другого
варианта. Использование анализа с проходом сверху-вниз не позволяет создавать
неграмматичные варианты. С другой стороны, анализ снизу-вверх не позволяет
генерировать гипотезы разбора, невозможные для данного предложения.
      Комбинацию достоинств этих вариантов представляет анализ с помощью таблиц,
содержимое которых является результатом частичного разбора. В случае, если разбор по
какому-то пути зашел в тупик, происходит возврат на точку выбора последнего правила и
делается попытка использовать другое правило. Однако заполнение таблицы, порожденное
предыдущим способом разбора, сохраняется в таблице и может быть использовано в
разборе по текущей ветке. Эта информация не запрещает проход анализа по тем веткам,
которые уже были опробованы, но неудачно. Для этой цели применяется запоминание
также и гипотез, выдвигаемых при разборе, и результатов их проверки. Такой подход
называется анализом с помощью схем (chart-parsing). Впервые его предложил Мартин Кэй
                                         17