Комбинаторы парсеров Scala, парсеры не работают из-за приоритета

Я пытаюсь написать интерпретатор для языка программирования Icon. Одним из шагов в этом процессе является написание синтаксического анализатора для Icon, который я сделал следующим образом:

import java.io.FileReader
import scala.util.parsing.combinator.syntactical._
import scala.util.parsing.combinator.RegexParsers
import scala.util.parsing.combinator.PackratParsers
import scala.util.parsing.combinator.JavaTokenParsers

abstract class expr
case class CstInt(val value : Int) extends expr
case class FromTo(val from : expr, val to : expr) extends expr
case class Write(val value : expr) extends expr
case class And(val e1 : expr, val e2 : expr) extends expr
case class Or(val e1 : expr, val e2 : expr) extends expr

object ExprParser extends JavaTokenParsers with PackratParsers{

lazy val exp : PackratParser[expr] = andexp | exp2

lazy val exp2 : PackratParser[expr] = fromTo | exp3

lazy val exp3 :PackratParser[expr] = orexp | exp4 

lazy val exp4 : PackratParser[expr] = integer | exp5

lazy val exp5 : PackratParser[expr] = write 

lazy val integer : PackratParser[expr] = wholeNumber ^^ { s => CstInt(s.toInt)}

lazy val  write : PackratParser[Write] =  "write" ~> "(" ~> exp <~ ")" ^^ {  e => Write(e)}

lazy val fromTo : PackratParser[FromTo] = ("(" ~> integer) ~ ("to" ~> integer <~ ")") ^^ { case from ~ to => FromTo(from, to)}

lazy val andexp : PackratParser[And] = exp ~ ("&" ~> exp) ^^ { case e1 ~ e2 => And(e1, e2)}

lazy val orexp : PackratParser[Or] = exp ~ ("|" ~> exp) ^^ { case e1 ~ e2 => Or(e1, e2)}

def parseInput(input: String) : expr =
    parseAll (exp, input) match {
        case Success(tree, _) => tree
        case e: NoSuccess => throw new IllegalArgumentException(e.toString())
    }

}

object Interpret {
def main(args : Array[String]) : Unit = {
    println(ExprParser.parseInput(args(0)))
    }
}

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

write((1 to 4) | 4)

Я получаю эту ошибку:

java.lang.IllegalArgumentException: [9.17] failure: `)' expected but ` ' found

В то время как разбор

write((1 to 4) & 4)

работает просто отлично. Первое выражение работает нормально, если я перемещаю анализатор orexp в группу exp выше анализатора fromto. Однако это не соответствует правилам, заданным Icon, и не решает основной проблемы.

У кого-нибудь есть идеи для решения? Согласно документам Scala, смешивание парсеров packrat и обычных парсеров должно быть в порядке.


parsing scala parser-combinators operator-precedence
person bassen    schedule 16.06.2011    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Хорошо, я прочитал статью. на парсерах packrat в Scala, и я боюсь, что эта грамматика не будет работать как есть. Проблема в том, что fromTo как exp внутри write, а затем и сам write терпит неудачу (и, не имея других альтернатив, выходит из строя внешняя exp). Он никогда не возвращается и не говорит "ну, давайте посмотрим, есть ли другой exp, который также является допустимым".

Однако, глядя на этот текст, я не вижу fromTo наличие скобок как часть его грамматики. Если бы это было просто переписано, чтобы удалить эти скобки с этого уровня, это сработало бы:

object ExprParser extends JavaTokenParsers with PackratParsers{
  lazy val exp : PackratParser[expr] = andexp | exp2
  lazy val exp2 : PackratParser[expr] = fromTo | exp3
  lazy val exp3 :PackratParser[expr] = orexp | exp4 
  lazy val exp4 : PackratParser[expr] = integer | exp5
  lazy val exp5 : PackratParser[expr] = write | exp6
  lazy val exp6 : PackratParser[expr] = "(" ~> exp <~ ")"
  lazy val integer : PackratParser[expr] = wholeNumber ^^ { s => CstInt(s.toInt)}
  lazy val  write : PackratParser[Write] =  "write" ~> "(" ~> exp <~ ")" ^^ {  e => Write(e)}
  lazy val fromTo : PackratParser[FromTo] = integer ~ ("to" ~> integer) ^^ { case from ~ to => FromTo(from, to)}
  lazy val andexp : PackratParser[And] = exp ~ ("&" ~> exp) ^^ { case e1 ~ e2 => And(e1, e2)}
  lazy val orexp : PackratParser[Or] = exp3 ~ ("|" ~> exp) ^^ { case e1 ~ e2 => Or(e1, e2)}
}
person Daniel C. Sobral    schedule 16.06.2011
comment
Я не знал, что нормальные синтаксические анализаторы Scala не возвращаются, знаете, почему это так? Я сейчас попробовал сменить сначала просто fromto на packratparser, а потом уже все. Однако ничего из этого не изменило проблемы. - person bassen; 17.06.2011
comment
@ChrKroer Это не так? Я сделал меньший тестовый пример (в основном потому, что приведенный вами пример относится к внешним типам), и он работал нормально. Опять же, были небольшие различия между тем, что я пробовал, и тем, что происходит на самом деле (в частности, fromto было полностью принято, а затем не было найдено закрытие ) из write). Из любопытства, если вы объедините все определения expN в одно гигантское определение exp со многими |, получится ли это? - person Daniel C. Sobral; 17.06.2011
comment
Нет, это тоже не сработало. Я просто попытаюсь обновить код в исходном посте, чтобы отразить, как он выглядит сейчас с пакетными анализаторами повсюду. - person bassen; 17.06.2011
comment
@ChrKroer Имейте в виду, моя проблема связана с типами FromTo, Or, Prim и т. д. Другими словами, я могу скомпилировать это самостоятельно. Если возможно, вы можете вставить суть полного кода, хотя для вас было бы лучшим упражнением попытаться создать минимальный возможный пример, показывающий проблему. - person Daniel C. Sobral; 17.06.2011
comment
правильно, я изменил код на пример, который имеет ту же проблему и может работать полностью сам по себе, с проанализированными строками, заданными в командной строке. Спасибо за помощь, кстати! - person bassen; 17.06.2011
comment
Я знаю, что история была отредактирована, но нормальные парсеры абсолютно не откатываются. Просто синтаксические анализаторы, не являющиеся пакетами, будут зацикливаться на левой рекурсии, так написана ваша грамматика, поэтому вы либо используете пакетные анализаторы, либо избавляетесь от левой рекурсии. - person James Iry; 18.06.2011
comment
Одна небольшая оптимизация, и exp = exp2 ~ (& ~› exp). Почему? Потому что exp слева не может быть andexp. - person James Iry; 18.06.2011
comment
@ Даниэль, спасибо, это работает! @James, этот код упрощен. Для настоящего синтаксического анализатора мне нужно иметь несколько типов выражений в категории перед andexp, которые все могут использоваться в andexpressions. По этой причине я не вижу способа избавиться от рекурсии. - person bassen; 18.06.2011
comment
@ChrKroer Он прав. На самом деле, именно так написана грамматика на бумаге, на которую я ссылаюсь. Цепочка a & b & должна анализироваться как exp2 & andexp, так что вы можете написать именно это. Или возьмем, к примеру, orexp, который можно записать как exp4 ~ ("|" ~> exp). В случае a & b | c он сначала разложится как andexp -- exp2 ~ ("&" ~> exp) -- а затем второй exp расширится как orexp. - person Daniel C. Sobral; 18.06.2011
comment
@James Я думаю, что об отступлении можно поспорить. Оператор | возьмет левую руку, если он выполняет синтаксический анализ, или правую руку, если нет — это не приведет к возврату. Но рассмотрим возникшую проблему: exp был принят, а затем синтаксический анализатор, включивший его, потерпел неудачу, вместо того чтобы вернуться к exp и попытаться добиться успеха каким-то другим способом. Я действительно хотел бы, чтобы эти механизмы были изложены в скаладоках ясно и легко для понимания. - person Daniel C. Sobral; 18.06.2011

arrow_upward
0
arrow_downward

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

lazy val exp : PackratParser[expr] = (andexp | orexp | fromTo | integer | write)

А потом я изменил порядок, который у вас был - fromTo был указан перед orexp.

Кажется, теперь все работает нормально.

Андрес

person Andres    schedule 18.06.2011
comment
Изменение порядка меняет семантику, так что это невозможно - он так сказал в вопросе. - person Daniel C. Sobral; 19.06.2011