正規表現の位置

Question

以下は、小数点以下の数字を小数点第二位或いは、第三位に切り捨てる正規表現です。
```正規表現
s/(\.\d\d[1-9]?)\d+/$1/
```
だたこの正規表現は、1.234のような小数点第三位の小数に対しても有効になってしまい、つまり2が```\d```、3も```\d```、4が```\d+```
にマッチしてしまいます。つまり1.23となってしまうのです。```[1-9]?```に4がマッチしても、必須ではなく他に試せる保存ステートが残っており、
それを試すと、```[1-9]?```には、マッチせず```\d+```という必須の一つが4にマッチする。

カレントステートを▲、正規表現を見ている開始位置を△とすると、
```.```が小数点、```\d```が2、```\d```が3にマッチしたあと

△1.23▲4 (\.\d\d▲[1-9]?)\d+
…4が```[1-9]?```にマッチするかどうかの前に、失敗した時のため、保存ステートリストに「△1.23▲4 (\.\d\d[1-9]?)▲\d+」を保存。
  4と```[1-9]?```は、マッチするので先に進む。
△1.234▲ (\.\d\d[1-9]?)▲\d+
…空白と一個以上の数字は、マッチしないので失敗。
ここで、先ほど保存していた状態のうち、一番最後のものを復活させる。
△1.23▲4 (\.\d\d[1-9]?)▲\d+
…数字の4と一個以上の数字は、マッチするので先に進む。
△1.234▲ (\.\d\d[1-9]?)\d+▲  
…正規表現の末尾に来たので終了。

というような図が出来たのですが、これは合っていますか。

Accepted Answer

「カレントステート」「保存ステート」という表現ですが、Jeffrey E.F. Friedl『[詳説 正規表現 第3版](https://www.oreilly.co.jp/books/9784873113593/)』の「4.4 バックトラック」に出てくるようです。

同書ではバックトラックを、分かれ道 (複数の選択肢がある位置) を通過するたびにパンくずを落としておくことにたとえています。道が行き止まりになっていたときは、落としておいたパンくずをたどってもとの場所へ戻って来られる、というわけです (「4.4.1 パン切れのたとえ」‘A Really Crummy Analogy’。原題はパンくずcrumbに掛けていますが、訳題はかなり残念)。

上記の表現が最初に出てくるのは「4.4.3 保存ステート」のところのようです。訳書は持っていないので、原著から引用します。

> In NFA regular expression nomenclature, the piles of bread crumbs are known as saved **states**. (...) 〔強調は原文のまま〕
> \--- ‘Saved States’, 原著p.159.

(試訳)

> NFA正規表現の用語法では、〔道々残しておく〕パンくずの山は保存された**状態**として知られている。(…)〔強調箇所は原文と同じ〕

このように、用語として強調されているのは「state」(状態、ステート) だけです。ですから、「カレントステート」「保存ステート」という言葉は説明抜きに理解できる言葉ではありません。**どういう**ステートなのかをみんなが知っているわけではないのです。

質問者さんは、すでにこれまで何度か指摘されていると思いますが、本を読んでいて目に入った片言隻句をご質問の中で説明抜きに使うのはやめて下さい。**その言葉はどんな考え方を指すのか**を前後の文章から読み取り、ご質問を読む人にわかるように説明して下さい。

# 回答

次のように理解しました。

- 「現在の状態」(current state、カレントステート) - 次にマッチの試行を開始しようとする位置 (と試行しようとするマッチの選択肢)。
- 「保存された状態」(saved state、保存ステート) - すでに試行したマッチの開始位置 (と試行したマッチの選択肢)。バックトラックが起きると保存された状態に戻り、他の選択肢を再試行する。

このように考えると、ご質問の図は正しそうに見えます。

# ご質問についての補足説明

ご質問の正規表現は前掲書「4.5.4 欲張りでも控え目でも常にマッチ優先」‘Greediness and Laziness Always Favor a Match’ から採られたのだと思います。著者は、小数第3位より後を切り捨てる (小数第2位か第3位までしかなければそのまま) という意図の通りに動作するのは

```
s/(\.\d\d[1-9]?)\d*/$1/

```

というコードであることを最初に述べた上で、正規表現の書きかたを変えるとどう動作が変わるかを説明しています。ご質問の表現も出てきます。

Answer

> 以下は、小数点以下の数字を小数点第二位或いは、第三位に切り捨てる正規表現です。
>
> ```
> s/(\.\d\d[1-9]?)\d+/$1/
> ```

小数点第三位を持つ小数を「小数点第二位」に切り捨て、小数点第四位以下を持つ小数を「小数点第三位」に切り捨てる正規表現に読めます。
質問文中では「`1.234` が `1.23` で切り捨てられてしまう」のように意図しない動作であるように書かれていますが、aaaaaaaa さんは「小数点第二位」に切り捨てるべき少数として何を想定しておられたのでしょうか。
仮に `1.234` が `1.23` に切り捨てられないとするなら全ての少数が「小数点第三位」に切り捨てられる事になり、**小数点第二位に切り捨てられる少数がなくなってしまいます**。

質問の後半の説明はバックトラック処理を表しており、認識は正しいと思います。

Re: aaaaaaaa さん

Answer

バックトラックするかどうかは実装によって異なります。
DFA を使いバックトラック無しでマッチさせる実装もあります。