Откат в комбинаторах парсера scala?

Кажется, что комбинаторы синтаксического анализатора scala не отступают. У меня есть грамматика (см. внизу), которая не может правильно проанализировать следующий "stmt":

copy in to out .

Это должно быть легко разобрать с возвратом:

stmt: (to out(copy in))

или я что-то упускаю?

Парсер:

type ExprP = Parser[Expr]
type ValueP = Parser[ValExpr]
type CallP = Parser[Call]
type ArgsP = Parser[Seq[Expr]]

val ident     = "[a-zA-Z\\+\\-\\*/%><\\\\\\=]+".r
val sqstart   = "\\["                          .r
val sqend     = "\\]"                          .r
val del       = ","                            .r
val end       = "\\."                          .r

def stmt: ExprP      = expr <~ end
def expr: ExprP      = ucall | call | value
def value: ValueP    = ident ^^ {str => IdentExpr(str)}
def call: CallP      = (args ~ ident ~ expr) ^^ {case args ~ method ~ upon => Call(args, method, upon)}
def ucall: CallP     = (ident ~ expr) ^^ {case method ~ upon => Call(Seq(), method, upon)}
def args: ArgsP      = advargs | smplargs
def smplargs: ArgsP  = expr ^^ {e => Seq(e)}
def advargs: ArgsP   = (sqstart ~> repsep(expr, del) <~ sqend) ^^ {seq => seq}

person Anonymous    schedule 06.01.2011    source источник
comment
Получил это близко к работе, теперь я получаю переполнение стека. Обновлен парсер.   -  person Anonymous    schedule 06.01.2011


Ответы (2)


Вы хотите использовать PackratParsers в версии 2.8. Я думаю, что синтаксический анализатор packrat является единственным парсером с возвратом.

Изменить: с середины 2015 года вместо этого следует использовать fastparse. Это не только намного быстрее, но и проще в использовании (особенно при построении структур данных из синтаксического анализа).

person Rex Kerr    schedule 06.01.2011
comment
Кажется, это не исправить; Я все еще получаю ТАК (из-за леворекурсивной грамматики), и я слышал, что синтаксический анализ packrat должен исправить это. Если я заставлю его анализировать значения перед вызовами, он не будет анализировать (без возврата?). Возможно, я не активировал синтаксический анализ packrat, но я позаботился о том, чтобы смешать PackratParsers и вернуть PakratParser из всех функций. Вы знаете что-нибудь о PackratParsers? - person Anonymous; 07.01.2011
comment
О, хорошо, теперь я нашел это. Всем, кому нужны парсеры-пакраты: не забудьте заменить def на lazy val, заменить Parser[T] на PackratParser[T] и сделать смесь парсеров-класса/объекта из PackratParsers. - person Anonymous; 07.01.2011
comment
@Anonymous Пожалуйста, будьте более ясны в своей последней инструкции: сделайте смесь парсеров-класса/объекта из PackratParsers. Это просто с PackratParsers для класса? - person WestCoastProjects; 08.11.2015
comment
@rex fastparse не будет обрабатывать левую рекурсию - person olyk; 22.07.2020

Ваша проблема не в откате. Стандартный оператор | в scala.util.parsing.combinator выполняет поиск с возвратом. Ваша проблема — левая рекурсия (exprcallargssmplargsexpr). Парсинг Packrat действительно может помочь с этим.

person Michael Norrish    schedule 09.08.2011