I. プログラミング言語の基本概念
低レベル言語と高レベル言語
低レベル言語：機械語やアセンブリ言語は低レベル言語と呼ばれます。
- 機械語とは、0と1で構成される一連の機械命令のこと。
- アセンブリ言語とは、命令を記号で表す言語のことです。
- MOV AX,2
- MOV BX,3
- ADD AX,BX
高級言語：人間の論理的思考の観点から、あらゆる種類のアプリケーションに対応するプログラミング言語で、抽象度が非常に高く、実行する特定のマシン上でターゲットコードを呼び出すためのコンパイルが必要。このタイプの言語は、人間が使用する自然言語に近く、プログラミングの効率が大幅に向上します。
コンパイルおよび解釈されたプログラム
高級言語やアセンブリ言語で書かれたプログラムはソース・プログラムと呼ばれ、コンピュータ上で直接実行することはできません。
プログラムの実行方法：
コンパイルと実行：高級言語で書かれたプログラムを、コンパイルされた形でコンピュータ上で実行すること。
実行フェーズ：実際にターゲットプログラムを実行します。
利点：効率的な実行、小さなリソースフットプリント
欠点：互換性が低い
解釈実行：ソース・プログラムの各ステートメントは、解釈されるとすぐに実行されます。
- 利点：移植性の向上、開発の迅速化、ユーザーとの容易なコミュニケーション
- 欠点：非効率
コンパイルシステムの基礎
編集プログラムの作業プロセス：
字句解析
ソースプログラムを入力し、ソースプログラムを構成する文字列をスキャンして分解し、単語を1つずつ識別し、無駄な情報を削除し、解析のエラーを報告します。
基本構文表記法：キーワード、識別子、定数、演算子、区切り文字
語彙アナライザーが出力する単語記号は、しばしば次のようなバイナリで表されます：
語彙規則は通常、正規形と有限オートマトンを使って記述されます。
文法分析
- 文法パーサーは、単語記号を入力として受け取り、単語記号文字列を解析して、式、代入、ループなどの文法規則に適合した文法単位を形成しているかどうかを確認し、各文を解析して、文法規則に従って正しい論理構造を持っているかどうかをチェックします。
- 文法解析の方法
- トップダウン分析
- ボトムアップ分析
意味解析
- 意味解析の主な仕事は、代入文の右端と左端の不一致、式の除数が0かどうかなど、型を解析してチェックすることです。
中間コード生成
- 中間コード生成フェーズでは、意味解析の出力に基づいて中間コードを生成します。
- 中間コードはシンプルで意味のある記法システムで、いくつかの形式がありますが、一般的なものは逆ポーランド記法、四元数、三元数、木です。
- これらの共通の特徴は、コードの書き方が機械に依存しないことです。
- 中間コード生成フェーズでは、意味解析の出力に基づいて中間コードを生成します。
コードの最適化
- コードの最適化フェーズでは、前フェーズで生成された中間コードをスワップまたは適合させます。
オブジェクトコード生成
- これは、中間コードを特定のマシン上の絶対命令コードや再配置可能な命令コード、アセンブリ命令コードに変換することです。これはコンパイルの最終段階で、ハードウェア・システムの構造や命令の意味と連動します。
状態遷移図
状態遷移グラフは、ノードの状態を表す円、状態遷移を表すノード間の有向辺を持つ状態限定有向グラフです。
ステートチャートの機能：特定の文字列を識別するために使用されます。
状態遷移図の要件
- 限られた州数
- 状態数の制限
- 各辺に記された文字
状態遷移図の表現規約
- 初期状態は"○"で表示されます。
- 非終端状態は「○」で表示されます。
- 状態間のジャンプは"→"で示されます。
- 終了状態は「◎」で表示されます。
- でもう1文字読み込んでください。
正規表現と正規セット
状態遷移図は、字句解析手順のために構築することができますが、非形式的な記述です。
正規表現は字句解析の形式的表現です。形式的な方法というのは、ある問題を厳密な仕様を持つ記号の体系全体で記述する方法のことです。
利点：より明瞭で正確
正規形と正規集合の再帰的定義
εとΦはどちらもアルファベット∑上の正則式で、それらが示す正則集合はそれぞれ{ε}とΦです。
任意のa∈∑、aは∑上の正則式であり、それが表す正則集合は{a}です。
フォーマル フォーマル フォーマル フォーマル フォーマル フォーマル フォーマル フォーマル フォーマル
u l(u) l(u) ∪ l(v)
v l(v) l(u) l(v)
* :: L(U)*
以上の3つのステップを有限回繰り返して得られた式だけが∑上で正規です。これらの正規式で表される部分集合だけが∑上の正規集合です。
有限オートマトン
- 初期状態
- 初期状態
- 後継状態: 有限状態マシンが文字を読み込んで、その状態が別の状態に変化するとき、変化した状態を後継状態と呼びます。
- 有限状態機械は、各遷移後の状態が一意である場合、決定論的有限状態オートマトンと呼ばれ、遷移後の後継状態が一意でない場合、不確定有限オートマトンと呼ばれます。
有限状態マシンの決定
- 決定論的有限状態機械Mは5進数：M =
- Sは有限集合で、その各要素は状態と呼ばれます。
- ∑ は無限のアルファベットで、その各要素は入力文字と呼ばれます。
- δはS x ∑からSへの単一値部分写像です。δ = s'は次のことを意味します：優勢状態がSで入力aが入力されたとき、次の状態s'への遷移があり、s'をSの後継状態と呼びます。
- s0∈S
- s0Sでの一意な初期状態
プログラミング言語の制御構造
式
前置表現：ポーランド語表現としても知られ、演算子をオペランドに置くことで特徴付けられます。
中間表現：つまり、よく使われる表現、x 5 -6
サフィックス式：逆ポーランド法としても知られ、演算子をオペランドの後に置くのが特徴です。
プレフィックス式
- 式を右から左へスキャンし、数値に出会ったらその数値をスタックに押し込み、演算子に出会ったらスタックの一番上にある2つの数値をポップし、演算子を使ってその数値に対応する計算を行い、結果をスタックに入れます。式の一番左端まで上記のプロセスを繰り返し、最後の演算から得られる値が式の結果です
サフィックス式
- 算術式や論理式の一般化された表現で、演算子がオペランドの中央に接頭辞の形で置かれるもの。
サフィックス式
- 順序が左から右であることを除けば、前置式と似ています。演算子に出会うと、スタックの一番上にある2つの数値がポップアップされ、演算子を使って対応する計算が行われ、その結果がスタックに追加されます。上記のプロセスが式の一番右端まで繰り返され、最終的な計算で得られた値が式の結果となります。
IV.オペレーターの優先順位
優先順位
- ポインタが最適であり、正負の符号のような二項演算よりも単峰演算が望ましい
- まず掛け算と割り算、次に足し算と引き算
- 最初に乗算と除算を行い、次に加算と減算を行います。
- 論理的な最終操作
V. 粒子間構造
分類
- じゅんぶん
- 逐次ステートメント
- 選択文
プロセス制御
定義
int Function1(int x, int y){ ... }
int Function1(int x, int y){ ... }
