字句解析・構文解析の調査
今回の調査の目的は,既に文法定義が存在する言語の字句解析・構文解析プログラムを作成する際の注意点を列挙することである.新しい言語の定義を行う際の注意点の列挙や,字句解析・構文解析プログラムの自動生成プログラムを作成する方法の調査は今回の目的ではない.
注意点の概要をまとめる.
- 字句解析については特段に注意すべき点はない.
- 構文解析アルゴリズムは LL(1) または LALR(1) のどちらか.
- LL(1) は手書きに適している.
- LALR(1) は自動生成プログラムが必要.
- 構文解析における文法記述では,左再帰性・右再帰性に注意する必要がある.
- LALR(1) についてはシフト還元構文解析の考え方を理解する必要がある.
- 理解するには LR 状態や LR マーカ(ポインタ)の考え方を利用する.
- 理解しなければならないわけは,構文解析プログラムの自動生成の際に発生するエラーに対処するため.
- 理解するには LR 状態や LR マーカ(ポインタ)の考え方を利用する.
- 文法のあいまいさを解決するには,
- 文法を書き換える.
- 演算子の優先度,結合性などのあいまいさ除去規則を利用する.
- 文法を書き換える.
いつも間違えるのだが,最左導出とは,文法形式(規則の右辺)の中の非終端記号のうち,最も左のものを最初に(構文木の「上」のほうで)展開する導出である.右辺の選択肢(|による列挙)のうちの左右は関係ない.