मेरे OCaml S- अभिव्यक्ति पार्सर को विफल करने के लिए क्या कारण है?
मैं OCaml में एक Lisp दुभाषिया बनाने पर काम कर रहा हूँ। मैंने स्वाभाविक रूप से फ्रंट-एंड के साथ शुरुआत की। अब तक मेरे पास एक एस-अभिव्यक्ति पार्सिंग एल्गोरिदम है जो ज्यादातर समय काम करता है। दोनों सरल एस-अभिव्यक्तियों जैसे (a b)और ((a b) (c d))मेरे फ़ंक्शन के लिए, ast_as_strयह दर्शाता है कि आउटपुट सूची संरचना गलत है। मैंने उसे नीचे प्रलेखित किया है। parseकाम करने के लिए कुछ भी नहीं लगता है पर अनगिनत बदलाव की कोशिश करने के बाद । क्या OCaml में पार्सर्स लिखने में किसी को शक है कि मैं अपना कोड कैसे ठीक कर सकता हूं?
type s_expression = Nil | Atom of string | Pair of s_expression * s_expression
let rec parse tokens =
match tokens with
| [] -> Nil
| token :: rest ->
match token with
| "(" -> parse rest
| ")" -> Pair(Nil, parse rest)
| atom -> Pair(Atom atom, parse rest)
let rec ast_as_str ast =
match ast with
| Nil -> "nil"
| Atom a -> Printf.sprintf "%s" a
| Pair(a, b) -> Printf.sprintf "(%s %s)" (ast_as_str a) (ast_as_str b);;
let check_output test = print_endline (ast_as_str (parse test));;
(*
Input:
(a b)
Output:
(a (b (nil nil)))
Almost correct...
*)
check_output ["("; "a"; "b"; ")"];;
(*
Input:
((w x) (y z))
Output:
(w (x (nil (y (z (nil (nil nil)))))))
Incorrect.
*)
check_output ["("; "("; "w"; "x"; ")"; "("; "y"; "z"; ")"; ")"]
जवाब
मैं मान रहा हूँ कि यह होमवर्क नहीं है। यदि यह है, तो मैं कुछ कम विशिष्ट संकेतों के उत्तर को बदल दूंगा।
एक पुनरावर्ती वंश पार्सर एक निर्माण की शुरुआत टोकन को पहचानने के द्वारा काम करता है, फिर निर्माण की सामग्री को पार्स करता है, फिर (बहुत बार) निर्माण के अंत टोकन को पहचानता है। एस-एक्सप्रेशंस में सिर्फ एक निर्माण होता है, कोष्ठक सूची। आपका पार्सर निर्माण के अंत की पहचान नहीं कर रहा है।
यदि आप मानते हैं कि आपका पार्सर सही ढंग से काम करता है, तो सही कोष्ठक )का सामना करना एक वाक्यविन्यास त्रुटि है। कोई बेजोड़ सही कोष्ठक नहीं होने चाहिए, और सही कोष्ठकों के मिलान को कोष्ठक सूची निर्माण के भाग के रूप में पार्स किया जाता है (जैसा कि मैंने ऊपर वर्णित किया है)।
यदि आप कसम खाते हैं कि यह सिर्फ एक निजी परियोजना है तो मैं एक पार्सर लिखना चाहूंगा। लेकिन आपको ऊपर बताए अनुसार कुछ लिखने की कोशिश करनी चाहिए।
ध्यान दें कि जब आप एक परमाणु देखते हैं, तो आप एक जोड़ी नहीं देख रहे हैं। Pair (Atom xyz, rest)परमाणु को देखते हुए वापस लौटना सही नहीं है ।
अपडेट करें
एक कार्यात्मक सेटिंग में चीजों को काम करने का तरीका पार्सिंग फ़ंक्शन को न केवल उस निर्माण को वापस करना है जो उन्होंने देखा था, बल्कि शेष टोकन जो अभी तक पार्स नहीं किए गए हैं।
निम्न कोड आपके उदाहरणों के लिए काम करता है और संभवतः सही करने के लिए बहुत करीब है:
let rec parse tokens =
match tokens with
| [] -> failwith "Syntax error: end of input"
| "(" :: rest ->
(match parselist rest with
| (sexpr, ")" :: rest') -> (sexpr, rest')
| _ -> failwith "Syntax error: unmatched ("
)
| ")" :: _ -> failwith "Syntax error: unmatched )"
| atom :: rest -> (Atom atom, rest)
and parselist tokens =
match tokens with
| [] | ")" :: _ -> (Nil, tokens)
| _ ->
let (sexpr1, rest) = parse tokens in
let (sexpr2, rest') = parselist rest in
(Pair (sexpr1, sexpr2), rest')
आप इस तरह check_output को परिभाषित कर सकते हैं:
let check_output test =
let (sexpr, toks) = parse test in
if toks <> [] then
Printf.printf "(extra tokens in input)\n";
print_endline (ast_as_str sexpr)
यहां मैं आपके दो परीक्षण मामलों को देखता हूं:
# check_output ["("; "a"; "b"; ")"];;
(a (b nil))
- : unit = ()
# check_output ["("; "("; "w"; "x"; ")"; "("; "y"; "z"; ")"; ")"];;
((w (x nil)) ((y (z nil)) nil))
- : unit = ()
मुझे लगता है कि ये सही परिणाम हैं।