Как локализовать ошибку в LR-парсере?

На всякий случай расскажу подробнее что я понимаю под LR-парсером и что у меня за проблема.

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

Кладем лексему в стек и если вершина стека (несколько верхних элементов) соответствует правилу, то подменяем её в соответствие с правилом.
Если подмена произошла, то начинаем проверять на соответствие правилам сначала, если нет, то кладем в стек следующую лексему.

Если в итоге в стеке остается один элемент, то последовательность лексем корректная и разбор завершился успешно.

Лексемы у меня это TreeNode. При замене по правилу удаленные лексемы я присоединяю как дочерние элементы к добавленной лексемы. В итоге оставшийся элемент у меня оказывается корнем дерева.

public class Lexem : TreeNode
    {
        public int Offset { get; set; }
        public int Length { get; set; }
        public LexemKind Kind { get; set; }
        public string Value {get;set;}
        
        public static Lexem GetLexem(LexemKind inKind)
        {
            return new Lexem() { Kind = inKind };
        }
    }

        public Lexem GetFormula()
        {
            var stack = new List<Lexem>();

            foreach (var lexem in lexer.GetLexems())
            {
                stack.Insert(0, lexem);
                while (true)
                {
                    Rule rule = null;
                    Lexem[] currentSet = null;
                    foreach (var nextRule in _Rules)
                    {
                        if (stack.Count < nextRule.IN.Length) continue;
                        currentSet = new Lexem[nextRule.IN.Length];
                        for (var idx = 0; idx < nextRule.IN.Length; idx++)
                        {
                            currentSet[idx] = stack[nextRule.IN.Length - idx - 1];
                            if ((nextRule.IN[idx] & currentSet[idx].Kind) != LexemKind.EMPTY) continue;
                            currentSet = null;
                            break;
                        }

                        if (currentSet == null) continue;

                        rule = nextRule;
                        break;
                    }

                    if (rule == null) break;

                    stack.RemoveRange(0, rule.IN.Length);
                    stack.Insert(0, Lexem.GetLexem(rule.OUT));
                    stack[0].Nodes.AddRange(currentSet);
                }
            }
            if (stack.Count == 0) return  null;
            if (stack.Count == 1) return stack[0];

            throw new ParserExeption();
        }


Собственно, вопрос: как определить в каком месте нарушился синтаксис во входной последовательности лексем?
  • Вопрос задан
  • 215 просмотров
Пригласить эксперта
Ответы на вопрос 1
middle
@middle
LR-парсер состоит из стека и конечного автомата. В конечном автомате дуги помечены двумя типами меток: SHIFT либо REDUCE <правило>. В приведённом вами примере при первом '+' будет произведён SHIFT (с переходом в соответствующее состояние), при последующем "b" будет произведён REDUCE по приведённому вами правилу с переходом в какое-то состояние.

Если же после первого '+' придёт второй '+', то это будет ошибкой, т.к. для текущего состояния не будет исходящей дуги для второго '+', ни SHIFT, ни REDUCE (дуга будет только для IDENTIFIER, если других правил нет).
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы