3

F# 型の構文を解析しようとしています。[F]Parsec 文法を書き始めて問題が発生したので、文法を次のように単純化しました。

type ::= identifier | type -> type
identifier ::= [A-Za-z0-9.`]+

FParsec で問題が発生した後、私は Parsec に切り替えました。なぜなら、私はそれを説明するための本の完全な章を持っているからです。この文法の私のコードは

typeP = choice [identP, arrowP]
identP = do
   id <- many1 (digit <|> letter <|> char '.' <|> char '`')
   -- more complicated code here later
   return id
arrowP = do
  domain <- typeP
  string "->"
  range <- typeP
  return $ "("++domain++" -> "++range++")"
run = parse (do t <- typeP
                eof
                return t) "F# type syntax"

問題は、Parsec がデフォルトでバックトラックしないことです。

> run "int"
Right "int"
-- works! 
> run "int->int"
Left "F# type syntax"
unexpected "-"
expecting digit, letter, ".", "`" or end of input
-- doesn't work!

私が最初に試みたのは、typeP の順序を変更することでした。

typeP = choice [arrowP, identP]

しかし、文法が左再帰であるため、これは単なるスタック オーバーフローidentPですarrowP。次に、さまざまな場所で試しtryました。たとえば、

typeP = choice [try identP, arrowP]

しかし、（1）スタックオーバーフローまたは（2）識別子に続く「->」の非認識の基本的な動作を変更することは何もないようです。

私の間違いは、Parsec 文法の記述に成功した人なら誰にでも明らかです。誰かがそれを指摘できますか？

4

3 に答える 3

5

問題はそれだと思います.F＃の仮定をしています（私はそれがわからないため）、矢印は右結合です。私はさまざまな文法に精通していないため、リンクされた文法がどの程度正確であるべきかわかりません。しかし、矢印が右結合的であると仮定できれば、問題は簡単になります。

したがって、その仮定を使用して、次のことを簡単に行うことができます。

identP = many1 (digit <|> letter <|> char '.' <|> char '`')

typeP = try arrowP <|> identP

arrowP = do
  i <- identP
  string "->"
  t <- typeP
  return $ "(" ++ i ++ " -> " ++ t ++ ")"

run = flip parse "F# type syntax" $ do
        t <- typeP
        eof
        return t

そう：

Haskell> run "int"
Right "int"
Haskell> run "int->int"
Right "(int -> int)"
Haskell> run "int->int->int->int"
Right "(int -> (int -> (int -> int)))"

さらに拡張すると、混乱するかもしれないのは、その文法では type -> type と書かれていることです。これは、左側に矢印がある可能性があることを意味します。それは問題ありませんが、括弧で囲む必要があります。これは役に立ちます。次の動作を確認すると役立つかもしれません。それは私を助けました。

typeP = try arrowP <|> parens typeP <|> identP

arrowP = do
 i <- parens typeP <|> identP
 string "->"
 t <- typeP
 return $ "(" ++ i ++ " -> " ++ t ++ ")"

parens p  = between (char '(') (char ')') p

これで、矢印の左側または右側に矢印を書くことができます:

Haskell> run "int->int->int"
Right "(int -> (int -> int))"
Haskell> run "(int->int)->int"
Right "((int -> int) -> int)"
于 2010-03-08T19:58:39.617 に答える
4

文法から左再帰を除外する必要があると思います。それ以外の

type ::= identifier | type -> type 
identifier ::= [A-Za-z0-9.`]+

あなたは次のようなものを得る

typeStart ::= identifier 
type ::= typeStart (-> type)?
identifier ::= [A-Za-z0-9.`]+

そうすれば、これを直接パーセクに変換するのが簡単になると思います。（それがうまくいくと思う人もいるだろうし、どういうわけかうまくいくと思うが、私の経験では、物事を機能させるためtryに「どこに置くべきか」を理解する前に、Parsecに少なくとも腰の深さまで行かなければならなかった。）try

基本については、F# の Monadic Parser Combinators (および以前の 7 つの C# ブログ エントリ) も参照することを検討してください。パーセクのドキュメント（上から下に読んでみてください。正しく思い出せば、まともです）と、さまざまな研究論文の例のいくつかが、質問のような問題について語っていると思います。

于 2010-03-09T00:42:56.510 に答える
0

これは、どこが間違っているのかを理解するのに役立ちませんが、シンボルでsepBy1区切られた型を解析するために使用することを検討することをお勧めします。->これにより、解析された型のリストが得られ、後で関数型に戻すことができます。

于 2010-03-08T19:55:20.627 に答える