3

ウィキペディアでProductionの正式な定義を読むことができますが、その記事を読み始めると、事前の知識についての仮定が立てられます。

ウィキペディアでは次のように定義しています。

コンピュータ サイエンスにおけるプロダクションまたはプロダクション ルールは、新しいシンボル シーケンスを生成するために再帰的に実行できるシンボル置換を指定する書き換えルールです。

これは、書き換えルールとは何かを知っていて理解していることを前提としています。リンクをクリックすると、別のかなり技術的な説明が表示されます。

プロダクションが実際に何であるかをわかりやすい英語で説明してもらえますか?

注: これを理解しようと何度も試みましたが、成功したとは思いません。私が言えることから、文法規則の観点から、指定された文字列を書き換えます。私が正しいかどうかはわかりません。

4

2 に答える 2

4

プロダクションとは何かを説明するために、最初に少し文脈を紹介したいと思います。

ドラゴン ブックでは、文脈自由文法には 4 つの構成要素があると述べています。

  • 終端記号 (トークン) のセット
  • 非終端記号 (構文変数) のセット
  • 次の形式のプロダクションのセット: 非ターム --> 端末と非端末のシーケンス
  • 開始記号として指定された非終端記号

構文解析とは、端末の文字列 (ソース コード) を取得し、文法の開始記号からこの端末の文字列を導き出すために必要な手順を理解する問題であるとも言われています。

そうは言っても、生産は本質的に可能な（中間の）ステップです。一部のシンボルは異なるシーケンスに派生する可能性があるため、可能だと言います。

たとえば、b で終わる a の任意の長さのシーケンスを表す単純な文法を作成してみましょう。この文法の 4 つのコンポーネントは次のようになります。

  • 端子：a、b
  • 非終端記号: S、X
  • ルール: S --> X, X --> aX, X --> ab
  • 開始記号: S

上記の説明から、「aaaab」はこの文法から導出できるはずです。それが続くかどうか見てみましょう。開始記号から開始し、a) 最終的なシーケンスを取得する、b) 成功せずにすべての可能性を使い果たす (シーケンスが「文法的に正しくない」ことを意味する) まで、プロダクションを適用します。

S
X (after applying S --> X)
aX (after applying X --> aX)
aaX (after applying X --> aX)
aaaX (after applying X --> aX)
aaaab (after applying X --> ab)

これで、元のシーケンスができました。ご覧のとおり、すべてのステップでシーケンスを新しいシンボルのシーケンスに変換するルール (再帰的に適用したルールの 1 つ) を適用して非終端記号を書き直し、最終的なシーケンスが得られるまでそれを行いました。

于 2013-08-20T09:27:22.857 に答える
1

書き換え規則は、式の部分項を他の項に置き換える方法です。最も基本的な形式では、一連のオブジェクトと、それらのオブジェクトを変換する方法に関する関係で構成されます。

書き換えルールの例は次のようになります。

A → B

さて、これが実際に何をするかについて！たとえば、もののリスト（および2つの書き換えルール）を取り上げます。

X, Y, Z
X → Y
Y → Z

その結果、次のようになります。

Z, Z, Z

プロダクション ルールは、数式のサブターム (おそらく文字列) を置き換える方法であるため、書き換えルールです。プロダクション ルールは次のようになります。

X, Y, Z
X → aX

このような方法でルールを使用することにより、再帰を適用 (新しいシーケンスを作成) することが可能になり、それ自体を置き換え続けます。

aX, Y, Z
aaX, Y, Z
aaaX, Y, Z

あなたが尋ねている質問については、「生産ルールは、再帰を使用して新しいシーケンスを作成する式の置換ルールです」と言うことができます。

于 2013-08-20T09:27:11.623 に答える