SavePearlHarbor

LR-парсеры

—

от автора

admin

Привет, Хабр!

LR-парсеры – это инструмент для анализа и синтаксического разбора языков программирования. LR в данном контексте означает Left-to-right, слева направо и Rightmost derivation, правое разложения. LR парсеры используют метод снизу вверх, который отличается от более известных LL-парсеров, работающих сверху вниз.

Одна из основных фич LR-парсеров — способность обрабатывать большую часть контекстно-свободных грамматик.

Типы LR-парсеров

LR(0) парсеры

LR(0) парсеры — это базовый тип LR-парсера, который использует нулевое заглядывание вперед, т.е принимает решения о переходах и редукциях, не анализируя следующие символы входной строки.

LR(0) парсеры являются базой для понимания более сложных парсеров. Они используют стек для хранения состояния и очереди для хранения входных символов.

Поскольку они не используют заглядывание вперед, их способность разрешать двусмысленности в грамматике ограничена.

Основная проблема LR(0) парсеров — это конфликты shift/reduce и reduce/reduce, которые могут возникать из-за недостатка информации о следующих символах.

Рассмотрим грамматику:

S → A A → aA | b

Для строки «aab», LR(0) парсер будет выполнять следующие шаги:

  1. Shift: перемещение a в стек.

  2. Shift: перемещение второго a в стек.

  3. Reduce: преобразование aA в A.

  4. Shift: перемещение b в стек.

  5. Reduce: преобразование A в S.

SLR (Simple LR) парсеры

SLR парсеры представляют собой апдейт версию LR(0) парсеров, в которых используется односимвольное заглядывание вперед для разрешения двусмысленностей.

SLR парсеры решают многие конфликты, присутствующие в LR(0) парсерах, путем использования дополнительных правил перехода.

аблицы переходов и действий для SLR парсеров меньше, чем у более сложных LR(1) парсеров, что делает их более производительней с точки зрения памяти.

Для той же грамматики:

S → A A → aA | b

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

LALR (Look-Ahead LR) парсеры

LALR парсеры — это еще один шаг в эволюции LR-парсеров, представляющий собой компромисс между мощностью и эффективностью.

LALR парсеры способны обрабатывать большинство грамматик, которые могут обрабатывать полные LR(1) парсеры, но с меньшими затратами на память.

Таблицы LALR парсеров более компактны, чем таблицы полных LR(1) парсеров.

Рассмотрим грамматику:

S → E E → E + T | T T → T * F | F F → ( E ) | id

LALR парсер будет использовать заглядывание вперед для корректного парсинга выражений, разрешая двусмысленности при помощи компактных таблиц переходов.

Canonical LR(1) парсеры

Canonical LR(1) парсеры представляют собой наиболее мощный тип LR-парсеров, способный обрабатывать любые контекстно-свободные грамматики без ограничений.

ти парсеры могут обрабатывать любые грамматики, которые может обрабатывать любая LR-парсерная техника.

Таблицы переходов и действий для LR(1) парсеров значительно больше, чем у других типов LR-парсеров.

Для той же грамматики:

S → E E → E + T | T T → T * F | F F → ( E ) | id

Canonical LR(1) парсер будет создавать полные таблицы переходов и действий для каждой возможной комбинации состояний и символов, обеспечивая максимально точный парсинг.

Из чего состоят LR-парсерсы и алгоритм их работы

Основные компоненты LR-парсера

  1. Стек:
    Стек используется для хранения состояний и символов грамматики. В процессе анализа парсер перемещает символы и состояния между стеком и входным буфером.

  2. Входной буфер:
    Входной буфер содержит строку, которая должна быть разобрана. Строка канчивается специальным символом конца ($).

  3. Action table:
    Таблица действий определяет действия парсера (shift, reduce, accept, или error) на основе текущего состояния и символа на вершине стека.

  4. Goto table:
    Таблица переходов определяет новое состояние, в которое парсер должен перейти после выполнения reduce-операции, на основе текущего состояния и символа, к которому была применена редукция.

Шаги выполнения алгоритма

Алгоритм LR-парсера состоит из повторяющихся шагов, включающих операции shift и reduce:

  1. Shift:

    • Перемещение следующего символа из входного буфера в стек.

    • Обновление состояния парсера в соответствии с таблицей действий.

  2. Reduce:

    • Применение правила грамматики к символам на вершине стека.

    • Замена правой части правила на левую часть в стеке.

    • Переход в новое состояние согласно таблице переходов.

Рассмотрим пример грамматики и выполнение шагов парсинга:

Грамматика:

E → E + T | T T → T * F | F F → ( E ) | id

Входная строка: id + id * id

Шаги выполнения:

  1. Shift: id перемещается в стек, состояние обновляется.

  2. Reduce: id преобразуется в F, затем F в T.

  3. Shift: + перемещается в стек.

  4. Shift: следующий id перемещается в стек, состояние обновляется.

  5. Reduce: id преобразуется в F, затем F в T, и T в E.

  6. Shift: * перемещается в стек.

  7. Shift: следующий id перемещается в стек, состояние обновляется.

  8. Reduce: id преобразуется в F, затем F в T.

  9. Reduce: T * F преобразуется в T.

  10. Reduce: E + T преобразуется в E.

  11. Accept: строка успешно разобрана.

Примеры кода

LR(0) парсер

class LR0Parser:     def __init__(self, grammar, parsing_table):         self.grammar = grammar         self.parsing_table = parsing_table      def parse(self, input_string):         stack = [0]         input_string = input_string.split() + ['$']         cursor = 0          while True:             state = stack[-1]             lookahead = input_string[cursor]             action = self.parsing_table[state][lookahead]              if action.startswith('s'):                 stack.append(lookahead)                 stack.append(int(action[1:]))                 cursor += 1             elif action.startswith('r'):                 production = self.grammar[int(action[1:])]                 for _ in range(2 * len(production[1])):                     stack.pop()                 state = stack[-1]                 stack.append(production[0])                 stack.append(self.parsing_table[state][production[0]])             elif action == 'accept':                 print("Parsing completed successfully!")                 return True             else:                 print("Error: Invalid syntax")                 return False  grammar = [     ('S', ['A']),     ('A', ['a', 'A']),     ('A', ['b']) ]  parsing_table = {     0: {'a': 's2', 'b': 's3', 'S': 1, 'A': 4},     2: {'a': 's2', 'b': 's3', 'A': 5},     3: {'$': 'r2'},     4: {'$': 'accept'},     5: {'a': 's2', 'b': 's3', 'A': 6},     6: {'$': 'r1'} }  parser = LR0Parser(grammar, parsing_table) parser.parse('a a b')

SLR парсер

class SLRParser:     def __init__(self, grammar, parsing_table, follow_set):         self.grammar = grammar         self.parsing_table = parsing_table         self.follow_set = follow_set      def parse(self, input_string):         stack = [0]         input_string = input_string.split() + ['$']         cursor = 0          while True:             state = stack[-1]             lookahead = input_string[cursor]             action = self.parsing_table[state].get(lookahead, None)              if action is None:                 print("Error: Invalid syntax")                 return False             elif action.startswith('s'):                 stack.append(lookahead)                 stack.append(int(action[1:]))                 cursor += 1             elif action.startswith('r'):                 production = self.grammar[int(action[1:])]                 for _ in range(2 * len(production[1])):                     stack.pop()                 state = stack[-1]                 stack.append(production[0])                 stack.append(self.parsing_table[state][production[0]])             elif action == 'accept':                 print("Parsing completed successfully!")                 return True             else:                 print("Error: Invalid syntax")                 return False  grammar = [     ('S', ['E']),     ('E', ['E', '+', 'T']),     ('E', ['T']),     ('T', ['T', '*', 'F']),     ('T', ['F']),     ('F', ['(', 'E', ')']),     ('F', ['id']) ]  parsing_table = {     0: {'id': 's5', '(': 's4', 'E': 1, 'T': 2, 'F': 3},     1: {'+': 's6', '$': 'accept'},     2: {'+': 'r2', '*': 's7', '$': 'r2'},     3: {'+': 'r4', '*': 'r4', '$': 'r4'},     4: {'id': 's5', '(': 's4', 'E': 8, 'T': 2, 'F': 3},     5: {'+': 'r6', '*': 'r6', '$': 'r6'},     6: {'id': 's5', '(': 's4', 'T': 9, 'F': 3},     7: {'id': 's5', '(': 's4', 'F': 10},     8: {')': 's11', '+': 's6'},     9: {'+': 'r1', '*': 's7', '$': 'r1'},     10: {'+': 'r3', '*': 'r3', '$': 'r3'},     11: {'+': 'r5', '*': 'r5', '$': 'r5'} }  follow_set = {     'S': ['$'],     'E': ['$', '+', ')'],     'T': ['$', '+', '*', ')'],     'F': ['$', '+', '*', ')'] }  parser = SLRParser(grammar, parsing_table, follow_set) parser.parse('id + id * id')

LALR парсер

class LALRParser:     def __init__(self, grammar, parsing_table):         self.grammar = grammar         self.parsing_table = parsing_table      def parse(self, input_string):         stack = [0]         input_string = input_string.split() + ['$']         cursor = 0          while True:             state = stack[-1]             lookahead = input_string[cursor]             action = self.parsing_table[state].get(lookahead, None)              if action is None:                 print("Error: Invalid syntax")                 return False             elif action.startswith('s'):                 stack.append(lookahead)                 stack.append(int(action[1:]))                 cursor += 1             elif action.startswith('r'):                 production = self.grammar[int(action[1:])]                 for _ in range(2 * len(production[1])):                     stack.pop()                 state = stack[-1]                 stack.append(production[0])                 stack.append(self.parsing_table[state][production[0]])             elif action == 'accept':                 print("Parsing completed successfully!")                 return True             else:                 print("Error: Invalid syntax")                 return False  grammar = [     ('E', ['E', '+', 'T']),     ('E', ['T']),     ('T', ['T', '*', 'F']),     ('T', ['F']),     ('F', ['(', 'E', ')']),     ('F', ['id']) ]  parsing_table = {     0: {'id': 's5', '(': 's4', 'E': 1, 'T': 2, 'F': 3},     1: {'+': 's6', '$': 'accept'},     2: {'+': 'r2', '*': 's7', '$': 'r2'},     3: {'+': 'r4', '*': 'r4', '$': 'r4'},     4: {'id': 's5', '(': 's4', 'E': 8, 'T': 2, 'F': 3},     5: {'+': 'r6', '*': 'r6', '$': 'r6'},     6: {'id': 's5', '(': 's4', 'T': 9, 'F': 3},     7: {'id': 's5', '(': 's4', 'F': 10},     8: {')': 's11', '+': 's6'},     9: {'+': 'r1', '*': 's7', '$': 'r1'},     10: {'+': 'r3', '*': 'r3', '$': 'r3'},     11: {'+': 'r5', '*': 'r5', '$': 'r5'} }  parser = LALRParser(grammar, parsing_table) parser.parse('id + id * id')

Canonical LR(1) парсер

class LR1Parser:     def __init__(self, grammar, parsing_table):         self.grammar = grammar         self.parsing_table = parsing_table      def parse(self, input_string):         stack = [0]         input_string = input_string.split() + ['$']         cursor = 0          while True:             state = stack[-1]             lookahead = input_string[cursor]             action = self.parsing_table[state].get(lookahead, None)              if action is None:                 print("Error: Invalid syntax")                 return False             elif action.startswith('s'):                 stack.append(lookahead)                 stack.append(int(action[1:]))                 cursor += 1             elif action.startswith('r'):                 production = self.grammar[int(action[1:])]                 for _ in range(2 * len(production[1])):                     stack.pop()                 state = stack[-1]                 stack.append(production[0])                 stack.append(self.parsing_table[state][production[0]])             elif action == 'accept':                 print("Parsing completed successfully!")                 return True             else:                 print("Error: Invalid syntax")                 return False  grammar = [     ('E', ['E', '+', 'T']),     ('E', ['T']),     ('T', ['T', '*', 'F']),     ('T', ['F']),     ('F', ['(', 'E', ')']),     ('F', ['id']) ]  parsing_table = {     0: {'id': 's5', '(': 's4', 'E': 1, 'T': 2, 'F': 3},     1: {'+': 's6', '$': 'accept'},     2: {'+': 'r2', '*': 's7', '$': 'r2'},     3: {'+': 'r4', '*': 'r4', '$': 'r4'},     4: {'id': 's5', '(': 's4', 'E': 8, 'T': 2, 'F': 3},     5: {'+': 'r6', '*': 'r6', '$': 'r6'},     6: {'id': 's5', '(': 's4', 'T': 9, 'F': 3},     7: {'id': 's5', '(': 's4', 'F': 10},     8: {')': 's11', '+': 's6'},     9: {'+': 'r1', '*': 's7', '$': 'r1'},     10: {'+': 'r3', '*': 'r3', '$': 'r3'},     11: {'+': 'r5', '*': 'r5', '$': 'r5'} }  parser = LR1Parser(grammar, parsing_table) parser.parse('id + id * id'

Каждый из парсеров обрабатывает строку, следуя правилам грамматики, и осуществляет операции shift и reduce для построения дерева разбора или обнаружения ошибок в синтаксисе.

В завершение напомню о ближайших открытых уроках:

  • 13 июня, «Этапы, задачи и виды проектирования»: разберем, как грамотно определить подход к проектированию информационной системы и программного обеспечения. Записаться по ссылке

  • 19 июня, «Event storming как инструмент изучения предметной области». Запись по ссылке


ссылка на оригинал статьи https://habr.com/ru/articles/819841/

Комментарии

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *