Parsec 練習問題

以下のプログラムTiny C のパーサをParsec ライブラリを使って書きかけたものである。

Tiny Cの構文を適切な代数的データ型として定義し、Tiny Cのパーサーを完成させよ。 (Tiny CのBNFはこのページの最後に示す。)

補足: パーサプリミティブの説明

tinyCStylelexerは、 C言語のトークンの定義(実際にはJava言語のものを流用)に合わせて、後述の whiteSpacereservedOpを用意するための補助的定義である。

whiteSpacereservedOpは、C言語のトークンをパースするための パーサ関数である。また、runLexはパーサをテストするための関数である。

これらは組み合わせて、例えば次のように使用する。

Parser> runLex (do {parseId; parseAddSub; parseId; return ()}) "x+y"
()  ← エラーがない場合は、パーサを実行した結果をそのまま返す。
Parser> runLex (do {parseId; parseAddSub; parseId; return ()}) "x*y"
parse error at (line 1, column 2):
unexpected "*"
expecting letter or digit, "+" or "-"  ← 構文エラーがある場合は、エラーメッセージを返す。
個々のパーサ関数の意味と使用例は以下の通りである。

詳しくは、Parsecのドキュメント内の The members of TokenParserを参照すること。

例として次のようなBNF

 S (L)
 |Id
 LS L'
 L',S L'
 |ε
に対するパーサを定義する。

data S = List [S] | Id String  -- Sに対応するデータ型
         deriving Show

parseS  = (do { l <- parens parseL; return (List l) })
          <|> (do { x <- identifier; return (Id x) })
parseL  = do { s <- parseS; l' <- parseL'; return (s:l') }
parseL' = (do { comma; s <- parseS; l' <- parseL'; return (s:l') }) 
          <|>  return []
実行結果は以下のようになる。
Parser> runLex parseS "(x, y, z)"
List [Id "x",Id "y",Id "z"]
Parser> runLex parseS "(x, (y, z), (w))"
List [Id "x",List [Id "y",Id "z"],List [Id "w"]]

蛇足

上記のプリミティブパーサ関数を使用した Tiny C用のパーサの書きかけの parse〜関数の意味は以下の通りである。

参考

Tiny CのBNFを示す。(上記 Tiny Cコンパイラ解説から引用)

Program      →  ExternalDeclaration | ExternalDeclaration Program
ExternalDeclaration → FunctionDef | FunctionDecl | VariableDecl
FunctionDef         → FunctionDeclarator Block
FunctionDecl        → FunctionDeclarator ";"
FunctionDeclarator  → TypeName FuncName "(" ParamList ")"

ParamList    → TypeName NameSpec ParamListTail | ε
ParamListTail→ "," TypeName NameSpec ParamListTail | ε

VariableDecl → TypeName NameSpec NameListTail ";"
NameListTail → "," NameSpec NameListTail | ε
NameSpec     → Id | Id "[" IntConstant "]"

Block        → "{" StatementSeq "}"
StatementSeq → Statement | Statement StatementSeq | ε
Statement    →
    Variable "=" Expression ";"
  | "if" "(" ConditionExp ")" Statement ElsePart
  | "while" "(" ConditionExp ")" Statement
  | FuncName "(" ExpressionList ")" ";"
  | Block   | "return" ";"
ElsePart     → "else" Statement | ε

ExpressionList → Expression ExpListTail | ε
ExpListTail  → "," Expression ExpListTail | ε

Expression   → SignPart Term ExpTail
ExpTail      → AddSub Term ExpTail | ε
Term         → Factor TermTail
TermTail     → MultDiv Factor TermTail | ε
Factor       → IntConstant | Variable | "(" Expression ")"
Variable     → Id SubscriptPart
SubscriptPart→ "[" Expression "]" | ε
ConditionExp → Expression CompOperator Expression

CompOperator → "==" | "!=" | ">" | ">=" | "<=" | "<"
AddSub       → "+" | "-"
MultDiv      → "*" | "/"
SignPart     → "+" | "-" | ε
FuncName     → Id
TypeName     → "int" | "void"
Id           → Alpha IdTail
IntConstant  → Digit ConstTail
IdTail       → Alpha IdTail | Digit IdTail | ε
Alpha →  "a"|"b"|"c"|"d"|"e"|"f"|"g"|"h"|"i"|"j"|"k"|"l"|"m"|
          "n"|"o"|"p"|"q"|"r"|"s"|"t"|"u"|"v"|"w"|"x"|"y"|"z"|
          "A"|"B"|"C"|"D"|"E"|"F"|"G"|"H"|"I"|"J"|"K"|"L"|"M"|
          "N"|"O"|"P"|"Q"|"R"|"S"|"T"|"U"|"V"|"W"|"X"|"Y"|"Z"
Digit →  "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"
ConstTail    →  Digit ConstTail | ε

記法: α→β	: 記号列βにαという名前を付ける(αはβで置き換えられる)。
(BNF)  b     : 記号列 a の後ろに記号列 b を置いた記号列
   a | b  : 記号列 a または記号列 b
       "〜" で囲まれた記号は終端記号("xx"は xx そのもの)、 
   εは空記号。
本例での用法: 英大文字で始まる語は非終端記号(構文要素名)。

ヒント

  1. BNF中の各非終端記号に対して parseSomethingという名前の関数を定義する。 BNF中の灰色の部分は既に定義済みである。
  2. 一度に定義するのは大変なので、まず ExpressionConditionExpn までのパーサを定義する。(それも大変なら、Factor, Variable の定義を一時的に次のように変更し、
    Factor       → IntConstant | Variable 
    Variable     → Id
    
    Variable, Factor, TermTail, Term, ExpTail, Expression, SubscriptPartの順に定義し、 ここで、Factor, Variableの定義を元に戻す。) 次に ExpListTail, ExpressionList, BlockElsePartの順に定義し、最後に全体のパーサを定義する。
  3. 構文解析の結果を格納するためにデータ型を適宜定義する必要がある。 (構文が正しいかどうかだけ判定するパーサの場合には必要ない。) 必要な情報を保持できれば、どのようなデータ型でも良いが、 例えば、Expressionの場合、次のような定義をすれば良い。
    type Expression    = (SignPart, Term, ExpTail)
    type ExpTail  	   = [(AddSub, Term)]
    type Term     	   = (Factor, TermTail)
    type TermTail 	   = [(MultDiv, Factor)]
    data Factor   	   = MkIntConst Integer | MkVar Variable | MkExpr Expression
                  	     deriving Show
    type Variable 	   = (Id, SubscriptPart)
    type SubscriptPart = Maybe Expression
    type ConditionExp  = (Expression, CompOperator, Expression) 
    type CompOperator  = String
    
    type AddSub   = String
    type MultDiv  = String
    type SignPart = String
    type Id       = String 
    
    同様にしてStatementProgramも対応するデータ型を 適宜定義する。