Какие правила синтаксического разбора? (Привидите примеры пожалуйста)

• В проверке цели проверяется, какие листья дерева синтаксического анализа точно соответствуют входной строке, без неизвестных и неохваченных входных данных.

Одна существенная проблема при нисходящем синтаксическом анализе возникает, когда приходится сталкиваться с так называемыми леворекурсивными правилами, т. е. правилами в формеПри поиске в глубину применение такого правила может привести к тому, что замена X на [X: х... ] будет осуществляться в бесконечном цикле. А при поиске в ширину можно будет успешно найти варианты синтаксического анализа для допустимых предложений, но при наличии недопустимого предложения может возникнуть такая ситуация, что программа не сможет выйти из бесконечного пространства поиска.

Ниже приведено описание восходящего синтаксического анализа как задачи поиска.

• Начальным состоянием является список слов во входной строке, где каждое из слов рассматривается как дерево синтаксического анализа только с одним листовым узлом, например [the,wumpus, is,dead]. Вообще говоря, каждое состояние в пространстве поиска представляет собой список деревьев синтаксического анализа.

• С помощью функции определения преемника выполняется поиск в каждой позиции i списка деревьев и в каждой правой части правила грамматики. Если подпоследовательность списка деревьев, начинающаяся с i, согласуется с правой частью, то эта подпоследовательность заменяется новым деревом, категорией которого является левая часть правила, а дочерними узлами — эта подпоследовательность. Под "согласованием" подразумевается, что категория узла является такой же, как и элемент в правой части. Например, правило согласуется с подпоследовательностью, состоящей из первого узла в списке [the,wumpus, is,dead], поэтому состоянием-преемником становится [ [Article: the] ,wumpus, is, dead].

• В проверке цели проверяется наличие состояния, представляющего собой единственное дерево с корнем S.

Пример восходящего синтаксического анализа приведен в табл. 22.2.

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

Таблица 22.2. Трассировка восходящего синтаксического анализа строки "The wumpus is dead". Работа начинается со списка узлов, состоящего из отдельных слов. После этого происходит замена подпоследовательностей, соответствующих правой части правила, новым узлом, корнем которого является левая часть правила. Например, в третьей строке показано, как узлы Article и Noun заменяются узлом WP, для которого эти два узла являются дочерними. Нисходящий синтаксический анализ приводит к выработке аналогичной трассировки, но в противоположном направлении