yacc - lex と yacc (シンボル テーブルの生成)

Question

私は lex と yacc とコンパイラの設計は初めてです。どのフェーズ (語彙、構文、またはその他のフェーズ) でシンボル テーブルがどのように生成されるかを知りたいのですが。

yacc に -v オプションを指定して生成される y.output ファイルについて簡単に説明してもらえますか?調べてみましたが、あまり情報が得られませんでした。

コンパイラの設計とは別に、lex と yacc が使用されている他のアプリケーションを教えてください。

Answer 1

シンボル テーブルは、コンパイラのすべてのステージ/フェーズ/パスで使用できるグローバル データ構造です。これは、lex と yacc で生成されたコンポーネントの両方から使用/アクセスできることを意味します。

識別子など、テーブルに格納されるトークンを見つけたときに、字句解析器からシンボル テーブル エントリにアクセスするのが一般的です。エントリを見つけて、行番号や行番号などのレクサーだけが利用できる情報で更新できます。また、語彙素の値が存在しない場合は格納することもできます。lvalトークンの でシンボル テーブル ポインタを返すことができるようになりました。

lval一部の人々は、レクサーからパーサーに( として) 語彙素自体へのポインターを返し、そこで最初のシンボル テーブル アクセスを行うことを好みます。これには、シンボル テーブルをレクサーに表示する必要がないという利点がありますが、前述のレクサー情報をシンボルと共に格納することができなくなる可能性があるという欠点があります。多くの場合、yacc からのパーサー アクションがもう少し「ビジー」になるという欠点があります。これは、シンボル テーブルと解析ツリーの管理に関与する可能性があるためです。

シンボル テーブル エントリは、型情報でシンボル エントリに注釈を付けたり、宣言されていないオブジェクトなどにフラグを付けたりできる解析ツリーのセマンティック ウォークなど、コンパイラの後の段階でさらに更新されます。シンボル テーブルは、ターゲット固有の情報が格納または必要とされるターゲット コードの生成中に再び使用されます。また、変数の使用法が調べられたり、最適化によって取り除かれたりする可能性がある最適化中にも使用されます。

シンボル テーブルは、コンパイラ作成者が自分で作成するデータ構造です。あなたのためにそれを行うlexまたはyaccの機能はありません。あなたが書いたコードがそれを作成するとき、それは生成されます!

y.output ファイルはシンボル テーブルとは関係ありません。yacc がどのように文脈自由文法を構文解析表に変換したかを記録したものです。あいまいな文法があり、文法をデバッグするときにシフト/リデュースまたはリデュース/リデュース エラーの原因となっているルールを知りたい場合に役立ちます。

質問の最後の部分、これらのツールにはどのような用途がありますか? lex は、指定したパターンを認識するステート マシンのコードを生成するツールです。コンパイラを記述する際に使用する必要はありません。興味深い用途の 1 つは、TCP/IP データグラムなど、ステート マシンによって処理できるネットワーク プロトコルの処理です。同様に、yacc は、文脈自由文法で記述されたシーケンスのマッチングに使用されます。これらはプログラムである必要はありませんが、シンボル、フィールド、またはデータ項目の他の複雑なシーケンスである可能性があります。それらは通常はテキストの断片であり、それがツールの正統な使用法です。

あなたの質問のこれらの部分は、コンパイラのコースに参加した学生のために誰かが書くかもしれない試験問題のようなものです!