質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
正規表現

正規表現とは特定の文字列によるパターンマッチングを行う際に用いられる宣言型プログラミングです。

Q&A

解決済

3回答

4466閲覧

正規表現の位置

aaaaaaaa

総合スコア501

正規表現

正規表現とは特定の文字列によるパターンマッチングを行う際に用いられる宣言型プログラミングです。

0グッド

0クリップ

投稿2017/02/13 10:23

以下は、小数点以下の数字を小数点第二位或いは、第三位に切り捨てる正規表現です。

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+▲
…正規表現の末尾に来たので終了。

というような図が出来たのですが、これは合っていますか。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

ikedas

2017/02/13 10:30 編集

まず、「カレントステート」「保存ステート」の意味を説明していただいた方がいいと思います。それと、改行が乱れていてちょっと読みにくいです。
guest

回答3

0

以下は、小数点以下の数字を小数点第二位或いは、第三位に切り捨てる正規表現です。

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

小数点第三位を持つ小数を「小数点第二位」に切り捨て、小数点第四位以下を持つ小数を「小数点第三位」に切り捨てる正規表現に読めます。
質問文中では「1.2341.23 で切り捨てられてしまう」のように意図しない動作であるように書かれていますが、aaaaaaaa さんは「小数点第二位」に切り捨てるべき少数として何を想定しておられたのでしょうか。
仮に 1.2341.23 に切り捨てられないとするなら全ての少数が「小数点第三位」に切り捨てられる事になり、小数点第二位に切り捨てられる少数がなくなってしまいます

質問の後半の説明はバックトラック処理を表しており、認識は正しいと思います。

Re: aaaaaaaa さん

投稿2017/02/14 04:43

編集2017/02/14 05:40
think49

総合スコア18156

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

「カレントステート」「保存ステート」という表現ですが、Jeffrey E.F. Friedl『詳説 正規表現 第3版』の「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/

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

投稿2017/02/14 09:18

編集2017/02/14 10:02
ikedas

総合スコア4227

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

投稿2017/02/13 10:32

Zuishin

総合スコア28656

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問