第 9 回正規表現、非決定性オートマトン

本日の内容

9-1. 構文解析
9-2. 非決定性オートマトン
9-3. 付録 Regtest.java(Java 1.4)

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

9-1. 構文解析

今週からは、入力データの意味や内容を解析するために、文法理論を学びます。参考書を選ぶ時は、「コンパイラ論」のようなものが参考になります。

言語と文法

コンピュータで記号列を解釈するには、その記号列がどのようなルールで作られているかを知る必要があります。記号列を生成するルールを文法と言います。そして、生成される記号列すべての集合を言語と言います。文法を記号 G で表す時、その文法で生成される言語を L(G) と書くことがあります。なお、記号の集合をアルファベットと言います。しばしばアルファベットはΣで表されます。そして、そのアルファベットΣから作られる記号列全体の集合を $Σ^{*}$ で表します。なお長さが0の記号列(空列)をεで表します。

アルファベット Σ: 使用する記号の集合
$Σ^{*}$: 空列を含む生成可能な記号列すべての集合
文法 G: 記号列を生成するルール
言語 L(G): G にしたがって生成される記号列すべての集合

例9-1

Σ = \{0, 1\}

Σ^{*} = \{ε 0100011011000 ...\}

G = "1 で終らないもの"

L (G) = \{ε 00010000010 ...\}

正規表現

正規表現を次のように定義します。

ε は正規表現です。
アルファベット一文字は正規表現です。
R と S が正規表現なら、 R | S, RS, {R} は正規表現です({R} は R の 0 回以上の繰返し)。

正規表現は一つの文法になりうるので、正規表現で一つの言語を定義することができます。

例9-2

$G_{1} = \{a\}$: $L (G_{1}) = \{ε a aa aaa ...\}$
$G_{2} = a | b | c$: $L (G_{2}) = \{a, b, c\}$
$G_{3} = (1| 2| 3| 4| 5| 6| 7| 8| 9) \{(0| 1| 2| 3| 4| 5| 6| 7| 8| 9)\}$: $L (G_{3}) = 自然数$

メモリーが有限個しか使えないコンピュータが計算できる言語は正規表現だけであることが知られています。このように正規表現はプログラムと非常に密接な関係にありますので、さまざまなところで使用されています。例えば、 MS-DOS プロンプトやコマンドプロンプトなどでも、ファイル名を指示する時、不完全ながらも正規表現が使えます。

文字は正規表現
正規表現の連結は正規表現
? は任意の一文字、* は任意の文字列を表します。

但し、これは ab, abab などの表現を指定できないので、完全な意味での正規表現ではありませんが、一応複数のファイル名などを一つの文法で表すことができます。

演習9-1

コマンドプロンプトまたは MS-DOS プロンプトで c:\windows または c:\winnt ディレクトリの中のファイルのうち、次の条件に当てはまるファイル名を dir コマンドを使って表示しなさい。但し、 Windows や MS-DOS はファイル名を二つの文字列を.(ピリオド)でつながった形で表し、後ろの文字列を拡張子と言います。例えば「拡張子が txt のファイル名」は dir *.txt で表示します。

a で始まるファイル名
拡張子が exe のファイル名
前の部分のファイル名が d で終るファイル名

Java での正規表現

Java ではバージョン 1.4 から java.util.regex パッケージが追加され、次のような構文で正規表現が使えるようになりました。


 Pattern p = Pattern.compile("a*b");
 Matcher m = p.matcher("aaaaab");
 boolean b = m.matches();

また簡易版として次の表記も可能になりました。


 boolean b = "aaaaab".matches("a*b");

以下は Java での正規表現を表しかたの例です(詳しくは言語のリファレンスを御覧下さい)。

. は任意の一文字を表す正規表現
^ は文字の最初、 $ は文字の最後を表す正規表現
英字、数字など特殊文字以外は正規表現
[ と ] に囲まれる文字の列は、それらの文字のうちのどれか一文字を表す正規表現(但し、次項の形になる場合は除く)で、特に文字クラスと呼ばれます。。 A-Zという表現で A から Z までのすべての文字を表します。
[^ と ] に囲まれる文字の列は、それらの文字のどれにも含まれない文字一文字を表す正規表現。これも同様に A-Z の表現が使えます。
\(バックスラッシュ、または円記号)に一文字を加えるとさまざまなものを表します。 \n や \t などは C 言語と同じですが、\d で数 [0-9]、 \D で数以外[^0-9]、 \s で空白[ \t\n\x0B\f\r]を表す記号(タブや改行も含む)、\S で空白以外の文字などを表します。また、 \\ でバックスラッシュまたは円記号を表します。
\p{名前} は POSIX character classes を指定するのに使います。 \p{Lower} は小文字[a-z]、\p{Upper}は大文字 [A-Z]、\p{Alpha} はアルファベット[\p{Lower}\p{Upper}]、 \p{Digit}は数字[0-9]、\p{Alnum}は英数字 [\p{Alpha}\p{Digit}]、\p{Space}は空白[ \t\n\x0B\f\r] を表します。
R,S が正規表現の時、 RS は R の次に S が来ることを示す正規表現
R,S,T が正規表現の時、(R|S|T) で R または S または T のどれかを示す正規表現
R が一文字を表す正規表現の時、R? で R が 0 回または 1 回を表す正規表現、R* で R が 0 回以上の繰返しを表す正規表現、 R+ で R が 1 回以上の繰返しを表す正規表現。なお、 R が複数の文字を表す正規表現の場合も、 (R)?, (R)*, (R)+ で同様の指定ができます

演習9-2

以下のアプレットを使って、ランダムな 1000 個の文字列のうち、次の文字列がいくつ出て来るか調べなさい。但し、文字列の長さは 5 とします。

a で始まる文字列
a を含む文字列
英字で始まり、残りは英字と数字だけの文字列

演習9-3

次の正規表現が受理する言語(文字列の集合)を求めなさい。

a*
[abc]
<[^>]*>
[1-9][0-9]*

演習9-4

次の文字列を表す正規表現を示しなさい。

先頭が a で始まる文字列
最後が b で終る文字列
c を含む文字列
abc を含む文字列
abc または def を含む文字列
先頭が英字または_(アンダースコア)、二文字目以降がある場合英字、数字、または_(アンダースコア)である文字列(C 言語では名前はこのルールに従う必要がある)

例えば、単語は、英字で始まって、英字または数字が連続するものですが、それは [A-Za-z][A-Za-z0-9]* と書くことができます。あるいは Java ではもっと簡単に \p{Alpha}\p{Alnum}*と書くこともできます。これを使うと次のようなプログラムが書けます。


import java.util.regex.*;
class Sample {
  public static void main(String[] args){
    String sample="This is a pen.";
    Pattern p = Pattern.compile("[A-Za-z][A-Za-z0-9]*");
    Matcher m = p.matcher(sample);
    while(m.find()){
      System.out.println(m.group());
    }
  }
}

演習9-5

Java の表現で、整数を表しなさい
次の文字列中の整数を列挙するプログラムを作りなさい
```
String input="-10+30-20";
```
input 文字列に含まれている整数の数を表示するプログラムを作りなさい

C, C++ での正規表現

C や C++ はそのままでは正規表現を取り扱えません。 UNIX 系の OS では POSIX 規格の関数が用意されているため利用できます (Windows 2000 Professional や Windows XP 系は POSIX をうたってますが、このライブラリはないようです)。 C では regex.h に regcomp という正規表現のコンパイラと regexec という正規表現を文字列と比較してマッチする位置を格納する関数があります。以下は上記の Java とほぼ同等のプログラム例です。

例9-3


#include <sys/types.h>
#include <regex.h>
#include <stdio.h>
int main(void){
  char sample[]="This is a pen.";
  char pattern[]="[A-Za-z][A-Za-z0-9]*";
  regex_t m;
  size_t nmatch=1;
  regmatch_t pmatch[nmatch];
  int i;
  char *p;
  regcomp(&m,pattern,0);
  for(p=sample;!regexec(&m,p,nmatch,pmatch,0);p+=pmatch[0].rm_eo){
    for(i=pmatch[0].rm_so;i<pmatch[0].rm_eo; i++){
      printf("%c",p[i]);
    }
    printf("\n");
  }
  return 0;
}

なお、 mingw でも rx というライブラリをインストールすれば上のプログラムを利用できます。その場合、 #include <regex.h> を #include <rxposix.h> と書き換えた後、コンパイルする時に gcc ファイル名 -lrxとすれば実行ファイルを作れます。

Boost ライブラリ

C++ 言語の拡張として Boost テンプレートライブラリがあります。これは C++ の正式な言語拡張ではありませんが、次期の C++ にライブラリの多くが含まれることが策定されています。 Boost の中に xpressive または regex という str::string 用の正規表現処理テンプレートが存在します。使用法に関しては詳しく説明しませんが、レポートなどで使用しても構いません。

コンパイラコンパイラ flex

lex や flex という、「正規表現からそれを認識する C プログラムを生成する」プログラムがあります。構文は次のようになっています。


初期設定
%%
正規表現パターン1 {処理プログラム1}
正規表現パターン2 {処理プログラム2}
...
正規表現パターンn {処理プログラムn}
%%
C プログラム

入力は基本的には標準入力になります。そして、処理プログラムではマッチした文字列へのポインタが yytext という変数名で参照できます。また、マッチしたもの以外を無視するには「その他は無視する」というパターン . ;を付加する必要があります。

例9-4

上記のJava や C のプログラム同様に名前を認識するプログラムを示します。始めに標準入力から入力を得る例を示します。



%%
[A-Za-z][A-Za-z0-9]* { printf("%s\n",yytext);}
. ;
%%
int main(void){
   yylex();
   return 0;
}

これを sampreg.l というファイルに保存した場合、flex sampreg.l とすると lex.yy.c という C 言語のソースファイルが出来上がるので、gcc lex.yy.c -lfl と -lfl オプション付きでコンパイルするとプログラムが作れます。通常、flex では標準入力が対象になってます。そのため、このサンプルのように入力が標準入力ではなく文字列の場合、入力を切替えるためのマクロや関数定義が必要となります。以下は入力を文字配列として与えるものです。柔軟性はあるものの、入力部分をすべて差し替えるので複雑です。



%{
#undef YY_INPUT
#define YY_INPUT(b, r, ms) (r=my_input(b,ms))
%}
%%
[A-Za-z][A-Za-z0-9]* { printf("%s\n",yytext);}
. ;
%%
char samp[]="This is a pen.";
char* ptr;
extern int my_input();
int my_input(char *buf, int max_size)
{
  int n;
  n = strlen(ptr);
  if(n>max_size){ n=max_size; }
  if (n>0){
    strncpy(buf, ptr, n);
    ptr +=n;
  }
  return n;
}
int main(void){
  ptr=samp;
  yylex();
  return 0;
}

演習9-6

次の文字列中の整数を列挙するプログラムを作りなさい
```
char inputstring[]="-10+30-20";
```
inputstring 文字列に含まれている整数の数を表示するプログラムを作りなさい

9-2. 非決定性オートマトン

ここまでは正規表現を解釈するツールを利用してきました。これからは、正規表現をプログラムに変換する手法を学びます。単純な正規表現ならわざわざツールに頼る必要はありません。

始めにオートマトンについて学びます。オートマトンとは次のような有向グラフです。

開始ノードというノードが一つ指定される
終了ノードが一つ以上指定される
各辺には文字が一つずつ割り振られている。

文字列に対して、開始ノードから一文字ずつたどって終了ノードにたどり着けた時、オートマトンはその文字列を受理すると言います。一方、辺がなかったり、文字列が終った時に終了ノードではなかった時拒否すると言います。オートマトンにより、受理する文字列の集合が決定できます。受理する文字列の集合をそのオートマトンが受理する言語と言います。

各ノードから出る辺に割り当てられている文字がすべて異なるオートマトンを決定性オートマトンと言います。このオートマトンは状態遷移図とも呼びます。決定性オートマトンは入力により流れが分岐するだけですので、簡単にプログラムに変換できます。

一方、各ノードから出る辺に割り当てられている文字にダブりがあったり、 ε(空文字)が割り当てられているオートマトンを非決定性オートマトンと言います。ここでは非決定性オートマトンの受理する言語と正規文法で定められる言語が一致することを示します。具体的には正規文法から非決定性オートマトンへの変換の仕方を示します。 (非決定性オートマトンから正規文法への変換方法は省略します)

正規文法から非決定性オートマトンへ

帰納法により証明します。

ε を受理する非決定性オートマトンは次の通りである。
文字 A を受理するオートマトンは次の通りである。
R と S が正規表現であり、それを受理する非決定性オートマトンが存在する時、R|S を受理する非決定性オートマトンは次の通りである。
R と S が正規表現であり、それを受理する非決定性オートマトンが存在する時、RS を受理する非決定性オートマトンは次の通りである。
R が正規表現であり、それを受理する非決定性オートマトンが存在する時、{R} を受理する非決定性オートマトンは次の通りである。

演習9-7

次の正規表現を受理する非決定性オートマトンを作りなさい。

a*
[abc]
(abc|asd)
.*(a|b)?
1[01]*

9-3. 付録 Regtest.java(Java 1.4)


package regtest;
import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
public class Regtest extends JApplet {
    Container contentPane;
    ResultPanel resultPanel;
    ControlPanel controlPanel;
    StringGenerator stringGenerator;
    public void init(){
	contentPane = getContentPane();
	resultPanel = new ResultPanel();
	contentPane.add(resultPanel.getPanel(),BorderLayout.NORTH);
	controlPanel = new ControlPanel();
	contentPane.add(controlPanel.getMiddlePanel(),BorderLayout.CENTER);
	contentPane.add(controlPanel.getSliderPanel(),BorderLayout.SOUTH);

	stringGenerator = new StringGenerator(controlPanel, resultPanel);
	controlPanel.setStartButtonAction(stringGenerator.getStartAction());
	controlPanel.setClearButtonAction(resultPanel.getClearAction());
    }
}
class ResultPanel {
    JPanel resultPanel;
    ResultArea okArea, ngArea;
    ClearAction clearAction;
    ResultPanel(){
	resultPanel=new JPanel();
	okArea = new ResultArea("適合");
	ngArea = new ResultArea("不適合");
	resultPanel.add(okArea.getPanel());
	resultPanel.add(ngArea.getPanel());
	clearAction = new ClearAction();
    }
    void add(String str, boolean b){
	if(b){
	    okArea.append(str);
	}else{
	    ngArea.append(str);
	}
    }
    JPanel getPanel(){
	return resultPanel;
    }
    ActionListener getClearAction(){
	return clearAction;
    }
    class ClearAction implements ActionListener {
	public void actionPerformed(ActionEvent event){
	    okArea.clear();
	    ngArea.clear();
	}
    }
}
class ResultArea {
    JPanel panel;
    JTextArea textArea;
    JScrollPane scrollPane;
    JLabel label,counter;
    int count;
    public ResultArea(String aLabel){
	count=0;
	panel = new JPanel();
	panel.setLayout(new BorderLayout());
	textArea = new JTextArea(10,20);
	scrollPane = new JScrollPane(textArea);
	label = new JLabel(aLabel,SwingConstants.CENTER);
	counter = new JLabel("0");
	counter.setHorizontalAlignment(SwingConstants.CENTER);
	panel.add(scrollPane,BorderLayout.CENTER);
	panel.add(label,BorderLayout.NORTH);
	panel.add(counter,BorderLayout.SOUTH);
    }
    JPanel getPanel(){
	return panel;
    }
    void append(String str){
	textArea.append(str+"\n");
	this.addCounter();
    }
    private void addCounter(){
	counter.setText(Integer.toString(++count));
    }
    void clear(){
	textArea.setText("");
	counter.setText("0");
	count=0;
    }
}
class ControlPanel {
    JPanel middlePanel,sliderPanel;
    RegField regField;
    Executer executer;
    ControlPanel(){
	regField = new RegField();
	executer = new Executer();
	middlePanel=new JPanel();
	sliderPanel = new JPanel();

	middlePanel.add(regField.getTextField());
	middlePanel.add(regField.getLabel());
	middlePanel.add(executer.getStartButton());
	middlePanel.add(executer.getClearButton());

	sliderPanel.add(new JLabel("長さ:"));
	sliderPanel.add(regField.getSlider());
	sliderPanel.add(new JLabel("回数:"));
        sliderPanel.add(executer.getNumberSlider());
    }
    int getTimes(){
	return executer.getTimes();
    }
    void setStartButtonAction(ActionListener al){
	executer.setStartButtonAction(al);
    }
    void setClearButtonAction(ActionListener al){
	executer.setClearButtonAction(al);
    }
    int getLength(){
	return regField.getLength();
    }
    String getText(){
	return regField.getText();
    }
    JPanel getMiddlePanel(){
	return middlePanel;
    }
    JPanel getSliderPanel(){
	return sliderPanel;
    }

    void setErrorMessage(String str){
	regField.setErrorMessage(str);
    }
}
class RegField {
    JTextField inputArea;
    JSlider lengthSlider;
    JLabel  errorMessage;
    RegField(){
	inputArea = new JTextField("正規表現を入れてください",20);
	errorMessage = new JLabel();
	lengthSlider = new JSlider(1,20,5);
	lengthSlider.setMajorTickSpacing(5);
	lengthSlider.setMinorTickSpacing(1);
	lengthSlider.setPaintTicks(true);
	lengthSlider.setSnapToTicks(true);
	lengthSlider.setPaintLabels(true);
    }
    int getLength(){
	return lengthSlider.getValue();
    }
    JLabel getLabel(){
	return errorMessage;
    }
    void setErrorMessage(String str){
	errorMessage.setText(str);
    }
    JSlider getSlider(){
	return lengthSlider;
    }
    JTextField getTextField(){
	return inputArea;
    }
    String getText(){
	return inputArea.getText();
    }
}
class Executer {
    JButton startButton,clearButton;
    JSlider numberSlider;
    Executer(){
	startButton = new JButton("Start");
	clearButton = new JButton("Clear");
	numberSlider = new JSlider(1,5,2);
	java.util.Hashtable table = new java.util.Hashtable();
	table.put(new Integer(1),new JLabel(Integer.toString(pow10(1))));
	table.put(new Integer(5),new JLabel(Integer.toString(pow10(5))));
	numberSlider.setLabelTable(table);
	numberSlider.setMinorTickSpacing(1);
	numberSlider.setPaintTicks(true);
	numberSlider.setPaintLabels(true);
	numberSlider.setSnapToTicks(true);
    }
    JSlider getNumberSlider(){
	return numberSlider;
    }
    int getTimes(){
	return pow10(numberSlider.getValue());
    }
    JButton getStartButton(){
	return startButton;
    }
    JButton getClearButton(){
	return clearButton;
    }
    void setStartButtonAction(ActionListener al){
	startButton.addActionListener(al);
    }
    void setClearButtonAction(ActionListener al){
	clearButton.addActionListener(al);
    }
    private int pow10(int j){
	int ret=1;
	for(int i=0; i<j ; i++){
	    ret *=10;
	}
	return ret;
    }
}
class StringGenerator {
    java.util.Random random;
    ControlPanel controlPanel;
    ResultPanel resultPanel;
    ActionListener startButtonAction;
    final char[]  letter = {'a','b','c','d','e','f','g','h','i','j','k','l',
			    'm','n','o','p','q','r','s','t','u','v','w','x',
			    'y','z','A','B','C','D','E','F','G','H','I','J',
			    'K','L','M','N','O','P','Q','R','S','T','U','V',
			    'W','X','Y','Z','0','1','2','3','4','5','6','7',
			    '8','9',' ','\t','1','\"','#','$','%','&','\'',
			    '(',')','-','=','^','~','\\','|','`','@','{','[',
			    ']','}',';','+',':','*',',','<','.','>','/','?',
			    '_'};
    StringGenerator(ControlPanel cp,ResultPanel rp){
	controlPanel = cp;
	resultPanel = rp;
	random = new java.util.Random();
	startButtonAction = this.new StartButtonAction();
    }
    ActionListener getStartAction(){
	return startButtonAction;
    }
    private char getChar(){
	return letter[random.nextInt(letter.length)];
    }
    String getString(int len){
	StringBuffer retStr=new StringBuffer(len);
	while(int i=0; i<len; i++){
	    retStr.append(this.getChar());
	}
	return retStr.toString();
    }
    class StartButtonAction implements ActionListener {
	public void actionPerformed(ActionEvent event){
	    int times = controlPanel.getTimes();
	    String regex = controlPanel.getText();
	    controlPanel.setErrorMessage("");
	    try{
		for(int i=0; i<times; i++){
		    String randomString=getString(controlPanel.getLength());
		    resultPanel.add(randomString,randomString.matches(regex));
		}
	    }catch(Exception e){
		controlPanel.setErrorMessage("正規表現に誤りがあります");
	    }
	}
    }
}

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 9 回 正規表現、非決定性オートマトン