На всякий случай расскажу подробнее что я понимаю под 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();
}
Собственно, вопрос: как определить в каком месте нарушился синтаксис во входной последовательности лексем?
