Parser Combinators: позволяет ли repsep осуществлять обратное отслеживание? - PullRequest
Новая
       19

Parser Combinators: позволяет ли repsep осуществлять обратное отслеживание?

5 голосов
/ 22 февраля 2012

Рассмотрим пример синтаксического анализатора следующим образом: 

object TestParser extends RegexParsers {
    override protected val whiteSpace = """[ \t]*""".r  

    def eol = """(\r?\n)+""".r
    def item = "[a-zA-Z][a-zA-Z0-9-]*".r
    def list = "items:" ~> rep1sep(item,",") 
    def constraints = "exclude:" ~> item

    def itemsDefinition = (rep1sep(list, eol) ~ repsep(constraints,eol))
}

Если я попытаюсь разобрать этот ввод (без двух строк, исключить работает ОК): 

items: item1, item2, item3, item3, item4
items: item2, item3, item3, item5, item4    
items: item4, item5, item6, item10      
items: item1, item2, item3
exclude: item1
exclude: item2

Я получаю следующую ошибку: 

[5.5] failure: `items:' expected but `e' found

       exclude: item1

       ^

Проблема очевидна в этой строке: 

def itemsDefinition = (rep1sep(list, eol) ~ repsep(constraints,eol))

По какой причине это не работает. Это как-то связано с возвратом? Какие у меня есть альтернативы, чтобы заставить его работать?

1 Ответ

6 голосов
/ 22 февраля 2012

Вам понадобится eol между списками и вашими ограничениями 

(rep1sep(list, eol) <~ eol) ~ repsep(constraint,eol)

Завершение ответа:

Ваша грамматика указывает eol как разделитель между списками, а не как терминатор. Будет принят ввод, в котором первый exclude появляется сразу после последнего item3 (с пробелом, но не с новой строкой).

После того, как ваш парсер достигнет нежелательного eol, он ищет items и вместо него находит excludes. Что дает отображаемое сообщение об ошибке. Затем синтаксический анализатор действительно возвращается назад к предыдущей новой строке. Он рассматривает возможность того, что часть списков на этом останавливается, и ищет исключения. Но если находит вместо этого eol. Таким образом, другое возможное сообщение об ошибке будет "excludes expected, eol found", что в этом случае было бы более полезным

Когда в грамматике есть выбор, и ни одна ветвь не удалась, синтаксический анализатор возвращает ошибку с самой дальней позицией, которая обычно является правильной стратегией. Предположим, что ваша грамматика допускает "if" или "for", а ввод "if !!!". В ветке if ошибка будет выглядеть примерно так: "(" expected, "!" found. В ветке for сообщение будет "for expected, if found". Ясно, что сообщение из ветви if, которое появляется на втором токене, намного лучше, чем сообщение из ветви for, на первом токене и не имеет отношения к делу вообще.

По вопросу о разделителе / ​​терминаторе вы можете рассмотреть:

  • разделитель (; в Паскале): repsep(item, separator)
  • терминатор (; в C): rep(item <~ terminator)
  • гибкий: repsep(item, separator) <~ separator?

последний допускал бы один разделитель после отсутствия элементов вообще. Если это нежелательно, возможно (rep1sep(item, separator) <~ separator?)?.

...