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级缩进。