字句解析(lexer)

■字句解析(lexer)

1. はじめに

2. 準備

3. 拡張BNF(Backus Naur Form)

4. 字句規則と記法

5. 字句解析器の実際


■CAI演習課題1


■参考資料・リンク集

■質問・相談用掲示板

←目次へ戻る

2009年2月16日 22:54 更新

 

1. はじめに

「0. 概略」にて述べたように、プログラムを人間が記述するためには、人間が容易に判読できるような単語と文法で規定された言語を用意すべきである。各命令は誰でも意味が判別できるように、数学で通常用いられるような演算子や、英単語に近い形の命令語(予約語)を用意する。命令に引き渡すパラメータは、整数型、浮動小数点型などの型に応じたリテラルの組で表現する。プログラムは、plain text形式のファイルで格納される。

上記のような前提で、コンパイラを構成する処理要素のうち、まず最初の段階は、プログラムを構成するテキストから、定義された命令語(予約語)やリテラルを取り出す(切り出す)作業が必要である。この処理を「字句解析(lexer)」と呼ぶ。コンパイラ内部で字句解析を行うような機能モジュールを「字句解析器」と呼ぶ。

字句規則の決定のため、まず「トークン(Token)」と呼ばれる、ラベル付き正規表現群を定義する。この定義は、単調BNF(Backus Naur Form)あるいは拡張BNF形式を用いて行う。後述する構文解析(parser)処理のため、BNFでは構文規則に関する定義も併せて行う。(若干の準備と)字句規則と構文規則の全てを記述したBNFは、文法記述ファイルとして利用することができる

 

2. 準備

2.1 簡単な文法ファイル
2.2 test0.grammarの説明
2.3 SableCCによる字句解析器の生成とテスト


2.1 簡単な文法ファイル

後の説明で出てくる構文記述(字句規則と構文規則)を実際に確認するために、簡単な文法ファイルの例(test0.grammar)を、まず最初に示しておく。
(説明上、左端に行番号を付した。実際の文法ファイル中に行番号は付されていない)

<文法ファイル:test0.grammar>

     1  Package test0;
     2
     3  Tokens
     4    number = [ '0' .. '9' ]+;
     5    plus   = '+';
     6    blank  = ( ' ' | 13 | 10 )+;
     7
     8  Ignored Tokens
     9    blank;
    10
    11  Productions
    12    expr = 
    13      {term} term |
    14      {plus} expr plus term;
    15
    16    term = 
    17      {number} number;

この文法ファイルは、「整数リテラル同士の加算演算」を記述したものである。
具体的には、以下の例のような文字列を受理するようなものである。([EOF]は入力シーケンスの終端を示す。[CR][LF]は改行コードである。)

例:
1 + 2 [EOF]
011 + 345[CR][LF][EOF]
3 + 4 + 5 [EOF]

 


2.2 test0.grammarの説明

※SableCCの文法ファイル形式はここから参照されたい。
http://sablecc.org/grammars/sablecc-2x.sablecc.web.html

簡単な文法ファイルの例(test0.grammar)について、各ディレクティブについて説明する。

1行目(Packageディレクティブ):

生成するJavaのクラスパッケージ名を指定している。
SableCCによって生成される全てのパッケージ指定は、この行の内容で決定される。

3-6行目(Tokensディレクティブ):

字句規則を指定している。
ここでは、number, plus, blank というラベルが付された3種類のトークンを定義している。各々の意味付けは以下の通り。

トークンnumber:
 '0'から'9'までのdigitが1つ以上並んだ列("整数"リテラル)

トークンplus :
 '+'が1つ並んだ列("加算"を表す2項演算子)

トークンblank :
 ' '(ホワイトスペース)またはCRコード(0x0D)あるいはLFコード(0x0A)
 が1つ以上並んだ列(空白ならびに改行)

Tokensディレクティブで「定義していない」トークンについては、生成される字句解析では「解析エラー」として処理されるので注意が必要である。

8-9行目(Ignored Tokensディレクティブ):

「無視するトークン」を指定している。ここでは、blankトークンを、字句解析時に無視(読み飛ばす)ように定義している。

所謂コメント行などは、構文解析まで引き渡されることのないように、字句規則には「無視するトークン(Ignored Tokens)」としてはっきりと定義しておく必要がある。

11-17行目(Productionsディレクティブ):

構文規則を指定している。(構文解析については、次の章で詳述する)
ここでは、expr, term というラベルが付された2つの規則を定義している。規則exprの内部でtermが使われているため、2つの規則には親子関係があり、expr > term である。
トークン plus と number は、各々 expr, term 内部で利用されている。

各々の規則の意味は以下の通り。

規則expr:
 {ラベルterm} :term が出現する
 あるいは
 {ラベルplus} :expr '+' term (2項演算式)が出現する(終わり)。

規則term:
 {ラベルnumber} :number(整数リテラル)が出現する(終わり)。

※規則expr: ラベルplusでは、expr自身が再帰的に出現することを許していることに注意せよ。

 


2.3 SableCCによる字句解析器の生成とテスト

付録A. SableCCのインストール、5. 実行試験 を参照して、test0.grammar試験用プロジェクトファイルをビルドして、SableCCによる字句解析/構文解析器を生成してみよう。
sablecc-install.html#sec5

実際に、入力シーケンス "3 + 4 + 5[EOF]"を解析器(test0.jar)に入力した場合の実行結果を以下に示す。
実行結果は、tool.PrintTreeクラスによって、構文木全体を深さ優先探索した結果で表示されている。

<実行結果>

$ echo "3 + 4 + 5" | java -jar test0.jar

Start
 APlusExpr
  APlusExpr
   ATermExpr
    ANumberTerm
     TNumber: 3
   TPlus: +
   ANumberTerm
    TNumber: 4
  TPlus: +
  ANumberTerm
   TNumber: 5
 EOF: 

字句解析の結果としては、定義した3種類のトークンのうち、無視するトークン(blank)を除く2つ(number, plus)を示す以下のノード(葉)名(TNumber, TPlus)を順番に並べると判然とする。([EOF]は、システム内部で特殊なトークンとして扱われている)

TNumber: 3
TPlus: +
TNumber: 4
TPlus: +
TNumber: 5
EOF:

 

3. 拡張BNF(Backus Naur Form)

test0.grammarのような構文規則を記述するために、生成規則中の正規表現を許した拡張BNFを使用する。

拡張BNFの記法についての記事は、インターネット上の資源として様々なものが既に存在する。故、Googleなどの検索エンジンを利用して各自参照されたい。

良質な解説記事としては、RFC2616(HTTPプロトコル仕様)の第2.1節 などがある。

ハイパーテキスト転送プロトコル -- HTTP/1.1(邦訳版)
http://www.studyinghttp.net/cgi-bin/rfc.cgi?2616#Sec2.1

<RFC2616 2.1節(拡張BNF)の抜粋>

2.1 拡張 BNF

この文書において詳述されるメカニズムのすべては、単調 Backus-Naur Form (BNF) と、RFC 822 [9] で使用されているものに似た拡張 BNF との両方で記述されている。 実装者は、この仕様書を理解するためにこの表記法に精通している必要があるだろう。 拡張 BNF は以下の構造を含んでいる。

name = definition
name とは、("<" と ">"で囲まれているものを除き) 単純にそれ自身の名前であり、その定義とは等号 "=" 文字によって分割されている。 空白は、二行以上に渡るルール定義を示すために使われる連続行の行頭空白においてのみ意味を持つ。 特定の基本ルールは SP, LWS, HT, CRLF, DIGIT, ALPHA 等のように大文字である。 角括弧は、それらの存在がルール名の使用の理解を容易にするであろうときに定義の中に使用される。
"literal"
クォーテーション記号はリテラルテキストを囲む。 もし特に明言されなければ、テキストは大文字・小文字を区別しない。
rule1 | rule2
バー ("|") で区切られた要素は二者択一である。例えば "yes | no" は yes か no を受け入れるだろう。
(rule1 rule2)
括弧で囲まれた要素は単一の要素として扱われる。 従って、"(elem (foo | bar) elem)" は、トークンシーケンス "elem foo elem" と "elem bar elem" を認める。
*rule
要素の前にある "*" 文字は繰り返しを意味する。 完全な形式は "<n>*<m>element" で、これは element 出現が最低<n>、最大<m>である事を示している。 デフォルト値は 0 と無限なので、"*(element)" はゼロを含むどんな回数も可能であり、"1*element" は最低一つ、"1*2element" は一つか二つが可能である。
[rule]
角括弧は省略可能な要素を囲む。 すなわち、"[foo bar]" は "*1(foo bar)" と同等である。
N rule
具体的な繰り返し。 "<n>(element)" は "<n>*<n>(element)" と同等である。 これは、(element) の出現が確実に <n> 存在する。 従って 2DIGIT は二文字の数字であり、3ALPHA は三文字のアルファベット文字の文字列である。
<以下、省略>

他方、XML1.0を例として、以下のような解説記事もある。

@IT : 「BNF記法入門(1) ─XML関連仕様を読むために─」
http://www.atmarkit.co.jp/fxml/ddd/ddd004/ddd004-bnf.html

 

4. 字句規則と記法

4.1 SableCCの文法ファイルの字句規則形式
4.2 字句規則における正規表現
4.3 字句規則の記述例


4.1 SableCCの文法ファイルの字句規則形式

SableCCの文法ファイル形式はここから参照されたい。
http://sablecc.org/grammars/sablecc-2x.sablecc.web.html

このうち、字句規則(構文規則token_def以下)について、以下に抜粋しておく。(文法ファイルを使って文法を定義しているから「鶏が先か、卵が先か」の様相を呈しているが、SableCC parser generatorの「実装」はJavaを用いて「手動」で書いているから一応大丈夫、としておこう(注記1

<SableCC文法ファイルの「字句規則」の部分(抜粋)>

Helpers

    all = [0 .. 0xFFFF];  
    lowercase = ['a' .. 'z'];
    uppercase = ['A' .. 'Z'];
    digit = ['0' .. '9'];
    hex_digit = [digit + [['a' .. 'f'] + ['A' .. 'F']]];

    cr = 13;
    lf = 10;

    not_cr_lf = [all - [cr + lf]];

    id_part = lowercase (lowercase | digit)*;


Tokens

    d_dot = '..';
    semicolon = ';';
    equal = '=';
    l_bkt = '[';
    r_bkt = ']';
    l_par = '(';
    r_par = ')';

    plus = '+';
    minus = '-';
    q_mark = '?';
    star = '*';
    bar = '|';
    comma = ',';
    slash = '/';

    id = id_part ('_' id_part)*;

    char = ''' not_cr_lf ''';
    dec_char = digit+;
    hex_char = '0' ('x' | 'X') hex_digit+;

    string = ''' [not_cr_lf - ''']+ ''';


Productions

    token_def =
        state_list? id equal reg_exp look_ahead? semicolon;

    reg_exp =
        concat [concats]:reg_exp_tail*;

    reg_exp_tail =
        bar concat;

    concat =
        [un_exps]:un_exp*;

    un_exp =
        basic un_op?;

    basic =
        {char}    P.char |
        {set}     set |
        {string}  string |
        {id}      id |
        {reg_exp} l_par reg_exp r_par;

    char = 
        {char} T.char | 
        {dec}  dec_char |
        {hex}  hex_char;

    set =
        {operation} l_bkt [left]:basic  bin_op [right]:basic  r_bkt |
        {interval}  l_bkt [left]:P.char d_dot  [right]:P.char r_bkt;

    un_op = 
        {star}   star |
        {q_mark} q_mark |
        {plus}   plus;

    bin_op =
        {plus}  plus |
        {minus} minus;

 

※注記1:これはgimmickである。本来は文法の複雑さ(言語生成の計算量)、言語クラスに関する議論を行わなければならない。詳しくは参考文献を見よ。


4.2 字句規則における正規表現

正規表現として使えるリテラルとメタ文字(構文的な演算子)について下の表にまとめる。

表1.1 : 字句規則における正規表現

表記法
意味 拡張BNF記法
name = definition;
トークンの定義
name = definition
'...'
引用符内に書かれた文字(列)と一致
"literal"
または
rule1 | rule2
[...]
文字クラス
..
範囲(文字クラス内でのみ)
+
文字クラスの和集合
-
文字クラスの差集合
(...)
単一の要素として扱う
(rule1 rule2)
(...)?
省略可能(...は0個あるいは1個)
[rule] または *1(rule)
(...)*
0回以上の任意繰り返し
(rule) または *0(rule)
(...)+
1回以上の繰り返し
1*(rule)



4.3 字句規則の記述例

例1:全ての文字(Unicode)

all = ( [ 0 .. 0xFFFF ] )+;

例2:英数字全体

letter = ( ['0'..'9'] | ['a'..'z'] | ['A'..'Z'] )+;

例3:10進正整数(0以外のdigitで始まる形式)

number = '0' | ['1'..'9'] ( ['0'..'9'] )*;

例4:16進数(例:0xABCD)

hex_num = '0' ( 'x' | 'X' ) ( [ ['0'..'9'] + [ ['a'..'f'] + ['A'..'F'] ] ] )+;

例5:加減乗除を表す演算子

plus = '+';
minus = '-';
mult = '*';
div =
'/';

例6:プログラムの命令語(予約語)

begin = 'begin';
end = 'end';
for = 'f
or';

 

5. 字句解析器の実際

test0.grammar文法ファイルに基づいて、SableCCによって字句解析器(lexer.Lexer class)が生成される。生成されたJavaソースファイルの、字句解析処理を行っている部分(getTokenメソッド)の抜粋を以下に示す。
(説明上、左端に行番号を付した。実際の文法ファイル中に行番号は付されていない)

src/test0/lexer/Lexer.java(ファイル全体:354行)

     1  /* This file was generated by SableCC (http://www.sablecc.org/). */
     2
     3  package test0.lexer;
     4
     5  import java.io.*;
     6  import java.util.*;
     7  import test0.node.*;
     8
     9  public class Lexer
    10  {

....中略....

    54      protected Token getToken() throws IOException, LexerException
    55      {

....中略....

    71          while(true)
    72          {
                    ....一文字づつ読み込んで文字コードの検査....
    73              int c = getChar();
    74
    75              if(c != -1)
    76              {
    77                  switch(c)
    78                  {
    79                  case 10:
                            ....行位置カウンタ++....
    89                      break;
    90                  case 13:
                            ....行位置カウンタ++....
    94                      break;
    95                  default:
                            ....列位置カウンタ++....
    98                      break;
    99                  };
   100
                        ....字句解析DFAへ有効文字を追加....
   101                  text.append((char) c);
   102
   103                  do
   104                  {
                            ....トークン切り出し位置に到達するまでDFA処理....
   132                  }while(dfa_state < -1);
   133              }
   134              else
   135              {
   136                  dfa_state = -1;
   137              }
   138
   139              if(dfa_state >= 0)
   140              {
   141                  if(accept[dfa_state] != -1)
   142                  {
                            ....トークン切り出しに成功。文字列の長さと位置をストア....
   143                      accept_state = dfa_state;
   144                      accept_token = accept[dfa_state];
   145                      accept_length = text.length();
   146                      accept_pos = pos;
   147                      accept_line = line;
   148                  }
   149              }
   150              else
   151              {
   152                  if(accept_state != -1)
   153                  {
                            ....検出各トークンに対応する、構文木用ノード生成処理....
   154                      switch(accept_token)
   155                      {
   156                      case 0:
   157                          {
   158                              Token token = new0(
   159                                  getText(accept_length),
   160                                  start_line + 1,
   161                                  start_pos + 1);
   162                              pushBack(accept_length);
   163                              pos = accept_pos;
   164                              line = accept_line;
   165                              return token;
   166                          }
   167                      case 1:
   168                          {
   169                              Token token = new1(
   170                                  start_line + 1,
   171                                  start_pos + 1);
   172                              pushBack(accept_length);
   173                              pos = accept_pos;
   174                              line = accept_line;
   175                              return token;
   176                          }
   177                      case 2:
   178                          {
   179                              Token token = new2(
   180                                  getText(accept_length),
   181                                  start_line + 1,
   182                                  start_pos + 1);
   183                              pushBack(accept_length);
   184                              pos = accept_pos;
   185                              line = accept_line;
   186                              return token;
   187                          }
   188                      }
   189                  }
   190                  else
   191                  {
                            ....未認識のトークンが残っていたらエラー....
   192                      if(text.length() > 0)
   193                      {
   194                        throw new LexerException(
   195                          "[" + (start_line + 1) + "," + 
                                            (start_pos + 1) + "]" +
   196                          " Unknown token: " + text);
   197                      }
   198                      else
   199                      {
                            ....[EOF]まで到達していたら、正常終了....
   200                          EOF token = new EOF(
   201                              start_line + 1,
   202                              start_pos + 1);
   203                          return token;
   204                      }
   205                  }
   206              }
   207          }
   208      }
   209
   210      Token new0(String text, int line, int pos)
                      { return new TNumber(text, line, pos); }
   211      Token new1(int line, int pos) 
                      { return new TPlus(line, pos); }
   212      Token new2(String text, int line, int pos) 
                      { return new TBlank(text, line, pos); }

....中略....

   354  }

 

入力シーケンスとして、"3 + 4 + 5[EOF]"を与えた場合の、このトークン切り出しメソッドの処理の流れは以下のようである。

line = 1, pos = 1 --> read '3'
line = 1, pos = 2 --> read ' '(blank)
--> accept_token=0 --> new0( "3", 1, 1 ) --> return TNumber("3")

line = 1, pos = 2 --> read ' '(blank)
line = 1, pos = 3 --> read '+'
--> accept_token=2 --> new2( " ", 1, 2 ) --> return TBlank(" ")

line = 1, pos = 3 --> read '+'
--> accept_token=1 --> new1( "+", 1, 3 ) --> return TPlus()

line = 1, pos = 4 --> read ' '(blank)
line = 1, pos = 5 --> read '4'
--> accept_token=2 --> new2( " ", 1, 4 ) --> return TBlank(" ")

line = 1, pos = 5 --> read '4'
line = 1, pos = 6 --> read ' '(blank)
--> accept_token=0 --> new0( "4", 1, 5 ) --> return TNumber("4")

.....以下、省略.....

信州大学インターネット大学院

wasaki@cs.shinshu-u.ac.jp
Copyright(c) 2006 Katsumi Wasaki. All rights reserved.