P96 - 检查 Ada 标识符语法
Syntax checking for Ada identifiers
官方模块：
Problems.P96核心函数：isIdentifier
语法规则
标识符必须以英文字母开头，之后可以包含字母、数字和下划线；下划线不能连续，也不能位于末尾。
实现
方法一：递归解析
1isIdentifier :: String -> Bool
2isIdentifier [] = False
3isIdentifier (first:rest) = asciiLetter first && consume False rest
4 where
5 consume previousUnderscore [] = not previousUnderscore
6 consume previousUnderscore (c:cs)
7 | asciiLetter c || asciiDigit c = consume False cs
8 | c == '_' && not previousUnderscore = consume True cs
9 | otherwise = False
10
11asciiLetter c = c `elem` ['A'..'Z'] || c `elem` ['a'..'z']
12asciiDigit c = c `elem` ['0'..'9']
状态 previousUnderscore 记录前一个字符是否为下划线；输入结束时它还为真，就说明标识符以下划线结尾。
方法二：按下划线分组
1isIdentifier :: String -> Bool
2isIdentifier input = case splitUnderscores input of
3 [] -> False
4 firstGroup : groups ->
5 not (null firstGroup)
6 && asciiLetter (head firstGroup)
7 && all validGroup (firstGroup : groups)
8 where
9 validGroup group =
10 not (null group) && all (\c -> asciiLetter c || asciiDigit c) group
11
12splitUnderscores :: String -> [String]
13splitUnderscores = foldr step [""]
14 where
15 step '_' groups = "" : groups
16 step c (group : groups) = (c : group) : groups
17 step _ [] = []
连续下划线、开头下划线或结尾下划线都会产生空分组，因此只需检查每组非空，再检查组内字符。首组还要额外保证第一个字符是字母。这个实现不依赖正则表达式包。
方法对比
| 方法 | 状态 |
|---|---|
| 递归解析 | 记录前一个字符是否为下划线 |
| 分组验证 | 用空分组表示非法下划线位置 |
测试
1>>> isIdentifier "this_is_a_long_identifier"
2True
3>>> isIdentifier "This_ends_in_an_underscore_"
4False
5>>> isIdentifier "This__has__two__underscores"
6False
7>>> isIdentifier "1234"
8False
9>>> isIdentifier "Fibonacci_sequence_1_1_2_3_5_8"
10True
算法单次扫描字符串，时间复杂度 。