Treetop грамматика бесконечный цикл - PullRequest
Новая
       24

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

5 голосов
/ 24 мая 2011

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

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

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

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

Ответы [ 2 ]

7 голосов
/ 24 мая 2011

Я попросил 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 и соединение_object. Верхушка дерева при столкновении с левой рекурсией съедает стек до тех пор, пока его не стошнит У меня нет быстрого решения этой проблемы, но, по крайней мере, теперь у вас есть трассировка стека.

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

1 голос
/ 24 мая 2011

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

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

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

...