1 言語 |
1.1 自然言語・プラグラミング言語 1 |
1.2 構文論・意味論・語用論 3 |
1.3 言語の構成要素 6 |
1.4 あいまいな文 9 |
演習問題 11 |
2 準備 |
2.1 基本的用語 13 |
2.2 基本的表現法 24 |
2.3 基本的証明法 27 |
2.4 算術式の定義 30 |
2.5 算術式の評価 34 |
演習問題 37 |
3 字句の定義 |
3.1 正規式 42 |
3.2 有限状態プログラム 44 |
3.3 有限オートマトン 49 |
3.4 字句認識 53 |
3.5 字句解析 60 |
演習問題 61 |
4 構文の定義 |
4.1 書換えシステム 64 |
4.2 文脈自由文法 68 |
4.3 文脈自由文法の例 72 |
4.4 文脈自由文法の上の計算 75 |
4.5 文脈自由文法の変形 79 |
演習問題 82 |
5 構文解析技術の応用例 |
5.1 変換系 84 |
5.2 翻訳系 86 |
5.3 解釈系 87 |
5.4 実際例 88 |
演習問題 91 |
6 構文解析の手法 |
6.1 構文解析の原理 92 |
6.2 非決定性手続き表現 97 |
6.3 バックトラック計算 101 |
演習問題 106 |
7 形式言語の性質 |
7.1 正規式と文脈自由文法の能力限界 108 |
7.2 有限オートマトンと正規言語の性質 111 |
7.3 プッシュダウンオートマトンと文脈自由言語の性質 115 |
7.4 プログラミング言語の構文の非文脈自由性 120 |
7.5 文脈自由文法以外の構文定義法 121 |
演習問題 128 |
8 降下型解析 |
8.1 LL(κ)解析の原理 130 |
8.2 LL(κ)構文解析法 132 |
8.3 LL(κ)構文解析表の構成法 135 |
8.4 再帰降下型解析法 141 |
演習問題 146 |
9 上昇型解析 |
9.1 LR(κ)解析の原理 147 |
9.2 LR(κ)解析 150 |
9.3 LR(κ)解析表の種類 153 |
9.4 LR(κ)解析表の構成法 156 |
9.5 バイパス型LR(κ)解析表の構成法 164 |
演習問題 168 |
10 一般の文脈自由文法の構文解析 |
10.1 索表計算法 169 |
10.2 CYK法 170 |
10.3 Earley法 172 |
10.4 ATN法 177 |
10.5 Prolog法 180 |
演習問題 187 |
あとがき 189 |
参考文献 190 |
索引 193 |