구문 참조

구문 참조 (Syntax Reference)

여기까지 앞의 여러 장에서 문법 형태를 조각조각 봤다면, 이 장은 그 모든 문법을 한곳에 모아 놓은 종합 참조예요. 문법 생성 규칙(productions)·어휘 구조·레이아웃·연산자 fixity 해석의 정밀한 정의가 이 장에 있어요. "문법이 도대체 어떻게 정의되는 거지?" 하고 궁금할 때 펼치는 완전한 명세예요.

출처: Haskell 2010 언어 리포트

본문

이 장은 Haskell 언어의 완전한 문법 요약이에요. 문법을 표현하는 데 쓰는 표기 규약부터 어휘 문법, 레이아웃 규칙, 생략 표기(literate comments), 문맥 자유 문법, 그리고 연산자 fixity 해석까지 차례로 다뤄요.

10.1 표기 규약 (Notational Conventions)

문법을 표현하는 데 쓰는 표기 규약은 다음과 같아요:

[pattern]   선택 사항 (optional)
{pattern}  0회 이상 반복 (zero or more repetitions)
(pattern)  묶음 (grouping)
pat1 | pat2  선택 (choice)
pat⟨pat′⟩   차이 — pat가 만드는 원소에서 pat′가 만드는 것을 뺀 것
fibonacci  타자기체의 종단 문법 (terminal syntax in typewriter font)

전체에 걸쳐 BNF 유사 문법을 쓰고, 생성 규칙은 다음과 같은 형태를 가져요:

nonterm → alt1 | alt2 | … | altn

어휘 문법과 문맥 자유 문법 양쪽에는 몇 가지 모호함이 있는데, 이를 문법 구(phrase)를 왼쪽에서 오른쪽으로 가능한 한 길게 만들어 해소해요. 어휘 문법에서는 이를 "최대한 길게 집어먹기(maximal munch)" 규칙이라고 하고, 문맥 자유 문법에서는 조건식·let 식·람다 추상이 오른쪽으로 가능한 한 멀리 확장된다는 뜻이에요.

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

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의 입력은:

  • 어휘 문법이 만드는 lexeme의 흐름인데, 다음과 같은 추가 토큰이 더해져요.
    • let, where, do, of 키워드가 lexeme {로 이어지지 않으면, 키워드 뒤에 토큰 {n}이 삽입돼요. 여기서 n은 다음 lexeme의 들여쓰기(들여쓰기 열)이고, 파일 끝이라면 0이에요.
    • 모듈의 첫 lexeme이 {나 module이 아니면, 그 lexeme은 들여쓰기 n만큼의 {n}이 앞에 붙어요.
    • 어떤 lexeme의 시작이 같은 줄에서 공백만으로 앞에 있으면, 그 lexeme 앞에 < n >가 붙어요(n은 그 lexeme의 들여쓰기). 단, 앞의 두 규칙 때문에 {n}이 이미 앞에 붙은 경우는 제외해요. (문자열 리터럴은 여러 줄에 걸칠 수 있어요 — 2.6절. 그래서 다음 조각에서 
      f = ("Hello \
\Bill", "Jake")
      \Bill 앞에는 < n >가 삽입되지 않아요 — 완전한 lexeme의 시작이 아니기 때문이에요. , 앞에도 삽입되지 않아요 — 공백만으로 앞에 있지 않기 때문이에요.)
  • "레이아웃 문맥(layout contexts)"의 스택인데, 각 원소는 다음과 같아요:
    • 0 — 둘러싼 문맥이 명시적이라는 뜻(즉 프로그래머가 여는 중괄호를 직접 제공). 가장 안쪽 문맥이 0이면, 둘러싼 문맥이 끝나거나 새 문맥이 밀릴 때까지 레이아웃 토큰이 삽입되지 않아요.
    • 양의 정수 — 둘러싼 레이아웃 문맥의 들여쓰기 열.

lexeme의 "들여쓰기"는 그 lexeme 첫 문자의 열 번호이고, 줄의 들여쓰기는 가장 왼쪽 lexeme의 들여쓰기예요. 열 번호는 고정폭 글꼴과 다음 규칙을 가정해 정해요:

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

레이아웃 규칙 목적상, 소스 프로그램의 유니코드 문자는 ASCII 문자와 같은 고정 너비로 간주돼요. 다만 시각적 혼란을 피하기 위해, 암묵적 레이아웃의 의미가 비-공백 문자의 너비에 의존하는 프로그램은 피하는 게 좋아요.

적용 L tokens []은 토큰의 레이아웃-민감하지 않은 번역을 산출해요, 여기서 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의 의미를 정리하면:

  • Note 1. 중첩 문맥은 둘러싼 문맥보다 더 들여써야 해요 (n > m). 그렇지 않으면 L이 실패하고 컴파일러는 레이아웃 오류를 알려줘야 해요. 예를 들어 다음 코드에서 p의 정의가 둘러싼 문맥(이 경우 h의 정의가 정하는)의 들여쓰기보다 덜 들여쓰여 있어요: 
    f x = let
        h y = let
                p z = z
              in p
      in h
  • Note 2. (where 같은) 키워드 뒤 첫 토큰이 둘러싼 레이아웃 문맥보다 더 들여쓰지 않았으면 블록은 비어 있어야 해요. 그래서 빈 중괄호가 삽입돼요. {n} 토큰은 < n >로 바뀌어, 빈 중괄호가 명시적이었던 상황을 흉내내요.
  • Note 3. 현재 레이아웃 문맥에 대해 0과 대조함으로써, 명시적 닫는 중괄호는 명시적 여는 중괄호에만 맞출 수 있게 보장해요. 명시적 닫는 중괄호가 암묵적 여는 중괄호와 맞으면 구문 오류가 나요.
  • Note 4. 이 절은 모든 중괄호 쌍을 명시적 레이아웃 문맥으로 취급해요 — 레이블로 만든 구성(labeled construction)과 갱신(3.15절)도 포함해서요. 이것이 이 정식화와 Haskell 1.4 사이의 차이예요.
  • Note 5. 보조 조건 parse-error(t)는 다음과 같이 해석돼요: L이 지금까지 만든 토큰들과 다음 토큰 t가 Haskell 문법의 잘못된 접두사(prefix)를 나타내고, 지금까지 만든 토큰들과 토큰 }가 유효한 접두사를 나타내면, parse-error(t)가 참이에요. 테스트 m∕ = 0은 암묵적으로 추가된 닫는 중괄호가 암묵적 여는 중괄호와 맞는지 검사해요.
  • Note 6. 입력이 끝나면, 보류 중인 닫는 중괄호들이 삽입돼요. 이 시점에 비-레이아웃 문맥(즉 m = 0) 안에 있으면 오류예요.

위 규칙 중 어느 것도 맞지 않으면 알고리즘은 실패해요. 예를 들어 입력 끝에 도달했는데 비-레이아웃 문맥이 활성 상태면 닫는 중괄호가 없어 실패할 수 있어요. Note 1은 구문 오류로 레이아웃 처리가 조기에 멈출 수 있다는 특징을 구현해요. 예를 들어:

let x = e; y = x in e'

은 유효한데, let { x = e; y = x } in e'로 번역되기 때문이에요. 닫는 중괄호는 위의 구문 오류 규칙 때문에 삽입돼요.

10.4 생략 표기 (Literate comments)

"생략(literate) 주석" 관례는 Richard Bird와 Philip Wadler가 Orwell을 위해 처음 개발하고, Donald Knuth의 "literate programming"에서 영감을 받은 것으로, Haskell 소스 코드를 표현하는 또 하나의 스타일이에요. 이 스타일은 주석을 기본값으로 만들어 주석을 장려해요. >가 첫 문자인 줄은 프로그램의 일부로 취급되고, 다른 모든 줄은 주석이에요.

프로그램 텍스트는 >로 시작하는 줄만 골라서 그 앞의 >를 공백으로 바꿔 복원해요. 결과 텍스트에는 10장에서 설명한 대로 레이아웃과 주석이 정확히 적용돼요. 실수로 >를 빠뜨리는 경우를 잡기 위해, 프로그램 줄이 비-빈 주석 줄에 인접해 있으면 오류예요(오직 공백만으로 이루어진 줄은 빈 줄로 취급).

관례상 주석 스타일은 파일 확장자로 표시하는데, .hs는 보통 Haskell 파일, .lhs는 literate 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}로 시작하는 줄 다음 첫 줄에서 시작된다.
프로그램 코드는 \end{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)

연산자 fixity 해석의 예시 구현이 이 절에 실려 있어요(전문 Haskell 코드). 함수 resolve는 식이거나 연산자인 원소들의 리스트(즉 문맥 자유 문법의 infixexp 비-종단의 인스턴스)를 받아, 해석된 식 Just e 또는 유효한 식이 아니면 Nothing을 돌려줘요:

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' ... 같은 식을 보고 있다는 뜻이에요(호출자가 E0를 쥐고 있어요). parse의 일은 op1 오른쪽의 식을 짓고, 그 식과 남은 입력을 돌려주는 거예요. 세 경우가 있어요:

  • case (1): op1과 op2의 우선순위가 같은데 결합성이 같지 않거나, 둘 중 하나가 nonfix로 선언되면 식은 불법이에요.
  • case (2): op1이 op2보다 우선순위가 높거나, op1·op2가 좌결합이면 op1 오른쪽의 식이 E1임을 알 수 있어서 호출자에게 돌려줘요.
  • case (3): 그 외에는 E1 'op2' R 형태의 식을 짓고 싶어요. R을 찾으려면 parseNeg op2 tokens로 op2 오른쪽의 식 R을 계산해요. 그러면 E0 'op1' (E1 'op2' R) 'op3' ...가 되고, 이는 (1)의 형태이므로 새 E1 == (E1 'op2' R)로 parse를 계속 불러요.

초기화를 위해 op1을 다른 어떤 것보다 낮은 우선순위의 가상 연산자로 두면, parse가 입력 전체를 소비해 결과 식을 돌려줘요. 접두 부정 연산자 -의 처리는 살짝 복잡할 뿐이에요. 접두 부정은 중위 부정과 같은 fixity(좌결합, 우선순위 6)를 갖고, - 왼쪽의 연산자는(있으면) 식이 유효하려면 우선순위가 6보다 낮아야 해요. 부정 연산자 자신은 같은 fixity의 연산자(예: +)와 좌결합할 수 있어요. 그래서 -a + b는 유효하고 (-a) + b로 해석되지만, a + -b는 불법이에요. parseNeg가 접두 부정을 처리해요.

이 알고리즘은 우선순위의 범위와 해상도에 민감하지 않아요. 원칙적으로 Haskell이 1부터 10까지의 정수 우선순위로 제한될 이유는 없고, 더 큰 범위나 분수 값도 특별한 어려움 없이 쓸 수 있어요.

더 알아보기 (Learn more)