4

このコードをここで入手しました。これはHaskellで構造化された命令型プログラミング言語で記述されたプログラムなので、問題は「この言語のレクサーアナライザーとパーサーを実装するにはどうすればよいですか」ということです。プログラムは次のシーケンスとして定義されます。ステートメントには、「：=」、「goto」、「write」、「stop」、「if goto」、「int」の6つのタイプがあります。

  1. int n = 5
  2. nを書く
  3. int fac = 1
  4. if0 n goto 8
  5. fac：= fac * n
  6. n：= n-1
  7. 後藤4
  8. 書き込みfac
  9. 止まる

私はここでちょっと迷っています。レクサーとパーサーについて読んだことがありますが、それらを実装する方法の例は見つかりませんでした。自分で試してみることができるように、コードを教えていただければ幸いです。少なくとも有用な情報とのリンク

4

1 に答える 1

24

はじめにParsecを使用した解析

全部を書くわけではありませんが、各ビットから始めましょう。実行する3つの段階は次のとおりです。

  1. 文法を定義する
  2. 抽象構文木を作成します。（これは文法のように見えるので、非常に簡単です。）
  3. パーサーを作成します。（これも文法のように見えるので、とても簡単です。）

2と3の間に別の字句解析ステージを作成することもできますが、Parsecは両方のレベルを実行できます。字句解析では、入力をトークン（意味のある入力のビット）に分割します。これは、語彙素とも呼ばれる人間の言語の単語に相当します。別の字句解析フェーズをスキップするということは、空白などについてもう少し明確にする必要があることを意味します。

1.文法

まず、文法を定義する必要があります。紙と鉛筆で行うのが最適ですが、始めましょう。

  program ::= line {[newline line]}
  line ::= num dot whitespace statement
  statement ::= declaration | write | ifstatement | goto | assignment | stop
  declaration = "Int" whitespace varname equals int
  varname = letter {[alphanum]}
  -- more things here, including the more interesting ifstatement:
  ifstatement = "if" whitespace expression whitespace equals expression whitespace statement


  -- lower level stuff:
  dot = "."
  int = digit {[digit]}
  digit = "0" | "1" | ...  | "9"
  whitespace = " " okspace | "\t" okspace
  okspace = "" | whitespace

それがサンプルプログラムとどのように一致するかを考え、それをどのように終了するかを考えてください。

1. Int n=5
2. write n
3. Int fac=1
4. if 0 n goto 8          -- unusual
5. fac := fac * n
6. n := n+1               -- complex
7. goto 4
8. write fac
9. stop

=4行目のifステートメントは、またはが含まれていないため、異常です==。おそらくそれは文法を単純化するためであり、間にスペースを入れた単一の変数または整数のみを受け入れることができます。おそらくそれはタイプミスであり、等号と任意の式を使用することを意味します。どれを見つけてifstatement、文法の一部を書き直してください。

6行目の割り当ては複雑です。これは、ここでは任意の算術式を解析する必要があるためです。私が覚えている限り、そのノックの例はたくさんあるので、今はそれを喜んでスキップします。あなたがそのビットで立ち往生しているなら、それを別の質問にしてください、しかしうまくいけば、あなたは最初にそれの残りであなたの構文解析スキルを構築したでしょう。

2.抽象構文木（AST）

抽象構文木は、入力を構成するトークンの組み合わせを表します。Haskellでは、コンテキストに合わせて独自の定義を行うことができます。これにより、生活がはるかに簡単になります。

私は実際にこの答えをコンパイルしています（タイプミスなどをチェックする良い方法です）。そのため、コードの先頭にいくつかの宣言が必要です。

module ParseLang where

import Text.Parsec hiding (Line)
import Text.Parsec.String
import Control.Applicative hiding ((<|>), many)

Programのリストを作成するだけLineですが、パーサーを使用して、少なくとも1つは存在する必要があることを強制します。

type Program = [Line]

の場合Line、数値とステートメントが必要ですが、ドットは格納する必要のない構文にすぎません。行番号をとして格納できるIntため、型宣言で負の数を使用できますが、パーサーは負の数を受け入れません。

data Line = Line {aNum::Int, aStatement :: Statement} 
   deriving Show

複数のオプションを簡単に定義できます。

data Statement = Declaration VarName Int
               | Write VarName
               | IfStatement Expression Expression Statement
               | Goto LineNumber
               | Assignment VarName Expression
               | Stop
   deriving Show

すべての構文のくだらない/接続詞/等号がなく、変更されたビットだけが残っていることに注意してください。

私はそこで止まります-あなたは終えることができます：

data Expression = Expression -- I've left this one for you
   deriving Show

type VarName = String   -- could use newtype for type safety for these to
type LineNumber = Int

下位レベルの構文は、文字列を使用するため、ASTで表す必要はありません。

3.パーサー

このビットは今では素晴らしくて簡単です。構文ツリーの一番下から始めて、作業を進めていきましょう。

num :: Parser Int
num = read <$> many digit

をインポートして得たものの<$>同義語であるを使用しました。ここでは、左側の純粋関数（この場合は）を使用して、パーサーによって返される値を変更します。あなたがそれに慣れていない場合の紹介については、この他の答えを見てください。fmapControl.Applicativereadfmap

文字列リテラルを解析してから空白を解析するパーサーを作成しましょう。

whitespace = space >> spaces  -- a space then optional spaces

lit :: String -> Parser String
lit xs = string xs <* whitespace

さて、それ<*は興味深いです。<*>これは、実際には2つのパーサーを組み合わせたもののように見え、実際<$>には純粋関数を結果にマップするために使用されます。*>2つのパーサーを<*結合しますが、そのうちの1つの出力を無視するためstring "goto" <* whitespace、aと一部の空白を解析し"goto"ますが、空白を破棄します。

これで、gotoステートメントを解析する準備が整いました。

goto :: Parser Statement
goto = Goto <$> (lit "goto" *> num)

それでは、varNameを試してみましょう

varName :: Parser VarName
varName = (:) <$> letter <*> many (alphaNum <|> oneOf "'_")

そこではいくつかのことが起こっています。

1. <|>代替の選択肢です-どちらか一方なので(alphaNum <|> oneOf "'_")、英数字またはその無実の文字のペアの1つを受け入れ、'変数_名に含めることができます。

2. f <$> parser1 <*> parser2パーサーを組み合わせるのに本当に良い方法です。それはparser1、次にparser2を実行し、次にfそれらが生成した結果fに関数をマップします。多くのパーサーで機能します。

--ifstatement = "if" whitespace expression whitespace equals whitespace expression whitespace statement
ifStatement :: Parser Statement
ifstatement = IfStatement 
          <$> (lit "if" >> expression) 
          <*> (lit "=" >> expression)    -- I put = in, but see below
          <*> (whitespace >> statement)  -- I'd be happier with a then in here

一般的なの代わりにVarNameまたはのみを許可する場合は、等号は必要ありません。IntExpression

まとめる方法は次のとおりです。

statement :: Parser Statement
statement = goto
        <|> stop
        <|> declaration 
        <|> write
        <|> ifStatement
        <|> assignment


--program ::= line {[newline line]}
program :: Parser Program
program = many1 line


--line ::= num dot whitespace statement
line :: Parser Line
line = Line <$> (num <* char '.') <*> (statement <* char '\n')

ただし、まだ終了していないパーサーを使用しようとするたびにエラーメッセージが表示されるので、すべてが正常にコンパイルされ、定義したビットが機能するはずです。

stop =        error "You've not yet defined stop"
declaration = error "You've not yet defined declaration"
write =       error "You've not yet defined write"
ifStatement = error "You've not yet defined ifStatement"
assignment =  error "You've not yet defined assignment"
expression =  error "You've not yet defined expression"
于 2012-12-05T03:55:27.423 に答える