字句解析
字句解析器を自動的に作成するソフトウェアを字句解析器生成器(英: lexical analyser generator)という。
1975年にマイク・レスク(en:Mike Lesk)とエリック・シュミットにより字句解析器生成器Lex が開発され、POSIXにも採用された。Lexは、トークンの規則を正規表現で記述した文書をもとに、自動的に字句解析器を作る。入力がどの規則にもマッチしないようであればエラーとする。
1987年ころには、Lexを en:Vern Paxson が改良したFlex(英語版記事)がリリースされ、広く利用されるようになった。Linuxのディストリビューションの多くがFlexを標準採用している。
なおLex 系の生成器は表駆動型の手法を採用している。
1994年にはPeter Bumbulisが開発したre2c(英語版記事)がリリースされた。 re2cはFlexの2倍から3倍の速度で処理を行う字句解析器を生成すると言われている
2017年にはFrank-Rene Schaeferが開発したquexがリリースされた。 これも高速な字句解析器を生成する。
ルールを直感的に言明すると「コメントには任意の文字が使えるが、"*/" という並びが現れたらそこで終わる」というものであるが、これを何も考えずにそのまま正規表現にしてしまうと、正規表現の * が最長一致(欲張り(greedy)な量指定子)であるために、「ソースコード中に現れる最初のコメントの開始から、ソースコード中に現れる最後のコメントの終了」にマッチしてしまう。正規表現に非欲張り量指定子か先読みがあればこれに対し正しい規則を書くのは簡単だが、無い場合は不可能ではないものの、その規則は読みやすいものではない。
コメントの例の場合は、手書きの解析器であればそこだけアドホックにちょっと先読みすれば簡単に済むが、こういったパターンが意外とあることも、手書きが選ばれる理由のひとつである。また、JavaのGenericsやC++のテンプレートなどの字句解析で「>>」という並びが現れうることも、悩ましい点のひとつである(C++でテンプレートが実装された初期の頃は、コードを書く側が空白を入れて分割しなければならないとしていた)。本格的な処理系では往々にして、こういった場合への対処のために後段からの情報を必要とし、実装がややこしいものになりやすい。