\section{はじめに}
LR構文解析法は，構文解析アルゴリズムとして最も効率の良い手法の一つである．LR構文解析法の中でも，横型探索で非決定的解析を行うことにより文脈自由言語の扱いを可能にした方法は一般化LR法(GLR法)と呼ばれ，自然言語処理および，音声認識で利用されている．また，LR法の構文解析過程に確率を割り当てることで，確率言語モデルを得ることができる．確率一般化LR(PGLR)モデル\cite{inui1998}，およびその一般化であるAPGLRモデル\cite{akiba2001}は，構文解析結果の構文木の曖昧性解消や，音声認識の確率言語モデル\cite{nagai1994,imai1999,akiba2001}として利用されている．LR構文解析法では，文法が与えられた時点であらかじめ計算できる解析過程を先に求め，LR解析表(以下，LR表)で表しておき，文解析時に利用する．LR法は，言わば，空間効率を犠牲にする(LR表を作成する)ことによって，解析時間の効率化を実現する手法である．LR法を実際の問題に適用する場合の問題点の一つは，文法の規則数増加に伴うLR表のサイズの増大である．計算機言語の解析\cite{aho1986}，自然言語の解析\cite{luk2000}，音声認識\cite{nagai1994}，それぞれの立場からこの問題点が指摘されている．LR表のサイズを押えるひとつの方法は，解析効率を犠牲にして空間効率をある程度に押える方法である．本来LR法が利用されていた計算機言語用の構文解析においては，LR法は決定的解析器として利用されてきた．決定的解析としてのLR法が扱える文法は，文脈自由文法のサブセットである．LR表は，その作り方から幾つかの種類に分類されるが，それらは決定的解析で扱える言語に違いがある．単純LR(SimpleLR;SLR)表は，作り方が単純で表サイズを小さく押えられるが扱える文法の範囲が狭い．正準LR(CannonicalLR;CLR)表は，サイズは非常に大きくなるが扱える文法の範囲は最も広い．両者のバランスを取るLR表として，サイズを小さく押えつつ扱える文法の範囲をそこそこ広くとれる，LALR(LookAheadLR)表が提案されている．一方，文脈自由文法を扱う自然言語処理でLR表を利用する場合は，非決定的解析として利用するのが普通である．決定的解析で扱える言語の大きさは，非決定的解析での解析効率に相当する．すなわち，SLR,LALR,CLRの順に効率は良くなるが，それに伴い表のサイズは増大する．また，計算機言語に用いるLR表のサイズ圧縮手法には，2次元配列としてのスパースな表をいかに効率よく圧縮するかという視点のものも多い．これらは，作成後の表を表現するデータ構造に工夫を行ったもので，表自体が運ぶ情報には違いがない．自然言語処理の分野でも，解析表縮小の手法が提案されている．田中らは，文脈自由文法と単語連接の制約を切り放して記述しておき，LRテーブル作成時に2つの制約を導入する手法(MSLR法)\cite{tanaka1995}を用いることで，単独の文脈自由文法を記述するより解析表のサイズを小さくすることができたと報告している\cite{tanaka1997}．Lukらは，文法を小さな部分に分割して，それぞれを扱うパーザを組み合わせることで，解析表のサイズを押える方法を提案している\cite{luk2000}．以上の従来手法をまとめると，次の3つの手法に分類できる．\begin{enumerate}\item処理効率を犠牲にして空間効率を稼ぐ方法．\item表のデータ構造を工夫して記憶量を引き下げる方法．\item文法の記述方法を工夫してより小さな表を導出する方法．\end{enumerate}本稿では，LR表のサイズを圧縮する，上記の3分類には当てはまらない新規の手法を提案する．提案法は従来の手法と異なり，LR表作成アルゴリズムの再検討を行い，解析に不要な情報を捨象することによって，表の圧縮を実現する．本手法は，次のような特徴を持つ．(1)上記の従来の縮小手法とは手法の軸が異なるため，どの手法とも同時に適用可能である\footnote{ただし，MSLR法\cite{tanaka1995}との同時適用には，表作成に若干の修正が必要である．MSLR法では，提案法で解析に不要とする情報の一部を利用しているためである．MSLR法への対応方法ついては，付録.Bで述べる．}．(2)入力文の構文木を得るという自然言語処理用途において，提案法は解析時の効率に影響をあたえることはない\footnote{計算機言語の構文解析では，解析時に規則に付随するアクション(プログラム)を実行することが要求される．提案法による圧縮LR表では適用されるCFG規則は解析時に動的に求まるので，規則から付随するアクションを検索する処理の分オーバーヘッドが生じる．入力文から構文木を得ることを目的とする自然言語処理用途では，このオーバーヘッドは生じない．}．(3)従来の表作成および解析アルゴリズムへの変更個所は小さく，プログラムの軽微な修正で適用可能である．特に，提案法によって作成された圧縮LR表は，既存のLR構文解析プログラムでほぼそのまま利用可能である．本稿の構成は以下の通りである．まず\ref{ss:base}節で，提案法の基本原理を説明する．また，提案法の性質を考察する．続く\ref{ss:experiment}節では，提案法の実装方法と，実際の文法に提案手法を適用した実験結果を示す．\ref{ss:extension}節では，提案手法の限界を克服するための拡張方法について述べ，実際の文法に適用した結果を報告する．\ref{ss:related}節では，関連研究について述べる．
\section{LR解析表の圧縮}
\label{ss:base}本稿で提案するLR解析表の圧縮方法について，その原理と性質について述べる．\subsection{提案法の基本原理}\label{sec:basic}LR構文解析法は，LR表と，スタック，先読み語を参照し，次の動作を決定する．LR表は，文法が与えられた時点であらかじめ計算できる構文解析過程を表したものである．LR表の作成(付録.A参照)には，構文解析中のある状態を表すデータ構造として，LR項(LRItem)を用いる．LR項とは，ある生成規則(CFG規則)の右辺の記号列中のある位置にドット`・'を付けたデータ構造である．ドットは，記号列のどの部分まで解析が進んだかを表す．下記のLR(0)項\footnote{説明では，LR(0)項を用いるが，提案法は，LR(1)項にも適用可能である．すなわち，SLR,LALR,CLRなどのLR表の種類に依らず適用可能である．}は，生成規則$A\rightarrow\alpha$において，$\alpha$の先頭部分列$\beta$まで解析が終了し，その後記号列$\gamma$を解析する必要がある状態を表す．\begin{quote}$[A\rightarrow\beta\cdot\gamma]$\end{quote}$\beta$や$\gamma$は空記号列の場合も含まれる．例えば，生成規則$A\rightarrowB_1B_2B_3$に対して，$[A\rightarrow\cdotB_1B_2B_3]$,$[A\rightarrowB_1\cdotB_2B_3]$,$[A\rightarrowB_1B_2\cdotB_3]$,$[A\rightarrowB_1B_2B_3\cdot]$の4つのLR項が考えられる．このように，従来のLR表で用いられるLR項は規則毎に作成され，LR項だけで解析中の規則とその解析位置，解析された記号列($\beta$)およびこれから解析すべき記号列($\gamma$)を特定することができる．一方，LR構文解析法では，解析途中の状態を表現するデータ構造として，解析済の(終端および非終端)記号を記憶する解析スタックが併用される(文脈自由言語を受理するプッシュダウン・オートマトンのスタックに相当する)．上の例のLR項が表す状態では，解析スタックには，記号列$\beta$が，スタックトップから逆順に保持されているはずである．例えば，LR項$[A\rightarrowB_1B_2\cdotB_3]$が表す状態では，スタックは$[...B_1,i,B_2,j]$(ただし，$i,j$は状態番号，スタックトップは右)となる．したがって，すでに解析済の記号列は，LR項と解析スタックに重複して記載されており，冗長である．そこで，LR項から冗長な解析済記号列$\beta$の記号情報を捨象することが可能となる．ここで，捨象可能なのは，記号情報だけで，記号数の情報は保持する必要があることに注意されたい．解析スタックには，解析済の記号がその記号が属する規則に関係なくフラットに保持される．スタック$[...,B_1,i,B_2,j,B_3,k]$を見ただけでは，記号$B_3$が規則$A\rightarrowB_3$，$A\rightarrowB_2B_3$，$A\rightarrowB_1B_2B_3$のいずれに属する$B_3$なのか，区別することができない．そこで，LR項が表す解析状態で，スタックトップからいくつの記号がこの規則で解析中かという情報を保持しなければならない．以上のことから，従来のLR項のドットの左側の記号列を抽象化して，その記号の個数で置き換え，新しいLR項とする．すなわち，次のようなLR項を用いる．\begin{quote}$[A\rightarrow|\beta|\cdot\gamma]$\end{quote}ここで，$|\beta|$は，記号列$\beta$の記号数を表すものとする．このLR項を{\bf左方抽象化LR項}と呼ぶことにする．例えば，生成規則$A\rightarrowB_1B_2B_3$に対して，$[A\rightarrow0\cdotB_1B_2B_3]$,$[A\rightarrow1\cdotB_2B_3]$,$[A\rightarrow2\cdotB_3]$,$[A\rightarrow3\cdot]$の4つの左方抽象化LR項が考えられる．LR表は，生成規則集合が与えられた時点で，そこから求められる構文解析時のあらゆる解析途中の状態を抽出し，また各状態間の遷移関係を求めて，状態遷移図(プッシュダウンオートマトン)として表現したものである．ここで解析途中の状態は，LR項の集合(クロージャ)に対応し，規則適用の部分的解析結果(LR項に相当)の複数の可能性(集合)を表している．この時，解析状態の同一性は，クロージャの同一性で判断される．例えば，異なる解析パスから，同一のLR項集合が得られる場合，それらは同じ状態とみなすことができる．クロージャの要素として，従来のLR項の代わりに，不必要な情報が捨象された左方抽象化LR項を用いると，より多くの解析状態(クロージャ)が同一の状態と見なされる．したがって，結果として得られるLR表の状態数が減少し，表のサイズが縮小される．これが提案手法の原理である．\newpage\subsection{圧縮LR表作成アルゴリズム}LR表作成アルゴリズムは，従来のLR項の代わりに，上記の左方抽象化LR項を用いても，新たな処理を加えること無く若干の修正だけで適用できる．以下では，LR表作成手順の[クロージャ][GOTO手続き][LR項集合の集合][LR表の作成]の各手続き(付録.A参照)，それぞれについて，修正手続きを示す．(この手法を，{\bf提案法1}と呼ぶ．また提案法1によって作成されたLR表を{\bf圧縮LR表}と呼ぶ．)[クロージャ]，[GOTO手続き]，[LR項集合の集合]では，LR項のドットの左側を参照する手続きが存在しないので，左方抽象化LR項を用いて，ほぼそのまま，「LR項集合の集合」を作成できる．唯一，ドットの左側の生成・修正の手続きに若干の変更を加える．具体的には，以下の2点を変更する．[クロージャ]作成手続きのステップ2を次のように変更する．\begin{enumerate}\setcounter{enumi}{1}\item$\mbox{closure}(I)$に左方抽象化LR項$[B\rightarrow|\beta|\cdotA\gamma]$があれば，左辺が$A$の全ての生成規則$A\rightarrow\alpha$について，LR項$[A\rightarrow0\cdot\alpha]$を加える．この手続きを新たなLR項が加えられなくなるまで繰り返す．\end{enumerate}また，[GOTO手続き]$\mbox{GOTO}(I,A)$を次のように変更する．\begin{itemize}\item$I$中の，ドットのすぐ右が$B$である全てのLR項$[A\rightarrow|\beta|\cdotB\gamma]$に対し，LR項$[A\rightarrow|\beta|+1\cdot\gamma]$を求め，そのクロージャを返す．\end{itemize}得られたLR項集合の集合から[LR表の作成]において，$\mbox{action}$表への$\mbox{shift}$や$\mbox{accept}$の書き込み，および$\mbox{goto}$表の作成にも変更点はない．一方，$\mbox{reduce}$動作の引数には，従来の生成規則の代わりに，生成記号の左辺記号と右辺記号列の記号数のペアを記述する．すなわち，[LR表の作成]のreduce動作の書き込みを次のように変更する．\begin{itemize}\item$I_i$にLR項$[A\rightarrow|\alpha|\cdot]$が存在するならば，$a\infollow(A)$について，$\mbox{action}(i,a)$に$\mbox{reduce}~~|\alpha|,A$を加える．\end{itemize}このように，修正手続きで作成されるLR表では，reduce動作の引数には生成規則のうち，左辺の記号列の記号情報を捨象した一部の情報しか記述されない．しかし，この情報$|\alpha|$と$A$さえあれば，どの生成規則が適用されたかは，構文解析時に特定可能である点に注意されたい．左辺記号$A$と，解析スタックから$|\alpha|$個の記号をポップすることで得られる記号列$\alpha$から，$A\rightarrow\alpha$と復元可能である．また，提案手法での修正箇所は，既存の表作成アルゴリズム中のある手続きを同等の手続きで置き換えただけであり，新たな手続きの呼び出しは行っていない．したがって，従来の表作成アルゴリズムと同じ計算オーダで作成可能である．\newpage\subsection{提案法の適用例}日本語において，動詞の格を表す句は，語順が自由であり，任意に省略可能であることが多い．次のような日本語を解析する文法(図\ref{fig:g_example})を考える．\begin{quote}太郎が花子にりんごを与える花子に太郎がりんごを与えるりんごを太郎が花子に与える太郎がりんごを与えるりんごを与える与える\end{quote}\begin{figure}\begin{quote}\begin{verbatim}S→PP_HUMAN_gaPP_HUMAN_niPP_OBJECT_woVPS→PP_HUMAN_gaPP_OBJECT_woPP_HUMAN_niVPS→PP_HUMAN_niPP_HUMAN_gaPP_OBJECT_woVPS→PP_HUMAN_niPP_OBJECT_woPP_HUMAN_gaVPS→PP_OBJECT_woPP_HUMAN_gaPP_HUMAN_niVPS→PP_OBJECT_woPP_HUMAN_niPP_HUMAN_gaVPS→PP_HUMAN_niPP_OBJECT_woVPS→PP_OBJECT_woPP_HUMAN_niVPS→PP_HUMAN_gaPP_OBJECT_woVPS→PP_OBJECT_woPP_HUMAN_gaVPS→PP_HUMAN_gaPP_HUMAN_niVPS→PP_HUMAN_niPP_HUMAN_gaVPS→PP_OBJECT_woVPS→PP_HUMAN_niVPS→PP_HUMAN_gaVPS→VPPP_HUMAN_ga→NP_HUMANがPP_HUMAN_ni→NP_HUMANにPP_OBJECT_wo→NP_OBJECTをNP_HUMAN→太郎NP_HUMAN→花子NP_OBJECT→りんごNP_OBJECT→本VP→与えるVP→渡す\end{verbatim}\end{quote}\caption{文法例}\label{fig:g_example}\end{figure}この文法から，従来の表作成アルゴリズムと，提案法による表作成アルゴリズムによってつくられたGOTOグラフの一部(記号`S'を左辺に持つ規則の集合に相当する部分)を，それぞれ図\ref{fig:goto}，図\ref{fig:r_goto}に示す．従来法では，規則右辺に現れる記号列の文脈によって異なる状態が作成されるため，木の形に分岐したグラフが作成される．一方提案法では，記号列の文脈によらずに後方部分がマージされたグラフが作成され，状態数が32から12へ大幅に減少することが分かる．\begin{figure}\begin{center}\leavevmode\epsfile{file=goto2.eps,scale=1.0}\caption{従来法によるGOTOグラフ}\label{fig:goto}\end{center}\end{figure}\begin{figure}\begin{center}\leavevmode\epsfile{file=r_goto2.eps,scale=1.0}\caption{提案法によるGOTOグラフ}\label{fig:r_goto}\end{center}\end{figure}\subsection{提案法の効果と解析効率}\label{ss:quality}提案法の効果と効率について，その性質を考察する．\subsubsection{圧縮の効果}LR項においてドットより左方の記号列が記号数へと抽象化されることにより，従来異なるLR項として認識された以下のような2つのLR項が，同一のLR項として認識されることになる．\begin{quote}$[A\rightarrow\beta_1\cdot\gamma]$~~~,~~~$[A\rightarrow\beta_2\cdot\gamma]$where$|\beta_1|=|\beta_2|$\end{quote}これらから生成されるクロージャも同一のクロージャとなる．すなわち，「LR項集合の集合」作成時に，従来異なる状態(LR項集合)となっていたものが，1つの状態にマージされることになる．よって，最終的なLR表の状態数は減少する．ここで，マージされるLR項が存在するための，文法$G$の必要条件を考察する．上記の同一視される2つのLR項について，$\beta_1$と$\beta_2$以外は等しくなければならない．また，$|\beta_1|=|\beta_2|$，すなわち$|\beta_1\gamma|=|\beta_2\gamma|$である必要がある．以上をまとめると，文法$G$に，以下の条件を満たす規則のペア$A_1\rightarrow\alpha_1$，$A_2\rightarrow\alpha_2$が少なくとも一組以上存在する必要がある．\begin{itemize}\item左辺記号$A_1$，$A_2$が等しい．\item$\alpha_1$と$\alpha_2$の接尾記号列が一致する．すなわち，$\alpha_1=\beta_1\gamma_1$，$\alpha_2=\beta_2\gamma_2$と書けるとき，$\gamma_1=\gamma_2$となる$\gamma_1,\gamma_2$が存在する．\item$|\alpha_1|=|\alpha_2|$\end{itemize}このような規則のペアが，文法$G$中に多く存在するほど，提案法による状態数の削減の効果は大きい．\subsubsection{解析の効率}圧縮LR表を用いて構文解析を行った場合の効率について考える．提案法は，すでに解析済の情報(ドットの左側の記号情報)だけを捨象する．これから解析する部分(ドットの右側の記号情報)には手を加えない．提案法によって状態の統合が行われた場合，統合後の状態(クロージャ)は以前の状態と同数のLR項を持ち，それぞれのLR項のこれから解析する部分(ドットの右側の記号情報)も等しい．したがって，統合後もその後の解析の処理量は等しく，構文解析の効率は悪くならない．\newpage
\section{実装と実験}
\label{ss:experiment}\subsection{実装}提案法を実装するには，LR表作成プログラム，構文解析プログラムの修正が必要となる．しかし以下に示す通り，既存の処理系のわずかな個所の修正で実装可能である．\subsubsection{LR表}圧縮LR表では，従来のLR表と比べ，唯一reduce動作の引数の意味が変更になる．従来のLR表では，reduce動作の引数には生成規則を指定する．実際には，規則へのポインタ(規則番号)が記述される．一方，圧縮LR表では，生成規則から右辺の記号情報を捨象した情報，すなわち「左辺記号と右辺の記号数」(へのポインタ)である．あらかじめ存在する生成規則のリストとは異なり，「左辺記号と右辺の記号数」のリストは表作成のために新規に導入する概念である．厳密に実装するならば，LR表作成プログラムでこのリストを新規に作成し，構文解析プログラムとの間でこのリストを共有しなければならない．しかし，「左辺記号と右辺の記号数」は生成規則の一部であることを利用して，reduceの引数に「左辺記号と右辺の記号数」の条件を満たす任意の規則番号を記述し代用することで，リストの受け渡しを避けることが可能である．\subsubsection{LR表作成プログラム}提案法で用いる左方抽象化LR項は，次のような方法によって，既存のLR表作成プログラムに比較的容易に導入することが可能である．左方抽象化LR項は，文法に現れない記号$X$を$|\beta|$個ドットの左に書くことでも表現できる．例えば，$|\beta|=2$とすると，次のように書ける．\begin{quote}$[A\rightarrowXX\cdot\gamma]$\end{quote}このようなLR項表現は，従来のLR項と容易に交換可能である．GOTO手続きにおいて，LR項のドットを右へ一つ移動する時に，飛び越えた記号を$X$で置き換えるように変更するだけで，従来法に組み込むことができる．\subsubsection{構文解析プログラム}「左辺記号と右辺の記号数」リストの参照を除けば，圧縮LR表は，従来のLR構文解析アルゴリズムでそのまま利用可能である．また多くの実装系では，読み込んだ規則集合のうち，実際の解析に利用する「左辺記号と右辺の記号数」だけを保持するものが多いため，提案法の実装は極めて容易である．実際，MSLRパーザ\cite{mslr1998}では，LR表読み込み部分の若干の修正で動作可能となった．また，LR法を利用した音声認識システムniNja\cite{itou1992}では，全く修正の必要はなくそのまま動作可能であった．\subsection{実験}\label{sec:exp1}提案法の効果を調べるため，3種類の文法から従来法と提案法1でLR表を作成し，表のサイズを比較した．比較には，LR表(およびGOTOグラフの)状態数，表中の空欄でないセルの数を表すエントリ数，を用いた．文法「道案内1」「道案内2」は，道案内対話\cite{itou1999}に現れるユーザの発話をモデル化した文法で，音声認識用に設計された\cite{akiba2001}．語彙サイズはどちらも約380，規則数はそれぞれ616，1302である．「道案内2」は，「道案内1」に比べて，意味的に整合性のある文だけを受理するように，より強い制約を加えた文法である．文法「旅行会話」は，ATR研究用自然発話音声データベース\cite{morimoto1994}旅行会話タスクの発話を受理するように記述した文法である\cite{imai1999}．語彙サイズは2839，規則数3971と，文法1,2に比べて大規模な文法である．また，自然言語処理用途に開発されており，入力文に対して構文的に可能な数多くの構文木を割り当てる．提案法1でLR表を作成し，その性質を調べた．結果を表\ref{tbl:state}に示す．すべての文法について，LR表圧縮の効果が得られていることがわかる．LR表のサイズは，「道案内1」「道案内2」に関しては約60\,\%前後に，「旅行会話」に関しては約1/4まで圧縮することができた．文法の規則数が大きいほど圧縮率が大きくなる傾向が見られるが，これは規則数が増えることで，\ref{ss:quality}節で述べた性質を満たす規則対の候補が増えることに起因すると考えられる．また，作成したLR表を用いてテキスト解析の実験を行ったが，従来のLR表を使った場合と全く同じ結果が得られ，解析時間にも差は認められなかった．\begin{table}\caption{LR表圧縮の効果}\label{tbl:state}\begin{center}\begin{tabular}{|l|l|r|r|r|r|r|}\hline&文法&\multicolumn{2}{c|}{道案内1}&\multicolumn{2}{c|}{道案内2}&\multicolumn{1}{c|}{旅行会話}\\\cline{2-7}&LR表タイプ&\multicolumn{1}{c|}{SLR}&\multicolumn{1}{c|}{CLR}&\multicolumn{1}{c|}{SLR}&\multicolumn{1}{c|}{CLR}&\multicolumn{1}{c|}{SLR}\\\cline{2-7}&規則数&\multicolumn{2}{c|}{616}&\multicolumn{2}{c|}{1,302}&\multicolumn{1}{c|}{3,971}\\\hline従来法&状態数&703&876&2,079&3,530&4,017\\&エントリ数&13,689&15,164&21,092&29,698&10,054,708\\\hline&状態数&444&568&757&1,815&935\\提案法1&(圧縮率)&(63.2\,\%)&(64.8\,\%)&(36.4\,\%)&(51.4\,\%)&(23.3\,\%)\\(左方抽象化LR項)&エントリ数&8,031&9,155&12,282&18,669&2,250,317\\&(圧縮率)&(58.7\,\%)&(60.4\,\%)&(58.2\,\%)&(62.9\,\%)&(22.4\,\%)\\\hline&状態数&404&518&669&1,600&842\\提案法2&(圧縮率)&(57.5\,\%)&(59.1\,\%)&(32.1\,\%)&(45.3\,\%)&(21.0\,\%)\\(可変長LR項)&エントリ数&7,111&8,132&10,435&16,345&1,978,521\\&(圧縮率)&(51.9\,\%)&(53.6\,\%)&(49.5\,\%)&(55.0\,\%)&(19.7\,\%)\\\hline\end{tabular}\end{center}\end{table}
\section{更なる圧縮のための改良手法}
\label{ss:extension}\ref{ss:quality}節で述べたように，(1)規則左辺の記号が同じ，(2)右辺の接尾部分が共通，(3)右辺の記号数が同じ，の3条件を満たす規則の組が文法中に多く現れるほど，提案法の効果は大きい．このうち，(3)右辺記号数の条件は，改善の余地がある．本節では，この条件を克服するための拡張方法について述べる．\subsection{可変長LR項}ドットの左側に記号数が必要なのは，reduce動作時にスタックからポップする要素数を記録するためである．この要素数は，LR表にreduce動作の引数として，静的に記述される．しかし，このポップ要素数は解析時に動的に求めることもできる．そこで，図\ref{fig:stack}のように，この情報をスタックに保持することを考える．すなわち，reduce動作の際，スタックに保持された区切り位置までポップするような構文解析アルゴリズムを考える．\begin{figure}\begin{center}\leavevmode\epsfile{file=stack2.eps,scale=1.0}\caption{区切り付きスタック}\label{fig:stack}\end{center}\end{figure}このような区切りをスタックに入れるようなLR表はどのように生成すればよいだろうか．区切りは，規則右辺の最初の記号をスタックに積む時に挿入すればよい．すなわち，LR項\begin{quote}$[A\rightarrow\cdotB\alpha]$\end{quote}からGOTO手続きによって，LR項\begin{quote}$[A\rightarrowB\cdot\alpha]$\end{quote}を生成する際に，スタックに挿入すればよい．ドットが最左にある場合の，次の状態への遷移(すなわち，shift動作やgoto)の場合に，スタックに区切りを挿入する．注意すべきなのは，ある状態(クロージャ)に，ドットのすぐ右の記号が同じで，ドットが最左のものと規則途中にあるものの，2つ以上のLR項が含まれている場合があることである．すなわち，次のような2つのLR項が，同じクロージャ$I$に含まれている可能性がある．\begin{quote}$[A\rightarrow\cdotB\alpha]$~~~,~~~$[A\rightarrow\beta\cdotB\gamma]$\end{quote}この場合，前者(ドットが最左のもの)と後者(ドットが途中のもの)からの，記号$B$による遷移($\mbox{GOTO}(I,B)$)を別に扱うことを考える．例えば，前者を記号$B_{\mbox{start}}$による遷移，後者を記号$B_{\mbox{cont}}$による遷移とし，$\mbox{GOTO}(I,B_{\mbox{start}})$と$\mbox{GOTO}(I,B_{\mbox{cont}})$を別々に計算する．このように変更したGOTOグラフでは，もはやLR項にドット左の記号数は必要ない．ただし，ドットが最左であるか，途中であるかの区別は必要となる．ドットが途中にある場合のLR項を，次のようなドット左方可変長のLR項で表すことにする．\begin{quote}$[A\rightarrow*\cdot\gamma]$\end{quote}記号$*$は，長さ1以上の記号列があることを表す．このようなLR項を用いることで，ドット左方の記号列に関する情報がさらに抽象化され，GOTOグラフ作成時の状態数がさらに減少することが期待できる\footnote{ただし，GOTO手続きの記号を場合別けしたことによって，状態数が増加するため，全体としてかならずしも状態数減少になるとは限らない．}．LR表生成アルゴリズムに必要な変更点は，以下の通りである．(この変更を行った手法を{\bf提案法2}とする．){\flushleft\bf[GOTO手続き]}\begin{itemize}\item$I$中の，ドットのすぐ右が$B$であるLR項$[A\rightarrow\cdotB\gamma]$すべてに対し，LR項$[A\rightarrow*\cdot\gamma]$を求め，そのクロージャを$\mbox{GOTO}(I,B_{\mbox{start}})$の返り値とする．また，LR項$[A\rightarrow*\cdotB\gamma]$に対し，LR項$[A\rightarrow*\cdot\gamma]$を求め，そのクロージャを$\mbox{GOTO}(I,B_{\mbox{cont}})$の返り値とする．\end{itemize}{\flushleft\bf[LR項集合の集合]}\begin{enumerate}\setcounter{enumi}{1}\item$C$の各LR項集合$I$，$G'$のある記号$A$，$s\in\{\mbox{start},\mbox{cont}\}$について，$\mbox{GOTO}(I,A_s)$を計算し，LR項集合$I'$を求め，$C$に加える．この手続きを，$C$に新たなLR項集合が加えられなくなるまで繰り返す．\end{enumerate}{\flushleft\bf[LR表の作成]}\begin{itemize}\item終端記号$a$と，$s\in\{\mbox{start},\mbox{cont}\}$について，$\mbox{GOTO}(I_i,a_s)=I_j$ならば，$\mbox{action}(i,a)$に$\mbox{shift}~s,j$を加える．\item非終端記号$A$，$s\in\{\mbox{start},\mbox{cont}\}$について，$\mbox{GOTO}(I_i,A_s)=I_j$ならば，$\mbox{goto}(i,A)$に$s,j$を加える．\end{itemize}構文解析アルゴリズムに必要な変更は，以下の3点である．\begin{itemize}\itemshift動作とgoto時に，LR表の記述に従い，スタックに区切り記号を挿入する．\itemshift動作とgoto時に，shift/shiftコンフリクト，goto/gotoコンフリクトを扱えるようにする．実装は，GLR法によるshift/reduceコンフリクト，shift/reduceコンフリクトの扱いと同様に，スタックを分岐させればよい．\itemreduce動作の際，従来の固定数ポップ動作の代わりに，スタックの最初の区切り記号までポップする．\end{itemize}\subsection{実験}\ref{sec:exp1}節で用いた3種類の文法から，提案法2を用いてLR表を作成した．実験結果を表\ref{tbl:state}に示す．LR表のサイズをさらに10\,\%程度縮小できることを確認した．また，音声認識システムniNja\cite{itou1992}に提案法2の解析アルゴリズムを実装し，従来法と同じ解析結果が得られることを確認した．
\section{関連研究}
\label{ss:related}\subsection{共通記号列のまとめ処理}生成規則($A\rightarrow\alpha$)に対し右辺記号列($\alpha$)中のある位置にドット`・'を付けたデータ構造($A\rightarrow\beta\cdot\gamma$,ただし$\alpha=\beta\gamma$)は，項(Item)と呼ばれ，構文解析中に規則のどこまで解析が進んだかを表すために，本稿で述べたLR項の他，Earley法\cite{earley1970}やチャート法\cite{key1980}など，種々の構文解析アルゴリズムで共通に利用されている．本稿で示した手法は，LR法においてItem以降の解析がドットの左側(右辺記号列のprefix，$\beta$)には依存しないことを利用し，ドットの右側の記号列(右辺記号列のsuffix，$\gamma$)が共通なものをまとめあげることによって，LR表の圧縮を実現したと考えることができる．同様に，Itemのドット左右の記号列について複数の規則の間で共通する記号列をまとめて処理することによる，解析の効率化手法が知られている．本稿の提案法のように，ドットの右側の記号列($\gamma$)が共通なItemをまとめて扱う手法が提案されている．文献\cite{leermakers1992}では，Earley法においてItem以降の解析がドットの右側の記号列($\gamma$)のみに依存し，ドットの左側($\beta$)や生成規則左辺の記号($A$)には依存しないことを利用して，これらを重複処理しないことによる効率化手法が示されている．文献\cite{moore2000}では，同様の手法をチャート法に適用している．逆に，ドットの左側の記号列($\beta$)が共通なItemをまとめて処理する手法としては，LR法が挙げられる．LR法では，共通なprefixを持つ複数のItemをまとめて解析の一状態とするようにLR表を作成することで，解析の効率化を実現している．文献\cite{nederhof1994}では，この考え方を進めて，共通のprefixをもつ規則をすべてまとめて処理する手法が示されている．また，共通したprefixを持つ2つ以上の規則を持たないように文法を変形することによって効率化を行なう手法も提案されている\cite{moore2000}．\subsection{可変な規則長の扱い}本稿の提案法2では，ドット左側の記号数情報を捨象した可変長LR項の導入のため，reduce動作時にスタックからポップする記号数を動的に求める必要があった．そのために，GOTO手続きを規則の解析開始か途中かによって別々に計算する手法を示した．同様の考え方は，規則の右辺に記号の正規表現を許した拡張CFG(正規右辺文法)を扱うLR構文解析法として提案されている\cite{nederhof1994,purdom1981}．正規右辺文法では，規則の右辺に合致する記号数を予め知ることができないので，解析時に動的に求める必要があるためである．
\section{結論}
解析に使用するLR表の大きさが問題であったLR構文解析法について，表作成に用いられる基本データ構造(LR項)の見直しを行うことにより，LR表の状態数を減少させ，サイズを圧縮する手法について述べた．提案法を実際の文法に適用したところ，規則数500〜1500程度の文法に対しては元のサイズの60\,\%程度，規則数4000の文法に対しては25\,\%程度に圧縮できることを確認した．提案法は，従来のLR表作成アルゴリズム，解析アルゴリズムに大きく手を加えることなく実装可能であるとともに，解析効率に影響を与えることもない．また，提案法を拡張し圧縮率を改善する手法を検討した．アルゴリズムへの変更個所は増加するが，実験結果ではさらに10\,\%程度サイズを圧縮できることを確認した．本研究により，これまで解析表のサイズの問題でLR法の適用が困難であった分野，例えば大規模な文法を用いた自然言語処理や音声認識，また計算資源(記憶容量)に制限がある環境(例えば，モバイル用途)での使用などにおいて，効率の良いLR法を適用する機会が増えると考えられる．\acknowledgment本稿の実験には，東工大田中・徳永研究室で開発されたMSLRパーザ\cite{mslr1998}および文法を使用した．また，本手法に関して御討論いただいた田中・徳永研究室の皆様に感謝する．\bibliographystyle{jnlpbbl}\bibliography{427}\appendix
\section{LR表作成手順}
LR表は，文法が与えられた時点であらかじめ計算できる構文解析過程を表したものである．LR構文解析法におけるパーザは，このLR表と，スタック，先読み語，を参照し，次の動作を決定する．LR表には，SLR(SimpleLR)，LALR(Look-AheadLR)，CLR(CanonicalLR)，などの幾つかのバリエーションがあり，これらは決定性解析で扱える言語の範囲に違いがある．以下，説明のためLR表の作成法を簡単に述べる．詳細は文献\cite{aho1986,tanaka1989}等を参照されたい．LR項は，LR表作成に使用するデータ構造であり，構文解析中のある状態を表すものである．SLR表作成にはLR(0)項を，CLR表作成にはLR(1)項を用いる\footnote{LALR表作成には，LR(0)項，LR(1)項それぞれから作成する手法が知られている．}．LR(0)項とは，ある生成規則の右辺の任意の位置にドットを付けたデータ構造である．ドットは，規則中のどの部分まで解析が進んだかを表す．下記のLR(0)項は，生成規則$A\rightarrow\alpha$において，$\alpha$が$\beta\gamma$と書けるとき，$\beta$まで解析が終わった状態を表している．\begin{quote}$[A\rightarrow\beta\cdot\gamma]$\end{quote}LR(1)項とは，ドット付き生成規則と，1つの先読み語(終端記号)からなるデータ構造である．下記のLR(1)項は，同様に$\beta$まで解析が終わった状態を表し，さらに1つの先読み語$a$を持つ．$a$は，直感的には，この生成規則適用の直後に現れる先読み語を表す．\begin{quote}$[A\rightarrow\beta\cdot\gamma,a]$\end{quote}以降の説明では，LR(0)項を用いてSLR表を作成する場合について考えるが，LR(1)項からCLR表を作成する場合も，先読み語の計算が付け加わるだけで，ほぼ同様に求めることができる．{\flushleft\bf[クロージャ]}クロージャ(closure)とは，LR項の集合であり，あるLR項集合$I$が与えられると，以下の手続きでクロージャ$\mbox{closure}(I)$を求めることができる．\begin{enumerate}\item$I$の全要素を$\mbox{closure}(I)$に加える．\item$\mbox{closure}(I)$にLR項$[B\rightarrow\beta\cdotA\gamma]$があれば，左辺が$A$の全ての生成規則$A\rightarrow\alpha$について，LR項$[A\rightarrow\cdot\alpha]$を加える．この手続きを新たなLR項が加えられなくなるまで繰り返す．\end{enumerate}クロージャとは，直感的には，あるLR項の表す解析状態と同時に現れ得る全てのLR項を，あらかじめトップダウンに展開して求めたものである．{\flushleft\bf[GOTO手続き]}GOTO手続き$\mbox{GOTO}(I,B)$は，アイテム集合$I$と記号$B$から，新しいアイテム集合を次のように求める．\begin{itemize}\item$I$中の，ドットのすぐ右が$B$である全てのLR項$[A\rightarrow\beta\cdotB\gamma]$に対し，ドットを一つ右に移動したLR項$[A\rightarrow\betaB\cdot\gamma]$を求め，そのクロージャを返す．\end{itemize}直感的には，構文解析のある状態$I$で，$B$が得られたときの，次の状態を求めている．{\flushleft\bf[LR項集合の集合]}上記クロージャ，GOTO手続きを用いて，ある拡大文法\footnote{開始記号を$S$とする文法$G$に対して，新しい開始記号$SS$と生成規則$SS\rightarrowS$を追加して得られる文法を，$G$の拡大文法という．}$G'$から，LR項集合の集合$C$を次の手順で求める．\begin{enumerate}\item初期のLR項集合を$\mbox{closure}({[SS\rightarrow\cdotS]})$とし，$C$に加える．\item$C$の各LR項集合$I$，$G'$のある記号$A$に対して，$\mbox{GOTO}(I,A)$を計算し，LR項集合$I'$を求め，$C$に加える．この手続きを，$C$に新たなLR項集合が加えられなくなるまで繰り返す．\end{enumerate}{\flushleft\bf[LR表の作成]}「LR項集合の集合」$C$の各状態(すなわちLR項集合)は，LR表の1状態に対応する．LR表は，状態$i$と終端記号$a$からパーザの動作を決める表$\mbox{action}(i,a)$と，$i$と非終端記号$A$から状態$j$を決める表$goto(i,A)$から成る．$C$の各LR項集合$I_i$について，次の手順でLR表を作成することができる．\begin{itemize}\item$I_i$にLR項$[A\rightarrow\alpha\cdot]$が存在するならば，終端記号$a\in\mbox{follow}(A)$について，$\mbox{action}(i,a)$に$\mbox{reduce}A\rightarrow\alpha$を加える．$\mbox{follow}(A)$は，ある記号の次に現れ得る終端記号を計算する手続き．\item$I_i$にLR項$[SS\rightarrowS\cdot]$が存在するならば，$\mbox{action}(i,\$)$に$\mbox{accept}$を加える．\item終端記号$a$について，$\mbox{GOTO}(I_i,a)=I_j$ならば，$\mbox{action}(i,a)$に$\mbox{shift}j$を加える．\item非終端記号$A$について，$\mbox{GOTO}(I_i,A)=I_j$ならば，$\mbox{goto}(i,A)$に$j$を加える．\end{itemize}\subsection*{LR構文解析法}LR構文解析法は，解析スタックのトップに積まれているLR表状態，次の入力語(先読み語)から，action表を参照して，次のように解析を進める．\begin{itemize}\item$\mbox{shift}i$:先読み語と状態$i$をスタックにプッシュする．先読み語を一つ読み進める．\item$\mbox{reduce}A\rightarrow\alpha$:スタックから$2|\alpha|$個ポップし，その時のスタックトップの状態$j$を用い，スタックに非終端記号$A$と$\mbox{goto}(j,A)$をプッシュする．\item$\mbox{accept}$:入力を受理\end{itemize}
\section{MSLR法への適用}
MSLR法\cite{tanaka1995}は，文脈自由文法から生成したLR表に，形態素の接続可能性を表した接続表の制約を組み込む手法である．終端記号$a$と$b$の接続可能性を使って，LR表から次のような動作を削除することで，接続表を組み込むことができる．\begin{quote}動作Actの直前に実行する動作がshiftで，そのshiftの先読み語が$a$，Actの先読み語が$b$であるとき，$a$と$b$が接続不可ならActを削除する．\end{quote}この手法を可能にするためには，shift直後の状態が，その先読み語($a$)毎に分節されていなければならない．しかし，提案法のLR表では，shift直後の状態では，直前の先読み語($a$)の情報は抽象化されてしまい，その結果，先読み語($a$)毎に分節された状態にはならないため，MSLR法をそのまま導入することはできない．この問題を解決するためには，提案手法においてドットのすぐ左の終端記号を抽象化しないようにすればよい．すなわち，次のようなLR項を導入する．\begin{quote}$[A\rightarrow|\beta|a\cdot\gamma]$($a$が終端記号の場合)$[A\rightarrow|\betaA|\cdot\gamma]$($A$が非終端記号の場合)\end{quote}このようなLR項からLR表を作成すると，終端記号の直後のshift動作で遷移する状態については，終端記号毎に分節された状態となり，MSLR法の適用が可能となる．\begin{biography}\biotitle{略歴}\bioauthor{秋葉友良}{1990年東京工業大学理学部情報科学科卒業．1995年同大学院総合理工研究科システム科学専攻博士課程了．同年，電子技術総合研究所入所．2001年，産業技術総合研究所．現在，情報処理研究部門主任研究員．博士（工学）．自然言語処理，音声認識，音声対話の研究に従事．}\bioauthor{伊藤克亘}{博士(工学)．1993年，電子技術総合研究所入所．2003年，名古屋大学大学院情報科学研究科助教授．現在に至る．音声を主とした自然言語全般に興味を持つ．}\bioreceived{受付}\biorevised{再受付}\bioaccepted{採録}\end{biography}\end{document}