字句解析
計算機科学における字句解析 (じくかいせき、英: lexical analysis) とは、ある言語で書かれた文について、その文字の並びを解析し、言語的に意味のある最小の単位（トークン）に分解する処理のこと[1]。
概要
[編集]字句解析は、コンピュータを用いた自然言語処理でも、プログラミング言語のコンパイルでも行われる[1]。
自然言語の文であれ、プログラムのソースコードであれ、文というのは結局、文字や記号や約物類が多数並んだもの（文字列）であるが、字句解析はそれを、言語的に意味のある最小単位トークン（英: token(s)）に分解する処理である。
文を解析してトークンに分解する作業を自動的に行うプログラムを字句解析器（英: lexical analyser）という。
具体例
[編集]コンパイラの中の字句解析の例を挙げる。
たとえばソースコード中に、あらかじめ現在値や初期値を入れるためのpresentやinitialという変数が宣言された後に、次の1行があるとする。
present := initial + 15[2]
これを字句解析すると次のようになる。
| 文字列 | 型 |
|---|---|
present |
識別子 |
:= |
代入演算子 |
initial |
識別子 |
+ |
演算子 |
15 |
数 |
つまり「present」や「initial」という変数名、「:=」という変数への値の代入を示す演算子、「15」という数字列は、意味を持つ最小単位（トークン）である。
文字と文字の間の空白（ブランク。スペース文字の1〜数個の並び）は、通常、字句解析の途中で除去する[3]。上の例では present と := の間やその後ろなどにある空白文字が除去されている。空白文字はトークンとトークンを分離する役割くらいしかないものなのでトークンには含めない。
また、コンパイラの字句解析では、コメント文つまり「/* 現在値を計算するためのプログラム。 */」といったような文は、処理の最初の段階でひとつのカタマリとして扱い、まるごと除去してしまうこともある。
もうひとつ、C言語での文の例を挙げる。
sum = 35 + 21;
これは、次の表のようにトークン化される。
| 文字列 | 型 |
|---|---|
sum |
識別子 |
= |
代入演算子 |
35 |
数 |
+ |
加算演算子 |
21 |
数 |
; |
セミコロン |
トークンは字句解析する段階では、プログラムの要素としての妥当性は必ずしも考慮されない。例えば上記の例で sum は、もしこの文の前にsumが宣言されていなければ意味がないが、字句解析器は通常トークンとしては問題ないとして扱う。
一方、数リテラルの値が、そのプログラミング言語で扱えるいかなる型がサポートする範囲よりも大きい値が書かれている場合は、最初からエラーにすることもある。
字句解析器
[編集]スキャナ
[編集]一般に、文字列をなめるような処理をするものをスキャナという。字句解析の場合、文字列から、1個のトークンになるような部分文字列を切り出す部分をスキャナとして分けて考える場合がある。
スキャナはある種の有限状態機械にモデル化できる。その有限状態機械は、それが処理する任意のトークンに含まれる文字の考えられる並びに関するルールを元に生成される。ここでいうルールとは例えば、「整数」トークンは任意個の数字の並びである、といったようなものである。プログラミング言語では、一般に、空白でない先頭の文字の種類によって、そこから始まるトークンの種類が類推できるよう設計され、その後の文字の並びはそのトークンとして受理できない文字が出てくるまでひとまとめとして処理される（最長一致の規則）。言語によっては、規則がもっと複雑で、複数個の文字について戻るようなバックトラッキングが必要になることもある。
狭義の正規表現（詳細に言うと、いわゆる非欲張り量指定子が無い正規表現）による表現が面倒な字句規則の代表例に、C言語の「/* コメント */」のようなコメントがある。ルールを直感的に言明すると「コメントには任意の文字が使えるが、"*/" という並びが現れたらそこで終わる」というものであるが、これを何も考えずにそのまま正規表現にしてしまうと、正規表現の * が最長一致（欲張り(greedy)な量指定子）であるために、「ソースコード中に現れる最初のコメントの開始から、ソースコード中に現れる最後のコメントの終了」にマッチしてしまう。正規表現に非欲張り量指定子か先読みがあればこれに対し正しい規則を書くのは簡単だが、無い場合は不可能ではないものの、その規則は読みやすいものではない。
コメントの例の場合は、手書きの解析器であればそこだけアドホックにちょっと先読みすれば簡単に済むが、こういったパターンが意外とあることも、手書きが選ばれる理由のひとつである。また、JavaのGenericsやC++のテンプレートなどの字句解析で「>>」という並びが現れうることも、悩ましい点のひとつである（C++でテンプレートが実装された初期の頃は、コードを書く側が空白を入れて分割しなければならないとしていた）。本格的な処理系では往々にして、こういった場合への対処のために後段からの情報を必要とし、実装がややこしいものになりやすい。
トークナイザ
[編集]トークン化は、スキャナによって得られた部分文字列に、トークンの種別の情報を付け（この部分の仕事は、実際のところスキャナによって適合するルールが選ばれた時点でほとんど済んでいる）、その種類によっては、たとえば整数ならその整数値といったような意味値（英: semantic value）を与える処理である。部分文字列の列からトークンを構築するには、字句解析器には第二段階の評価器が必要であり、評価器は文字列に対して「値」を付与する。文字列と型を結びつけたものが適切にトークンを表し、構文解析器に入力できるものとなる。括弧などの一部のトークンは「値」を持たないので、評価器（関数）はそれらについては何も返さない。整数、識別子、文字列などを扱う評価器は非常に複雑になる。空白やコメントなどはそのまま捨ててしまうこともある。最終的に、#トークンの節に挙げた表のような形の情報を持った、トークン列が得られる。
字句解析器生成器
[編集]字句解析器を自動的に作成するソフトウェアを字句解析器生成器（英: lexical analyser generator）という。
1975年にマイク・レスク（en:Mike Lesk）とエリック・シュミットにより字句解析器生成器Lex が開発され、POSIXにも採用された。Lexは、トークンの規則を正規表現で記述した文書をもとに、自動的に字句解析器を作る。入力がどの規則にもマッチしないようであればエラーとする。
1987年ころには、Lexを en:Vern Paxson が改良したFlex（英語版記事）がリリースされ、広く利用されるようになった。Linuxのディストリビューションの多くがFlexを標準採用している。
なおLex 系の生成器は表駆動型の手法を採用している。
1994年にはPeter Bumbulisが開発したre2c（英語版記事）がリリースされた。[4] re2cはFlexの2倍から3倍の速度で処理を行う字句解析器を生成すると言われている
2017年にはFrank-Rene Schaeferが開発したquexがリリースされた。[5] これも高速な字句解析器を生成する。
脚注
[編集]- ^ なおParsing Expression Grammar（PEG）のように、字句の規則も構文規則と一緒に扱ってしまうことも多い手法もあり、「字句解析」と(狭義の)「構文解析」という分担は絶対のものでもない。また実際のC言語の処理系では、言語処理系本体の前にプリプロセッサによってもトークンとしての扱いがある（プリプロセッサトークン）。
- ^ プログラミング言語開発の途中段階では、仕様が頻繁に変わるため、スキャナ生成器などの単純なツールの方が有用な場合もある。正規表現として語彙構成要素を表現する能力により、字句解析器の記述が容易になる。一部の字句解析器生成器は、人間が書くのが難しい事前条件や事後条件を記述でき、開発時間を大幅に節約するのに役立つ。
- ^ なお、コンパイラでは通常、字句解析の次には構文解析が行われ、その後は言語処理系本体の処理となる。
- ^ a b IT用語辞典 e-words【字句解析】
- ^ コンパイラの技術書のバイブル、Alfred V.Aho, Compilers,Principles, Techniques, and Tools のp.5で、字句解析についての、最初の説明で挙げられた例に、やや似た例を当記事で用意したもの。Ahoの例文では「position」や「initial」や「rate」などの変数あるいは定数が含まれている。
- ^ Alfred V.Aho, Compilers,Principles, Techniques, and Tools p.5
- ^ r2c公式サイトはこちら[1]
- ^ quexのsourceforge.net上の外部リンクはこちら[2] ]
参考文献
[編集]- CS 164: Programming Languages and Compilers (Class Notes #2: Lexical)
- Compiling with C# and Java, Pat Terry, 2005, ISBN 0-321-26360-X
- Algorithms + Data Structures = Programs, Niklaus Wirth, 1975, ISBN 0-13-022418-9
- Compiler Construction, Niklaus Wirth, 1996, ISBN 0-201-40353-6
- Sebesta, R. W. (2006). Concepts of programming languages (Seventh edition) pp.177. Boston: Pearson/Addison-Wesley.
外部リンク
[編集]- U-Tokenizer - 日中韓自然言語に対応している字句解析API
- Flex lexical analyser - lex の GNU 版
- JLex - Java 向け字句解析器生成器
- Quex ('Queχ') - C++ 向け字句解析器生成器
- OOLEX - オブジェクト指向字句解析器生成器