챕터 10 — 구문 참조

챕터 10 — 구문 참조 (Syntax Reference)

Haskell 2010 언어 리포트의 마지막 본문 챕터예요. 지금까지 본문 곳곳에서 "정의는 10장을 참고하세요"라는 식의 언급을 많이 봤을 텐데, 바로 그 역할을 하는 곳이 이 챕터입니다. 어휘 구문(lexical syntax)과 문맥 자유 구문(context-free syntax), 레이아웃(layout) 규칙, 리터럴 주석(literate comments), 그리고 연산자 fixity 해석까지 — Haskell 프로그램의 구문을 결정짓는 모든 정의가 한데 모여 있어요. 보고서 전체에서 사실상의 "공식 문법 참조" 역할을 한다고 보면 됩니다.

출처: https://www.haskell.org/onlinereport/haskell2010/haskellch10.html

본문

이 챕터는 Haskell 구문의 공식 정의를 담고 있어요. 어떤 구문이 유효한지 컴파일러와 정확히 같은 기준으로 판정해야 할 때, 또는 문법 규칙 하나하나를 뜯어 보고 싶을 때 펼쳐 보는 문서라고 생각하면 돼요. 다만 보고서 전체를 처음 읽는 분이라면 이 챕터의 모든 세부 내용을 한 번에 외울 필요는 없습니다. 필요할 때 찾아 보는 참조서로 써도 충분해요.

10.1 표기 규약 (Notational Conventions)

구문을 기술할 때 쓰는 표기 규약부터 정리할게요.

표기 의미
[pattern] 선택 — 있어도 되고 없어도 돼요 (optional)
{pattern} 0회 이상 반복 (zero or more repetitions)
(pattern) 그룹 (grouping)
pat₁ | pat₂ 선택 — 둘 중 하나 (choice)
pat⟨pat′⟩ 차집합 — pat이 만들어내는 요소 중에서 pat′이 만들어내는 것을 제외한 나머지 (difference)
fibonacci 타자체(typewriter font)로 표시된 터미널 구문 (terminal syntax in typewriter font)

전반적으로 BNF스러운 문법을 쓰는데, 생산 규칙(production)의 형태는 이렇게 생겼어요.

nonterm  →  alt1 | alt2 | … | altn

어휘 구문과 문맥 자유 구문 양쪽 모두, 몇몇 모호함(ambiguity)이 있긴 한데, 이 모호함은 문법적 구(phrase)를 최대한 길게 만드는 방식으로 해소합니다. 왼쪽에서 오른쪽으로 진행하면서 말이죠. 쉽게 말해 (shift-reduce 파싱에서 shift/reduce 충돌을 shift로 해결하는 방식으로) 최대한 길게 뭉치라는 규칙이에요. 어휘 구문에서는 이걸 "맥시멈 먼치(maximal munch)" 규칙이라고 불러요. 문맥 자유 구문에서는 이 규칙 덕분에 조건문(conditional), let식, 람다 추상(lambda abstraction)이 오른쪽으로 최대한 멀리 확장됩니다.

10.2 어휘 구문 (Lexical Syntax)

이 절은 어휘 구문을 문법으로 정의해요. 여기서 등장하는 규칙들은 소스의 글자 하나하나가 어떻게 토큰이 되는지를 규정하죠. 먼저 프로그램이 쌓이는 가장 큰 단위부터 시작할게요.

program  →  { lexeme | whitespace }
lexeme  →  qvarid | qconid | qvarsym | qconsym
|  literal | special | reservedop | reservedid
literal  →  integer | float | char | string
special  →  ( | ) | , | ; | [ | ] | ` | { | }
whitespace  →  whitestuff {whitestuff}
whitestuff  →  whitechar | comment | ncomment
whitechar  →  newline | vertab | space | tab | uniWhite
newline  →  return linefeed | return | linefeed | formfeed
return  →  a carriage return
linefeed  →  a line feed
vertab  →  a vertical tab
formfeed  →  a form feed
space  →  a space
tab  →  a horizontal tab
uniWhite  →  any Unicode character defined as whitespace
comment  →  dashes [ any⟨symbol⟩ {any} ] newline
dashes  →  -- {-}
opencom  →  {-
closecom  →  -}
ncomment  →  opencom ANY seq {ncomment ANY seq} closecom
ANY seq  →  {ANY }⟨{ANY } ( opencom | closecom ) {ANY }⟩
ANY  →  graphic | whitechar
any  →  graphic | space | tab
graphic  →  small | large | symbol | digit | special | " | '
small  →  ascSmall | uniSmall | _
ascSmall  →  a | b | … | z
uniSmall  →  any Unicode lowercase letter
large  →  ascLarge | uniLarge
ascLarge  →  A | B | … | Z
uniLarge  →  any uppercase or titlecase Unicode letter
symbol  →  ascSymbol | uniSymbol⟨special | _ | " | '⟩
ascSymbol  →  ! | # | $ | % | & | ⋆ | + | . | / | < | = | > | ? | @
|  \ | ^ | | | - | ~ | :
uniSymbol  →  any Unicode symbol or punctuation
digit  →  ascDigit | uniDigit
ascDigit  →  0 | 1 | … | 9
uniDigit  →  any Unicode decimal digit
octit  →  0 | 1 | … | 7
hexit  →  digit | A | … | F | a | … | f

이제 식별자와 이름(names) 관련 규칙이에요. 어떤 이름이 변수로, 어떤 이름이 생성자로 해석되는지가 여기서 정해져요.

varid  →  (small {small | large | digit | ' })⟨reservedid⟩
conid  →  large {small | large | digit | ' }
reservedid  →  case | class | data | default | deriving | do | else
|  foreign | if | import | in | infix | infixl
|  infixr | instance | let | module | newtype | of
|  then | type | where | _
varsym  →  ( symbol⟨:⟩ {symbol} )⟨reservedop | dashes⟩
consym  →  ( : {symbol})⟨reservedop⟩
reservedop  →  .. | : | :: | = | \ | | | <- | -> | @ | ~ | =>
varid  (variables)
conid  (constructors)
tyvar  →  varid (type variables)
tycon  →  conid (type constructors)
tycls  →  conid (type classes)
modid  →  {conid .} conid (modules)
qvarid  →  [ modid . ] varid
qconid  →  [ modid . ] conid
qtycon  →  [ modid . ] tycon
qtycls  →  [ modid . ] tycls
qvarsym  →  [ modid . ] varsym
qconsym  →  [ modid . ] consym
decimal  →  digit{digit}
octal  →  octit{octit}
hexadecimal  →  hexit{hexit}
integer  →  decimal
|  0o octal | 0O octal
|  0x hexadecimal | 0X hexadecimal
float  →  decimal . decimal [exponent]
|  decimal exponent
exponent  →  (e | E) [+ | -] decimal
char  →  ' (graphic⟨' | \⟩ | space | escape⟨\&⟩) '
string  →  " {graphic⟨" | \⟩ | space | escape | gap} "
escape  →  \ ( charesc | ascii | decimal | o octal | x hexadecimal )
charesc  →  a | b | f | n | r | t | v | \ | " | ' | &
ascii  →  ^cntrl | NUL | SOH | STX | ETX | EOT | ENQ | ACK
|  BEL | BS | HT | LF | VT | FF | CR | SO | SI | DLE
|  DC1 | DC2 | DC3 | DC4 | NAK | SYN | ETB | CAN
|  EM | SUB | ESC | FS | GS | RS | US | SP | DEL
cntrl  →  ascLarge | @ | [ | \ | ] | ^ | _
gap  →  \ whitechar {whitechar} \

10.3 레이아웃 (Layout)

섹션 2.7에서 레이아웃 규칙을 비공식적으로 다룬 적이 있어요. 이 절은 그 규칙을 더 정밀하게 정의합니다.

Haskell 프로그램의 의미는 그 레이아웃에 따라 달라질 수 있어요. 레이아웃이 의미에 미치는 영향은, 레이아웃이 결정하는 위치에 중괄호와 세미콜론을 넣어 주는 것만으로 완전히 설명할 수 있습니다. 그렇게 보강된 프로그램의 의미는 이제 레이아웃에 무관해지죠.

레이아웃의 효과는, 레이아웃이 적용된 프로그램에 중괄호와 세미콜론을 어떻게 추가할지를 기술함으로써 지정돼요. 그 명세는 변환을 수행하는 함수 L의 형태로 표현됩니다. L의 입력은 다음과 같아요.

  • Haskell 리포트의 어휘 구문이 규정하는 lexeme의 스트림(stream). 여기에 다음 토큰들이 추가로 붙어요.
    • let, where, do, 또는 of 키워드 뒤에 { lexeme이 따라오지 않으면, 그 키워드 뒤에 {n} 토큰이 삽입돼요. 여기서 n은 다음 lexeme이 있을 경우 그 들여쓰기, 파일 끝에 도달했다면 0이에요.
    • 모듈의 첫 lexeme이 {나 module이 아니면, 그 lexeme 앞에 {n}이 붙어요. 여기서 n은 그 lexeme의 들여쓰기예요.
    • 어떤 lexeme의 시작이 같은 줄에서 공백(white space)만으로 앞에 놓여 있으면, 그 lexeme 앞에 < n >이 붙어요. 여기서 n은 그 lexeme의 들여쓰기이고, 단 첫 두 규칙의 결과로 이미 {n}이 앞에 붙은 경우는 제외해요. (참고: 문자열 리터럴은 여러 줄에 걸칠 수 있어요 – 섹션 2.6. 예를 들어 아래 조각에서 
      f = ("Hello \
        \Bill", "Jake")
      \Bill 앞에는 < n >이 삽입되지 않아요. 완전한 lexeme의 시작이 아니기 때문이죠. , 앞에도 삽입되지 않아요. 같은 줄에서 공백만으로 선행되지 않았기 때문이고요.)
  • 레이아웃 컨텍스트(layout context)의 스택. 각 요소는 다음 중 하나예요.
    • 0 — 둘러싼 컨텍스트가 명시적(explicit)임을 나타내요. 프로그래머가 여는 중괄호를 직접 제공했다는 뜻이죠. 가장 안쪽 컨텍스트가 0이면, 둘러싼 컨텍스트가 끝나거나 새 컨텍스트가 push될 때까지 레이아웃 토큰이 삽입되지 않아요.
    • 양의 정수 — 둘러싼 레이아웃 컨텍스트의 들여쓰기 열(column) 번호.

lexeme의 "들여쓰기"는 그 lexeme의 첫 문자가 있는 열 번호이고, 한 줄의 들여쓰기는 그 줄에서 가장 왼쪽 lexeme의 들여쓰기예요. 열 번호를 정할 때는 다음과 같은 규약을 가진 고정폭 폰트를 가정해요.

  • newline, return, linefeed, formfeed 문자는 모두 새 줄을 시작해요.
  • 첫 열은 1번 열로 지정돼요. 0번이 아니에요.
  • 탭 정지는 8문자 간격이에요.
  • 탭 문자는 현재 위치를 다음 탭 정지에 맞추는 데 충분한 공백을 삽입해요.

레이아웃 규칙을 적용할 때, 소스 프로그램의 유니코드 문자는 ASCII 문자와 같은 고정된 폭을 가진 것으로 간주해요. 다만 시각적 혼란을 피하기 위해, 프로그래머는 암묵적 레이아웃의 의미가 공백이 아닌 문자의 폭에 의존하는 프로그램을 작성하는 것을 피해야 합니다.

다음 적용

L tokens []

은 토큰의 레이아웃 비민감(layout-insensitive) 변환을 내놓아요. 여기서 tokens는 모듈을 어휘 분석하고 위에서 설명한 대로 열 번호 표시기를 붙인 결과예요. L의 정의는 다음과 같습니다. 여기서 :는 스트림 생성 연산자, []는 빈 스트림이라고 써요.

L (< n >: ts) (m : ms)  =  ; : (L ts (m : ms))  if m = n
                       =  } : (L (< n >: ts) ms)  if n < m
L (< n >: ts) ms  =  L ts ms
L ({n} : ts) (m : ms)  =  { : (L ts (n : m : ms))  if n > m (Note 1)
L ({n} : ts) []  =  { : (L ts [n])  if n > 0 (Note 1)
L ({n} : ts) ms  =  { : } : (L (< n >: ts) ms)  (Note 2)
L (} : ts) (0 : ms)  =  } : (L ts ms)  (Note 3)
L (} : ts) ms  =  parse-error  (Note 3)
L ({ : ts) ms  =  { : (L ts (0 : ms))  (Note 4)
L (t : ts) (m : ms)  =  } : (L (t : ts) ms)  if m∕ = 0 and parse-error(t)
                       (Note 5)
L (t : ts) ms  =  t : (L ts ms)
L [] []  =  []
L [] (m : ms)  =  } : L [] ms  if m≠0 (Note 6)

Note 1. 중첩 컨텍스트는 둘러싼 컨텍스트보다 더 들여쓰여야 해요 (n > m). 그렇지 않으면 L이 실패하고, 컴파일러는 레이아웃 오류를 표시해야 합니다. 예를 들어 보죠.

f x = let
        h y = let
    p z = z
              in p
     in h

여기서 p의 정의는 둘러싼 컨텍스트의 들여쓰기보다 덜 들여쓰여 있어요. 이 경우 그 들여쓰기는 h의 정의가 설정하죠.

Note 2. where(가령) 앞에 오는 첫 토큰이 둘러싼 레이아웃 컨텍스트보다 더 들여쓰여 있지 않다면, 블록은 비어 있어야 해요. 그래서 빈 중괄호가 삽입됩니다. {n} 토큰은 < n >으로 대체돼서, 빈 중괄호가 명시적이었을 상황을 흉내 냅니다.

Note 3. 현재 레이아웃 컨텍스트를 0에 대응시킴으로써, 명시적인 닫는 중괄호가 오직 명시적인 여는 중괄호에만 대응되도록 보장해요. 명시적인 닫는 중괄호가 암묵적인 여는 중괄호에 대응되면 파싱 오류가 발생합니다.

Note 4. 이 절은 모든 중괄호 쌍을 명시적 레이아웃 컨텍스트로 취급한다는 뜻이에요. 라벨 붙은 생성과 갱신(labeled construction and update, 섹션 3.15)도 포함해서요. 이것은 이 공식화와 Haskell 1.4 사이의 차이점이에요.

Note 5. 부수 조건 parse-error(t)는 이렇게 해석해요. L이 지금까지 생성한 토큰에 다음 토큰 t를 더한 것이 Haskell 문법의 유효하지 않은 접두사이고, L이 지금까지 생성한 토큰에 토큰 }를 붙인 것은 Haskell 문법의 유효한 접두사라면, parse-error(t)는 참이에요. 그리고 m∕ = 0 검사는, 암묵적으로 추가된 닫는 중괄호가 암묵적인 여는 중괄호와 대응될지를 확인하는 것이에요.

Note 6. 입력의 끝에서, 대기 중인 닫는 중괄호가 모두 삽입돼요. 이 시점에 레이아웃이 아닌 컨텍스트(즉 m = 0) 안에 있는 것은 오류예요.

위의 규칙 중 어느 것도 대응하지 않으면 알고리즘은 실패해요. 예를 들어 입력의 끝에 도달했는데 레이아웃이 아닌 컨텍스트가 활성 상태라면 닫는 중괄호가 없으므로 실패할 수 있어요. 일부 오류 조건은 알고리즘이 감지하지 못하는데, 예를 들어 let } 같은 경우 감지할 수 있음에도 못 잡는 경우가 있어요.

Note 1은 레이아웃 처리가 파싱 오류에 의해 조기에 중단될 수 있는 기능을 구현해요. 예를 들어

let x = e; y = x in e'

는 유효해요. 다음과 같이 변환되기 때문이죠.

let { x = e; y = x } in e'

닫는 중괄호는 위의 파싱 오류 규칙 때문에 삽입됩니다.

10.4 리터럴 주석 (Literate comments)

"리터럴 주석(literate comment)" 규약은 Richard Bird와 Philip Wadler가 Orwell을 위해 처음 개발했고, 다시 Donald Knuth의 "리터럴 프로그래밍(literate programming)"에서 영감을 받은 것으로, Haskell 소스 코드를 인코딩하는 대안적인 스타일이에요. 리터럴 스타일은 주석을 기본값으로 둠으로써 주석을 장려합니다. >가 첫 문자인 줄은 프로그램의 일부로 취급되고, 그 외의 모든 줄은 주석으로 취급돼요.

프로그램 텍스트는 >로 시작하는 줄만 골라내어 그 앞의 >를 공백으로 바꿈으로써 복구돼요. 결과 텍스트에 레이아웃과 주석은 10장에서 설명한 것과 정확히 동일하게 적용됩니다.

>를 실수로 빼먹는 경우를 잡기 위해, 프로그램 줄이 비어 있지 않은 주석 줄에 인접해 나타나는 것은 오류로 처리해요. 여기서 줄이 오직 공백만으로 이루어져 있으면 빈 줄로 봅니다.

관례에 따라 주석 스타일은 파일 확장자로 표시돼요. .hs는 보통의 Haskell 파일, .lhs는 리터럴 Haskell 파일을 나타내죠. 이 스타일을 쓰면 간단한 팩토리얼 프로그램은 이렇게 됩니다.

   This literate program prompts the user for a number
   and prints the factorial of that number:

> main :: IO ()
> main = do putStr "Enter a number: "
>           l <- readLine
>           putStr "n!= "
>           print (fact (read l))

  This is the factorial function.

> fact :: Integer -> Integer
> fact 0 = 1
> fact n = n ⋆ fact (n-1)

리터럴 프로그래밍의 또 다른 스타일은 LaTeX 텍스트 처리 시스템과 함께 쓰기에 특히 적합해요. 이 규약에서는 \begin{code}…\end{code} 구분 기호 사이에 온전히 들어 있는 리터럴 프로그램의 부분만 프로그램 텍스트로 취급하고, 그 외의 모든 줄은 주석으로 취급합니다. 더 정확히 말하면,

  • 프로그램 코드는 \begin{code}로 시작하는 줄 바로 다음 줄에서 시작해요.
  • 프로그램 코드는 그 뒤에 \begin{code}로 시작하는 줄이 나오기 직전에 끝나요. (물론 문자열 리터럴 안은 무시합니다.)

이 구분 기호 앞뒤에 추가 빈 줄을 넣을 필요는 없지만, 스타일상 넣는 게 좋을 수는 있어요. 예를 들어,

\documentstyle{article}

\begin{document}

\chapter{Introduction}

This is a trivial program that prints the first 20 factorials.

\begin{code}

main :: IO ()
main =  print [ (n, product [1..n]) | n <- [1..20]]

\end{code}

\end{document}

이 스타일도 같은 파일 확장자를 사용해요. 같은 파일에서 두 스타일을 섞는 것은 권장되지 않습니다.

10.5 문맥 자유 구문 (Context-Free Syntax)

이 절은 문맥 자유 구문을 문법으로 정의해요. 모듈 선언, 타입, 식, 패턴 등 프로그램을 이루는 구조적 요소들이 여기서 규정됩니다.

module  →  module modid [exports] where body
|  body
body  →  { impdecls ; topdecls }
|  { impdecls }
|  { topdecls }
impdecls  →  impdecl1 ; … ; impdecln (n ≥ 1)
exports  →  ( export1 , … , exportn [ , ] ) (n ≥ 0)
export  →  qvar
|  qtycon [(..) | ( cname1 , … , cnamen )]  (n ≥ 0)
|  qtycls [(..) | ( qvar1 , … , qvarn )]  (n ≥ 0)
|  module modid
impdecl  →  import [qualified] modid [as modid] [impspec]
|  (empty declaration)
impspec  →  ( import1 , … , importn [ , ] ) (n ≥ 0)
|  hiding ( import1 , … , importn [ , ] )  (n ≥ 0)
import  →  var
|  tycon [ (..) | ( cname1 , … , cnamen )]  (n ≥ 0)
|  tycls [(..) | ( var1 , … , varn )]  (n ≥ 0)
cname  →  var | con
topdecls  →  topdecl1 ; … ; topdecln (n ≥ 0)
topdecl  →  type simpletype = type
|  data [context =>] simpletype [= constrs] [deriving]
|  newtype [context =>] simpletype = newconstr [deriving]
|  class [scontext =>] tycls tyvar [where cdecls]
|  instance [scontext =>] qtycls inst [where idecls]
|  default (type1 , … , typen)  (n ≥ 0)
|  foreign fdecl
|  decl
decls  →  { decl1 ; … ; decln } (n ≥ 0)
decl  →  gendecl
|  (funlhs | pat) rhs
cdecls  →  { cdecl1 ; … ; cdecln } (n ≥ 0)
cdecl  →  gendecl
|  (funlhs | var) rhs
idecls  →  { idecl1 ; … ; idecln } (n ≥ 0)
idecl  →  (funlhs | var) rhs
|  (empty)
gendecl  →  vars :: [context =>] type (type signature)
|  fixity [integer] ops  (fixity declaration)
|  (empty declaration)
ops  →  op1 , … , opn (n ≥ 1)
vars  →  var1 , …, varn (n ≥ 1)
fixity  →  infixl | infixr | infix
type  →  btype [-> type] (function type)
btype  →  [btype] atype (type application)
atype  →  gtycon
|  tyvar
|  ( type1 , … , typek )  (tuple type, k ≥ 2)
|  [ type ]  (list type)
|  ( type )  (parenthesized constructor)
gtycon  →  qtycon
|  ()  (unit type)
|  []  (list constructor)
|  (->)  (function constructor)
|  (,{,})  (tupling constructors)
context  →  class
|  ( class1 , … , classn )  (n ≥ 0)
class  →  qtycls tyvar
|  qtycls ( tyvar atype1 … atypen )  (n ≥ 1)
scontext  →  simpleclass
|  ( simpleclass1 , … , simpleclassn )  (n ≥ 0)
simpleclass  →  qtycls tyvar
simpletype  →  tycon tyvar1 … tyvark (k ≥ 0)
constrs  →  constr1 | … | constrn (n ≥ 1)
constr  →  con [!] atype1 … [!] atypek (arity con = k, k ≥ 0)
|  (btype | ! atype) conop (btype | ! atype)  (infix conop)
|  con { fielddecl1 , … , fielddecln }  (n ≥ 0)
newconstr  →  con atype
|  con { var :: type }
fielddecl  →  vars :: (type | ! atype)
deriving  →  deriving (dclass | (dclass1, … , dclassn)) (n ≥ 0)
dclass  →  qtycls
inst  →  gtycon
|  ( gtycon tyvar1 … tyvark )  (k ≥ 0, tyvars distinct)
|  ( tyvar1 , … , tyvark )  (k ≥ 2, tyvars distinct)
|  [ tyvar ]
|  ( tyvar1 -> tyvar2 )  tyvar1 and tyvar2 distinct
fdecl  →  import callconv [safety] impent var :: ftype (define variable)
|  export callconv expent var :: ftype  (expose variable)
callconv  →  ccall | stdcall | cplusplus (calling convention)
|  jvm | dotnet
|  system-specific calling conventions
impent  →  [string] (see Section 8.5.1)
expent  →  [string] (see Section 8.5.1)
safety  →  unsafe | safe
ftype  →  frtype
|  fatype → ftype
frtype  →  fatype
|  ()
fatype  →  qtycon atype1 … atypek (k ≥ 0)
funlhs  →  var apat { apat }
|  pat varop pat
|  ( funlhs ) apat { apat }
rhs  →  = exp [where decls]
|  gdrhs [where decls]
gdrhs  →  guards = exp [gdrhs]
guards  →  | guard1, …, guardn (n ≥ 1)
guard  →  pat <- infixexp (pattern guard)
|  let decls  (local declaration)
|  infixexp  (boolean guard)
exp  →  infixexp :: [context =>] type (expression type signature)
|  infixexp
infixexp  →  lexp qop infixexp (infix operator application)
|  - infixexp  (prefix negation)
|  lexp
lexp  →  \ apat1 … apatn -> exp (lambda abstraction, n ≥ 1)
|  let decls in exp  (let expression)
|  if exp [;] then exp [;] else exp  (conditional)
|  case exp of { alts }  (case expression)
|  do { stmts }  (do expression)
|  fexp
fexp  →  [fexp] aexp (function application)
aexp  →  qvar (variable)
|  gcon  (general constructor)
|  literal
|  ( exp )  (parenthesized expression)
|  ( exp1 , … , expk )  (tuple, k ≥ 2)
|  [ exp1 , … , expk ]  (list, k ≥ 1)
|  [ exp1 [, exp2] .. [exp3] ]  (arithmetic sequence)
|  [ exp | qual1 , … , qualn ]  (list comprehension, n ≥ 1)
|  ( infixexp qop )  (left section)
|  ( qop⟨-⟩ infixexp )  (right section)
|  qcon { fbind1 , … , fbindn }  (labeled construction, n ≥ 0)
|  aexp⟨qcon⟩ { fbind1 , … , fbindn }  (labeled update, n ≥ 1)
qual  →  pat <- exp (generator)
|  let decls  (local declaration)
|  exp  (guard)
alts  →  alt1 ; … ; altn (n ≥ 1)
alt  →  pat -> exp [where decls]
|  pat gdpat [where decls]
|  (empty alternative)
gdpat  →  guards -> exp [ gdpat ]
stmts  →  stmt1 … stmtn exp [;] (n ≥ 0)
stmt  →  exp ;
|  pat <- exp ;
|  let decls ;
|  ;  (empty statement)
fbind  →  qvar = exp
pat  →  lpat qconop pat (infix constructor)
|  lpat
lpat  →  apat
|  - (integer | float)  (negative literal)
|  gcon apat1 … apatk  (arity gcon = k, k ≥ 1)
apat  →  var [ @ apat] (as pattern)
|  gcon  (arity gcon = 0)
|  qcon { fpat1 , … , fpatk }  (labeled pattern, k ≥ 0)
|  literal
|  _  (wildcard)
|  ( pat )  (parenthesized pattern)
|  ( pat1 , … , patk )  (tuple pattern, k ≥ 2)
|  [ pat1 , … , patk ]  (list pattern, k ≥ 1)
|  ~ apat  (irrefutable pattern)
fpat  →  qvar = pat
gcon  →  ()
|  []
|  (,{,})
|  qcon
var  →  varid | ( varsym ) (variable)
qvar  →  qvarid | ( qvarsym ) (qualified variable)
con  →  conid | ( consym ) (constructor)
qcon  →  qconid | ( gconsym ) (qualified constructor)
varop  →  varsym | ` varid ` (variable operator)
qvarop  →  qvarsym | ` qvarid ` (qualified variable operator)
conop  →  consym | ` conid ` (constructor operator)
qconop  →  gconsym | ` qconid ` (qualified constructor operator)
op  →  varop | conop (operator)
qop  →  qvarop | qconop (qualified operator)
gconsym  →  : | qconsym

10.6 Fixity 해석 (Fixity Resolution)

다음은 Haskell 식에 대한 fixity 해석의 예시 구현이에요. fixity 해석은 Haskell 패턴에도 적용되지만, 패턴은 식의 부분집합이므로 이하에서는 설명을 위해 식만 고려할게요.

resolve 함수는 요소가 식이거나 연산자인 리스트, 즉 문맥 자유 문법에서 infixexp 비터미널의 한 사례를 입력으로 받아요. 입력이 유효한 식을 나타내면 Just e(여기서 e는 해석된 식)를, 유효하지 않으면 Nothing을 반환해요. 실제 컴파일러에서는 유용한 오류 메시지를 만들기 위해 관련 연산자에 대한 더 많은 정보를 반환하는 편이 낫겠지만, 여기서는 알고리즘을 설명하는 데 Maybe 타입이면 충분해요.

import Control.Monad

type Prec   = Int
type Var    = String

data Op = Op String Prec Fixity
  deriving (Eq,Show)

data Fixity = Leftfix | Rightfix | Nonfix
  deriving (Eq,Show)

data Exp = Var Var | OpApp Exp Op Exp | Neg Exp
  deriving (Eq,Show)

data Tok = TExp Exp | TOp Op | TNeg
  deriving (Eq,Show)

resolve :: [Tok] -> Maybe Exp
resolve tokens = fmap fst $ parseNeg (Op "" (-1) Nonfix) tokens
  where
    parseNeg :: Op -> [Tok] -> Maybe (Exp,[Tok])
    parseNeg op1 (TExp e1 : rest)
       = parse op1 e1 rest
    parseNeg op1 (TNeg : rest)
       = do guard (prec1 < 6)
            (r, rest') <- parseNeg (Op "-" 6 Leftfix) rest
            parse op1 (Neg r) rest'
       where
          Op _ prec1 fix1 = op1

    parse :: Op -> Exp -> [Tok] -> Maybe (Exp, [Tok])
    parse _   e1 [] = Just (e1, [])
    parse op1 e1 (TOp op2 : rest)
       -- case (1): check for illegal expressions
       | prec1 == prec2 && (fix1 /= fix2 || fix1 == Nonfix)
       = Nothing

       -- case (2): op1 and op2 should associate to the left
       | prec1 > prec2 || (prec1 == prec2 && fix1 == Leftfix)
       = Just (e1, TOp op2 : rest)

       -- case (3): op1 and op2 should associate to the right
       | otherwise
       = do (r,rest') <- parseNeg op2 rest
            parse op1 (OpApp e1 op2 r) rest'
       where
         Op _ prec1 fix1 = op1
         Op _ prec2 fix2 = op2

알고리즘은 이렇게 동작해요. 각 단계에서 다음과 같은 호출이 있습니다.

parse op1 E1 (op2 : tokens)

이는 다음과 같은 식을 바라보고 있다는 뜻이에요.

E0 ‘op1‘ E1 ‘op2‘ ...     (1)

(호출자가 E0을 들고 있죠.) parse의 일은 op1의 오른쪽에 오는 식을 만들어 내서, 그 식과 남은 입력을 반환하는 것입니다.

고려할 경우는 세 가지예요.

  • op1과 op2의 우선순위는 같은데 결합성(associativity)이 다르거나, 둘 중 하나가 nonfix로 선언되어 있으면, 그 식은 불법이에요.
  • op1의 우선순위가 op2보다 높거나, op1과 op2가 왼쪽 결합이어야 한다면, op1의 오른쪽 식이 E1임을 알 수 있어요. 그래서 그것을 호출자에게 반환해요.
  • 그 외의 경우, E1 ‘op2‘ R 형태의 식을 만들고 싶다는 뜻이에요. R을 찾기 위해 parseNeg op2 tokens를 호출해서 op2 오른쪽의 식, 즉 R을 계산해요(parseNeg에 대해서는 아래에서 더 설명하지만, 본질적으로 tokens가 (E2 : rest) 형태라면 parse op2 E2 rest와 같아요). 이제 우리는 
    E0 ‘op1‘ (E1 ‘op2‘ R) ‘op3‘ ...
    을 가지는데, 여기서 op3는 입력의 다음 연산자예요. 이는 위 (1)의 한 사례이므로, 새 E1 == (E1 ‘op2‘ R)로 parse를 계속 호출해요.

알고리즘을 초기화할 때 op1을 그 무엇보다도 낮은 우선순위를 가진 가상의 연산자로 설정해요. 그래서 parse는 입력 전체를 소비하고 결과 식을 반환합니다.

전위 부정(prefix negation) 연산자 -의 처리는 단지 조금만 복잡해질 뿐이에요. 전위 부정은 중위 부정과 같은 fixity를 가진다는 점을 기억하세요. 왼쪽 결합에 우선순위 6이에요. -의 왼쪽에 연산자가 있다면, 그 연산자의 우선순위는 식이 유효하려면 6보다 낮아야 해요. 부정 연산자 자체는 같은 fixity의 연산자(예: +)와 왼쪽 결합할 수 있어요. 그래서 예를 들어 -a + b는 유효하고 (-a) + b로 해석되지만, a + -b는 불법이에요.

parseNeg 함수가 전위 부정을 처리해요. 부정 연산자를 만났는데 그 위치에서 합법이라면(왼쪽의 연산자 우선순위가 6보다 낮다면), 위의 경우 3과 비슷하게 진행합니다. -의 인자를 재귀적으로 parseNeg를 호출해서 계산한 다음, parse를 계속 호출하는 것이죠.

이 알고리즘은 우선순위의 범위와 분해능에 무관하다는 점을 눈여겨 두세요. Haskell이 원칙상 1에서 10 범위의 정수 우선순위로 제한될 이유는 없어요. 더 큰 범위나 분수 값을 써도 추가적인 어려움은 없습니다.

더 알아보기 (Learn more)

  • Haskell 2010 Language Report — 챕터 10 (Syntax Reference) 원문: https://www.haskell.org/onlinereport/haskell2010/haskellch10.html
  • 챕터 10에서 언급된 다른 절: 레이아웃 규칙의 비공식 논의(섹션 2.7), 문자열 리터럴의 여러 줄(섹션 2.6), foreign 선언(섹션 8.5.1), 라벨 붙은 생성과 갱신(섹션 3.15)
  • 관련 주제: GHC에서의 어휘 처리(lex), 레이아웃 규칙의 공식 알고리즘(L 함수), 연산자 fixity와 결합성, 리터럴 프로그래밍(.lhs 파일)