0

CFG をハイレベル コードにレンダリングしたいと考えています。通常、これは非常に簡単です。ツリーをたどり、各基本ブロックを順番にレンダリングし、goto ですべてを接着します。

残念ながら、最近 goto は時代遅れになっており、最新の言語のほとんどは goto をサポートしていません。そのため、言語に存在する制御フロー ステートメントのみを使用して基本ブロックを接着する何らかの方法が必要です: for、while、do... while、if、breakおよびcontinue. (変数を使用してステート マシンを構築することは考えたくありません。)

これを行うアルゴリズムはありますが、すべての場合に機能するとは限りません。つまり、上記の限られた一連の制御フロー構造のみを使用して、構造化コードにフラット化できない CFG を構築することが可能です。

これは私には直感的に明らかなように思えますが、それを証明することはできません (そして、私が見つけたアルゴリズムのドキュメントでは、これ以上詳しく説明されていません)。そして、このように平坦化できない CFG の例を見つけることができませんでした。

これが可能かどうか、はっきりと知りたいです。

オプション (a): 上記のように平坦化できない CFG の例はありますか? （それは不可能だと教えてくれます。）

オプション (b):上記のように CFG を平坦化できるという証拠を誰かが持っていますか? （それが可能であることがわかります。）それを機能させる必要があるため、それを行うアルゴリズムも非常に望ましいでしょう...

4

3 に答える 3

1

結果があると思います。

答えはそうです：それは不可能です。これは、Communications of the ACM、第9巻、366〜371ページの1966年の論文、Giuseppe Jacopiniによる「フロー図、チューリングマシン、および2つの形成規則のみの言語」からのものです。CiteSeerリンク。（これは、面白いことに、Knuthの独創的なものから参照されていることがわかりました（そして、私の観点からは、信じられないほど迷惑です）有害と考えられるステートメントに移動します。）

残念ながら、彼らは証拠を見つけることができなかったと言って、証拠を持っていません。

幸いなことに、このペーパーでは、制限された制御フローメカニズムのみを効率的に使用し、可能な限り少ない状態を使用して、任意のCFGをCFGに変換するための戦略について説明しています。この論文はかなり難しいですが、有望に見えます。

于 2012-01-31T21:07:51.997 に答える
0

一般に、ツリーをたどって CFG を平坦化することはできません。k 個の先読みトークンがある場合、これは LL(k) 文法で機能します。ただし、LR(k) 文法などのより複雑な文法の場合は、より高度な手法が必要になります。たとえば、http://en.wikipedia.org/wiki/LR_parserを参照してください。

一般に、ANY CFG を解析する既知のアルゴリズムはありませんが、有用なほとんどの CFG は LR(k) 文法として記述できます。より多くの研究がこれを改善し、大規模なクラスの CFG を解析できるようになりました。問題が決定不可能だとは思わない (確信はありませんが) ので、これがいつでも実行できる可能性は確かにありますが、これは研究上の問題であり、はい/いいえで答えられるものではないと思いますここにいる。

また、今日のすべての価値のある言語はチューリング完全であることも付け加えておく必要があります。つまり、GOTO で実行できることはすべて、if/while/for/... 型の構造で実行できます。新しい言語は制限ではありません。助けが必要なのは理論的な構成要素です。

ただし、実際には、必要な CFG を解析することはできません。しかし、それは将来の方法がわからないという意味ではありません...

于 2012-01-14T22:58:05.167 に答える