字句解析器生成器(Lexical analyzer generator)のルール定義における、包含的/排他的スタート

lex と flex と rex

ゆるく違いを述べる。

• lexは、ユーザーが定義したルールを元に、Cで書かれた字句解析器を生成してくれる。
• flexも、ユーザーが定義したルールを元に、Cで書かれた字句解析器を生成してくれる。Lexの改良版。
• rexは、ユーザーが定義したルールを元に、Rubyで書かれた字句解析器を生成してくれる。rexicalというgemで配布されている。

ルール定義 - スタート状態

"ユーザーが定義したルール" の書き方は以下を参照。

• flexは、http://quruli.ivory.ne.jp/document/flex_2.5.4/flex-ja_2.html
• rexは、https://github.com/tenderlove/rexical/blob/master/DOCUMENTATION.ja.rdoc

さて、flexとrexでは、このルールの中で、スタート状態を定義することができる。

rexの例で説明

rexの例(ref)で説明する。

class MyLexicalAnalyzer

# マクロ定義。要はルール内で使い回される定数の定義。
macro
DIGIT         \d+
IDENT         [a-zA-Z_][a-zA-Z0-9_]*
BLANK         [\ \t]+
REMIN         \/\*     # /* つまり、 複数行コメントの始まりを表す
REMOUT        \*\/     # */ つまり、 複数行コメントの終わりを表す


# ルール定義。
# [state]  pattern  [actions] の順に並んでいる。
rule
      {REMIN}                 { state = :REM ; [:REM_IN, text] }
:REM  {REMOUT}                { state = nil ; [:REM_OUT, text] }
:REM  (.+)(?={REMOUT})        { [:COMMENT, text] }
      {BLANK}
      -?{DIGIT}               { [:NUMBER, text.to_i] }
      {WORD}                  { [:word, text] }
      .                       { [text, text] }

この中で、以下がスタート定義を表している。

state = :REM
:REM

先述の例だと、:REM {REMOUT} {state = nil; [:REM_OUT, text]}のルールが適応されるのは、stateが:REMである時に{REMOUT}patternが現れた場合のみ。

さて、ここから、包含的/排他的スタート (inclusive/exclusive)の違いを説明する。rexでは、

続く英字が小文字のとき、包含的スタート状態となる。
大文字のとき、排他的スタート状態となる。

つまり、

• actionsの中でstate = :remと記述されると、包含的スタート状態のステートである:remに遷移する。
• actionsの中でstate = :REMと記述されると、排他的スタート状態のステートである:REMに遷移する。

これらの違いを例を出して説明する。
(stateの指定がない){WORD} {[:word, text]}というルールは、

• 現在のステートが(包含的スタート状態のステートである):remの場合に、{WORD}patternが現れたら、この行は適応される。
• 現在のステートが、(排他的スタート状態のステートである):REMの場合には、{WORD}patternが現れても、この行は適応されない。

要は、state≠:REM,state≠:remの時に違いが発生するということである。

flexのドキュメントの引用

より、

これまでのところでは、 Flexが異なる２種類のスタート状態をサポートしている事実から目をそらしてきました。 ２つのスタート状態とは、 包含的スタート状態（%s）と排他的スタート状態（%x）のことです。 これら２つの相違点は、 排他的スタート状態が活性化された場合は、 その状態に属するルールだけが活性化されるのに対して、 包含的スタート状態の場合は、 その状態に属するルールとスタート状態への参照を持たないルールの両方が活性化されるという点にあります。 この違いを示す例を挙げると、 以下のようになります。

%s state1
%%
"one" printf("two");
"three" printf("four");

この場合、 state1状態が活性化されている場合は‘one’を‘two’に置き換え、 state1状態が活性化されているか否かにかかわらず‘three’を‘four’に置き換えます。 デフォルトのルールにより、 その他のテキストはstdoutに出力されます。 これに対して、

%x state1
%%
"one" printf("two");
"three" printf("four");

は、 state1状態が活性化されている時は‘one’を‘two’に置き換え、 state1状態が活性化されていない時のみ‘three’を‘four’に置き換えます。 デフォルトのルールにより、 その他のテキストはstdoutに出力されます。

このことは、 排他的スタート状態が使われる場合には、 マッチしないテキストがstdoutに出力されてはならないのであれば、 すべての可能な入力にマッチするルールを、 個々の排他的スタート状態が持たなければならないことを意味しています。 包含的スタート状態の場合は、 あらゆる状態において有効な、 スタート状態への参照を持たないルールを１つ持つ必要があります。

注： 排他的スタート状態はPOSIXの一部であるにもかかわらず、 Lexではサポートしていません。