以下の慣習的表記が文法を表現するのにつかわれる:

• [pattern] 省略可能
• {pattern} 0回以上の繰り返し
• (pattern) グループ化
• pat1 | pat2 選択
• pat<pat'> 差(patによって生成された要素で、pat'で生成されたものを除いたもの)
• fibonacci タイプライターフォントで表記される終端文法

BNFのような文法をレポートを通して用いる。文法の生成は次のような形をしている:

nonterm -> alt1 | alt2 | .. | altn

字句文法、文脈自由文法いずれも曖昧さが残るが、これは文法語句をできる限り長く取り、左から右に進む(shift-reduceパースでは、shift/reduceコンフリクトはシフトを取ることで解決する)ことで解決するものとする。字句文法では、これは「最長一致」と呼ばれるルールである。文脈自由文法では、これは条件式やlet式、ラムダ抽象などが右方向に取れるだけ長くとることを表す。

セクション2.7([訳注] TODO:リンク)ではレイアウトルールに対する非形式的な議論を見た。このセクションではより正確に定義をする。

Haskellプログラムの意味はそのレイアウトに依存する場合がある。レイアウトが意味に与える効果は波括弧とセミコロンをレイアウトによって決定される位置に追加することで完全に説明できる。このようにして追加されたプログラムの意味は今やレイアウトによって影響を受けない。

レイアウトがプログラムに対して与える影響は、このセクションで波括弧とセミコロンをどのように追加するかを説明することで指定される。仕様は、プログラムの返還を行う関数Lの形で与えられる。Lの入力は次のようなものである:

• Haskellレポートにある字句文法によって定められた語句の列であって、さらに次のような追加の語句を含む:
  • let, where, do, ofキーワードの後に{が続かない場合、トークン{n}がキーワードの後に挿入される。ただしnは、続くトークンがあればそのインデントを表し、ファイルの終端に達した場合は0を表す。
  • モジュールの最初のトークンが{でもmoduleでもない場合、そのトークンのインデントをnとすると、{n}が先行する。
  • 同じ行で空白のみが最初のトークンに先行する場合、<n>がこの語句に先行する。ここでnは語句のインデントであり、もしインデントが存在しない場合には先の2つのルールの結果として{n}が先行することとなる。(注意: 文字列リテラルはセクション2.6で説明したように、複数行に及ぶこともある。よって次のコードにおいては、\Billの前に<n>が挿入されることはない。なぜなら、これは完全な語句の開始でもなければ,の前でもなく、単純に空白文字によって先行されているだけだからである。)

f = ("Hello \  
        \Bill", "Jake")    

• "レイアウト文脈"のスタックで、各要素が次のいずれかであるもの:
  • 文脈の囲みを明示することを表すゼロ(すなわち、プログラマは開いた波括弧を書いていた場合) 最も内側の文脈が0である場合、レイアウトトークンは文脈の囲いが終了するか新しい文脈が追加されるまで挿入されない。
  • レイアウト文脈を囲うインデントの段数を表す正の整数

語句の"インデント"とは、語句の最初の文字の段数である。そしてある行のインデントとは、最も左にある語句のインデントである。段数を決定するには、次の慣習に従う固定幅フォントを使っていると仮定する。 - 次の文字 newline, return, linefeed, formfeed は新しい行を開始する。 - 最初の段数は0ではなく、1とする。 - タブは8文字分の幅だけ次の文字位置までの間が空く。 - タブ文字は現在の位置をタブの次の文字位置まで揃えるためにそれに足りるだけのスペースを挿入させる。

レイアウトルールのために、ソースコード中のユニコード文字もASCII文字と同じ固定された幅をもつものとみなされる。しかし見た目の混乱を防ぐために、プログラマーは見た目に分からないレイアウトの意味を、空白でない文字幅に依存させるようなプログラムを書くことは避けるべきである。

関数適用 L tokens [] は、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 (ノート) 1)
L ({n} : ts) []         = {  :  (L ts [n])                  if n > 0 (ノート 1)
L ({n} : ts) ms         = {  :  }  :  (L (< n >: ts) ms)    (ノート 2)
L (} : ts) (0 : ms)     = }  :  (L ts ms)                   (ノート 3)
L (} : ts) ms           = parse-error                       (ノート 3)
L ({ : ts) ms           = {  :  (L ts (0 : ms))             (ノート 4)
L (t : ts) (m : ms)     = }  :  (L (t : ts) ms)             if m≠0 and parse-error(t)
                                                            (ノート 5)
L (t : ts) ms           = t  :  (L ts ms)
L [] []                 = []
L [] (m : ms)           = }  :  L [] ms                     if m≠0 (ノート 6)

ノート1 ネストされたコンテキストは文脈の囲い(n > m)よりも深くインデントされなければならない。そうでなければ、Lは失敗し、コンパイラはレイアウトエラーを示すだろう。次は例である。

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

ここで、pの定義は、ここではhの定義によって定まっている文脈の囲いのインデントより浅くインデントされている。

ノート2 (例えば)whereの後に出現する最初のトークンがレイアウト文脈の囲いよりもインデントされていなかった場合、そのwhereのブロックは空でなければならず、よって中身のないの波括弧が挿入される。{n}トークンは中身のない波括弧が明示されたを模倣して<n>によって置き換えられる。

ノート3 現在のレイアウト文脈を0と比べることで、明示された閉じ波括弧が明示された開き波括弧のみと対応していることを保証できる。明示された閉じ波括弧が明示されていない開き波括弧と対応している場合はパースエラーが出力される。

ノート4 この句は、ラベル付き構成と更新を含めた(セクション3.15)すべての波括弧の組が明示的なレイアウト文脈として扱われるようにするためのものである。この式はHaskell1.4とは異なっている。

ノート5 横の条件parse-error(t)は次のように解釈される: Lによってこれまでに生成された次のトークンtをもつトークン列がHaskell文法において無効なものから始まっていることを表しており、またLによってこれまでに生成された"}"に続くトークン列がHaskell文法において有効なものから始まっていることを表している場合、parse-error(t)は真である。

m≠0は暗黙的に追加された閉じ波括弧が明示されていない開き波括弧と対応することを確認している。

ノート6 入力に終わりに、保留されている閉じ波括弧が挿入される。非レイアウト文脈に含まれている場合(すなわち、m = 0)、ここでエラーになる。

上のルールのいずれもマッチしない場合、このアルゴリズムは失敗する。例えば入力の最後に到達したときに、非レイアウト文脈が有効であれば、閉じ波括弧が存在しないので失敗することになる。このアルゴリズムによって検知されないエラー条件も一部存在する。例えば、let }である。

ノート1はレイアウト処理がパースエラーによって途中で停止する可能性があることを言っている。例えば

let x = e; y = x in e'

は有効である。なぜならこれは次のように変換されるからである。

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

閉じ波括弧は上のパースエラーのルールにより挿入される。

「文芸的コメント」の慣習は、リチャード・バードとフィリップ・ワドラーらがOrwell言語のために初めて導入し、そして次にドナルド・クヌースの「文芸的プログラミング」に影響を与えたものであるが、Haskellのソースコードを記述するためのもう一つのスタイルである。文芸的スタイルはコメントを書くことを、それをデフォルトとすることで推奨している。始めの文字が">"である行はプログラムの一部として扱われ、それ以外の行はすべてコメントとなる。

プログラムの本文は">"で始まる行のみを拾い、">"とそれに続く空白を置き換えることで復元することができる。その結果残る本文の中では、レイアウトやコメントは10章で説明したとおりに適用される。

">"を間違って省略してしまった場合に備えて、空でないコメント行に隣接するプログラム行はエラーになる。ここで空のコメント行とは、空白しか含まないもののことである。

慣習的に、コメントのスタイルはファイル拡張子によって指定される。".hs"であれば通常のHaskellファイルであり、".lhs"であれば文芸的Haskellファイルである。このスタイルを用いると、階乗の簡単なプログラムは次のようになる。

(訳注: 文芸的Haskellに対応するsyntax highlighterがないので通常のHaskellハイライトで代用しています。本来コメントとして扱われるThis literate...やThis is the factorial...などに色が付いていますがここは上でも説明があった通りコメントです。)

   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}

このスタイルは同じファイル拡張子を用いる。同じファイルに対してこれら2つのスタイルを混ぜるのはおすすめできない。

次はHaskellの式における結合性解決の実装例である。結合性解決はHaskellのパターンに対しても適用可能であるが、パターンは式のサブセットであるので、以下では簡単のため式のみを考えることにする。

resolve関数はリストであって、それぞれの要素が式または演算子であるもの、すなわち、文脈自由文法において非終端記号infixexpのインスタンスとなるもの(訳注: 上の文法表でinfixexpに当てはまるもの、の意味)を受け取る。resolveは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): 不当な式をチェック
       | prec1 == prec2 && (fix1 /= fix2 || fix1 == Nonfix)  
       = Nothing  

       -- case (2): op1とop2は左結合であるべきである
       | prec1 > prec2 || (prec1 == prec2 && fix1 == Leftfix)  
       = Just (e1, TOp op2 : rest)  

       -- case (3): op1とop2は右結合であるべきである
       | 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を保持している)

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

parseの仕事はop1の右側の式を構築し、入力の残りの部分を返すことである。

3つの場合を考慮する必要がある:

1. op1とop2が同じ優先度であるが、同じ結合性を持たない場合あるいは不結合(nonfix)であることが宣言されている場合には、式は不当である。
2. op1がop2よりも高い優先度であるかop1とop2が左結合である場合には、op1の右側の式はE1であることがわかり、よってこれを呼び出し側に返却する。
3. いずれでもない場合、E1 `op2` Rの形の式が求めているものであることがわかる。Rを見つけるには、parseNeg op2 tokensを呼び出してop2の右側の式を計算し、これを今はRと名前を付ける(parseNeg以下の部分についての詳細は以下に示すが、本質的には、もしもtokensが(E2 : tokens)の形をしている場合、parseNegはparse op2 E2 restと同値である)。さて、E0 `op1` (E1 `op2` R) `op3` ...の形を得た、ここでop3は入力に出現する次の演算子である。これは上の(1)の場合の具体的な例になっているから、E1 == (E1 `op2` R)と新たに置いてparseを続いて呼び出す。

アルゴリズムを初期化するには、op1は他の何よりも優先度の低い仮想的な演算子であるとおく。そしてparseは入力全体を消費し結果の式を返す。

前置マイナス演算子の-の扱いは若干込み入っている。前置のマイナスは中置のマイナスと同じ結合性であったことを思い出そう、いずれも左結合で優先度は6だ。-の左にくる演算子は、もし存在すれば、式が正当であるためには優先度が6より低くなければならない。マイナス演算子そのものは同じ結合性を持つ演算子に対しては左結合的にはたらく(例: +)。よって例えば-a + bは正当であり(-a) + bとして解決されるが、a + -bは不当である。

関数parseNegは前置マイナスを処理する。前置演算子に遭遇して、それがその位置で正当であれば(左側にある演算子の優先度が6より低ければ)、上の(3)のケースと同様にして進めていく。つまり、-の引数をparseNegを再帰的に呼ぶことで計算し、そしてparseを呼んで続けていく。

このアルゴリズムは優先度の範囲と解決には影響されないことに注意せよ。原則として、Haskellの優先度が1から10までの範囲の整数に制限される理由は何もない。より広い範囲や分数の値を使うことで特別に難しくなるわけではない。