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

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 как инструмент изучения предметной области». Запись по ссылке