|
目次 |
このページでは、Java向けの字句解析生成系・構文解析生成系に関する勉強ログを掲載しています。ちなみに、3種類ご紹介しますが、いずれもオープンソースになっています。
|
目次 |
このページでは、Java向けの字句解析生成系・構文解析生成系に関する勉強ログを掲載しています。ちなみに、3種類ご紹介しますが、いずれもオープンソースになっています。
|
Jlex ─ 字句解析生成系 |
そもそも「字句解析」とは
冒頭から文献[1]引用で恐縮ですが...(以降の引用は一部抜粋です)
字句解析【lexical analysis】:
プログラムを表現する文字の列を、プログラムを表現する意味のある最小単位である字句の列に変換することをいう。
例えば、プログラムを表現する文字の列「aValue = 123 + 456;」を、意味のある最小単位「aValue」「=」「123」「+」「456」「;」に分解すること、それが字句解析に相当します。 私たち人間も、プログラム「aValue = 123 + 456;」の意味を考えるとき、「123は数値だな」とか「+だから足し算だな」などと、ある程度のまとまりごとの意味を把握した上で、全体の意味を理解しますよね。 コンピュータがプログラムを実行する際も同様で、全体の処理を行うために、意味のある小さなまとまりごとに区切ってゆくのです。これを字句解析と呼びます。
ならば「字句解析生成系」とは
これもまた文献[1]からの引用となります。
字句解析ルーチン生成系【lexical analyzer generator】:
字句解析生成系ともいう。字句単位の構文規則を指定すると字句解析を行なうルーチンを生成する生成系をいう。
簡単にいえば「字句解析プログラム」を自動的に作ってくれるものが「字句解析生成系」です。
「123」とか「456」は「数値」であり、「+」とか「-」は「演算子」である...という定義(構文規則)を用意すると、
その規則に従う字句解析プログラムを生成してくれます。それが字句解析生成系であり、自力で字句解析プログラムを作成できない場合に用いるツールです。
「lex」とは。そして「Jlex」とは。
実際に字句解析プログラムを作り出してくれる有名なプログラムに「lex」というものがあります。これはC言語製の字句解析生成系で、何らかの構文規則を与えてやると、それに従ったC言語製の字句解析プログラムを生成してくれます。 似たもので「Jlex」という生成系も存在し、こちらはJava製の字句解析生成系になります。そして構文規則を与えればJava製の字句解析プログラムを得ることができるのです。
これは、Jlexのウェブサイト[2]からの引用です。
JLex is a lexical analyzer generator, written for Java, in Java.
Javaによる、Javaのための、字句解析生成系「Jlex」 ── 字句を解析する際には、こんな字句が取れたらこんな処理をする...あんな字句が取れたらこんな処理をする... という具合に、それぞれの字句に対して一定の処理を加えることができます。その処理をJavaプログラムで指定できるのが、このJlexのミソ。 Javaの豊富な標準ライブラリの恩恵を授かるには、このJlexを用いるのが良いかもしれません。
簡単な実例(detab:タブ文字をスペースに置換する)
ほげほげほげ。。。(準備中)
[1] 岩波書店「岩波情報科学辞典」 1990年 ISBN:4000800744
|
jay ─ LALR(1)の構文解析生成系 |
そもそも「構文解析」とは
上で述べた「字句解析」では、意味のある最小単位(「数値」とか「演算子」など)でプログラムを区切ることができますが、 次にその区切られた単位の並びを見て、つながり方のパターンを見いだす「構文解析」というものがあります。 以下は、先の文献[1]より。
構造解析【parsing, syntax analysis】:
プログラムの構造をその言語の構文規則に基づいて解析することをいう。
ならば「構文解析生成系」とは
文献[1]より。
構造解析ルーチン生成系【parsing generator】:
構文解析生成系ともいう。構文規則を指定すると構文解析を行なうルーチンを生成する生成系をいう。
「変数 = 式;」は代入の処理だとか、「式 + 式」「式 - 式」「式 * 式」「式 / 式」は演算の処理だとか。そういった定義(これまた構文規則)を用意すると、 その規則に従った構文解析プログラムを生成してくれる、それが構文解析生成系です。字句解析生成系に似ていますよね。
LR(1)法とは
jayは、LALR(1)法を用いるパーザ(構文解析プログラム)を生成するとされていますが、そもそもLALR(1)法は、LR(1)法をより実用的にしたものなのです。 では、その基となったLR(1)法について、少し整理しておきたいと思います。
(準備中:LR(1)法の概要)
「yacc」とは。そして「jay」とは。
字句解析生成系の「lex」と同じように、構文解析生成系の有名どころとして「yacc」というものがあります。 C言語製の生成系で、何らかの構文規則を入力すると、それに従ったC言語製構文解析プログラムを自動生成してくれます。 そして、その「yacc」のJava版として「jay」があるのです。
jay reads a grammar specification from a file and generates an LALR(1) parser for it.
jayは構文規則を読み込んで、その規則に対応するLALR(1)[3]解析プログラムを生成する。(jayのウェブサイト[4]より) ── 構文規則を用意しさえすれば、「jay」を用いてJava製の構文解析プログラムを自動生成することができます。
簡単実例(未定)
(何を作ろうかと思いを馳せているところ)
[3] LALR(1):構文解析法の一つ。状態数が非常に大きくなってしまう「LR構文解析法」というものを、より実用的にするために考案されたようです。この他にSLR構文解析法というものもあります。
(文献[1]より)
ちなみに「(1)」は、「高々1つの先読みができれば全てを読み込むことができる」ということを表します。
[4] ウェブサイト jay (Language Processing)
|
JavaCC ─ LL(1)の構文解析生成系 |
JavaCC : Java Compiler Compiler
Java Compiler Compilerと聞いて、何の疑いもなく「コンパイラコンパイラ」のことについて調べてしまった(メタコンパイラ)のですが
コンパイラー【compiler】:
翻訳系ともいう。原始言語が高水準言語で目的言語が目的計算機の機械語に近い低水準の言語である場合のトランスレーターをいう。
誤解を恐れず「日本人」に喩えてみます。大人は漢字を使って表現活動をしますよね。しかしながら幼児は漢字を理解することができませんので、漢字を全て平仮名に直したりするわけですが、 この「漢字を平仮名に変換すること」こそが、「コンパイラ」の行う「コンパイル」という作業なのです。 私たち人間はC言語やJavaなどのプログラミング言語を使って表現することができますが、コンピュータは電気が流れるか流れないか(1か0か)しか識別することができず、つまるところ、1と0の組み合わせで表現する言語(機械語)しか理解できません。
「x = 3 + 4;」(コンピュータは理解できない) →→→「1000101100111011001」(コンピュータが理解できる)
そこで、人間が使う「プログラミング言語」から、コンピュータが理解できる「機械語」に変換するという操作(コンパイル)が必要になるわけですね。そのコンパイル操作を実現してくれるのが「コンパイラ」なのです。
ならば「メタコンパイラ(コンパイラコンパイラ、コンパイラ生成系)」とは
細かいことは注釈[5]に任せるとして、メタコンパイラ(コンパイラコンパイラ、コンパイラ生成系)とは...
コンパイラー生成系【compiler generator】:
コンパイラーを生成する生成系をいう。一般に、コンパイラーは字句解析部、構文解析部、意味解析部、コード生成部で構成され、
これに対応してコンパイラー生成系は字句解析ルーチン生成系、構文解析ルーチン生成系、意味解析ルーチン生成系、コード生成ルーチン生成系で構成される。
文献[1]より。要は、コンパイラの部品を作り出す各種生成系を寄せ集めたものです。 C言語の構文規則を入力すれば、C言語のコンパイラが出力されますし、Javaの構文規則を入力すれば、Javaのコンパイラが出力されます。
LL(1)文法とは
「JavaCC」とは。
以下はJavaCCのウェブサイト[6]より引用したもの。
Java Compiler Compiler tm (JavaCC tm) is the most popular parser generator for use with Java tm applications. A parser generator is a tool that reads a grammar specification and converts it to a Java program that can recognize matches to the grammar.
文意の取れない部分がありますが、とかく「人気のあるパーサ生成系」で、ある文法規則を基に、その文法に合致するものを認識するJavaプログラムを生成するようです。 ん?構文解析生成系との違いがよくわかりません...。
[5] 厳密な意味での「コンパイラコンパイラ」は、「原始言語と目的言語の定義を与えるとそのコンパイラーを自動的に生成するという理想的なコンパイラー生成系を意味する語」なのですが、 それを実現することは困難であり、実際にこの意味で「コンパイラコンパイラ」という言葉が使われることは稀なのだそうです。ここでは、コンパイラ生成系と同じ意味で用います。
|
メタコンパイラ(コンパイラコンパイラ、コンパイラ生成系) |
そもそも「コンパイラ」とは
例によって、文献[1]からの引用です。
コンパイラー【compiler】:
翻訳系ともいう。原始言語が高水準言語で目的言語が目的計算機の機械語に近い低水準の言語である場合のトランスレーターをいう。
誤解を恐れず「日本人」に喩えてみます。大人は漢字を使って表現活動をしますよね。しかしながら幼児は漢字を理解することができませんので、漢字を全て平仮名に直したりするわけですが、 この「漢字を平仮名に変換すること」こそが、「コンパイラ」の行う「コンパイル」という作業なのです。 私たち人間はC言語やJavaなどのプログラミング言語を使って表現することができますが、コンピュータは電気が流れるか流れないか(1か0か)しか識別することができず、つまるところ、1と0の組み合わせで表現する言語(機械語)しか理解できません。
「x = 3 + 4;」(コンピュータは理解できない) →→→「1000101100111011001」(コンピュータが理解できる)
そこで、人間が使う「プログラミング言語」から、コンピュータが理解できる「機械語」に変換するという操作(コンパイル)が必要になるわけですね。そのコンパイル操作を実現してくれるのが「コンパイラ」なのです。
ならば「メタコンパイラ(コンパイラコンパイラ、コンパイラ生成系)」とは
細かいことは注釈[5]に任せるとして、メタコンパイラ(コンパイラコンパイラ、コンパイラ生成系)とは...
コンパイラー生成系【compiler generator】:
コンパイラーを生成する生成系をいう。一般に、コンパイラーは字句解析部、構文解析部、意味解析部、コード生成部で構成され、
これに対応してコンパイラー生成系は字句解析ルーチン生成系、構文解析ルーチン生成系、意味解析ルーチン生成系、コード生成ルーチン生成系で構成される。
文献[1]より。要は、コンパイラの部品を作り出す各種生成系を寄せ集めたものです。 C言語の構文規則を入力すれば、C言語のコンパイラが出力されますし、Javaの構文規則を入力すれば、Javaのコンパイラが出力されます。
[5] 厳密な意味での「コンパイラコンパイラ」は、「原始言語と目的言語の定義を与えるとそのコンパイラーを自動的に生成するという理想的なコンパイラー生成系を意味する語」なのですが、 それを実現することは困難であり、実際にこの意味で「コンパイラコンパイラ」という言葉が使われることは稀なのだそうです。ここでは、コンパイラ生成系と同じ意味で用います。
|
Jlex・jayを用いた実装例(ハイパーリンクの置換) |
(準備中)