SiroKuroの作ったPEGライクのHaskell文法

出典: どう書くwiki

Haskell Hackathon 2008

なるべく曖昧さが無くなるように整形してみました。

Module
    : "module" modid [ Exports ] "where" Body
    | Body
    ;
Body
    : "{" ImplementDecls ";" TopDecls "}"
    | "{" ImplementDecls "}"
    | "{" TopDecls "}"
    ;
ImplementDecls
    : ImplementDecl (";" ImplementDecl)*
    ;
Exports
    : "(" [ Export ("," Export)* [ "," ] ] ")"
    ;
Export
    : QualifiedVariable
    | qtycon [ "(" ".." ")" | "(" [ CName ("," CName)* ] ")" ]
    | qtycls [ "(" ".." ")" | "(" [ QualifiedVariable ("," QualifiedVariable)* ] ")" ]
    | "module" modid
    ;
ImplementDecl
    : "import" [ qualified ] modid [ "as" modid ] [ ImplementSpec ]
    |
    ;
ImplementSpec
    : "(" [ Import ("," Import)* [ "," ] ] ")"
    | "hiding" "(" [ Import ("," Import)* [ "," ] ] ")"
    ;
Import
    : Variable
    | tycon [ "(" ".." ")" | "("[ CName ("," CName)* ] ")" ]
    | tycls [ "(" ".." ")" | "(" [ Variable ("," Variable)* ] ")" ]
    ;
CName
    : Variable | Constructor
    ;
TopDecls
    : [ TopDecl (";" TopDecl)* ]
    ;
TopDecl
    : "type" SimpleType "=" Type
    | "data" [ Context "=>" ] SimpleType "=" Constructors [ Deriving ]
    | "newtype" [ Context "=>" ] SimpleType "=" NewConstructor [ Deriving ]
    | "class" [ SimpleContext "=>" ] tycls tyvar [ "where" CDecls ]
    | "instance" [ SimpleContext "=>" ] qtycls Instance [ "where" IDecls ]
    | "default" "(" [ Type ("," Type)* ] ")"
    | Decl
    ;
Decls
    : "{" [ Decl (";" Decl)* "}"
    ;
Decl
    : GenDecl
    | (FunctionLHS | Pattern0) RHS
    ;
CDecls
    : "{" [ CDecl (";" CDecl)* ] "}"
    ;
CDecl
    : GenDecl
    | (FunctionLHS | Variable) RHS
    ;
IDecls
    : "{" [ IDecl (";" IDecl)* "}"
    ;
IDecl
    : (FunctionLHS | Variable) RHS
    |
    ;
GenDecl
    : Variables "::" [ Context "=>" ] Type
    | Fixity [ integer ] Operators
    |
    ;
Operators
    : Operator ("," Operator)*
    ;
Variables
    : Variable ("," Variable)*
    ;
Fixity
    : "infixl" | "infixr" | "infix"
    ;
Type
    : BType [ "->" Type ]
    ;
BType
    : [ BType ] AType
    ;
AType
    : GtyCon
    | tyvar
    | "(" Type "," Type ("," Type)* ")"
    | "[" Type "]"
    | "(" Type ")"
    ;
GtyCon
    : qtycon
    | "(" ")"
    | "[" "]"
    | "(" "->" ")"
    | "(" (",")+ ")"
    ;
Context
    : Class
    | "(" [ Class ("," Class)* ] ")"
    ;
Class
    : qtycls tyvar
    | qtycls "(" tyvar (AType)+ ")"
    ;
SimpleContext
    : SimpleClass
    | "(" [ SimpleClass ("," SimpleClass)* ] ")"
    ;
SimpleClass
    : qtycls tyvar
    ;
SimpleType
    : tycon (tyvar)*
    ;
Constructors
    : Constructor ("|" Constructor)*
    ;
Constructor
    : Constructor ([ "!" ] AType)*
    | (BType | "!" AType) ConstructorOperator (BType | "!" AType)
    | Constructor "{" [ FieldDecl ("," FieldDecl)* ] "}"
    ;
NewConstructor
    : Constructor AType
    | Constructor "{" var "::" Type "}"
    ;
FieldDecl
    : Variables "::"
    ;
Deriving
    : Deriving (DerivingClass | "(" [ DerivingClass ("," DerivingClass)* ")")
    ;
DerivingClass
    : qtycls
    ;
Instance
    : GtyCon
    | "(" GtyCon (tyvar)* ")"
    | "(" tyvar "," tyvar ("," tyvar)* ")"
    | "[" tyvar "]"
    | "(" tyvar "->" tyvar ")"
    ;
FunctionLHS
    : Variable AtomPattern {AtomPattern}
    | Pattern(i+1) VariableOperator(A,i) Pattern(i+1)
    | LeftPattern(i) VariableOperator(L,i) pat(i+1)
    | Pattern(i+1) VariableOperator(R,i) RightPattern(i)
    | "(" FunctionLHS ")" AtomPattern {AtomPattern}
    ;
RHS
    : "=" Expression [ "where" Decls ]
    | GuardRHS [ "where" Decls ]
    ;
GuardRHS
    : Guard "=" Expression [ GuardRHS ]
    ;
Guard
    : "|" Expression(0)
    ;
Expression
    : Expression(0) "::" [ Context "=>" ] Type
    | Expression(0)
    ;
Expression(i)
    : Expression(i+1) [ QualifiedOperator(N,i) Expression(i+1) ]
    | LeftExpression(i)
    | RightExpression(i)
    ;
LeftExpression(i)
    : (LeftExpression(i) | LeftExpression(i+1)) QualifiedOperator(L,i) LeftExpression(i+1)
    ;
LeftExpression(6)
    : "-" LeftExpression(7)
    ;
RightExpression(i)
    : Expression(i+1) QualifiedOperator(R,i)
    ;
Expression(10)
    : "\" (AtomPattern)+ "->" Expression
    | "let" Decls "in" Expression
    | "if" Expression "then" Expression "else" Expression
    | "case" Expression "of" "{" Alts "}"
    | "do" "{" Statements "}"
    | FuncApplyExpression
    ;
FuncApplyExpression
    : [ FuncApplyExpression ] AtomExpression
    ;
AtomExpression
    : QualifiedVariable
    | GConst
    | literal
    | "(" Expression ")"
    | "(" Expression ("," Expression)+ ")"
    | "[" Expression ("," Expression)* "]"
    | "[" Expression [ "," Expression ] ".." [ Expression ] "]"
    | "[" Expression | Qual ("," Qual)+ "]"
    | "(" Expression(i+1) QualifiedOperator(A,i) ")"
    | "(" LeftExpression(i) QualifiedOperator(L,i) ")"
    | "(" QualifiedOperator(A,i) "<->" Expression(i+1) ")"
    | "(" QualifiedOperator(R,i) "<->" RightExpression(i) ")"
    | QualifiedConstructor "{" [ FBind ("," FBind)* ] "}"
    | AtomExpression<QualifiedConstructor> "{" FBind ("," FBind)* "}"
    ;
Qual
    : Pattern "<-" Expression
    | "let" Decls
    | Expression
    ;
Alts
    : Alt (";" Alt)*
    ;
Alt
    : Pattern "->" Expression [ "where" Decls ]
    | Pattern GuardPat [ "where" Decls ]
    |
    ;
GuardPat
    : Guard "->" Expression [ GuardPat ]
    ;
Statements
    : (Statement)* Expression [ ";" ]
    ;
Statement
    : Expression ";"
    | Pattern "<-" Expression ";"
    | "let" Decls ";"
    | ";"
    ;
FBind
    : QualifiedVariable "=" Expression
    ;
Pattern
    : Variable "+" integer
    | Pattern(0)
    ;
Pattern(i)
    : Pattern(i+1) [ QualifiedConstructorOperator(N,i) Pattern(i+1) ]
    | LeftPattern(i)
    | RightPattern(i)
    ;
LeftPattern(i)
    : (LeftPattern(i) | Pattern(i+1)) QualifiedConstructorOperator(L,i) Pattern(i+1)
    ;
LeftPattern(6)
    : "-" (integer | float)
    ;
RightPattern(i)
    : Pattern(i+1) QualifiedConstructorOperator(R,i)
    ;
Pattern(10)
    : AtomPattern
    | GConst (AtomPattern)+
    ;
AtomPattern : Variable [ "@" AtomPattern ]
     | GConst
     | QualifiedConstructor "{" [ FieldPattern ("," FieldPattern)* ] "}"
     | literal
     | "_"
     | "(" Pattern ")"
     | "(" Pattern ("," Pattern)+ ")"
     | "[" Pattern ("," Pattern)* "]"
     | "~" AtomPattern
    ;
FieldPattern
    : QualifiedVariable "=" Pattern
    ;
GConst
    : "(" ")"
    | "[" "]"
    | "(" (",")+ ")"
    | QualifiedConstructor
    ;
Variable : varid | "(" varsym ")"
    ;
QualifiedVariable
    : qvarid | "(" qvarsym ")"
    ;
Constructor
    : conid | "(" consym ")"
    ;
QualifiedConstructor
    : qconid | "(" GuardConstructorSynonym ")"
    ;
VariableOperator
    : varsym
    | "`" varid "`"
    ;
QualifiedVariableOperator
    : qvarsym
    | "`" qvarid "`"
    ;
ConstructorOperator
    : consym
    | "`" conid "`"
    ;
QualifiedConstructorOperator
    : GuardConstructorSynonym
    | "`" qconid "`"
    ;
Operator
    : varop
    | ConstructorOperator
    ;
QualifiedOperator
    : QualifiedVariableOperator
    | QualifiedConstructorOperator
    ;
GuardConstructorSynonym
    : ":"
    | qconsym
    ;