3

私は関数型プログラミングが初めてで、変数の割り当てを使用せずに、純粋に関数的な方法でコンテキストフリー文法で null 許容非終端記号のセットを計算する問題をどのように解決するのか疑問に思っていました。

null 許容非終端記号は、直接空を生成する非終端記号 (たとえば A ::= )、または null 許容非終端記号を含む本体を持つ非終端記号 (たとえば 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

基本的なアルゴリズムは、直接 null 可能なすべての非終端記号を収集し、それらをセットに入れることです。次に、反復ごとに、本体に null 許容のすべての非終端記号を持つプロダクション ルールを特定しようとします。これらの非終端記号は、新しい非終端記号がセットに追加されなくなるまで、セットに追加されます。

この手順を 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

これは、メモ化（参照、別の参照）を使用する別のアプローチです。これにより、ユーザーや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 に答える
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 に答える
0

ようやく、循環属性文法を使用して文法の nullability 計算を行う方法の例を書く時間を見つけました。以下のコードは、Scala 用の Kiama 言語処理ライブラリを使用しています。サンプルとテストの完全なソース コードはKiama にあります。nullableなどの主要な属性コードについては SemanticAnalysis.scala を参照してください。

つまり、このアプローチは次のことを行います。

  • 文法を抽象的な構文木構造として表現し、

  • ツリー構造で名前分析を実行して、文法記号の使用からそれらの記号の定義への参照を解決します。

  • 結果の DAG 構造の循環属性として nullability を計算します。

私が使用する属性定義は、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属性の定義を示しています。false から始まり、固定小数点の「ループ」に入り、値が安定するまで計算されます。ケースは、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 内のノードからその親への参照です。

1 つのルールまたはシンボルの null 可能性は、他の null 可能性に依存するため、取得されるのは、依存サイクルに参加する属性オカレンスのセットです。結果は、「教科書」の定義によく似た、null 可能性計算の宣言型バージョンです。(この例では、null 可能性に関して定義される FIRST および FOLLOW セット計算の属性も定義します。) 循環属性は、この種の問題に便利なパッケージでメモ化と固定小数点計算を組み合わせます。

于 2014-01-03T10:07:36.100 に答える