Haskell2010中文報告/語言/詞法結構

本章，我們討論Haskell的下層詞法結構。在第一次閱讀本報告時，這裡面絕大部分細節可以先忽略。

記法約定

在顯示語法時，有下面的記法約定：

• [pattern] 可選
• {pattern} 0次或多次重複
• (pattern) 分組
• pat₁ |pat₂ 選擇
• pat_<pat′> 從pat而不是pat'生成
• fibonacci 終結符(文字)使用打印機字體

本節中的語法都是討論詞法語法。所以，空白符都顯式表示，在並列的符號之間不隱藏空白符。本節大量使用類BNF的文法，產生式的形式如下：

nonterm → alt₁ | alt₂ | … | alt_n

雖然從上下文通常可以判斷出符號的意思，但必須要注意區分元邏輯文法符號，比如|，[…]和終結符(打印機字體)|和[...]的不同。

Haskell使用Unicode字符。但是，源程序現在仍傾向於使用早先版本Haskell的ASCII字符集。

Haskell語法的Unicode字符集屬性取決於Unicode委員會的定義。因此，一旦有新的Unicode發布，Haskell編譯器總是假定使用新版本。

詞法程序結構

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

詞法分析總是按照"最大滿足"規則: 每次做詞法分析，總是按照最長的詞法規則產生詞彙(lexeme類)。因此，雖然case是保留字，但cases卻不是。同樣地，雖然=是保留字，但==以及~=卻不是。

任意空格符也可看作是詞彙的分隔符。

不在ANY類的字符在Haskell程序中是非法字符，會報詞法錯誤。

注釋

注釋是合法的空格符。

常規注釋從兩個或者多個連續橫線開始，一直到本行結束。注釋橫線前後的連續部分不能組成合法的詞。舉個例子，"-->"或者"|--"不是注釋的開始，因為他們都是合法詞彙。而"--foo"卻開始一個新的注釋。

嵌入注釋從"{-"開始，到"-}"結束。沒有合法詞彙從"{-"開始，因此,"{-"總是開始注釋。舉個例子，"{---"開始一個嵌入注釋，並不理會後面的橫線。

嵌入注釋本身不做詞法分析。第一個未匹配的字符串"-}"結束嵌入注釋。嵌入注釋可以嵌入任意多個層次。在嵌入注釋裡面出現"{-"將開啟一個新的嵌入注釋，以"-}"結束。在一個嵌入注釋內部，每個"{-"由一個對應的"-}"匹配。、

在一個常規注釋內，字符序列"{-"及"-}"沒有特殊含義。同樣，在一個嵌入注釋內，橫線序列也沒有特殊含義。

嵌入注釋也用作編譯器指示，在編譯器指示節介紹。

如果使用嵌入注釋將某些代碼注釋掉，那麼代碼中的字符串或者行注釋部分出現"{-"或"-}"將會打斷嵌入注釋。

標識符和運算符

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 | _

一個標識符包含首字母及隨後的0個或多個字母、數字、下劃線及單引號。從詞法分析的角度，標識符分為兩類：小寫字母開頭(變量標識符)以及大寫字母開頭(構造符標識符)。標識符大小寫敏感：name, naMe以及Name是三個不同的標識符(前兩個是變量標識符，最後一個是構造符標識符)。

下劃線，"_"，被處理為小寫字母，可以替代小寫字母出現。而"_"本身則是保留標示符，用作模式中的通配符。如果編譯器為未使用標識符提供告警，那麼下劃線為首字符的標識符通常建議不告警。這樣，如果某個參數foo未使用，程序員可以使用"_foo"做參數。

varsym → ( symbol_<:> {symbol} )_{<reservedop | dashes>}
consym → ( : {symbol})_<reservedop>
reservedop → .. | : | :: | = | \ | | | <- | -> | @ | ~ | =>

如上所示，操作符由一個或多個符號字符組成。同樣，從詞法分析角度，被區分為兩類(名字空間)：

• 冒號開始的操作符是構造符
• 其它符號開始的操作符是常規標識符

需要注意的是冒號本身被保留，唯一用作列表的構造符；這樣，它可以和其它的列表語法形式，比如"[]「及"[a,b]"統一。

除了求反是特殊的前綴形式，其它操作符都是中綴形式。此外，中綴操作符也可以用在一個分切中，以產生偏應用操作符(見分切)。所有的中綴操作符都是預定義符號，可以回彈。

本報告的其餘部分，使用6類不同的名字：
varid (變量)
conid (構造符)
tyvar → varid (類型變量)
tycon → conid (類型構造符)
tycls → conid (類型類)
modid → {conid .} conid (模塊)

變量及類型變量用小寫字母開頭的標識符表示，其它類型名字用大寫字母開始的標識符表示。另外，變量和構造符有中綴形式，而其它四類名字沒有。模塊名由點分割的conid序列組成。名字空間在名字空間節討論。

在特定環境下，可以在名字前添加模塊名來限定名字。這種方法對變量、構造符、類型構造符及類型類名適用，對類型變量或模塊名無效。限定名在模塊節詳細討論。

qvarid → [modid .] varid
qconid → [modid .] conid
qtycon → [modid .] tycon
qtycls → [modid .] tycls
qvarsym → [modid .] varsym
qconsym → [modid .] consym

由於模塊名也是有效詞彙，限定及名字之間不允許有空格。一些詞法分析的結果可以見下表：

名字	詞法分析結果
f.g	f . g (三符號)
F.g	F.g (限定'g')
f..	f .. (兩符號)
F..	F.. (限定 『.』)
F.	F . (兩符號)

限定不改變名字的語法處理; 比如，Prelude.+ 是中綴操作符，和Prelude中定義的"+"(嵌套聲明)有相同的綴形式。

數符

decimal → digit{digit}
octal → octit{octit}
hexadecimal → hexit{hexit}
integer → decimal

| 0ooctal | 0Ooctal

| 0xhexadecimal | 0Xhexadecimal

float → decimal.decimal [exponent]

| decimal exponent

exponent → (e | E) [+ | -] decimal

Haskell有兩種不同的數符: 整數符和浮點數符。整數符可以用十進制(缺省)、八進制(Oo或OO前綴)或者十六進制(Ox或OX)表示。浮點數符總是用十進制表示。浮點數符在點號前後都必須包含數字，以保證和其它帶點的字符區別開來。負數符在操作符應用節討論。數符的類型在數節討論。

字符和串符

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} \

字符在兩個單引號之間，比如'a'。串符在兩個雙引號之間，比如"Hello"。

字符和串符中可以使用退出碼(escape)來表示特殊字。注意，單引號'可以在出現在串中，但必須使用退出碼；同樣地，雙引號"也可以出現在字符中，也必須使用退出碼。\後面跟字符表示退出碼。上面詞法規則中，charesc類包含了可移植的特殊字符，比如「報警"(\a)，"退格"(\b), "換頁"(\f)，"新行"(\n)，"回車"(\r)，"水平制表"(\t)以及"垂直制表"(\v)。

Haskell提供Unicode字符集的退出碼，包括像\^X這樣的控制符。數字退出碼，比如\137，表示該字符的數字表示是137；Haskell也允許八進制和十六進制的數字退出碼。

根據「最大匹配」原則，\後面的數字退出碼總是包含最多的連續數字，且長度任意。同樣地，\後面的ASCII退出碼也滿足這條規則。比如,"\SOH"詞法分析結果是長度為1的串符。退出碼\&表示"空字符"，這樣，我們可以構造類似"\137\&9"或"\SO\&H"這樣的串符(串的長度都為2)。"\&"等價於""，而字符'\&'卻是不允許的。字符之間的等價性在標準Haskell類型節定義。

兩個反斜槓之間只有一個或多個空白符，稱為"間隔「。串內如果有間隔，則間隔被忽略。這樣，我們可以寫出超過一行的字符串：在行的末尾插入反斜槓，在下一行的開頭插入斜槓。比如：

"Here is a backslant \\ as well as \137, \  
    \a numeric escape character, and \^X, a control character."

串符實際上字符列表的簡寫(見列表節)。

排版

Haskell允許某些文法省略大括號和分號，取而代之，使用排版來傳遞相同信息。這樣，我們可以同時使用排版和不排版兩種編程風格，即使在同一程序內部，這兩種風格也可以混用。由於程序排版不是必選項，haskell程序可直接由其它程序生成。

排版的haskell程序，使用排版格式的地方完全可以通過添加大括號和分號的辦法實現等價的Haskell程序。這個等價的Haskell程序即不排版程序。

大致上，大括號和分號可用下面的方法添加：如果關鍵字where、let、do、of後面的左括號被省略，則表示開始一個排版("越位")列表。這時，下一個詞彙(不管是不是在新行)的縮進被記錄下來(詞彙前面的空白符可能也包含注釋)，插入被省略的左括號。在處理後續行時，如果後續行包含更多的縮進，表示繼續前面行的語法項(不插入)；如果後續行包含相同的縮進，表示開始一個新的語法項，插入一個分號；如果後續行縮進變少，則表示當前排版列表結束(插入右括號)。如果where、let、do、of後面緊跟的非括號詞彙，其縮進比當前縮進級別相等或者更小，這時，Haskell並不開始新的排版列表，而是插入括號對"{}"，仍然在當前縮進上進行排版處理(即，插入一個分號或者右括號)。如果包含當前排版列表的文法類結束，也將插入右括號;即，如果某處出現詞彙錯誤，而將此錯誤詞彙替換為右括號時正確，則在此處添加右括號。排版規則只對自己插入的左括號配對；顯式的左括號必須有顯式的右括號配對。如果給出顯式左括號，則括號內不對括號外的結構排版，即便某行的縮進在之前某個插入的隱式左括號的左邊。

版式節對排版規則給出更精確的定義。

給出排版規則後，一個新行可能結束多個排版列表。同樣地，規則使得：

f x = let a = 1; b = 2  
          g y = exp2  
       in exp1

a, b 和 g 從屬於一個排版列表。

一個實例，下面是一個排版程序(有些人為修飾):

module AStack( Stack, push, pop, top, size ) where  
data Stack a = Empty  
             | MkStack a (Stack a)  
 
push :: a -> Stack a -> Stack a  
push x s = MkStack x s  
 
size :: Stack a -> Int  
size s = length (stkToLst s)  where  
           stkToLst  Empty         = []  
           stkToLst (MkStack x s)  = x:xs where xs = stkToLst s  
 
pop :: Stack a -> (a, Stack a)  
pop (MkStack x s)  
  = (x, case s of r -> i r where i x = x) -- (pop Empty) is an error  
 
top :: Stack a -> a  
top (MkStack x s) = x                     -- (top Empty) is an error

程序應用排版規則後的結果如下：

module AStack( Stack, push, pop, top, size ) where  
{data Stack a = Empty  
             | MkStack a (Stack a)  
 
;push :: a -> Stack a -> Stack a  
;push x s = MkStack x s  
 
;size :: Stack a -> Int  
;size s = length (stkToLst s)  where  
           {stkToLst  Empty         = []  
           ;stkToLst (MkStack x s)  = x:xs where {xs = stkToLst s  
 
}};pop :: Stack a -> (a, Stack a)  
;pop (MkStack x s)  
  = (x, case s of {r -> i r where {i x = x}}) -- (pop Empty) is an error  
 
;top :: Stack a -> a  
;top (MkStack x s) = x                        -- (top Empty) is an error  
}

特別要注意的是：

• 以}};pop開始的行，終結前面行的排版應用了3次排版規則，對應3層嵌套where語句。
• 在case表達式和元組之間where語句後又添加了一個右括號，因為系統檢測到元組的結束，意味着語法case項也要結束。
• 添加最後一個右括號是因為，最後一列是對end-of-file符號的0級縮進。