４、コンパイラ検討 １、字句解析による誤り処理。 字句解析における誤り処理としては、読み込む文字が未知の場合におこることがある。 処理できる言語において、定義していない字句を読み込んでしまった場合、この字句解析は適したトークンを返せない。 ２、コンパイラに用いられるほかの構文解析法について。 作成したコンパイラのプログラムでは、LL(1)文法において、下向き構文解析を再帰的に用いるものであった。その他には次のような構文解析がある。 （１）、シフト還元構文解析 入力文字を先頭からスタックに読み込んでいき、構文解析表を参考にして、順次文法規則で還元していく、上向き構文解析。特徴は最右導出の逆順で解析する手法である。最右導出とは、常に最も右の非終端記号を生成規則によって書き換えることが出来る。 （２）、LR構文解析 シフト還元構文解析のうちで最も一般的で、効率がよいものである。解析できる文法もLL(1)文法よりも多く、決定性構文解析のうちでは最も広い範囲を解析することが可能。左から右に解析して分かる最も早い段階で構文誤りを検出できる。LR構文解析では、ある時点まで読んで分かる複数の可能性を状態として覚えておく。 （３）、SLR(1)構文解析 ＬＲ構文解析の中で最も単純で、還元のために先読み記号の決め方はfollowを用いる。構文解析表は、LR(0)集成を用いる。 （４）、正準LR(1)構文解析 SLR(1)構文解析に対し、正準LR(1)集成から構文解析表を作る。SLR(1)より状態を細分化することにより衝突を回避する。それによって、状態数は多くなる。一つ先の先読み記号を持つために、SLR(1)より多くの情報を保持する事が出来る。 （５）、LALR(1)構文解析 これは、正準LR(1)の状態数をへらしたものである。解析できる文法は正準LR(1)と等しい。 現在、実用化されているコンパイラのほとんどがこれらのLR構文解析であるようだ。 ３、意味解析と最適化。 （１）、意味解析 意味解析とは、プログラムソースに出てきた１つの意味が、そのプログラムを通して、一貫しているかどうかの意味規則の対応を取ることである。 例えば、Ｃ言語において、intで宣言した変数は、そのプログラムでは終始intとしてしか使えない、こういった変数や、定数などの情報を管理するために記号表を作る。 また、これ以外に、変数のスコープの管理も意味解析に含まれる。ブロックが入れ子になったとき、深いブロックにある変数は、そのブロックより浅いブロックからは範囲外である。スコープ管理も記号表にブロックレベルの欄を作ることによって、制御する事が出来る。 コンパイラの扱える文法が複雑になったり、プログラムソースが長くなるにつれて、意味解析での記号表は膨大な大きさになる。そのために、記号表の検索方法として、線形検索や２分法、ハッシュ法など、工夫されるのが一般的である。 （２）最適化 最適化とは、プログラムの実行時間を短くする目的で、定数同士の掛け算や、同じ計算の省略、実行前からの害損の条件分岐など、コンパイル時に簡略することで、実行効率をあげることである。中間コードの形としては、三番地コードや四つ組などが有名である。コンパイラによっては、何度も最適化し、中間コードを生成するものもあるが、一般的に最適化はコンパイラの要であるために、そう方法については、非公開なこともある。 ４、条件文、繰り返し文に対するコード生成 ２重のif文 if(e1){ if(e2)s1 else s2 } に対して、以下のようなコード生成が得られる。 --------------------------------------- e1を計算し、結果が偽ならL1へ移動する。 e2を計算し、結果が偽ならL2へ移動する。 S1の実行 jmp L3 L2：s2の実行 L3： L1： --------------------------------------- L1とL3はそれぞれ、外側の内側のif文のコードの終わりを表すラベルである。これらは同じ場所を表すので、一方のラベルだけを使い、以下のようにするほうが、より簡潔のなる。 --------------------------------------- e1を計算し、結果が偽ならL1へ移動する。 e2を計算し、結果が偽ならL2へ移動する。 S1の実行 jmp L1 L2：s2の実行 L1： --------------------------------------- ５、字句解析器生成系と構文解析器生成系 （１）、字句解析器生成系 字句解析器生成系とは、文法ファイルに世紀表現で、処理対象の字句の定義を書いておく事で、自動的に字句解析プログラムを生成してくれるツールのことを言う。 有名なのが、lexとよばれ、yacc（次に説明する構文解析器生成系のツール）で生成する構文解析プログラムが呼び出す字句解析プログラムをlexが自動生成する。文法ファイルの記述は、正規表現で字句を記述する。 （２）、構文解析器生成系 構文解析器生成系とは、字句解析器生成系と同様に、記号列だけを見て会席できるように言語を設計し、自動的に構文木をつくるツールのことである。最も有名なものとして、yaccというのがある。yaccは、文法ファイルという自分の扱いたい文法を記述したファイルを、yaccにに入力することで、自動的にＣ言語のソースコードを生成してくれる。yaccでは、上向き構文解析で奇異席するので、今回の実験のLL(1)文法ではエラーが発生するために使えない。文法ファイルは、３つの部分からなっており、ヘッダ、規則部、ユーザー定義部である。最も重要な部分は規則部で、ここにＢＮＦで対象言語を書くと、後は自動で解析してくれる。