Parsec 練習問題

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

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

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

tinyCStyleとlexerは、 C言語のトークンの定義（実際にはJava言語のものを流用）に合わせて、後述の whiteSpace〜reservedOpを用意するための補助的定義である。

whiteSpace〜reservedOpは、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 "-"  ← 構文エラーがある場合は、エラーメッセージを返す。

個々のパーサ関数の意味と使用例は以下の通りである。

whiteSpace … 空白の0個以上の並びをパースする。

Parser> runLex whiteSpace ""
()
Parser> runLex whiteSpace "   "
()
Parser> runLex whiteSpace " x  "
parse error at (line 1, column 2):
unexpected "x"
expecting end of input

lexeme … (lexeme p)は (do { x <- p; whiteSpace; return x })と同等である。つまり、pを使ってパースし、続けて直後の空白の（0個以上の）並びを読み飛ばす。

symbol … (symbol s)は文字列 sをパースし、直後の空白の並びを読み飛ばす。

Parser> runLex (symbol "+") "+" 
"+"
Parser> runLex (symbol "+") "*" 
parse error at (line 1, column 1):
unexpected "*"
expecting "+"

natural … 自然数のリテラルをパースする。直後の空白の並びを読み飛ばす。

Parser> runLex natural "112"
112
Parser> runLex natural "-112"
parse error at (line 1, column 1):
unexpected "-"
expecting natural
Parser> runLex natural "x1"
parse error at (line 1, column 1):
unexpected "x"
expecting natural

identifier … 識別子をパースし、直後の空白の並びを読み飛ばす。予約語（tinyCStyleの場合、 "if", "else", "while", "return", "int", "void"の6つ）に対しては失敗する。内部でtryを使っているので、失敗した時は入力を消費しない。
```
Parser> runLex identifier "x1"
"x1"
Parser> runLex identifier "1"
parse error at (line 1, column 1):
unexpected "1"
expecting identifier
Parser> runLex identifier "while"
parse error at (line 1, column 1):
unexpected reserved word "while"
expecting letter or digit
```

reserved … (reserved name)は (symbol name) のように振舞うが、nameが識別子の一部でないか、チェックも行なう。内部でtryを使っているので、失敗した時は入力を消費しない。

Parser> runLex (do { reserved "int"; identifier }) "int x"
"x"
Parser> runLex (do { reserved "int"; identifier }) "intx"
parse error at (line 1, column 1):
unexpected "x"
expecting end of "int"
Parser> runLex (do { symbol "int"; identifier }) "intx"
"x"

operator … operatorは演算子をパースし、直後の空白の並びを読み飛ばす。 tinyCStyleの場合、演算子とは “:!#$%&*+./<=>?@\^|-~” の中の記号の1つ以上の並びである。予約語に対しては失敗する。（ただし、tinyCStyleの場合、演算子の予約語はない。）内部でtryを使っているので、失敗した時は入力を消費しない。
```
Parser> runLex operator "->"
"->"
Parser> runLex operator "&&"
"&&"
```

reservedOp …(reservedOp name)は (symbol name) のように振舞うが、nameが演算子の一部でないか、チェックも行なう。内部でtryを使っているので、失敗した時は入力を消費しない。

Parser> runLex (do { identifier; reservedOp "++"; operator }) "x++ +"
"+"
Parser> runLex (do { identifier; reservedOp "++"; operator }) "x+++"
parse error at (line 1, column 2):
unexpected "+"
expecting letter or digit or end of "++"

parens … (parens p)は、 (do { symbol "("; x <- p; symbol ")"; return x })と同等である。

Parser> runLex (parens natural) "(123)" 
123
Parser> runLex (parens natural) "(123" 
parse error at (line 1, column 5):
unexpected end of input
expecting digit or ")"
Parser> runLex (parens natural) "123" 
parse error at (line 1, column 1):
unexpected "1"
expecting "("

braces … (braces p)は、 (do { symbol "{"; x <- p; symbol "}"; return x })と同等である。
squares … (squares p)は、 (do { symbol "["; x <- p; symbol "]"; return x })と同等である。
semi … semiは (symbol ";")と同等である。
comma … commaは (symbol ",")と同等である。

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

例

例として次のようなBNF

S	→	“`(`” L “`)`”
	\|	Id
L	→	S 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〜関数の意味は以下の通りである。

parseTypeName … intまたはvoidをパースする。

Parser> runLex parseTypeName "void "
"void"
Parser> runLex parseTypeName "int "
"int"
Parser> runLex parseTypeName "foo"
parse error at (line 1, column 1):
unexpected "f"
expecting "int" or "void"

parseSignPart … 符合部をパースする。

Parser> runLex (do { s <- parseSignPart
                   ; n <- parseIntConstant
                   ; return (s, n) 
                   }) "-123"
("-",123)
Parser> runLex (do { s <- parseSignPart
                   ; n <- parseIntConstant
                   ; return (s, n) 
                   }) "+456"
("+",456)
Parser> runLex (do { s <- parseSignPart
                   ; n <- parseIntConstant
                   ; return (s, n) 
                   }) "789"
("+",789)

parseMultDiv … *または/演算子をパースする。

Parser> runLex (do { n1 <- parseIntConstant
                   ; op <- parseMultDiv
                   ; n2 <- parseIntConstant
                   ; return (n1, op,  n2)
                   }) "1*2"
(1,"*",2)
Parser> runLex (do { n1 <- parseIntConstant
                   ; op <- parseMultDiv
                   ; n2 <- parseIntConstant
                   ; return (n1, op,  n2)
                   }) "1+2"
parse error at (line 1, column 2):
unexpected "+"
expecting digit, "*" or "/"

参考

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 そのもの）、　
　　　εは空記号。
本例での用法：　英大文字で始まる語は非終端記号（構文要素名）。

ヒント

BNF中の各非終端記号に対して parseSomethingという名前の関数を定義する。 BNF中の灰色の部分は既に定義済みである。
一度に定義するのは大変なので、まず Expression〜ConditionExpn までのパーサを定義する。（それも大変なら、Factor, Variable の定義を一時的に次のように変更し、
```
Factor       → IntConstant | Variable 
Variable     → Id
```
Variable, Factor, TermTail, Term, ExpTail, Expression, SubscriptPartの順に定義し、ここで、Factor, Variableの定義を元に戻す。）次に ExpListTail, ExpressionList, Block〜ElsePartの順に定義し、最後に全体のパーサを定義する。

構文解析の結果を格納するためにデータ型を適宜定義する必要がある。（構文が正しいかどうかだけ判定するパーサの場合には必要ない。）必要な情報を保持できれば、どのようなデータ型でも良いが、例えば、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

同様にしてStatementやProgramも対応するデータ型を適宜定義する。