Возвратная вершина Treetop похожа на регулярные выражения?

Question

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

Предположим, у меня есть следующая грамматика:

grammar TestGrammar
  rule open_close
    '{' .+ '}'
  end
end

Это не соответствует строке {abc}, Я подозреваю, что это потому, что .+ потребляет все из письма a и далее. То есть потребляет abc} когда я хочу только потреблять abc,

Это отличается от того, что делает подобное регулярное выражение. Регулярное выражение /{.+}/ будет соответствовать {abc}, Насколько я понимаю, это возможно, потому что двигатель regex возвращается после использования закрытия } как часть .+ а затем не в состоянии соответствовать.

Так может ли Treetop сделать такой возврат? Если так, то как?

Я знаю, что вы можете использовать отрицание, чтобы соответствовать "чему-либо, кроме }"Но это не мое намерение. Предположим, я хочу соответствовать строке {ab}c}, Жетоны, которые я хочу в этом случае, являются открытием {средняя строка ab}cи закрытие }, Это надуманный пример, но он становится очень актуальным при работе с вложенными выражениями, такими как {a b {c d}},

Answer 1

Treetop - это реализация синтаксического анализатора выражения синтаксического анализа. Одним из преимуществ PEG является их сочетание гибкости, скорости и требований к памяти. Однако этот балансный баланс имеет некоторые компромиссы.

Цитата из статьи в Википедии:

Операторы "ноль или более", "один или более" и "необязательные" потребляют ноль или более, один или более или ноль или одно последовательное повторение их подвыражения e соответственно. Однако, в отличие от контекстно-свободных грамматик и регулярных выражений, эти операторы всегда ведут себя жадно, потребляя как можно больше входных данных и никогда не возвращаясь назад. […] выражение (a* a) всегда потерпит неудачу, потому что первая часть (a*) никогда не оставит ни один для второй части, чтобы соответствовать.

(Акцент мой.)

Короче говоря: в то время как некоторые операторы PEG могут вернуться назад в попытке выбрать другой маршрут, + оператор не может

Вместо этого, чтобы соответствовать вложенным подвыражениям, вы хотите создать чередование между разделенным подвыражением (проверяется первым), за которым следуют символы без выражения. Что-то вроде (не проверено):

grammar TestGrammar
  rule open_close
    '{' contents '}'
  end
  rule contents
    open_close / non_brackets
  end
  rule non_brackets
    # …
  end
end