بارسيك: التراجع لا يعمل

Question

أحاول تحليل بناء جملة نوع F #. بدأت في كتابة قواعد اللغة [f] وهرب إلى مشاكل، لذلك أنا مبسطة قواعد اللغة إلى هذا:

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]

ولكن هذا مجرد تفيضات المكدس لأن القواعد هي المتردد - typep لا يحاول typep identP لأنه يحاول المحاولة 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.`]+ 

ثم سيكون هذا أسهل للترجمة مباشرة إلى Parsec، على ما أعتقد. (واحد يعتقد ذلك try سوف تعمل، وأتوقع أنه يفعل ذلك بطريقة أو بأخرى، ولكن نعم، كانت تجربتي أيضا أنه كان علي أن أكون على الأقل في أعماق الخصر في بارسيك قبل أن أفهم أبدا "أين تضع try"لجعل الأمور تعمل.)

النظر في الرؤية أيضا مجاتن محلل موناديك في F # (بالإضافة إلى 7 مدخلات مدونات 7 7) لبعض الأساسيات. اعتقد ان مستندات PARSEC. (جرب مجرد قراءة لهم أعلى أسفل، فهي لائقة، إذا كنت أتذكر بشكل صحيح) وكذلك بعض الأمثلة في أوراق البحث المختلفة تتحدث عن مشكلات مثل تلك الموجودة في سؤالك.

Answer 3

هذا لن يساعدك على فهم المكان الذي تسير فيه، لكنني أقترح النظر في استخدام sepBy1 لتحليل أنواع مفصولة -> حرف او رمز. سيعطيك هذا قائمة من أنواع المحور، والتي يمكنك العودة إليها بعد ذلك إلى أنواع الوظائف بعد ذلك.