Lecture Notes1-2 字句解析２ 正規表現によるパターンマッチ Lex は正規表現で定義された token を認識する関数 yylex() を自動的に合成する。yylex() は実際にどのようなアルゴリズムで、token を認識しているのだろうか？ yylex()の中身は、有限状態オートマトンである。yylex()は文字を一文字づつ読みながら、正規表現に対応する状態遷移図に従って状態遷移していき、token を認識していく。 例えば、正規表現 a(b|c)* は次のような状態遷移図に対応する。 S が開始状態で、Fが終了状態である。 S から始めて全ての入力文字列を読み込み終えたときに、状態 F になっていれば、入力文字列は正規表現 a(b|c)* と一致するといえる。 途中で遷移不能な入力 (例えば状態 S のときに a 以外の入力) が来て状態 F に達しない場合、入力文字列は正規表現 a(b|c)
