ocaml的解釋

Question

有人可以給我一些幫助建立一個ocaml的解釋與語法的語言：

Prog ::= Def* Expr 
Def ::= id id* = Expr 
Expr ::= int | id | Expr '+' Expr | Expr '*' Expr | id Expr* | if Expr then Expr else Expr 

到目前爲止，我這樣做：

type expr = I of int 
| Id of string 
| Add of expr * expr 
| Multiply of expr * expr 
| If of expr * expr * expr 

let rec evaluate = function 
| I n -> n 
| Add(e1,e2) -> evaluate e1 + evaluate e2 
| Multiply(e1,e2) -> evaluate e1 * evaluate e2 
| If(a,b,c) -> if evaluate a<>0 then evaluate b else evaluate c 

這是什麼好？

Answer 1

在您的語法中，可以通過生產Expr ::= id或Expr ::= id Expr*來匹配單個ID。換句話說，無法區分無函數函數應用程序（假設生產應該匹配函數應用程序）和變量。也許你的意思是id Expr+（不允許使用無功函數應用程序）。

現有的代碼看起來不錯，但它是不完整的：

你expr類型缺少構造函數id Expr*生產的語法，即你錯過了代表功能的應用構造。您應該添加一個，然後將其添加到evaluate函數。

在您的evaluate函數中，缺少Id構造函數的一個例子。該情況應該在從標識符到值（整數）的映射中查找給定標識符的值。爲此，您的evaluate函數應該將這樣的映射作爲一個額外的參數。它還應該使用標識符到函數的另一個映射，然後可以在函數應用程序的情況下使用它來循環函數名稱。

說到這些映射，您目前沒有任何代碼來表示或處理定義。你應該想出一個類型來表示一個定義，另一個來表示函數。後一種類型應該包含功能參數的名稱和正文expr。

然後，您應該編寫一個函數，該函數接受一個定義列表並創建變量和函數的映射。對於每個變量定義，它應該評估右側的表達式並將結果值添加到變量映射中。對於每個函數定義，您應該將函數類型的值添加到函數映射中。在處理定義之後，您應該通過調用帶有該表達式的evaluate函數和作爲參數創建的兩個映射來評估最終表達式。

最後，您沒有任何實際解析程序的代碼，但我認爲這可能是故意的。