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

本日の内容

1-1. この授業のねらい
1-2. 正規文法
1-3. 非決定性オートマトン
1-4. 付録 Regtest.java(Java 1.4)

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

1-1. この授業のねらい

この授業では、データの解釈方法などを通じてまず、形式言語理論などのプログラミング理論を学びます。これを習得すると、様々なファイルの形式をプログラムで読めるようになります。キーワードはオートマトン、文脈自由文法、コンパイラコンパイラ、パーサなどです。そして、 XML に焦点をあて、解釈の原理、ツールの利用法などを学び、 XML 技術を習得します。キーワードは XML, DOM, SAX などです。最後に形式言語理論で学んだことを応用し、 GUI におけるイベントの制御を行います。キーワードはイベントリスナ、 UML などです。

データ構造とアルゴリズム I では様々なプログラムの定石を学びました。本講義では、自分で作成したプログラムのルールを実際にプログラムにするような定石を学びます。

この講義を習得すると、さまざまなアプリケーションプログラムを作れるようになります。また、大学院受験においてソフトウェアの試験で主に出題されるのがこの講義の範囲になります。但し、もっとも基本的なことしか取り上げませんので、他大学院の受験などでは適宜補う必要があります。

1-2. 正規文法

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

言語と文法

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

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

例1-1

Σ = \{0, 1\}

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

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

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

正規表現

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

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

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

例1-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, ababab などの文字列の繰り返しの表現を指定できないので、完全な意味での正規表現ではありません。しかし、一応複数のファイル名などを一つの文法で表すことができます。

演習1-1

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

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

Java での正規表現

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


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

また簡易版として、 java.lang.String クラスに 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)+ で同様の指定ができます

演習1-2

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

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

演習1-3

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

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

演習1-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){
    final String sample="This is a pen.";
    final Pattern p = Pattern.compile("\p{Alpha}\p{Alnum}*");
    final Matcher m = p.matcher(sample);
    while(m.find()){
      System.out.println(m.group());
    }
  }
}

演習1-5

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

演習1-6

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

1-3. 非決定性オートマトン

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

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

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

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

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

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

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

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

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

例1-3

正規表現 a は次のような非決定性オートマトンになります。
正規表現 ab は次のような非決定性オートマトンになります。

但し、このオートマトンでεを考える必要は無いので、省略できます。このように状態数の少ない等価なオートマトンを導くことを簡単化と言います。
正規表現 (ab|ac) は次のような非決定性オートマトンになります。

但し、これも最初の入力はどちらも a なので εを考える必要はありません。また、次の入力 b, c でともに受理状態に入ればいいので、こちらも省略できます。そのため次のように簡単化できます。
正規表現 (ab|ac)* は次のような非決定性オートマトンになります。

これもこのように簡単化できます。

演習1-7

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

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

1-4. 付録 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 {
    private final JPanel resultPanel;
    private final ResultArea okArea, ngArea;
    private final ClearAction clearAction;
    public 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 {
    private final JPanel panel;
    private final JTextArea textArea;
    private final JScrollPane scrollPane;
    private final JLabel label,counter;
    private 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);
    }
    public JPanel getPanel(){
	return panel;
    }
    public void append(String str){
	textArea.append(str+"\n");
	this.addCounter();
    }
    private void addCounter(){
	counter.setText(Integer.toString(++count));
    }
    private void clear(){
	textArea.setText("");
	counter.setText("0");
	count=0;
    }
}
class ControlPanel {
    private final JPanel middlePanel,sliderPanel;
    private final RegField regField;
    private final Executer executer;
    public 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());
    }
    public int getTimes(){
	return executer.getTimes();
    }
    public void setStartButtonAction(ActionListener al){
	executer.setStartButtonAction(al);
    }
    public void setClearButtonAction(ActionListener al){
	executer.setClearButtonAction(al);
    }
    public int getLength(){
	return regField.getLength();
    }
    public String getText(){
	return regField.getText();
    }
    public JPanel getMiddlePanel(){
	return middlePanel;
    }
    public JPanel getSliderPanel(){
	return sliderPanel;
    }

    public void setErrorMessage(String str){
	regField.setErrorMessage(str);
    }
}
class RegField {
    private final JTextField inputArea;
    private final JSlider lengthSlider;
    private final JLabel  errorMessage;
    public 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);
    }
    public int getLength(){
	return lengthSlider.getValue();
    }
    public JLabel getLabel(){
	return errorMessage;
    }
    public void setErrorMessage(String str){
	errorMessage.setText(str);
    }
    public JSlider getSlider(){
	return lengthSlider;
    }
    public JTextField getTextField(){
	return inputArea;
    }
    public String getText(){
	return inputArea.getText();
    }
}
class Executer {
    private final JButton startButton,clearButton;
    private final JSlider numberSlider;
    public Executer(){
	startButton = new JButton("Start");
	clearButton = new JButton("Clear");
	numberSlider = new JSlider(1,5,2);
	final Hashtable table = new 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);
    }
    public JSlider getNumberSlider(){
	return numberSlider;
    }
    public int getTimes(){
	return pow10(numberSlider.getValue());
    }
    public JButton getStartButton(){
	return startButton;
    }
    public JButton getClearButton(){
	return clearButton;
    }
    public void setStartButtonAction(ActionListener al){
	startButton.addActionListener(al);
    }
    public 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 {
    private final Random random;
    private final ControlPanel controlPanel;
    private final ResultPanel resultPanel;
    private final ActionListener startButtonAction;
    private 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','\"','#','$','%','&','\'',
			    '(',')','-','=','^','~','\\','|','`','@','{','[',
			    ']','}',';','+',':','*',',','<','.','>','/','?',
			    '_'};
    public StringGenerator(ControlPanel cp,ResultPanel rp){
	controlPanel = cp;
	resultPanel = rp;
	random = new Random();
	startButtonAction = this.new StartButtonAction();
    }
    public ActionListener getStartAction(){
	return startButtonAction;
    }
    private char getChar(){
	return letter[random.nextInt(letter.length)];
    }
    public String getString(int len){
	final 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){
	    final int times = controlPanel.getTimes();
	    final String regex = controlPanel.getText();
	    controlPanel.setErrorMessage("");
	    try{
		for(int i=0; i<times; i++){
		    final String randomString=getString(controlPanel.getLength());
		    resultPanel.add(randomString,randomString.matches(regex));
		}
	    }catch(Exception e){
		controlPanel.setErrorMessage("正規表現に誤りがあります");
	    }
	}
    }
}

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

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