Scala：自定义 grammar/parser 组合器

Question

我编写了一个 Scala 程序，它从用户那里读取一个字符串，并使用递归下降解析器或解析器组合器来确定输入字符串是否匹配以下语法（即由 a 和 b 组成），在此过程中构建解析树。然后匹配成功输出生成的树。

语法：

S -> E$
E -> C E2
E2 -> E
E2 -> NIL
C -> 'a' | 'b'

我是 Scala 的新手，所以任何阅读都将不胜感激，如果您有任何想法，请告诉我如何实现它，谢谢。

这是我目前拥有的

我已有的代码：

class MPParser extends JavaTokenParsers{
def c[C] = (“a” | “b”) ^^ {case ch => C(ch)}
}

abstract class MatchTree
case class C(s:String) extends MatchTree

输出应如下所示：

scala> Microproject.main(Array("ababa"))
input : ababa
[1.6] parsed: S(E(C(a),E(C(b),E(C(a),E(C(b),E(C(a),NIL()))))))

 scala> Microproject.main(Array("ababac"))
 input : ababac
[1.6] failure: `b' expected but `c' found

ababac
^

Answer 1

生产规则 def c[C] = ... 看起来很奇怪。您可能指的是 def c: Parser[C] = ...。

以下代码将向您展示如何定义生产规则并使用 scala-parser-combinators 构建自定义解析树：

import scala.util.parsing.combinator.RegexParsers

case class S(e: E)

// E2 -> E | NIL
sealed abstract class E2
case class E(c: C, e2: E2) extends E2
case object NIL extends E2 { override def toString = "NIL()" }

case class C(aOrB: String)

class MPParser extends RegexParsers {
  // S -> E
  def s: Parser[S] = e ^^ { S(_) }
  // E -> C E2
  def e: Parser[E] = c ~ e2 ^^ { case c ~ e2 => E(c, e2) }
  // E2 -> E | NIL
  def e2: Parser[E2] = opt(e) ^^ { _.getOrElse(NIL) }
  // C -> 'a' | 'b'
  def c: Parser[C] = ("a" | "b") ^^ { C(_) }
}

object Microproject extends App {
  val parser = new MPParser
  for (arg <- args) {
    println("input : " + arg)
    println(parser.parseAll(parser.s, arg))
  }
}

Live on Scastie

Scala：自定义 grammar/parser 组合器

Scala: custom grammar/parser combinators

scala

parsing

grammar

matching

parser-combinators