1

解析ツリーの属性の循環依存関係のコンテキストで次の行に出くわしたとき、「コンパイラ: Aho、Ullman、Sethi、および Lam による Principles, Techniques and Tools」から Syntax Directed Definition を研究していました。

特定の SDD が変換しなければならない解析ツリーのいずれかに循環性が存在するかどうかを判断することは、計算上困難です。(セクション: 5.1.2)

http://cs.nyu.edu/courses/fall12/CSCI-GA.2130-001/lecture8.pdfにも記載されています

サイクルの検出には指数関数的な時間の複雑さがあります

しかし、O(E+V) のサイクルを見つけることができる Tarjan の強連結成分アルゴリズムがあります。では、なぜ上記の情報源はこれと矛盾しているのでしょうか?

私が欠けているものを誰か教えてもらえますか？

4

1 に答える 1

2

O(E+V)ある解析ツリーでサイクルを見つけることです。しかし、それは問題ではありません。問題は

特定の SDD が変換しなければならない解析ツリーのいずれかに循環性が存在するかどうかを判断します。（強調を追加）。

それはむしろ難しい問題です。

于 2014-04-29T04:45:17.860 に答える