Формальные языки


Резюме


    Одним из классов грамматик, обеспечивающих построение детерминированных магазинных распознавателей, является класс LL(1)

    грамматик. Этот класс включает разделенные

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

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

  • Пред.Страница 

    След.Страница   Раздел   Содержание




- Начало -  - Назад -