Рекурсивная вершина дерева не работает - PullRequest
Новая
       31

Рекурсивная вершина дерева не работает

2 голосов
/ 13 июля 2011

Я пытаюсь создать парсер с использованием Treetop, который несколько рекурсивен. Выражение может быть числом, но также может быть добавлением выражений, поэтому я написал это: 

grammar Language
  rule expression
    "(" _ expression _ ")" / addition / integer 
  end

  rule addition
    expression _ "+" _ expression
    /
    expression _ "-" _ expression
  end

  rule integer
    '-'? _ [0-9]+
  end

  # space
  rule _
   ' '*
  end
end

Это просто не работает. Каждый раз, когда я пытаюсь разобрать что-либо, я получаю исключение «SystemStackError: слишком большой уровень стека» (переполнение стека! Ууу!). Есть идеи почему? Как правильно указать такое рекурсивное определение с помощью Treetop?

1 Ответ

2 голосов
/ 13 июля 2011

Ваша грамматика является леворекурсивной: то есть expression может быть сразу addition, что, в свою очередь, может быть expression и т. Д., Вызывая синтаксический анализатор в бесконечном цикле.

Попробуйте что-то вроде этого ( не проверено! ): 

grammar Language

  rule expression
    addition
  end

  rule addition
    multiplication (_ [+-] _ multiplication)*
  end

  rule multiplication
    unary (_ [*/%] _ unary)*
  end

  rule unary
    "-"? _ atom
  end

  rule atom
    number / "(" _ expression _ ")"
  end

  rule number
    float / integer
  end

  rule float
    [0-9]+ "." [0-9]+
  end

  rule integer
    [0-9]+
  end

  rule _
    ' '*
  end

end
...