基本情報の正規表現を具体例で理解する記号・繰返し・一致判定

基本情報の正規表現は、記号を一つずつ暗記するだけでは文字列の一致判定で迷いやすい分野です。例えば英字の後に数字が続く式でも、数字が必須なのか、省略できるのかで答えが変わります。

読み方の軸は「どの文字を使うか」「何回繰り返すか」「どの順番で並ぶか」の三つです。まず問題文の記法を確認し、式を小さなまとまりへ分け、候補文字列を最後まで対応させれば判定できます。この記事では独自例題を使い、空文字列や括弧の読み違いまで確かめます。

この記事のポイント

文字クラスは一文字を選ぶ指定で、文字の並びそのものではない
繰返し記号は直前の一文字や括弧のまとまりに作用する
一致判定は最小文字数と文字の順序から候補を絞れる
形式言語の記法と実用ツールの部分一致は分けて考える

無料

基本情報技術者試験過去問アプリ

本番形式で繰り返し解ける。スキマ時間に1問から

2,000問以上収録

無料で過去問を解く

基本情報の正規表現と記号の読み方

正規表現は文字列の集合を表す

正規表現は、条件に合う文字列の集まりを式で表す方法です。例えば ab は文字aの直後に文字bがある並びを表します。a|b ならaまたはbを選び、a* ならaを0回以上並べます。文字を並べる連接、どちらかを選ぶ選択、同じ部分を繰り返す操作が基本になります。

ここでの「文字列の集合」は、単語帳のように候補をすべて書き出した一覧という意味ではありません。a* が表すものには、文字のない空文字列、a、aa、aaaなどが含まれます。長さの上限がなければ候補は無数にあるので、共通する作り方を一つの式で指定するわけですね。

空文字列は、文字が一つもない長さ0の文字列です。半角スペース一文字や、文字0とは違います。形式言語では ε と表すことがありますが、実用ツールへεを入力すると、その文字自体を探す場合があります。本記事で「空文字列」と書いた箇所は、文字を何も入力しない状態を指します。

IPAの基本情報技術者試験シラバスVer.9.2では、形式言語の項目に正規表現が挙げられています。ただし、シラバスは各プログラミング言語で使える記号を一つに固定するものではありません。設問に記号の定義がある場合は、その定義に従って読みます。

本記事の例題では、特記しない限り候補文字列の全体が式の条件を満たすかを判定します。aだけを表す式へbaを与えたら、末尾にaを含んでいても不一致です。「文字列の集合の要素」と「文章のどこかに一致する部分がある」は違う問いなので、最初に区別しておきましょう。

文字クラスは一文字を選ぶ

角括弧で囲む [ABC] は、A・B・Cのどれか一文字を表す指定です。ABCという三文字の並びを表すわけではありません。したがってAやBは一致しますが、ABやABCは、この文字クラスだけでは全体一致しません。長さを増やすには、文字クラスを続けて書くか、繰返しを指定します。

スクロールできます

式	この例で表すもの	全体一致する例	一致しない例
`[ABC]`	A・B・Cのいずれか一文字	A、C	AB、D
`[AB][12]`	AかBの後に1か2	A1、B2	1A、AB
`[A-Z]`	半角英大文字一文字と定義	M、Z	m、Ｍ
`[0-9]`	半角数字一文字と定義	0、7	12、７

範囲を表すハイフンは、[A-Z] ならAからZまで、[0-9] なら0から9までという指定に使います。本記事では表のようにASCIIの半角文字を対象にします。「英字一文字」とだけ書かれた設問では、問題文で大文字・小文字の扱いを確認してください。見た目の似た全角文字を勝手に含めないことが大切です。

[AB][12] を読むときは、一つ目の箱からAかB、二つ目の箱から1か2を取り出して並べるイメージです。作れる文字列はA1、A2、B1、B2の四つになります。どの文字を選んでも箱の順番は変わらないので、1Aは作れません。選択できることと、順序が自由であることを混同しないようにします。

実用正規表現には [^0-9] のように角括弧の先頭に ^ を置き、指定した文字以外を表す記法もあります。ここでは「半角数字以外の一文字」です。「数字以外の文字列を何文字でも」ではなく、長さは一文字のままです。この記号を使う問題でも、否定と回数を別々に読みましょう。

繰返しは回数と対象を分ける

繰返し記号でまず覚えたいのは、* が0回以上、+ が1回以上という違いです。A* はAを一度も使わなくてもよく、A+ は少なくとも一度は使います。どちらも上限はありませんが、最低限必要な文字数が違います。

スクロールできます

式	最低回数	最大回数	全体一致する例
`A*`	0回	上限なし	空文字列、A、AAA
`A+`	1回	上限なし	A、AAA
`A?`	0回	1回	空文字列、A
`A{3}`	3回	3回	AAA
`A{2,4}`	2回	4回	AA、AAA、AAAA

? や波括弧による回数指定は実用正規表現の補助記法として示しています。試験で登場したら問題文の定義を確認し、知らない記号を見た目だけで決めつけないでください。記号の種類が違っても、最低回数と最高回数を取り出す読み方は共通です。

次に、繰り返す対象を確認します。AB* はAを一文字、その後にBを0回以上並べる式です。A、AB、ABBは一致しますが、ABABは一致しません。一方、(AB)* はABという二文字のまとまりを0回以上並べるので、空文字列、AB、ABABなどが一致します。括弧の有無で長さの増え方も変わります。

「0回以上」の0回は、その部分を省略できるという意味です。AB*C のBを0回にするとACが残ります。式全体が空になるわけではありません。前後に必須のAとCがあるため、最小長は2文字です。空文字列が一致するか知りたいときは、星印の部分だけでなく、式全体で必須の文字が残るかを見ます。

ここで正規表現の + や * は回数の指示であり、候補文字列へその記号を追加する指示ではありません。A+ に対してA+という二文字を選ぶと、後ろの+を対応させる部分がないので不一致になります。記号自体を対象文字にしたい場合は、別に文字として扱う記法が必要です。

選択と連接は括弧で整理する

連接は、複数の式が表す文字列を順に結び付けることです。ab のように並べて書くほか、形式言語の説明では a・b のように連接の記号を明示することもあります。この中点は文字の「・」を入力する意味ではありません。教材ごとの定義を読んで、操作を表す記号と対象の文字を区別します。

選択に | を使う記法では、ab|cd はabまたはcdです。aに続いてbかc、その後にdと読むと別の条件になります。その条件は a(b|c)d と書き、abdまたはacdを表します。同じa・b・c・dが出ていても、どこを選ぶのかによって作れる文字列は変わります。

本記事で採用する記法では、繰返し、連接、選択の順に結び付きが強いものとします。例えば ab|c* はab全体か、cを0回以上並べた文字列を選びます。(ab|c)* は、abかcを一単位として何度でも選び直せます。実用記法の優先順位と括弧は、GNU grep公式マニュアルの基本構造でも確認できます。

繰返しの中に選択がある場合、各回で同じ枝を選ぶ必要はありません。(ab|c)* なら、1回目にab、2回目にc、3回目にabを選び、abcabを作れます。abだけを何回か並べるか、cだけを何回か並べるかという読み方では、許される組合せを狭めすぎてしまいます。

また、[ab] と (ab) は役割が違います。前者はaかbの一文字、後者はabという二文字のまとまりです。[ab]* ならabaも作れますが、(ab)* ではab単位で区切れないabaを作れません。角括弧は文字の候補、丸括弧は式のまとまりと読み分けると整理できます。

実用記号は試験の定義と分ける

形式言語としての正規表現と、エディタやプログラミング言語で使う正規表現には共通する考え方があります。ただし、実用ツールには検索位置、文字の種類、取得方法などの拡張があります。あるツールで通る式を、問題文の定義と比較せずに試験の正解へ流用しないようにしましょう。

例えば . は実用正規表現で任意の一文字を表すことが多い記号です。A.C はABCやA7Cのような三文字に一致します。点は「任意の長さ」ではないので、ACやABBCには全体一致しません。改行を含むかはエンジンや設定で異なるため、本記事の例は改行を含まない半角文字列に限定します。

点そのものに一致させたい場合、ここで使う実用記法では \. とします。A\.C ならA.Cが一致し、ABCは不一致です。バックスラッシュを前に置いて特殊な意味を外す操作をエスケープと呼びます。プログラムの文字列リテラルへ式を書くときは、その言語の文字列側でもエスケープが必要になる場合があり、正規表現だけの記法とは分けて確認します。

^ と $ は、JavaScriptでは通常それぞれ入力の先頭と末尾の位置を指定します。^AB$ はABの前後に余計な文字がない条件です。一方、複数行モードでは行の境界も対象になります。MDNの入力境界アサーションにあるように、位置指定は設定まで含めて読む必要があります。

「^は常に先頭」と丸暗記するのも危険です。角括弧の中の [^AB] ではAとB以外の一文字を表す記法になり、角括弧の外の ^AB とは役割が違います。さらに \d が対象にする数字の範囲も実装で差があるため、半角の0〜9だけを指定したい例では [0-9] と明示します。

形式言語の基本的な意味づけは、北海道大学の講義資料「情報検索とパターン照合」でも確認できます。本記事の中心は、定義された式から作れる文字列を判断することです。状態遷移図を追う練習は、基本情報のオートマトンと状態遷移図の解き方で別に学べます。

基本情報の正規表現を一致判定する手順

最低文字数から候補を絞る

一致判定は、いきなりすべての選択肢を細かく読むより、式の条件を先に整理すると見通しがよくなります。最初に問題文の記号の定義と、全体一致を問うのか部分一致を問うのかを確認します。次に式を文字クラス・固定文字・括弧のまとまりに分け、各部分へ最低回数を添えます。

設問の記法と照合範囲を確認する
括弧と繰返しの作用範囲を囲む
最低文字数と必須文字を求める
候補を順に対応させ、末尾に余りがないか見る

例えば [A-Z]+[0-9]* は、英大文字が1文字以上、その後に数字が0文字以上です。最小長は1文字で、数字はなくてもかまいません。英大文字が必須なので数字だけの候補は除けます。英字の後で数字へ移ったら英字へは戻れないので、M3Nのような並びも除けます。

IPAが公開する平成28年度春期の基本情報技術者試験午前問題の問3でも、文字クラスと0回以上・1回以上の定義を使う問題が確認できます。以下の例題はこの過去問の転載ではなく、条件を少し変えて読み方を練習するために作った独自問題です。

最低文字数は候補を絞る道具であり、それだけで一致が決まるわけではありません。必要な長さを満たしていても、文字の種類や順序が違えば不一致です。また選択を含む式では、枝ごとに最低文字数を求めます。AB|C は長さ2か1の文字列を表すので、「最小長が1だからどの一文字でもよい」とは読めません。

候補を式へ対応させるときは、どの部分がどの文字を使ったかを区切りで書くと説明しやすくなります。境目が複数あり得る場合は、一つの区切りで失敗しただけで除外せず、条件を満たす別の区切りがあるか確かめます。全体を条件どおりに分ける方法が一つでもあれば一致です。

例題で文字の順序と省略を確認

例題：[A-C]+[0-2]* に全体一致する文字列をすべて選んでください。文字クラスは半角の指定範囲、+は1回以上、*は0回以上とします。候補はA、CAB20、20CAB、AB2C、ABC+です。

スクロールできます

候補	判定	対応または不一致の理由
A	一致	英字Aを1回、数字を0回
CAB20	一致	CABと20に分けられる
20CAB	不一致	先頭から必須の英字部分を作れない
AB2C	不一致	数字部分へ進んだ後のCが余る
ABC+	不一致	末尾の+を対象文字として許していない

答えはAとCAB20です。Aで迷った場合は、[0-2]* を数字が「あるかもしれない部分」と読むと整理できます。0回のときに数字部分は空になり、英字だけが残ります。CAB20はCABを英字部分、20を数字部分へ割り当てれば、順序も回数も満たします。

20CABは、使っている文字だけなら範囲内です。しかし式は英字から始まるので、先頭の2を対応させられません。AB2Cも似た誤答で、文字の種類が正しくても順序が違います。ABを英字、2を数字に割り当てた後、最後のCを受け持つ式がありません。文字の集合に入っているかと、文字列全体を作れるかは別の確認です。

ABC+の+は、式の中では繰返しの指示でした。候補側に書かれた+は実際の一文字なので、この式では処理できません。正規表現を入力データに写すように考えると混同しがちですが、式は条件、候補は条件を確かめる対象です。この二つを分けて読むのがポイントです。

では式を [A-C]*[0-2]+ へ変えたらどうでしょうか。必須なのは数字側になり、2や012は一致します。Aは数字がないので不一致です。[A-C]+[0-2]+ なら英字も数字も必須となり、最小長は2文字です。記号を一つ変えたとき、どの候補が入れ替わるかも確かめておきましょう。

例題で括弧と選択を確認

例題：(ab|c)*d に全体一致する文字列を選んでください。候補はd、abd、cabcd、acbdです。|は左右どちらかの選択、括弧はまとまり、*は括弧全体の0回以上の繰返しとします。

答えはd、abd、cabcdです。dは括弧部分を0回にすれば作れます。abdはabを1回選び、その後に必須のdを置きます。cabcdは c / ab / c / d と区切れば、繰返し部分の各単位がcまたはabになり、最後のdも対応します。

acbdは不一致です。末尾のdを外したacbを、abかcだけで区切ろうとしても、先頭のaに続く文字がcなのでabを作れません。aやbを一文字ずつ好きな順番で使える条件ではないため、a・c・bが全部登場していることだけでは一致しません。括弧の選択肢を単位として読んでください。

次は (ab|c)+d へ変えた場合です。括弧のまとまりが1回以上必要になるので、dだけは不一致へ変わります。abdとcabcdは引き続き一致します。最小長は、短い枝cを一度選んでdを続ける2文字です。繰返し対象が二文字を含むからといって、毎回二文字増えるとは限りません。

もう一つ、ab|c*d と比較すると違いがはっきりします。この式は、abという文字列、またはcを0回以上並べた後にdがある文字列です。ab、d、ccdは一致しますが、abdは一致しません。最後のdが必須なのは右側の枝だけであり、左側のabへ自動的に付くわけではありません。

括弧を扱う練習では、短い一致例と似た不一致例を対にすると理解を確認できます。(ab)* にABの大文字を当てる前に、まず半角小文字のab、abab、abaを比べてみましょう。記号の役割と大文字小文字の違いを一度に混ぜず、作用範囲を理解してから条件を増やす方が原因を見つけやすくなります。

例題で境界と重なる条件を確認

例題：[A-Z]{2}[0-9]{2,3} に全体一致する文字列はどれでしょうか。回数指定は、{2}がちょうど2回、{2,3}が2回から3回とします。候補はAB12、AB123、A123、ABC12、AB1234です。

答えはAB12とAB123です。式は半角英大文字がちょうど2文字、その後に半角数字が2文字か3文字続く条件なので、全体の長さは4文字か5文字になります。A123は全体では4文字ですが英字が1文字しかなく、ABC12は5文字でも英字が3文字あります。長さが合っているだけでは正解になりません。AB1234は数字の上限を超えています。

このような問題は、最小回数の直前、最小回数ちょうど、最大回数ちょうど、最大回数の直後を比べると理解を確認できます。数字部分なら1桁、2桁、3桁、4桁を用意する方法です。境界を一つずつ動かせば、どの回数条件に違反しているか説明できます。

境目が重なる例として、a*ab とaaabを考えます。先頭の a* にaaを割り当て、後ろのabへ残りのabを割り当てれば一致します。a*へ先頭のaaaを全部割り当てた結果、後ろのaが足りなくなっても、それだけで不一致とはいえません。式全体を満たす分割があるかを見ます。

同じ式へabを与えた場合は、a*を0回として後ろのabへ二文字を割り当てれば一致します。bだけなら後ろのaが欠け、aaabaなら末尾のaが余るため不一致です。左から追う手順は便利ですが、繰返しが後ろの必須部分と同じ文字を使う場合は、割当てを調整する必要があります。

一方、[A-Z]+[0-9]* をAB12xへ当てると、英字部分ABと数字部分12の後にxが残るので全体一致しません。実用ツールで部分を検索する操作ならAB12が見つかることがあります。この違いは式の文字だけではなく、呼び出す照合方法にも関係します。Python公式のre.fullmatchは文字列全体を確認する方法で、searchは文字列内の一致箇所を探す方法です。

検算用ツールを使うときは、問題と同じ記法、全体一致、大文字小文字、改行の条件を選びます。設定の異なる検索結果が正解を保証するわけではありません。式に一致する形式を満たしていても、会員番号が実在するかなど別の意味的な条件までは確認できないことも、実用上は区別しておきましょう。