![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
FrontPage 2008/035/13からのアクセス回数 7124
この章では、いくつかの事柄を統合している。すなわち、yacc入力される文法、構文解析プログラムlexの仕様、さらに簡単な記号テーブルの機能を結び付け、言語認識プログラムを作成する。ここでの例で示されるように、このような言語認識は、整ったプリンタ出力を行なうプログラムなどに利用することができる。
まず最初に、yaccが文法を入力とし、ファイルy.tab.cに出力し、またファイルy.outputにその解説を出力するパーサの働きを理解しなければならない。この背景を明確にするために、3.2節では、samp1eCの言語認識においてそれらが実際にどのように結び付けられるかを示す。
ここでは、認識プログラムを起動するためのmain()プログラムと、入力に誤りがあった場合にパーサから呼ばれるyyerror()が示される。3.3節では、コンパイラの前にCプリプロセッサを呼ぶことができるような高機能のmain()を示すまでには至らない。また、パーサヘの入力におけるエラー位置を示すための一般的なyyerror()関数を示すに留める。
残念ながら、文法がいつも言語デザイナーの意図した通りになっているとは限らない。そこで3.4節では、言語認識におけるバグの対処の仕方を述べる。そして、ファイルy.outputとya?tのデバッグ・オプションを結び付けることにより、文法における誤りを見つける有効な方法を示す。
この章の最後には、samp1eCのフォーマッタを示す。このようなプログラムを実際に実行するためには、その前に、終端記号に関する情報を構文解析プログラムがらパーサに渡すための問題を解決しなければならない。そこで3.5節では、yaccがどのように実行されるかを示し、さらに、簡単な電卓の例によってyaccの柔軟性を示す。
1.4節では、文法がyaccによってどのように解析されるかを説明した。解析は、任意の終端記号が受け入れられるかどうかを、すべての規則にわたって同時に行なうことになる。しかし、もしyaccに対して実際の入力を行なうとすると、実際には多少単純なものとなる。なぜなら、膨大なすべての可能性を同時に調べるのではなく、yaccは入力によって選ばれた状態にのみ遷移するからである。そして、その結果は言語認識のための一つの機構、つまり、パーサあるいはシンタックス解析プログラムとならわばならない。
yaccは文法を解析し、パーサを生成する。パーサは、現在の状態を記憶するための大きなスタック、現在の状態と次の入力記号のすべての可能な組合せに対して新しい状態を作り出す遷移行列、認識のある時点において実行されるユーザ定義アクション、および、実際に許される実行を行なう最終的な翻訳機からなる自動装置、すなわちスタック・マシンである。この結果は、標準入力を読み込むための、構文解析の関数yylex()を繰り返し呼ぶ関数yyparse()としてまとめられる。yyparse()は、入力ファイルに“文”があったかどうかを示すために、1または0を返す。
パーサの機能を図化すると、次のようになる。
yylex()を呼んだ時に必要に応じて作られる、現在の状態、すなわちスタックの一番上にある“状態”と次の終端記号とによって、一つの操作が遷移行列から選び出される。ファイルy.outputは、次の可能な終端記号と状態のための遷移行列の内容を示している。遷移行列中には五つのタイプの操作がある。
前項で示されたように、本来、reduceの操作は、次の終端記号より前に用いられる非終端記号を生成するものである。gotoはこの非終端記号に対するshiftの操作である。shiftは次の終端記号を使ったり捨てたりするものであるが、gotoは非終端記号を使い、次の終端記号を後のshift操作に委ねる。それ以外はgotoとshiftは基本的に同じである。つまり、新しい状態がスタックに積まれ、やがて“現在の状態”となる。操作の働きを理解するため、第1章に出てきた簡単な文法の例をもう一度見てみよう。
expression
: expression '-' IDENTIFIER
| IDENTIFIER
第1章では、この文法からyaccが作るファイルy.outputを示した。ここで、このファイルがパーサを完全に示していることを確かめてみよう。パーサは、スタック上の現在の状態として、state 0から始める。
state 0
$accept : _expression $end
IDENTIFIER shift 2
. error
expression goto 1
もし、次の終端記号がIDENTIF1ERであったら、次にshiftの操作が行なわれる。すなわち、記号を受け入れ、新しい状態state2をスタックに積む.これ以外のいかなる入力記号もerrorとみなされる。
state 2
expression : IDENTIFIER_ (2)
. reduce 2
新しい次の終端記号に関係なく、reduceの操作としてfomulation2を用いる。formulatIon2は記号(IDENTIFIER)からなっているので、スタックから次の状態をポップすることになる。そしてstate 0がもう一度スタックの一番上に現われる。
reduceの操作により非終端記号としてexpressionが生成され,state Oの命令によりgoto state1が実行されることになる.それゆえ、もし次の終端記号があったとしても,ここでは考慮されないことに注意しなくてはならない。
state 1
$accept : expression_$end
expression : expression_- IDENTIFIER
$end accept
- shift 3
. error
state1において、入力の最初のIDENTIFIERの後の記号を考えた。この段階では、$end、すなわち入力の終わり、あるいは一の演算子が次に来ることになる。$endは、このパーサがIDENTIFIERを文として認識したことを意味するacceptの操作へと続く。ここで説明したステップは、より長い文に対するy.outputにおけるパーサの働きを理解する助けとなるであろう。
ここにおいて、一つの問題が残っている。yy1ex()は、yyparse()が次の終端記号の値としていかなる値を取るかを、どのように知るのであろうか? 一つの自然なやり方としては、その文字セットの値を用いて、終端記号として1文字で表わす方法である。たとえば、C言語の定数'X'をyaccのための文法における終端記号'X'で表わすようにする。しかし、yaccの%tokenによって導入される一つの終端記号の名前に対して、yyparse()とyylex()は、同じ整数の値を用いなければならない。そしてこの値は、1文字で他のものと区別されねばならない。
yaccは適当な値を決める手助けをしてくれる。次のコマンド、
yacc -d grammar.y
は、%tokenによって導入されるおのおのの名前に対して、C言語のプリプロセッサの文である#define一つを持つファイルy.tab.hを作成する。 (( 終端記号の名前は、最初の%leftや%rightあるいは%nonassoc文において導入することも可能である。しかし、ここでは必ず%tokenを用いて終端記号を定義することにする。 )) それぞれの名前に割り当てられるのは、257から始まる整数の定数となる。
ファイルy.tab.hは、同じくyaccによって作成され、関数yyparse()を含むy.tab.cにすでに現われている。それゆえ、構文解析関数yylex()に対しても、C言語のプリプロセッサの文の#inc1udeを用いてy.tab.hを取り込むことにより、一つの終端記号に対して同じ値を用いることができることになる。
しかしこのために、終端記号のための文法で使われる名前や、%tokenによって導入される名前は、C言語の予約語とすることができない。構文解析関数yylex()は、自分で作ることも、あるいは第2章で示したように、1exによって生成することも可能である。
この記事は、
皆様のご意見、ご希望をお待ちしております。
