こんにちは、Habr！ この記事では、Haskellで日曜大工（下）インタープリターを作成する方法について説明します。 興味のあるカットをお願いします！
ある日、私は自分のインタープリターを作成するというアイデアを得ました。そして、Haskellで作成しました。 ゼロから書くことは心の弱い人のための活動ではありません。そして、もしすべてがすでに他の（おそらく）より経験のある人々によってこのために書かれているのなら、なぜでしょう！
ステップ1：TKを自分で表現する
（下の）インタープリターは次のように機能します。
let a = 2 in a*2
4
let a = 8 in (let b = a - 1 in a*b)
56
加算、減算、乗算、除算（整数）の演算からのレットインのみ、整数のみ。 行こう！
ステップ2：アレックス
最初に必要なのはレクサー（コードを粒子に分割するプログラム-トークン）です。 偉大で強力なCで翻訳者を書いた人は、おそらくflex-偉大で強力なlexerジェネレーターを覚えているでしょう。 Haskellではなく、レクサージェネレーターでもある、より優れた強力なalexを使用します。
こちらからアレックス
をダウンロードまたは
$ sudo apt-get install alex次に、お気に入りのテキストエディタを開いて次のように記述します
{ module Lex where } %wrapper "basic" $digit = 0-9 $alpha = [a-zA-Z] tokens :- $white ; let { \s -> TLet } in { \s -> TIn } $digit+ { \s -> TNum (read s)} [\=\+\-\*\/\(\)] { \s -> TSym (head s)} $alpha [$alpha $digit \_ \']* { \s -> TVar s} { data Token = TLet | TIn | TNum Int | TSym Char | TVar String deriving (Eq, Show) }
怖い。
実際、すべてがシンプルです。 まず、Lexモジュールを宣言し（中括弧内のコードは純粋なHaskellです）、基本的なラッパーを使用することを言います。つまり、安価で陽気な、文字セット（charsets）の定義に移動します-charsetの名前は$で始まり、値は（ほぼ）正規表現です。 $数字はすべて数字、$ alphaはすべて文字です。 今、最も重要なことはトークンです。 後：-それらの定義は、左側に正規表現、右側にトークンが続くはずです。 スペース（左側の空白の文字セット、右側のセミコロン）を無視します.- TIn、1つ以上の数字-TNum、すべてのプラスとマイナス-TSym、文字、下線、および '-TVar さらに、文字Tの怖い単語はすべてトークン値であり、複雑なものではないことがわかります。
今こそ魔法の時です。
ファイルをLex.xとして保存してから、
$ alex Lex.xできた！ Unasはレクサーモジュール-Lex.hsです！
ステップ3：幸せ
パーサージェネレーターが必要になりました-幸せです。 Cに対応するのは、bisonとyaccです。
ここからダウンロードするか、
$ sudo apt-get install happySynt.yファイルを作成する
{ module Synt where import Lex } %name synt %tokentype { Token } %error { parseError } %token let { TLet } in { TIn } num { TNum $$ } var { TVar $$ } '=' { TSym '=' } '+' { TSym '+' } '-' { TSym '-' } '*' { TSym '*' } '/' { TSym '/' } '(' { TSym '(' } ')' { TSym ')' } %% Exp: let var '=' Exp in Exp { Let $2 $4 $6 } | Exp1 { Exp1 $1 } Exp1: Exp1 '+' Term { Plus $1 $3 } | Exp1 '-' Term { Minus $1 $3 } | Term { Term $1 } Term: Term '*' Factor { Mul $1 $3 } | Term '/' Factor { Div $1 $3 } | Factor { Factor $1 } Factor: num { Num $1 } | var { Var $1 } | '(' Exp ')' { Brack $2 } { parseError :: [Token] -> a parseError _ = error "Parse error" data Exp = Let String Exp Exp | Exp1 Exp1 deriving (Show) data Exp1 = Plus Exp1 Term | Minus Exp1 Term | Term Term deriving (Show) data Term = Mul Term Factor | Div Term Factor | Factor Factor deriving (Show) data Factor = Num Int | Var String | Brack Exp deriving (Show) }
さらに悪い。
ここでも、Haskellコードは中括弧で囲まれているため、まずSyntモジュールを宣言し、次にLexをインポートします（そこからTokenタイプが必要です）。 「％name synt」は、パーサー関数が「％tokentype {Token}」と呼ばれる構文であることを意味します-トークンのタイプ
は推測されないので 、タイプTokenを使用します。「％error {parseError}」は、エラーを処理します。
次に、エイリアスに一致するトークンが来ます。 しかし、今は怖いでしょう。 式（Exp）は、式または副式（Exp1）の変数=式とします。 最初のケースでは、Let構造を作成する必要があり（そのタイプはExpで、以下の宣言を参照）、2番目、4番目、6番目の単語（つまり、var、Exp、Exp）を引数として使用し、2番目の場合、Exp1構造を作成します最初の単語を引数として使用します。 Exp1は、1番目と3番目の単語を引数またはTermとして使用する加算または減算演算です。 用語の構造は似ていますが、加算と乗算の演算に使用されます。 読者は「なぜ2つのタイプに分かれるのか、Exp1で乗算と除算を詰め込むのは本当に不可能なのか？」と尋ねます。実際、パーサーの仕事はいわゆる「構文解析ツリー」を構築することです。 最も深くネストされた操作が最初に実行されます。 項はExp1よりも深くなります。つまり、乗算の演算は加算よりも早く実行されます。 ファクターは、数字、変数、または角括弧で囲まれた式になります。これもアクションの順序です。 次に、エラーやExpやFactorなどのすべてのデータ型を「処理」するparseError関数を宣言します。
すべて、パーサーの準備ができました！
$ happy Synt.yこれでSynt.hsファイルができました
最後のブレークスルー：通訳
インタープリターコードは次のとおりです。
module Main where import qualified Data.Map as M import Lex import Synt newtype Context = Context {getContext :: M.Map String Int} deriving (Show) pull :: Maybe a -> a pull (Just m) = m pull Nothing = error "Undefined variable" createContext :: Context createContext = Context {getContext = M.empty} getValue :: Context -> String -> Maybe Int getValue ctx name = M.lookup name $ getContext ctx solveExp :: Context -> Exp -> Maybe Int solveExp ctx exp = case exp of (Let name expl rexp) -> solveExp newCtx rexp where newCtx = Context {getContext = M.insert name (pull (solveExp ctx expl)) (getContext ctx)} (Exp1 exp1) -> solveExp1 ctx exp1 solveExp1 :: Context -> Exp1 -> Maybe Int solveExp1 ctx exp1 = case exp1 of (Plus lexp1 rterm) -> (+) <$> (solveExp1 ctx lexp1) <*> (solveTerm ctx rterm) (Minus lexp1 rterm) -> (-) <$> (solveExp1 ctx lexp1) <*> (solveTerm ctx rterm) (Term term) -> solveTerm ctx term solveTerm :: Context -> Term -> Maybe Int solveTerm ctx term = case term of (Mul lterm rfactor) -> (*) <$> (solveTerm ctx lterm) <*> (solveFactor ctx rfactor) (Div lterm rfactor) -> (div) <$> (solveTerm ctx lterm) <*> (solveFactor ctx rfactor) (Factor factor) -> solveFactor ctx factor solveFactor :: Context -> Factor -> Maybe Int solveFactor ctx factor = case factor of (Num n) -> (Just n) (Var s) -> getValue ctx s (Brack exp) -> solveExp ctx exp main = do s <- getContents mapM putStrLn $ (map (show . pull . (solveExp createContext) . synt . alexScanTokens) . lines) s
ここでは、変数名とその値を持つ連想配列（Map）を含むContext型を宣言します。変数の値があれば、それ以外の場合はエラーを返すプル関数を宣言します。 createContext関数は単に空のコンテキストを作成し、getValueはコンテキスト内の変数の値を探します。 楽しい部分になりました！ ここで何が起こっているのかを理解するために、コードの行が次のようになっていると想像してください。
8解析ツリーは次のようになります。
let res = Exp (Exp1 (Term (Num 8)))結果（つまり8）は後になります
((solveFactor ctx) <- (solveTerm ctx) <- (solveExp1 ctx) <- (solveExp ctx)) resこれはHaskellコードではなく、ダイアグラム：solveExpはres solveExp1などを渡します。
ここでのctxは単なるコンテキストです。
つまり、solveExp関数の機能は、変数をコンテキストに追加し、let-in関数の入力に行く場合は、後でExpを計算することです。そうでない場合は、単にExp1を計算します。
関数solveExp1は、加算または減算、solveTerm-乗算および除算を行います。 solveFactorは変数の値を取り出し、数値を返します。括弧内のExpに移動すると、solveExpを渡します
（再度ではなく、再度） 。
メイン関数は、stdin文字列をEOFに取り込み、それらを文字列のリストに分割し、各トークンを選択し（alexScanTokens）、パーサーを実行し（synt）、空のコンテキストで式の値を計算し（solveExp）、Maybe Int Intを作成します。その後、文字列、その後に結果を表示します。
それだけです！ 確かに！ すべてをコンパイルし、インタープリターの準備ができました！ コメント、コメント、提案-コメントしてください。