Расширенный контроль рекурсивного парсера в scala - PullRequest
Новая
       15

Расширенный контроль рекурсивного парсера в scala

5 голосов
/ 12 мая 2010 
val uninterestingthings = ".".r
val parser = "(?ui)(regexvalue)".r | (uninterestingthings~>parser)

Этот рекурсивный парсер будет пытаться выполнить синтаксический анализ "(? Ui) (regexvalue)". R до конца ввода. Является ли в Scala способ запретить синтаксический анализ, когда определенное количество символов было использовано «неинтересными вещами»?

UPD: у меня есть одно плохое решение: 

object NonRecursiveParser extends RegexParsers with PackratParsers{
  var max = -1
  val maxInput2Consume = 25
  def uninteresting:Regex ={
    if(max<maxInput2Consume){
    max+=1
    ("."+"{0,"+max.toString+"}").r
    }else{
      throw new Exception("I am tired")
    }
  }
  lazy val value = "itt".r
  def parser:Parser[Any] = (uninteresting~>value)|parser
  def parseQuery(input:String) = {
      try{
      parse(parser, input)
      }catch{
          case e:Exception => 
      }
  }
}

Недостатки:
- не все участники ленивы, поэтому PackratParser будет иметь некоторое время штраф
- построение регулярных выражений для каждого «неинтересного» вызова метода - штраф времени
- использование исключения для управления программой - стиль кода и штраф времени

Ответы [ 2 ]

3 голосов
/ 12 мая 2010

Быстрый-грязный ответ - просто ограничить количество символов в регулярном выражении для неинтересных вещей и сделать его не рекурсивным: 

val uninterestingthings = ".{0,60}".r  // 60-chars max
val parser = (uninterestingthings~>"(?ui)(regexvalue)".r)*

На основании комментария о жадности, употребляющей регулярное выражение, я предлагаю одно регулярное выражение: 

val parser = ("(?.{0,60}?)(?ui)(regexvalue)".r)*

Но мы, похоже, отважились выйти за рамки синтаксических анализаторов scala в мелкие выражения регулярного выражения. Мне было бы интересно увидеть другие результаты.

0 голосов
/ 24 мая 2010

Используйте токенизатор, чтобы сначала разбить вещи, используя все регулярные выражения для интересных вещей, которые вы уже знаете. Используйте один ".".r, чтобы соответствовать неинтересным вещам, если они важны для вашей грамматики. (Или выбросьте их, если они не имеют значения для грамматики.) Ваши интересные вещи теперь имеют известные типы, и они распознаются токенизатором с использованием другого алгоритма, нежели синтаксический анализ. Так как все проблемы с обращением вперед решаются с помощью токенизатора, анализатор должен быть простым.

...