字句解析・構文解析の調査

プログラミング言語の字句解析・構文解析を調べている．

今回の調査の目的は，既に文法定義が存在する言語の字句解析・構文解析プログラムを作成する際の注意点を列挙することである．新しい言語の定義を行う際の注意点の列挙や，字句解析・構文解析プログラムの自動生成プログラムを作成する方法の調査は今回の目的ではない．

注意点の概要をまとめる．

• 字句解析については特段に注意すべき点はない．
• 構文解析アルゴリズムは LL(1) または LALR(1) のどちらか．
• LL(1) は手書きに適している．
• LALR(1) は自動生成プログラムが必要．
• 構文解析における文法記述では，左再帰性・右再帰性に注意する必要がある．
  • LL(1) は最左導出を行うので，左再帰性があると構文解析ができない．
  • LALR(1) は最右導出を行うので，右再帰性があると効率が悪い．
• LALR(1) についてはシフト還元構文解析の考え方を理解する必要がある．
  • 理解するには LR 状態や LR マーカ（ポインタ）の考え方を利用する．
  • 理解しなければならないわけは，構文解析プログラムの自動生成の際に発生するエラーに対処するため．
• 文法のあいまいさを解決するには，
  • 文法を書き換える．
  • 演算子の優先度，結合性などのあいまいさ除去規則を利用する．
  という方法があるが，除去規則を用いたほうが効率がよく見通しがよい．

いつも間違えるのだが，最左導出とは，文法形式（規則の右辺）の中の非終端記号のうち，最も左のものを最初に（構文木の「上」のほうで）展開する導出である．右辺の選択肢（｜による列挙）のうちの左右は関係ない．

参考文献

[1] 佐々政孝 「プログラミング言語処理系」 第４章．

[2] Levine et al. 「lex & yacc プログラミング」 第８章．