-
Пред.Страница
След.Страница
Раздел
Содержание
3.9. Резюме.
Одним из классов грамматик, обеспечивающих построение детерминированных
магазинных распознавателей, является класс LL(1)
грамматик. Этот класс включает разделенные
и слаборазделенные грамматики. Чтобы
определить является ли заданная грамматика LL(1) грамматикой, необходимо
найти значения функций ПЕРВ и СЛЕД,
а затем проверить условия принадлежности классу LL(1) грамматик.
Для построения команд распознавателя нужно найти множества ВЫБОР
для каждого правила грамматики. Распознаватель выполняет команды двух видов:
со сдвигом и без
сдвига входной головки. При работе распознавателя в магазине происходит
построение вывода входной цепочки. Такой вывод соответствует левому
выводу входной цепоч-
ки. Правила применяються при выводе цепочки в такой последовательности,
как строится синтаксическое дерево при левом выводе от корня к конечным
узлам, поэтому распознаватель называют нисходящим.
Если при построении грамматики для заданного языка получилась не LL(1)
грамматика, то ее можно попытаться преобразовать, применяя приемы устранения
леворекурсив-
ных правил, выделения общих частей и построения неукорачивающей грамматики.
Однако, эти приемы не всегда приводят к успеху.
-
Пред.Страница
След.Страница
Раздел
Содержание