hayamiz.parsing-01 RSSPLAIN

Related pages:
555555555555555545555555555
5

ゆるりと構文解析入門 --構文解析の'こ'--

5

 

5

これから数回のエントリに分けて、構文解析についての入門を書いてみようかと思います。予定としては、構文解析の概要から始まり、文脈自由文法、LL、LR構文解析、また最近になって出てきたPackrat Parsingなどについて説明しようと考えています。

5

 

5

方針としては、それぞれのトピックについて読者の方が概要を理解できるような説明を目指します。そのため、理論的に厳密な話などは端折ることが多いと思います。

5

 

5

構文解析ことはじめ

5

 

5

プログラミング言語処理系を実装しようとしたことのある人であれば、一度は"構文解析"という言葉を耳にしたことがあると思います。構文解析の入門に先立って、まずはこの構文解析とはどういうものか、説明してゆきましょう。

5

 

5

文の構造をしらべる

5

 

5

「構文解析」という単語の意味について考えてみましょう。

5

 

5

「構文」とは、読んで字のごとく「文の構造」です。自然言語にしろ、プログラミング言語にしろ、文には構造があります。例えば、"I have a book." という英文は、"I"が主語で、"have"が動詞で、"a book"が目的語である、という構造を持ちます。つまり、構文解析とは、「文の構造を解析」するということになります。もっとくだけた言い方をすると「どのように文が組み立てられているかを調べる」ことになりますね。

5

 

4

では、どのように文の構造を調べればよいのでしょうか。文の構造を調べるには、まず「文を組み立てる規則」を知らなければなりません。たとえば英文の場合は、基本5文型というルールがあり「<主語> <動詞>」「<主語> <動詞> <補語>」「<主語> <動詞> <目的>語」「<主語> <動詞> <目的語> <目的語>」「<主語> <動詞> <目的語> <補語>」という規則のどれかにあてはまるものが正しい英文になります。

5

 

5

ということは、調べる対象の文が、どの規則に従って作られたかを調べることが、構文解析をする、ということになりますね。

5

 

5

プログラミング言語の場合、多くの場合 *文脈自由文法* によって文を組み立てる規則を定めます。つまり、プログラミング言語において、構文解析というのは文脈自由文法によって定義された文法規則をどのように組み合わせてコードが構成されているかを解析すること、ということです。

5

 

5

文を組み立てる

5

 

5

前節では、文脈自由文法によってプログラミング言語の文法規則を定めると説明しました。ではこの文脈自由文法とはどういうものか、みていくことにしましょう。

5

 

5

文脈自由文法