問題タブ [symbol-tables]

現在取り組んでいるプロジェクトのシンボル テーブルを作成しています。シンボル テーブルの保存と作成に利用できるさまざまな方法の長所と短所について、人々の意見はどうなっているのかと思っていました。

私はかなりの検索を行いましたが、最も一般的に推奨されるのは、バイナリ ツリー、リンク リスト、またはハッシュ テーブルです。上記のすべての利点と欠点は何ですか? (C++ で作業)

Symbol テーブルに関するウィキペディアのエントリは参考になります。

http://en.wikipedia.org/wiki/Symbol_table

しかし、Ruby のシンボルと、それらがシンボル配列 (Symbol.all_symbolsメソッドによって返される) でどのように表現されるかを理解しようとすると、

シンボル テーブルに対する Ruby のアプローチに、他の言語との重要な違いがあるかどうか疑問に思っています。

Google の新しい言語「Go」は、そのウェブサイトで次のように述べています。

言語は分析しやすいように設計されており、記号テーブルなしで解析できます

私は確かにこれらの問題の専門家ではありませんが、シンボル テーブルは、変数を使用する言語のすべてのコンパイラに共通の基本的な構造であり、Go は明らかに変数を使用していると思いました。私は何を理解していませんか？

私は自分が何をすべきかを理解するのに苦労しています。私が理解した唯一のことは、cminus.y ファイルで yacc を使用する必要があるということです。その後のことについては完全に混乱しています。私が何をする必要があるかを理解できるように、誰かが私にこれを別の方法で説明できますか?

前書き：

lex/flex と yacc/Bison を使用して LALR パーサーを生成します。cminus.y というファイルをお渡しします。これは、C-minus と呼ばれる単純な C に似た言語の yacc 形式の文法ファイルで、Kenneth C. Louden 著 Compiler Construction という本から引用されています。文法はかなり明白であるべきだと思います。Yahoo グループには、yacc の使用方法に関するいくつかの説明へのリンクがあります。flex を理解したので、yacc を学ぶのはかなり簡単です。基本型は int のみです。int は 4 バイトです。ブール値は、C のように int として処理されます (実際には、文法では変数を void 型として宣言できますが、そうしないでください)。1 次元配列を使用できます。ポインターはありませんが、配列要素への参照は (C のように) ポインターとして扱われるべきです。この言語は、代入、IF-ELSE、WHILE、および関数の呼び出しと戻りを提供します。コンパイラに MIPS アセンブリ コードを出力させ、それを SPIM で実行できるようにします。このような最適化のない単純なコンパイラの場合、IR は必要ありません。アセンブリ コードを 1 回のパスで直接出力できます。ただし、最初のステップはシンボル テーブルを生成することです。

記号表:

ここでの Barrett 博士のアプローチは気に入っています。これは、さまざまな型のオブジェクトを処理するために多くのポインターを使用します。基本的に、シンボル テーブルの要素は、識別子、型、および属性オブジェクトへのポインターです。属性オブジェクトの構造は、タイプによって異なります。扱うタイプはごく少数です。少なくとも最初は、線形検索を使用してテーブル内のシンボルを見つけることをお勧めします。より良いパフォーマンスが必要な場合は、後でハッシュに変更できます。(C で保持したい場合は、malloc を使用してオブジェクトの動的割り当てを行うことができます。) 最初に、存在するすべての異なる種類のシンボルのリストを作成する必要があります (それほど多くはありません)。各。まだすべての問題をカバーしていないため、新しい属性を追加できるようにしてください。文法を見てみると、関数のパラメーター リストの問題は、設計に考慮が必要な場所です。シンボル テーブルのエントリとポインタを増やすことをお勧めします。

テスト:

文法は正しいので、既存の文法をそのまま使用してパーサーを生成すると、パーサーは正しい C マイナス プログラムを受け入れますが、ルールに関連付けられたコード スニペットがないため、出力は生成されません。コード スニペットを追加して、シンボル テーブルを作成し、その際に情報を出力します。識別子が宣言されたら、シンボル テーブルに入力されている情報を出力する必要があります。同じスコープで同じシンボルの以前の宣言が見つかった場合は、エラー メッセージが出力されます。識別子が参照されている場合は、テーブルで参照して、そこにあることを確認する必要があります。現在のスコープで宣言されていない場合は、エラー メッセージが出力されます。スコープを閉じるとき、参照されていない識別子に対して警告が生成される必要があります。テスト入力は、正しく形成された C マイナス プログラムでなければなりません。

スコープ:

最も基本的なアプローチには、グローバル スコープと、宣言された各関数のスコープがあります。この言語では、複合ステートメント内での宣言、つまりスコープのネストが可能です。これを実装するには、ある種のスコープの番号付けまたはスタック方式が必要になります。(スタッキングは、私たちが構築しているワンパス コンパイラに最適です。)

malloc を使用してシンボル テーブル エントリを追加できますか? テーブルをトラバースして、何かが既に存在するかどうかを確認するにはどうすればよいですか?

実行可能ファイルをデバッグしようとしたとき:

それは正確にはどういう意味ですか？

実行可能ファイルにシンボル テーブルが追加されていますか?

私は現在、プログラミング言語コースの原則を取っていますが、一生これを理解することはできません。これは宿題ではなく、一般的な概念の問題です。

クラスでは、静的チェーンとディスプレイについて話しました。なぜこれらが必要なのか理解できたと思います。そうしないと、ネストされたメソッドがあるときに、ネストされたメソッドがあるときにどの変数について話しているのかを理解できません。

私の教授もシンボルテーブルについて話しました。私の質問は、シンボルテーブルは何に使用されるのですか? 静的チェーンとどのように関係していますか?

背景を説明します（間違っている場合は修正してください）。

（説明を簡単にするために、いくつかのことを定義します）

次のコードがあるとします。

そして、このスタック：

復習として の静的チェーンの簡単な説明。

静的チェーンは、内部関数内で変数が再定義されたときに使用する変数を見つけるために使用されます。上記のスタックでは、各フレームにそれを含むメソッドへのポインターがあります。そう：

(静的スコープを仮定すると、動的スコープの場合、すべてのスタック フレームはその下のフレームを指すだけだと思います)

メソッドprint(<something>)内で実行すると、次のようになると思います。innerA

シンボル テーブルの簡単な復習

シンボルテーブルの目的がよくわかりません。しかし、これは次のようになります。

• 次へのリンク - 複数のものに同じハッシュ値がある場合、これはリンクです
• name - 要素の名前 (例: i、j、a、int)
• type - 内容 (例: 変数、関数、パラメーター)
• スコープ レベル - これがどのように定義されているかは 100% わかりません。私はそれを考えます：
  • 0 はビルトイン
  • 1はグローバルになります
  • 2が主な方法になります
  • 3はaとbになります
  • 4 は innerA になります

私の質問をもう一度言います：

• シンボルテーブルは何に使用されますか?
• 静的チェーンとどのように関係していますか?
• スコープ情報はシンボル テーブルにあるのに、なぜスタティック チェーンが必要なのですか。

Common Lisp ランタイム内でアクティブなシンボル テーブルにアクセスできると聞いたことがあります。私は誤解しましたか？

実行時にPerlシンボルテーブルからメソッドを削除する必要があります。を使用してこれを実行しようとしましundef &Square::areaたが、関数は削除されますが、いくつかの痕跡が残ります。具体的には、$square->area()が呼び出されると、Perlは、私が期待している「未定義のサブルーチン＆Square :: area called」ではなく、「CODE参照ではない」と文句を言います。

「なぜそれが重要なのですか？関数を削除したのに、なぜそれを呼び出すのですか？」と尋ねるかもしれません。答えは、私がそれを呼んでいないということです、Perlはそうです。SquareはRectangleから継承し、継承チェーンをに渡したいのですが、メソッドが存在しないSquareをスキップしてRectangleのarea（）にフォール$square->areaスルー&Rectangle::areaする代わりに、メソッド呼び出しは「コード参照ではありません」で終了します。

奇妙なことに、これは＆Square :: areaがtypeglob割り当てによって定義された場合にのみ発生するようです（例*area = sub {...}）。関数が標準的なsub area {}アプローチを使用して定義されている場合、コードは期待どおりに機能します。

また興味深いことに、グロブ全体の定義を解除すると、期待どおりに機能します。サブルーチン自体の定義を解除しないでください。

症状を説明し、正しい動作と対比する短い例を次に示します。

更新：それ以来、Package :: Stashを使用してこの問題を解決しました（@Etherに感謝）が、そもそもなぜそれが起こっているのかまだ混乱しています。perldoc perlmod言う：

package main;

sub Some_package::foo { ... } # &foo defined in Some_package

これは、コンパイル時のtypeglob割り当ての省略形です。

BEGIN { *Some_package::foo = sub { ... } }

しかし、関数の定義を解除した後、2つは異なる動作を引き起こすため、これは単なる速記ではないようです。これが（1）誤ったドキュメント、（2）perlのバグ、または（3）PEBCAKのいずれの場合であるかを誰かに教えてもらえれば幸いです。

私は、C に似た言語用のコンパイラを構築している最中です。レクサーとパーサーの使用はある程度完了しました。現在、セマンティック分析を行おうとしており、シンボル テーブルを構築しようとしています。現在、仕様によれば、同じレキシカル レベルでの重複宣言は許可されていません。これには、レキシカル レベルごとに異なるシンボル テーブルを作成する必要がありますね。どうすればこれを行うことができますか？現在、私が持っている 1 つのシンボル テーブルは、各ノードが次のように見えるバイナリ ツリーの形式になっています。

特定のノードを別のツリーの「ルート」ノードにポイントするにはどうすればよいですか?

どんな助けでも素晴らしいでしょう！どうもありがとう。