Treetop грамматика бесконечный цикл

Question

У меня были некоторые идеи относительно нового языка программирования, плавающего в моей голове, поэтому я решил попробовать его реализовать. Друг предложил мне попробовать использовать Treetop (самоцвет Ruby) для создания парсера. Документация Treetop редкая, и я никогда раньше такого не делал.

Мой парсер работает так, как будто в нем бесконечный цикл, но без следов стека; это трудно отследить. Может кто-нибудь направить меня в сторону руководства по разбору /AST начального уровня? Мне действительно нужно что-то, что перечисляет правила, общее использование и т. Д. Для использования инструментов, таких как Treetop. Мой грамматик парсера находится на GitHub, на случай, если кто-то захочет помочь мне улучшить его.

class {
  initialize = lambda (name) {
    receiver.name = name
  }

  greet = lambda {
    IO.puts("Hello, #{receiver.name}!")
  }
}.new(:World).greet()

Answer 1

Я попросил treetop скомпилировать ваш язык в файл.rb. Это дало мне кое-что, чтобы покопаться:

$ tt -o /tmp/rip.rb /tmp/rip.treetop

Затем я использовал эту маленькую заглушку, чтобы воссоздать цикл:

require 'treetop'
load '/tmp/rip.rb'
RipParser.new.parse('')

Это висит. Разве это не интересно! Пустая строка воспроизводит поведение так же хорошо, как пример с дюжиной строк в вашем вопросе.

Чтобы выяснить, где он висит, я использовал макрос клавиатуры Emacs для редактирования rip.rb, добавив оператор отладки в запись каждого метода. Например:

def _nt_root
  p [__LINE__, '_nt_root'] #DEBUG
  start_index = index

Теперь мы можем увидеть область действия цикла:

[16, "root"]
[21, "_nt_root"]
[57, "_nt_statement"]
...
[3293, "_nt_eol"]
[3335, "_nt_semicolon"]
[3204, "_nt_comment"]
[57, "_nt_statement"]
[57, "_nt_statement"]
[57, "_nt_statement"]
...

Дальнейшая отладка показывает, что целое число может быть пустой строкой:

rule integer
   digit*
end

Это косвенно позволяет оператору быть пустой строкой и правилом верхнего уровня statement* навсегда потреблять пустые заявления. изменения * в + исправляет цикл, но выявляет еще одну проблему:

/tmp/rip.rb:777:in `_nt_object': stack level too deep (SystemStackError)
        from /tmp/rip.rb:757:in `_nt_compound_object'
        from /tmp/rip.rb:1726:in `_nt_range'
        from /tmp/rip.rb:1671:in `_nt_special_literals'
        from /tmp/rip.rb:825:in `_nt_literal_object'
        from /tmp/rip.rb:787:in `_nt_object'
        from /tmp/rip.rb:757:in `_nt_compound_object'
        from /tmp/rip.rb:1726:in `_nt_range'
        from /tmp/rip.rb:1671:in `_nt_special_literals'
         ... 3283 levels...

Диапазон является рекурсивным влево, косвенно, через special_literals, literal_object, object и component_object. Верхушка дерева при столкновении с левой рекурсией съедает стек до тех пор, пока его не стошнит. У меня нет быстрого решения этой проблемы, но, по крайней мере, теперь у вас есть трассировка стека.

Кроме того, это не ваша непосредственная проблема, но определение digit нечетно: может быть либо одна цифра, либо несколько. Это вызывает digit* или же digit+ разрешить (предположительно) незаконное целое число 1________2,

Answer 2

Мне очень понравились шаблоны реализации языка от Parr; Поскольку Парр создал генератор синтаксических анализаторов ANTLR, это инструмент, который он использует на протяжении всей книги, но он должен быть достаточно простым, чтобы учиться на нем.

Что мне действительно понравилось в этом, так это то, как каждый пример вырос по сравнению с предыдущим; он не начинает с гигантского синтаксического анализатора, способного работать с AST, вместо этого он медленно вводит проблемы, для выполнения которых требуется все больше и больше "умных механизмов", поэтому книга хорошо масштабируется вместе с языком, требующим синтаксического анализа.

Что бы я хотел, чтобы это было немного более подробно, это типы языков, на которых можно писать и давать советы о том, что можно и чего нельзя делать при разработке языков. Я видел несколько языков, которые очень трудно анализировать, и мне бы хотелось узнать больше о тех дизайнерских решениях, которые могли быть приняты по-другому.