6

最初の説明

カスタム正規表現エンジンを使ってテストをしようとしていますが、NFA を手で書くのに飽きてしまったので、パーサーを作成しようとしましたが、ほとんど成功しませんでした。通常、人々が正規表現を解析するとき、最終的に最終的なマシンに変換される複数の中間構造を作成します。私の単純な NFA 定義では、解析は実際には 1 回のパスで実行できると思いますが、(a) 実際にできない理由、または (b) どのように実行するかはまだ決定していませんが、私のパーサーは非常に単純に解析できます。ステートメント。

(単純化された) 状態エンティティは [1] のように定義されます。

type Tag = Int

data State a =
    Literal Tag a (State a)
  | Split (State a) (State a)
  | OpenGroup Tag (State a)
  | CloseGroup Tag (State a)
  | Accept                     -- end of expression like "abc"
  | Final                      -- end of expression like "abc$"

タグは、最終的な NFA にサイクルが含まれる可能性がある場合でも、Show および Eq インスタンスを許可します。たとえば、式をモデル化するには

-- "^a+(b*)c$"

[2] 使えます

c = Literal 3 'c' $ Final 1
b = OpenGroup 1 $ Literal 2 'b' bs
bs = Split b $ CloseGroup 1 c
expr = Literal 1 'a' $ Split expr bs

Thompson NFA 実装の C 実装を Haskell に移植することにより、この文法 (グループ タグを除く) 用に機能するスタック マシン ベースのパーサーを作成しましたが、これを構築するには 2 つのパス [3] が必要であり、最終的には上記の構造。

したがって、Parsec を介してこの構造を構築するために、リストのような構造を再帰的に構築することに関するこのサイトのエントリを読み、次のことを思いつきました。

import           Control.Applicative
import           Text.Parsec         hiding (many, optional, (<|>))
import           Text.ExpressionEngine.Types
import qualified Text.ExpressionEngine.Types as T

type ParserState = Int
type ExpParser = Parsec String ParserState
type ExpParserS a = ExpParser (T.State a)

parseExpression :: String -> T.State Char
parseExpression e = case runParser p 1 e e of
  Left err -> error $ show err
  Right r -> r
where
  p = p_rec_many p_char $ p_end 1

p_rec_many :: ExpParser (T.State a -> T.State a) -> ExpParserS a -> ExpParserS a
p_rec_many p e = many'
  where
    many' = p_some <|> e
    p_some = p <*> many'

p_end :: Int -> ExpParserS a
p_end n = (Final n <$ char '$') <|> (Accept n <$ eof)

step_index :: ExpParser Int
step_index = do
  index <- getState
  updateState succ
  return index

p_char = do
  c <- noneOf "^.[$()|*+?{\\"
  i <- step_index
  return $ Literal i c

そして、「ab」や「abc$」などの文字列を解析するには、これで十分です [4]。

問題

問題は、次のステップに進むときに発生します。「|」の解析です。またはステートメント。これが機能する方法は、次のような文字列です。

-- "(a|b|c)$"

次の構造を作成する必要があります。

final = Final 1
c = Literal 3 'c' final
b = Split (Literal 2 'b' final) c
a = Split (Literal 1 'a' final) b

つまり、 or ステートメントを構築するパーサーは、その後に続く代替式を取り、それをすべてのブランチに渡す必要があります (リストを取るように Split を変更すると、代わりに何かが変更されるとは思いません。各エントリはまだ同じものを受け取る必要があるためです)以下の式）。私の試みは：

p_regex :: T.State Char -> ExpParser (T.State Char)
p_regex e = do
  first <- p_rec_many p_char $ pure e
  (Split first <$> (char '|' *> p_regex e)) <|> return first

メインのパーサーは次のように変更されます。

parseExpression :: String -> T.State Char
parseExpression e = case runParser p 1 e e of
  Left err -> error $ show err
  Right r -> r
  where
    p = p_regex <*> p_end 1

しかし、これは型チェックに失敗します[5]。p_regex にはビルドされた (State a) オブジェクトが供給される必要があり、p_rec_many を使用した「リテラル」チェーンのビルドもこのように機能するように見えるため、これは正しいと思います。

おそらく、buildExpressionTable を使用する必要がありますか? ('$' <|> eof) を最高の優先度にすることができるため、この特定の問題に役立つ可能性があります。私はそれを試み始めましたが、スタープラスや疑問符演算子などをどのように処理するか想像できません。これらはすべて自分自身を参照する必要があるためです。

（編集：buildExpressionTableをもう一度試してみましたが、やりたいことには単純すぎるように思えます。スタックされた後置演算子[たとえば、「a？*」]をネイティブに処理できず、作成の計画「'$' <|> eof」は、文字列全体ではなく、最後に解析された「用語」にのみ適用されるため、最も高い優先度も機能しません。たとえそうできたとしても、「$」演算子は逆方向に適用: これは最後に解析された用語であり、前の用語にフィードされる必要があります.これを使用すればするほど、解析する前に式文字列を逆にするべきではないかと思うようになります.)

質問

それで、私は何を間違っていますか？私がやろうとしていることを行う方法があると確信していますが、これまでのところそれを理解できていません。お時間をいただきありがとうございます。

脚注

[1] 私が実際に使用しているものを正確に見たい場合は、ここで見つけることができます。

[2] Open/CloseGroup タグのアイデアは、NFA の実行中にグループの一致を追跡することです。リストされた式の配置は正確ではないかもしれませんが、対応する OpenGroup が見つかった場合にのみ CloseGroup タグがキャプチャ グループを作成する場合、この方法は適切に機能します (つまり、上記の例では、少なくとも 1 つの場合にのみキャプチャを作成します)。 'b' が見られた)。

他のすべてのタグ構造は正しく、この NFA が期待どおりに文字列に一致することをテストしました。

[3] Thompson の実装はここで説明されており、私のポートはここで見ることができます。これにより、NFA サブセットが完全に構築されますが、結果の構造では、次のすべての状態が Just でラップされます。これは、Nothing を使用してダングリング ポインターを表し、後のステップで正しい次のステップにパッチが適用されるためです。すべての (Just state) エントリを (state) エントリに変換することで、この構造を上記の構造に変換できますが、それは 3 回目のパスになります。この実装では、正規表現を後置表記に変換するための最初のパスが既に必要です。

【4】結果として

Literal 1 'a' (Literal 2 'b' (Accept 1))

と

Literal 1 'a' (Literal 2 'b' (Literal 3 'c' (Final 1)))

それぞれ。

[5]

Couldn't match expected type `a0 -> b0'
        with actual type `ExpParser (T.State Char)'
Expected type: T.State Char -> a0 -> b0
Actual type: T.State Char -> ExpParser (T.State Char)
In the first argument of `(<*>)', namely `p_regex'
In the expression: p_regex <*> p_end 1
4

2 に答える 2

1

わかりましたので、質問は基本的に次のとおりです。再帰的なデータ構造 (質問で定義) が与えられた場合、1 回のパスで式を構築するパーサーを作成するにはどうすればよいでしょうか。私の最初の試みは、本質的に「応用的」なものでした。条件分岐がなければ、再帰構造を構築できました。しかし、正規表現の解析には分岐が必要です。これが、私のアプローチがorステートメントに対して機能しない理由です。

これを解決するには、何らかの状態が必要でした。関数型言語で状態を運ぶ良い方法は、部分的に適用された関数を使用することです。p_char上記の署名は次のとおりです。

p_char :: ExpParser (T.State Char -> T.State Char)

したがって、それらを組み合わせる必要があるのは、複数の(T.State Char -> T.State Char)関数を一緒に構成するコンビネーターです。したがって、この洞察により、シーケンスは次のようになります。

p_many1 :: ExpParser (T.State Char -> T.State Char) -> ExpParser (T.State Char -> T.State Char)
p_many1 p = do
    f <- p
    (p_many1 p >>= return . (f .)) <|> return f

ここでorステートメントに必要なのは、"a|b|c" のような式を取り、次のような関数を作成するものです。

\e -> Split (Literal 1 'a' e) (Split (Literal 2 'b' e) (Literal 3 'c' e))

そのために、これを使用できます。

p_splitBy1 :: ExpParser (T.State Char -> T.State Char) -> Parsec String ParserState Char -> ExpParser (T.State Char -> T.State Char)
p_splitBy1 p sep = do
    f <- p
    (sep >> p_splitBy1 p sep >>= return . (\f' e -> Split (f e) (f' e))) <|> return f

そして、それは確かに私が必要とする構造を作成します. したがって、将来誰かが同様の問題に遭遇した場合、この質問/回答が役立つ可能性があります。

于 2013-05-16T19:33:50.003 に答える