3

我是函数式编程的新手，想知道如何在不使用变量赋值的情况下以纯函数方式解决在上下文无关语法中计算可空非终结符集的问题。

可空非终结符是直接产生空的非终结符，例如 A ::= ，或具有包含可空非终结符的主体，例如 A ::= BCD，其中所有 BC 和 D 都产生空。

我在 Scala 中使用以下定义来定义语法：

case class Grammar(name:String, startSymbol:Nonterminal, rules:List[Rule])
case class Rule(head: Nonterminal, body:List[Symbol])
abstract class Symbol
case class Terminal(c:Char) extends Symbol
case class Nonterminal(name:String) extends Symbol

一个基本算法是收集所有可直接为空的非终结符并将它们放入一个集合中。然后在每次迭代中尝试确定哪些生产规则在其主体上具有所有可为空的非终结符。这些非终结符将被添加到集合中，直到没有新的非终结符添加到集合中。

我在Scala中实现了这个过程：

  def getNullableNonterminals(grammar:Grammar) = {

  var nieuw : Set[Nonterminal] = (for(Rule(head, Nil) <- grammar.rules) yield head) (collection.breakOut)
  var old = Set[Nonterminal]()

  while(old != nieuw) {
    old = nieuw
    for{
        Rule(head, symbols) <- grammar.rules
        if symbols.length > 0
        if symbols.forall( s => s.isInstanceOf[Nonterminal] && old.contains(s.asInstanceOf[Nonterminal]))
       } nieuw = nieuw + head
  }
  nieuw   
}

尽管代码比等效的 Java 版本短得多，但它使用变量。有什么建议可以用函数式风格重写这段代码吗？

4

3 回答 3

1

这是一个更惯用的 Scala 解决方案：

object Algorithm {

  def getNullableNonterminals(grammar:Grammar) = {
    loop(grammar, Set())
  }

  @tailrec
  private def loop(grammar: Grammar, nullablesSoFar: Set[Nonterminal]): Set[Nonterminal] = {
    val newNullables = generateNew(grammar, nullablesSoFar)
    if (newNullables.isEmpty)
      nullablesSoFar //no new nullables found, so we just return the ones we have
    else
      loop(grammar, nullablesSoFar ++ newNullables) //add the newly found nullables to the solution set and we keep going
  }

  private def generateNew(grammar: Grammar, nullableSoFar: Set[Nonterminal]) = {
    for {
      Rule(head, body) <- grammar.rules
      if !nullableSoFar.contains(head)
      if body.forall(isNullable(_, nullableSoFar))
    } yield head
  }

  //checks if the symbol is nullable given the current set of nullables
  private def isNullable(symbol: Symbol, provenNullable: Set[Nonterminal]) = symbol match {
    case Terminal(_) => false
    case x@Nonterminal(_) => provenNullable.contains(x)
  }

}

while 语句替换为递归函数 - loop。此外，避免使用isInstanceOf- 模式匹配更适合于此。

小观察 - 制作 Symbol 类sealed，因为这可以强制警告模式匹配中缺少案例。

于 2013-01-20T23:07:58.787 回答
1

这是另一种使用记忆的方法（参考，另一个参考），它避免了像您和 MAD 的解决方案那样需要定点计算。此外，它是适用于大量场景的通用模式。看看Scalaz 的实现。

def getNullableNonterminals(g: Grammar): Iterable[Nonterminal] = {
  /* Cache that is used by isNullable to memoise results. */
  var cache: Map[Nonterminal, Boolean] = Map()

  /* Assumption: For each nonterminal nt there exists only one rule r
   * such that r.head == nt.
   */
  var rules: Map[Nonterminal, List[Symbol]] = g.rules.map(r => (r.head, r.body)).toMap

  def isNullable(s: Symbol): Boolean = s match {
    case _: Terminal => false
    case nt: Nonterminal =>
      /* Either take the cached result, or compute it and store it in the cache. */
      cache.getOrElse(nt, {
        /* rules(nt) assumes that there is a rule for every nonterminal */
        val nullable = rules(nt) forall isNullable
        cache += ((nt, nullable))
        nullable
      })
  }

  rules.keys filter isNullable
}

测试用例：

val ta = Terminal('a')
val tb = Terminal('b')

val ntX = Nonterminal("X")
val ntY = Nonterminal("Y")
val ntZ = Nonterminal("Z")
val ntP = Nonterminal("P")
val ntQ = Nonterminal("Q")
val ntR = Nonterminal("R")
val ntS = Nonterminal("S")

val rX = Rule(ntX, ntP :: ntQ :: Nil)
val rY = Rule(ntY, ntP :: ta :: ntQ :: Nil)
val rZ = Rule(ntZ, ntR :: Nil)
val rP = Rule(ntP, ntQ :: Nil)
val rQ = Rule(ntQ, Nil)
val rR = Rule(ntR, tb :: Nil)
val rS = Rule(ntS, ntX :: ntY :: ntZ :: Nil)

val g = Grammar("Test", ntS, List(rX, rY, rZ, rP, rQ, rR, rS))

getNullableNonterminals(g) foreach println
  // Nonterminal(Q), Nonterminal(X), Nonterminal(P)
于 2013-01-21T09:51:10.863 回答
0

我终于有时间写一个如何使用循环属性语法进行语法可空性计算的示例。下面的代码使用我们用于 Scala 的 Kiama 语言处理库。您可以在 Kiama中找到示例和测试的完整源代码。有关主要属性代码，请参见 SemanticAnalysis.scala，例如nullable。

简而言之，该方法执行以下操作：

  • 将语法表示为抽象语法树结构，

  • 对树结构执行名称分析，以解析从语法符号使用到这些符号定义的引用，以及

  • 将可空性计算为生成的 DAG 结构上的循环属性。

我使用的属性定义与 LDTA 2003 的 Magnusson 和 Hedin 的论文Circular Reference Attribute Grammars中用作示例的属性定义非常相似。他们在JastAdd 系统中实现了循环属性，我强烈推荐这篇论文给任何希望理解这一点的人话题。我们在 Kiama 中使用基本相同的算法。

这是示例使用的 AST 的定义。Tree是提供一些常见行为的 Kiama 类型。

sealed abstract class GrammarTree extends Tree

case class Grammar (startRule : Rule, rules : Seq[Rule]) extends GrammarTree

case class Rule (lhs : NonTermDef, rhs : ProdList) extends GrammarTree

sealed abstract class ProdList extends GrammarTree
case class EmptyProdList () extends ProdList
case class NonEmptyProdList (head : Prod, tail : ProdList) extends ProdList

case class Prod (symbols : SymbolList) extends GrammarTree

sealed abstract class SymbolList extends GrammarTree
case class EmptySymbolList () extends SymbolList
case class NonEmptySymbolList (head : Symbol, tail : SymbolList) extends SymbolList

sealed abstract class Symbol extends GrammarTree
case class TermSym (name : String) extends Symbol
case class NonTermSym (nt : NonTermUse) extends Symbol

sealed abstract class NonTerm extends GrammarTree {
    def name : String
}
case class NonTermDef (name : String) extends NonTerm
case class NonTermUse (name : String) extends NonTerm

下面的代码显示了nullable属性的定义。它开始为假，然后输入一个定点“循环”进行计算，直到值稳定。这些案例展示了如何计算 AST 中不同类型节点的属性。

Kiama 的circular属性构造器包含了属性的所有实现，包括存储缓存、定点检测等。

val nullable : GrammarTree => Boolean =
    circular (false) {

        // nullable of the start rule
        case Grammar (r, _) =>
            r->nullable

        // nullable of the right-hand side of the rule
        case Rule (_, rhs) =>
            rhs->nullable

        // nullable of the component productions
        case EmptyProdList () =>
            false
        case NonEmptyProdList (h, t) =>
            h->nullable || t->nullable

        // nullable of the component symbol lists
        case Prod (ss) =>
            ss->nullable
        case EmptySymbolList () =>
            true
        case NonEmptySymbolList (h, t) =>
            h->nullable && t->nullable

        // terminals are not nullable
        case TermSym (_) =>
            false

        // Non-terminal definitions are nullable if the rule in which they
        // are defined is nullable. Uses are nullable if their associated
        // declaration is nullable.
        case NonTermSym (n) =>
            n->nullable
        case n : NonTermDef =>
            (n.parent[Rule])->nullable
        case n : NonTermUse =>
            (n->decl).map (nullable).getOrElse (false)

    }

引用属性decl是将非终结使用连接到规则左侧的相应定义的属性。该parent 字段是从节点到 AST 中其父节点的引用。

由于一个规则或符号的可空性取决于其他规则或符号的可空性，因此您得到的是一组参与依赖循环的属性出现。结果是与“教科书”定义非常相似的可空性计算的声明性版本。（该示例还定义了 FIRST 和 FOLLOW 集计算的属性，这些计算是根据可空性定义的。）循环属性将记忆和定点计算组合在一个方便的包中，以解决此类问题。

于 2014-01-03T10:07:36.100 回答