本論文では，GLR法\cite{Tomita1987}に基づく痕跡処理の手法を示す．痕跡という考え方は，チョムスキーの痕跡理論で導入されたものである．痕跡とは，文の構成素がその文中の別の位置に移動することによって生じた欠落部分に残されると考えられるものである．例えば，``Achildwhohasatoysmiles.''という文では，`achild'がwhoの直後(右隣り)から現在の位置に移動することによって生じた欠落部分に痕跡が存在する．痕跡を{\itt}で表すと，この文は``Achildwho{\itt}hasatoysmiles.''となる．構文解析において，解析系が文に含まれる痕跡を検出し，その部分に対応する構成素を補完することができると，痕跡のための特別な文法規則を用意する必要がなくなり，文法規則の数が抑えられる．これによって，文法全体の見通しが良くなり，文法記述者の負担が軽減する\cite{Konno1986}．GLR法は効率の良い構文解析法として知られるが，痕跡処理については考慮されていない．本論文では，GLR法に基づいて痕跡処理を実現しようとするときに問題となる点を明らかにし，それに対する解決方法を示す．これまでに，痕跡を扱うための文法の枠組みが提案されるとともに，それらを用いた痕跡処理の手法が示されている\cite[など]{Pereira1981,Konno1986,Hayashi1988,Tokunaga1990,Haruno1992}．これらのうち痕跡の扱いに関する初期の考え方として，ATNGのHOLD機構\cite{Wanner1978}，PereiraによるXGのXリスト\cite{Pereira1981}が知られている．本論文で示す手法では，XGでのXリストの考え方と基本的に同じものを用いる．