6

OCaml を使用して、Scheme のサブセット用の再帰降下パーサーを作成しています。文法は次のとおりです。

    S -> a|b|c|(T)
    T -> ST | Epsilon

だから私が持っていると言います：

   type expr = 
       Num of int | String of string | Tuple of expr * expr

疑似コード

これらの関数は、AST を構築するために expr 型を返す必要があります。

parseS  lr =
   if head matches '(' then
     parseL lr
   else
     match tokens a, b, or c

トークンと '(' である S の最初のセットを使用:

parseL lr = 
   if head matches '(' or the tokens then
       Tuple (parseS lr, parseL lr)
  else
       match Epsilon

私の質問は、「() を返すことができないので、イプシロンの部分を返すにはどうすればよいですか?」です。OCaml 関数は同じ戻り値の型を必要とし、Epsilon 部分を空白のままにしても、OCaml はユニット型を想定します。

4

2 に答える 2

6

私が見る限り、あなたの AST はあなたの文法と一致しません。

文法でイプシロンを表すために、AST タイプに特に空のノードを用意することで、問題を解決できます。

または、文法を変更してイプシロンを除外することもできます。

イプシロンなしの同等の文法は次のとおりです。

S -> a|b|c|()|(T)
T -> S | S T
于 2012-11-30T20:06:53.037 に答える
4

パーサー関数を手動で作成する代わりに、既存のアプローチを使用する方がよいかもしれません: たとえば、LALR(1) ocamlyaccまたは camlp4 ベースの LL(k)パーサー?

于 2012-11-30T19:45:27.557 に答える