Синтаксический анализатор Scala сравнивает перед анализом - PullRequest
Новая
       6

Синтаксический анализатор Scala сравнивает перед анализом

0 голосов
/ 18 февраля 2019

Я ищу способ, которым комбинатор синтаксического анализатора Scala сопоставляется с регулярным выражением, прежде чем его анализировать.

Пример: 

import scala.util.parsing.combinator.RegexParsers

object MetaCommandParser extends RegexParsers with App {

  def parseSub: Parser[Object] = (parseElement <~ "=>") ~ parseExpression.*

  def parseElement: Parser[Object] = """\w+""".r

  def parseOr: Parser[Object] = listElements

  def listElements: Parser[Object] = parseExpression ~ opt("|" ~ listElements)

  def parseExpression: Parser[Object] = parseElement | parseOr

  def parseMetaCommand(s: String) = {
    MetaCommandParser.parseAll(parseSub, s) match {
      case Success(result, _) => result
      case Failure(msg, _)    => throw new Exception("FAILURE: " + msg)
      case Error(msg, _)      => throw new Exception("ERROR: " + msg)
    }
  }

  println(parseMetaCommand("operation => test"));
}

Типы: 

sealed trait Command;
case class Sub(tag: Word, sub: List[Expression]) extends Command;
case class ReplaceBy(tag: Word, sub: List[Expression]) extends Command;

sealed trait Expression;
case class Or(elements: Set[Expression]) extends Expression;
case class Reference(tag: String) extends Expression;
case class Option(element: Expression) extends Expression;
case class Word(tag: String) extends Expression;
case object Empty extends Expression;

Если я выполняю свой анализатор на parseSub с этим выражением: «operation => test»

У меня есть StackOverflow.Мой синтаксический анализатор хорошо разбирает Sub (Word (операция), Word (тест)), но ошибка появляется сразу после.Я думаю, что синтаксический анализатор попытался вычислить пустую строку в parseExpression, чтобы завершить "parseExpression. *", Но цикл в listElements.Если я могу убедиться, что моя запись действительна перед вызовом parseExpression, я думаю, что это может решить мою проблему (функция parseValidString)!

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

Спасибо!

1 Ответ

0 голосов
/ 18 февраля 2019

Ваши parseExpression и listElements правила взаимно леворекурсивны (через parseOr).В своем комментарии я предположил, что это, вероятно, не приведет к переполнению стека, поскольку parseElement пробуется раньше listElements, что означает, что listElements никогда не будет достигнуто (что само по себе является другой проблемой).

Однако, поскольку вы используете parseExpression в цикле *, он будет применяться неоднократно, пока не выйдет из строя, что означает, что все его альтернативы будут опробованы в конце.Таким образом, будет достигнут listElements, и левая рекурсия действительно вызовет переполнение вашего стека.Это также видно из того факта, что переполнение стека исчезает, если вы закомментируете | parseOr в parseExpression.

...