LR-парсеры13.06.2024 08:15

6aff21f37efe37647d3d8174f82b3f73.png

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

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

© Habrahabr.ru