パーセク：バックトラック機能していません

Question

私はF＃型の構文を解析しようとしています。私は、[F] Parsecの文法を書き始め、問題に走ったので、私は<のhref = "http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/manual/spec.html#簡素化_Toc245030785" のrel = "nofollowをnoreferrer">文法はこれまでします：

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が試されますので、typePをしようとしてarrowPになることはありません。次は、たとえば、様々な場所でtryを試します：

typeP = choice [try identP, arrowP]

しかし、私は何も（1）スタックオーバーフローまたは（2）非認識の基本的な行動変化していないようにみえ「 - >」。識別子次の

私の間違いは、おそらく成功しParsecの文法を書いています誰にも明らかです。誰かがそれを指摘することはできますか？

Answer 1

私は（私はそれを知らないので）問題があることである、と私は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)))"

あなたは左側にある矢印を持っている可能性を意味し、>タイプ -

さらに拡大し、何を混乱する可能性があると、その文法で、それはタイプと言うことです。それは大丈夫ですが、それは括弧の中にする必要があります。これは多分、アクションに以下を見てすることは有用である、ことができます。それは私を助けてくれます。

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)"

Answer 2

私はあなたの文法のうち、左再帰を考慮すべきだと思います。代わりの

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

は、

のような何かを得ます

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

そして、これはパーセクに直接変換することが容易になります、私は思います。 （一つはtryが働くだろうと思うだろう、と私はそれが何らかの形でない期待しますが、はい、私の経験でも、私が今まで物事を動作させるために、「どこtryを置くために」理解する前に、私はParsecの中で、少なくとも腰までの深さでなければならなかったということでした。 ）

（F＃のの中で単項パーサコンビネータも見て考えてみましょうだけでなく、7個の以前のC＃のブログエントリ）いくつかの基本について。私は、トップダウン、それらを読んでみてくださいパーセクドキュメントに（だと思います私が正しくリコール）だけでなく、様々な研究論文の例のいくつかは、あなたの質問内の1つのような問題について話す場合、彼らは、まともです。

Answer 3

これは、あなたが間違っているつもりかを理解する助けにはなりませんが、私はsepBy1記号で区切られた型を解析する->を使用してに探してお勧めしたいです。これは、あなたが、その後、その後、関数型に戻すことができます解析された種類のリストが表示されます。