Дизайн компилятора - анализатор снизу вверх

Разбор снизу вверх начинается с листовых узлов дерева и работает вверх, пока не достигнет корневого узла. Здесь мы начинаем с предложения, а затем применяем правила производства в обратном порядке, чтобы достичь начального символа. На приведенном ниже изображении показаны доступные парсеры снизу вверх.

Анализ снизу вверх

Shift-Reduce Parsing

Разбор Shift-Reduce использует два уникальных шага для анализа снизу вверх. Эти шаги известны как шаг сдвига и шаг понижения.

  • Шаг сдвига: шаг сдвига относится к продвижению входного указателя к следующему входному символу, который называется смещенным символом. Этот символ помещается в стек. Смещенный символ обрабатывается как один узел дерева разбора.

  • Шаг сокращения : когда анализатор находит полное правило грамматики (RHS) и заменяет его на (LHS), это называется сокращением шага. Это происходит, когда вершина стека содержит дескриптор. Чтобы уменьшить, функция POP выполняется в стеке, который выскакивает из дескриптора и заменяет его нетерминальным символом LHS.

LR Parser

Парсер LR - это нерекурсивный парсер снизу вверх. Он использует широкий класс контекстно-свободной грамматики, что делает его наиболее эффективным методом синтаксического анализа. Парсеры LR также известны как парсеры LR (k), где L обозначает сканирование входного потока слева направо; R обозначает построение крайнего правого вывода в обратном направлении, а k обозначает количество символов с предварительным ожиданием для принятия решений.

Существует три широко используемых алгоритма для создания LR-парсера:

  • SLR (1) - простой анализатор LR:
    • Работает на наименьшем классе грамматики
    • Несколько штатов, следовательно, очень маленькая таблица
    • Простая и быстрая конструкция
  • LR (1) - LR Parser:
    • Работы по комплектации грамматики LR (1)
    • Создает большую таблицу и большое количество состояний
    • Медленное строительство
  • LALR (1) - синтаксический анализатор LR:
    • Работает на промежуточном размере грамматики
    • Количество состояний такое же, как в SLR (1)

Алгоритм синтаксического анализа LR

Здесь мы опишем скелетный алгоритм парсера LR: 

token = next_token()

repeat forever
   s = top of stack
   
   if action[s, token] = “shift si” then
      PUSH token
      PUSH si 
      token = next_token()
      
   else if action[s, token] = “reduce A::= β“ then 
      POP 2 * |β| symbols
      s = top of stack
      PUSH A
      PUSH goto[s,A]
      
   else if action[s, token] = “accept” then
      return
      
   else
      error()

LL vs. LR

LL LR
Делает самый левый вывод. Делает самый правый вывод в обратном порядке.
Начинается с корневого нетерминала в стеке. Заканчивается корневым нетерминалом в стеке.
Заканчивается, когда стек пуст. Начинается с пустого стека.
Использует стек для обозначения того, что еще ожидается. Использует стек для обозначения того, что уже увидено.
Строит дерево разбора сверху вниз. Строит дерево разбора снизу вверх.
Непрерывно выталкивает нетерминал из стека и выталкивает соответствующую правую часть. Пытается распознать правую часть стека, вытолкнуть его и вытолкнуть соответствующий нетерминал.
Расширяет нетерминалы. Уменьшает нетерминалы.
Читает терминалы, когда он выталкивает один из стека. Читает терминалы, пока он толкает их в стек.
Предварительный порядок обхода дерева разбора. Последовательный обход дерева разбора.
Назад Вперёд