Ocamllex 指南

原译文发布在ocaml.cn , 这里的blog不支持html的说,郁闷
Ocamllex 改编者: SooHyoung Oh 
此指南讲解怎么使用Ocaml语言分发包所带的ocamllex.
此文档从 flex 手册借签了很多.
请把你的意见和建议发至
此指南还在编写当中，最新的版本放在 http://pllab.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamllex-tutorial/index.html.
此指南的姐妹篇ocamlyacc指南在 http://pllab.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamlyacc-tutorial/index.html.
下载此文档的源文件: ocamllex-tutorial-src.tar.gz. 打印文件: pdf (A4 纸张) , 还有网页文件: html (tar.gz).
此文档中用到的示例源文件: ocamllex-examples.tar.gz.
最近更新: 2004-11-16
目录
    简介
    一些简单示例
    格式化输入文件
    模式
    输入是怎样匹配的
    动作
6.1. 位置
    生成扫描器 The generated scanner
    开始条件
    与 ocamlyacc的接口
    选项
    使用技巧
11.1. 关键字哈希表
11.2. 嵌套注释
    示例
12.1. 翻译
12.2. 字数统计
12.3. Toy 语言
    许可
13.1. flex 手册许可
13.2. Ocamllex 修订版的版权和许可注意事项



第1章. 简介
ocamllex 是一个用来生成扫描器的工具. 扫描器是一个从文本中识别词法模式的程序. ocamllex 读取指定的文件,此文件包含一个生成扫描器的描述。 这个描述以正则表达式和Ocaml代码对( 译注,即<正则表达式, Ocal代码>,同后面章节的模式-代码)的格式给出, 此格式被称为 规则(rules). ocamllex生成一个Ocaml代码的源文件，此文件定义了词法分析器的函数。经编译和链接，可以产生一个可执行文件。当可执行文件运行时, 它将分析输入文件中是否出现描述中的正则表达式。如果找到了一个，则执行相应的Ocaml代码.
比如你以一个名为 lexer.mll的输入文件作为参数，执行下面的命令
ocamllex lexer.mll
你将得到一个名为 lexer.ml的文件，此文件是用Caml写的词法分析器.
————————————————————————————————————————————————
第2章. 一些简单示例
第一批示例将使你对 ocamllex的使用有一些感性的认识. 下面的 ocamllex 输入语句定义了一个扫描器.此扫描器每碰到”current_directory”字符串就会把它替换成当前目录:
{}
rule translate = parse
  | "current_directory"{print_string (Sys.getcwd()); translate lexbuf }
  | _ as c      {print_char c; translate lexbuf }
  | eof         {exit 0}
在第一个规则里, “currentdirectory” 是 模式(pattern) 而两个大括号括起来的是相应的 动作(action). 通过此规则, 扫描器每匹配到一个”currentdirectory”字符串,就会执行相应的动作。此动作会显示当前目录名,并再次调用扫描器.递归调用自身是必要的，因为扫描器还要做其它的工作。
没有通过 ocamllex扫描器匹配的任何文字都会产生一个失败信息: “lexing: empty token”, 所以你必须提供后面的两条规则.第二条规则将进屏幕上显示任何没有匹配到第一条规则的字符. 第三条规则规定了,当碰到文件结尾符(eof)退出程序. So the net effect of this scanner is to copy its input file to its output with each occurrence of “current_directory” expanded. 第一行的 “{ }”是首段和其它段的分界符.
下面是另外一个简单示例:
{
  let num_lines = ref 0
  let num_chars = ref 0
}
rule count = parse
  | '\n'        {incr num_lines; incr num_chars; count lexbuf }
  | _           {incr num_chars; count lexbuf }
  | eof         {()}
{
  let main ()=
    let lexbuf = Lexing.from_channelstdin in
    count lexbuf;
    Printf.printf"# of lines = %d, # of chars = %d\n"!num_lines !num_chars
  let _ = Printexc.printmain ()
}
此扫描器计算输入的字符数和行数.(直到最后报告时,它才产生输出结果). 首段声明了两个全局变量: “numlines” 和”numchars”。 扫描器count函数之中的代码和最后部分由大括号括起来的 尾 段都可以访问得到它们. 存在三条规则,一条匹配换行符(“\n”) 且增加行数和字符数, 一条匹配除换行符外的其它的字符(由正则表达式”_”指出). At the end of file, the scanner function count returns unit.
一个更复杂的示例:
(* scanner for a toy language *)
{
  open Printf
}
let digit = ['0'-'9']
let id = ['a'-'z']['a'-'z' '0'-'9']*
rule toy_lang = parse
  | digit+ as inum
    {printf "integer: %s (%d)\n"inum (int_of_string inum);
      toy_lang lexbuf
    }
  | digit+ '.' digit* as fnum
    {printf "float: %s (%f)\n"fnum (float_of_string fnum);
      toy_lang lexbuf
    }
  | "if"
  | "then"
  | "begin"
  | "end"
  | "let"
  | "in"
  | "function"as word
    {printf "keyword: %s\n"word;
      toy_lang lexbuf
    }
  | id as text
    {printf "identifier: %s\n"text;
      toy_lang lexbuf
    }
  | '+'
  | '-'
  | '*'
  | '/' as op
    {printf "operator: %c\n"op;
      toy_lang lexbuf
    }
  | '{' [^ '\n']* '}'   {toy_lang lexbuf }(* eat up one-line comments *)
  | [' ' '\t' '\n']{toy_lang lexbuf }(* eat up whitespace *)
  | _ as c
    {printf "Unrecognized character: %c\n"c;
      toy_lang lexbuf
    }
  | eof     {}
{
  let main ()=
    let cin =
      if Array.lengthSys.argv> 1
      then open_in Sys.argv.(1)
      else stdin
    in
    let lexbuf = Lexing.from_channelcin in
    toy_lang lexbuf
  let _ = Printexc.printmain ()
}
这是一个简单扫描器的开端,此扫描器扫描一种语言,区分不同的标记(token) 并汇报它发现了什么。
这个示例的细节会在以后的章节中再解释.



第3章. 格式化输入文件
ocamllex 输入文件由四段组成: 首段, 定义段, 规则段 和 尾段 .
(* 首段 *)
    {header }
    (* 定义段 *)
    let ident = regexp
    let ...
    (* 规则段 *)
    rule entrypoint [arg1... argn]= parse
      | pattern {action }
      | ...
      | pattern {action }
    and entrypoint [arg1... argn]= parse
      ...
    and ...
    (* 尾段 *)
    {trailer }
注释和Caml一样,由(* 和 *)间隔.
The 首段 和 规则段 是必须的, 而 定义段 和 尾段 是可选的.
首段 和 尾段 由大括号括起来,并且它们里面可以包含任意的Caml代码. At the beginning of the output file, the header text is copied as is while the trailer text is copied at the end of the output file. 例如: 你可以在首段中写上open命令(译注: 打开Ocaml模块的函数)和一些输助函数的代码.
定义段包括一些简单的ident 定义,用来简化扫描器的规范. Ident 定义有如下格式:
let ident = regexp
    let ...
“ident” 必须是Caml值的合法标识符(以小写字母开头). 例如:
let digit = ['0'-'9']
    let id = ['a'-'z']['a'-'z' '0'-'9']*
定义了 “digit” 匹配一个简单数字的正则表达式, “id” 匹配一个后面跟着零个或多个字母或数字的字母. 其后的一个引用(译注: 就是对digit的引用):
digit+ "."digit*
和以下的表示同义:
['0'-'9']+ "."['0'-'9']*
都匹配一个或多个数字后面跟一个’.’, 后面再跟零个或者多个数字.
ocamllex 输入文件的 规则段 包含类似以下格式的一系列入口:
rule entrypoint [arg1... argn]= parse
      | pattern {action }
      | ...
      | pattern {action }
    and ...
第一个在parse后面的 | 是可选的.
每个入口都一系列的模式-动作(pattern-action)对组成:
| pattern {action }
这里动作要由大括号括起来.
要进一步了解模式和动作，请看下面的章节.



第4章. 模式
The patterns in the input are written using regular expressions in the style of lex, with a more Caml-like syntax. These are:
class="geshifilter"'c'
  匹配字符'c'.这个字符常量和Object Caml字符的语法一样.
 
  _ 
  (下划线)匹配任何字符.
 
  eof
  匹配文件结尾符.
 
  "foo"
  文本串"foo". 其语法和Object Caml 字符串常量一样.
 
 
  ['x' 'y' 'z']
  字符集; 在这儿, 此模式匹配一个'x',或一个'y',或一个'z'.
 
 
  ['a' 'b' 'j'-'o' 'Z']
  带范围的字符集.'c1' - 'c2'范围,即包括c1至c2之间的所有字符. 在这儿, 此模式匹配一个'a',或一个'b',或'j'至'o'的任何一个字符,或一个'Z'.
 
 
  [^ 'A'-'Z']
  一个"拒绝字符集",即任何不含此类的字符.此处表示任何一个非大写字母的字符.
 
 
  [^ 'A'-'Z' '\n']
  任何一个非大写字母的字符，或者一个换行符.(译注: 前者其实包括后者,换行符)
 
 
  r*
  零个或多个r. r代表任何与正则表达式.
 
 
  r+
  一个或多个r. r代表任何与正则表达式.
 
 
  r?
  零个或一个r. r代表任何与正则表达式.(即可选的r)
 
 
  ident
  "ident"的意义由前面的let ident = regexp 定义.
 
 
  (r)
  匹配一个r, 圆括号用来改变优先级(见下面的例子).
 
 
  rs
  正则表达式r后面跟着正则表达式s, 称作"连接".
 
 
  r|s
  一个r或者一个s
 
 
  r#s
  匹配两个指定集合的差集.
 
 
  r as ident
  把匹配r的字符串绑定到标识符ident.
上面列出的正则表达式根据优先级排下来, 最顶端的是最高优先级的, 最底端的是最低优先级的. ‘*’和’+’拥有最高优先级，接着是’?’,’连接’，和’as’. 例如:
"foo"| "bar"*
与下面的语义一样:
("foo")|("bar"*)
因为’*’的优先级要比交替 (‘|’)的高,所以这个模式匹配: 一个字符串”foo”,或者零个或多个”bar”字符串.
要匹配零个或多个”foo”或”bar”字符串，如下:
("foo"|"bar")*
像上面”[^ ‘A’-‘Z’]”这种”拒绝字符集”的例子将 A negated character set such as the example “[^ ‘A’-‘Z’]” above will match a newline unless “\n” (or an equivalent escape sequence) is one of the characters explicitly present in the negated character set (e.g., “[^ ‘A’-‘Z’ ‘\n’]”). This is unlike how many other regular expression tools treat negated character set, but unfortunately the inconsistency is historically entrenched. Matching newlines means that a pattern like [^”]* can match the entire input unless there’s another quote in the input.



第5章. 输入是怎样匹配的
当生成描描器运行之时,它会分析输入文本中哪些字符串匹配了它所定义的任何模式.如果它发现有多个匹配，则会选择匹配文字最多的那个(这就是”最长 匹配原则”). 如果它发现两个或两个以上长度也一样的匹配, 那在ocamllex输入文件(译注,指*.mll文件,默认为lexer.mll)定义较前的那个规则将被匹配. (这就是”最先匹配原则”).
Once the match is determined, the text corresponding to the match (被称为标记(译注,token有的书中译做单词)) is made available in the form of a string. The action corresponding to the matched pattern is then executed (a more detailed description of actions follows), and then the remaining input is scanned for another match.
If no match is found, the scanner raises the Failure “lexing: empty token” exception.
Now, let’s see the examples which shows how the patterns are applied.
rule token = parse
  | "ding" {print_endline "Ding"}       (* "ding" 模式 *)
  | ['a'-'z']+ as word              (* "word" 模式*)
        {print_endline ("Word: "^ word)}
  ...
When “ding” is given as an input, the ding and word pattern can be matched. ding pattern is selected because it comes before word pattern. So if you code like this:
rule token = parse
  | ['a'-'z']+ as word              (* "word" 模式 *)
        {print_endline ("Word: "^ word)}
  | "ding" {print_endline "Ding"}       (* "ding" 模式 *)
  | ...
ding 模式将失去作用了.
In the following example, there are three patterns: ding, dong and dingdong.
rule token = parse
  | "ding" {print_endline "Ding"}       (* "ding" 模式 *)
  | "dong" {print_endline "Dong"}       (* "dong" 模式 *)
  | "dingdong" {print_endline "Ding-Dong"}  (* "dingdong" 模式 *)
  ...
When “dingdong” is given as an input, there are two choices: ding + dong pattern or dingdong pattern. But by the “longest match” principle, dingdong pattern will be selected.
Though the “shortest match” principle is not used so frequently, ocamllex supports it. If you want to select the shortest prefix of the input, use shortest keyword instead of the parse keyword. The “first match” principle holds still with the “shortest match” principle.



第6章. 动作
Each pattern in a rule has a corresponding action, which can be any arbitrary Ocaml expression. For example, here is the specification for a program which deletes all occurrences of “zap me” from its input:
{}
rule token = parse
  | "zap me"   {token lexbuf }   (* ignore this token: no processing and continue *)
  | _ as c  {print_char c; token lexbuf }
这儿有一个程序, 它会把多个空格或制表符压缩成单个空格, 且会剔除在行结尾处的空白. Here is a program which compresses multiple blanks and tabs down to a single blank, and throws away whitespace found at the end of a line:
{}
rule token = parse
  | [' ' '\t']+     {print_char ' '; token lexbuf }
  | [' ' '\t']+ '\n'    {token lexbuf }     (* ignore this token *)
Actions can include arbitrary Ocaml code which returns a value. Each time the lexical analyzer function is called it continues processing tokens from where it last left off until it either reaches the end of the file.
Actions are evaluated after the lexbuf is bound to the current lexer buffer and the identifer following the keyword as to the matched string. The usage of lexbuf is provided by the Lexing standard library module;
class="geshifilter"*
 
  Lexing.lexeme lexbuf
 
  Return the matched string.
*
 
  Lexing.lexeme_char lexbuf n
 
  Return the nth character in the matched string. The index number of the first character starts from 0.
*
 
  Lexing.lexeme_start lexbuf
 
  Lexing.lexeme_end lexbuf
 
  Return the absolute position in the input text of the beginning/end of the matched string. The position of the first character is 0.
*
 
  Lexing.lexeme_start_p lexbuf
 
  Lexing.lexeme_end_p lexbuf
 
  (Since Ocaml 3.08) Return the position of type position (See Position).
*
 
  entrypoint [exp1... expn] lexbuf
 
  Call the other lexer on the given entry point. Notice that lexbuf is the last argument.
6.1. 位置
Since Ocaml 3.08
The position information on scanning the input text is recorded in the lexbuf which has a field lexcurrp of the type position:
type position = {
     pos_fname : string;    (* 文件名 file name *)
     pos_lnum : int;        (* 行数 line number *)
     pos_bol : int;     (* 到行头的偏移量 the offset of the beginning of the line *)
     pos_cnum : int;        (* 到此位置的偏移量 the offset of the position *)
  }
The value of posbol field is the number of characters between the beginning of the file and the beginning of the line while the value of poscnum field is the number of characters between the beginning of the file and the position.
The lexing engine manages only the poscnum field of lexbuf.lexcurr_p with the number of characters read from the start of lexbuf. So you are reponsible for the other fields to be accurate. Typically, whenever the lexer meets a newline character, the action contains a call to the following function:
let incr_linenum lexbuf =
    let pos = lexbuf.Lexing.lex_curr_pin
    lexbuf.Lexing.lex_curr_p<- {pos with
      Lexing.pos_lnum= pos.Lexing.pos_lnum+ 1;
      Lexing.pos_bol= pos.Lexing.pos_cnum;
    }
  ;;



第7章. 生成扫描器
当调用 ocamllex lex.mll 时, ocamllex 的输出文件是 lex.ml. 这个生成的文件包含The generated file contains the 扫描函数, 一些用来匹配标记的表，和一些输助程序. 扫描函数 的声明类似下面所示:
let entrypoint [arg1... argn]lexbuf =
  ...
and ...
函数 entrypoint 有 n + 1 个参数.其中 n 个参数是从规则段的定义得到的. 而生成的扫描函数会多一个类型为Lexing.lexbuf，叫作lexbuf的参数.此参数是扫描函数的最后一个参数.
每当 entrypoint被调用时, 它会扫描来自lexbuf 参数的标记. 当它发现一个模式刚好匹配时, 执行对应的动作并返回. 如果你想做完动作之后,继续进行词法分析,那你得递归地调用扫描函数.



第8章. 开始条件
ocamllex 提供一个条件激活规则的机置。当你想激活其它规则, 只要调用其它的入口(entrypoint) 函数. 例如, 下面有两条规则, 一条是用来找出标记, 另一条用来跳过注释.
{}
rule token = parse
  | [' ' '\t' '\n']+
    (* skip spaces *)
    {token lexbuf }
  | "(*"
    (* activate "comment" rule *)
    {comment lexbuf }
  ...
and comment = parse
  | "*)"
    (* go to the "token" rule *)
    {token lexbuf }
  | _
    (* skip comments *)
    {comment lexbuf }
  ...
当生成扫描器在 token 规则时碰到注释开始标记”(“时 ,它会激活另外一个规则comment. 当它在 comment规则碰到注释结束标记 “)” 时,它会回过来扫描token 规则.



第9章. 与 ocamlyacc ocamlyacc的接口
ocamllex 的一个重要用途就是和 ocamlyacc 语法分析器的生成器协作。 ocamlyacc 分析器调用其中的 扫描函数 来查找下一个输入标记. 这个函数会返回下一个标记的类型和值. 用ocamllex 配合 ocamlyacc时, 扫描函数得使用分析器模块来识别标记类型.标记类型定义在ocamlyacc 输入文件的`%tokens’属性中. 例如, 如果 ocamlyacc的输入文件名是 parse.mly 且其中有一个标记是”NUMBER”型,扫描器的部分代码将会如下:
{
  open Parse (* 译注, 这里导入分析器模块 *)
}
rule token = parse
  ...
  | ['0'-'9']+ as num {NUMBER (int_of_string num)}
  ...



第10章. 选项
ocamllex 有以下几个选项:
class="geshifilter"-o 输出文件名
  当 ocamllex 以 "ocamllex lexer.mll"的形式调用时, ocamllex 默认会生成 lexer.ml. 你可以用-o 选项来改变输出文件名.
 
  -ml
  By default, ocamllex produces code that uses the Caml built-in automata interpreter. Using this option, the automaton is coded as Caml functions. This option is useful for debugging ocamllex, but it's not recommended for production lexers.
 
  -q
  ocamllex 默认会输出生成信息到标准输出设备上, 但如果你使用 -q 选项,它们就会被禁止.



第11章. 使用技巧
11.1. 关键字哈希表
ocamllex 生成的状态转换数被限制在最多只能有32767个.如果你使用过多的转换，比如过多的关键字, ocamllex 会产生如下错误信息:
camllex: transition table overflow, automaton is too big
它告诉你，你的词法定义太复杂了. 为了让生成的自动机简单些, 你得使用关键字哈希表:
{
  let keyword_table = Hashtbl.create72
  let _ =
    List.iter(fun (kwd, tok)-> Hashtbl.addkeyword_table kwd tok)
              [("keyword1", KEYWORD1);
                ("keyword2", KEYWORD2);
        ...
              ]
}
rule token = parse
  | ...
  | ['A'-'Z' 'a'-'z']['A'-'Z' 'a'-'z' '0'-'9' '_']* as id
               {try
                Hashtbl.findkeyword_table id
                 with
            Not_found -> IDENT id
        }
  | ...
11.2. 嵌套注释
很多语言像Ocaml都支持嵌套的注释,它可以通过如下形式来实现扫描:
{}
rule token = parse
  | "(*"       {print_endline "comments start"; comments 0lexbuf }
  | [' ' '\t' '\n']{token lexbuf }
  | ['a'-'z']+ as word
        {Printf.printf"word: %s\n"word; token lexbuf }
  | _ as c  {Printf.printf"char %c\n"c; token lexbuf }
  | eof     {raise End_of_file }
and comments level = parse
  | "*)"   {Printf.printf"comments (%d) end\n"level;
          if level = 0then token lexbuf
          else comments (level-1)lexbuf
        }
  | "(*"   {Printf.printf"comments (%d) start\n"(level+1);
          comments (level+1)lexbuf
        }
  | _       {comments level lexbuf }
  | eof     {print_endline "comments are not closed";
          raise End_of_file
        }
当扫描器通过 token规则，分析到注释开始标记 “(” , 它将进入 comments规则，且此时等级level为0. 当所有的注释都关闭的时候, token规则又将被调用. 每当在输入文本中碰到一个 注释开始标记 “(” 时, 注释嵌套等级level将会增加一。
如果扫描器碰到注释结束 标记 “*)”时, 它会检查注释嵌套等级.当嵌套等级level不是0, level会减一,并继续扫描注释. 当所有的注释都关闭，即level为0时,它会返回到token规则.



第12章. 示例
这章将以完整的形式展现示例.一些是改编前面章节的代码片段的.This chapter includes examples in complete form. Some are revised from the code fragments of the previous chapters.
12.1. 翻译
这个例子把”current_directory”翻译成 当前路径.
{}
rule translate = parse
  | "current_directory"{print_string (Sys.getcwd())}
  | _ as c      {print_char c }
  | eof         {exit 0}
{
  let main ()=
    let lexbuf = Lexing.from_channelstdin in
    while true do
      translate lexbuf
    done
  let _ = Printexc.printmain ()
}
12.2. 字数统计
在这个例子中,如果给定文件了文件名，它会输出此文件的行数、字数以及字符数. 如果没有给定命令行参数,它将会以标准输入的相应信息输出.
{}
rule count lines words chars = parse
  | '\n'        {count (lines+1)words (chars+1)lexbuf }
  | [^ ' ' '\t' '\n']+ as word
        {count lines (words+1)(chars+ String.lengthword)lexbuf }
  | _       {count lines words (chars+1)lexbuf }
  | eof     {(lines, words, chars)}
{
  let main ()=
    let cin =
      if Array.lengthSys.argv> 1
      then open_in Sys.argv.(1)
      else stdin
    in
    let lexbuf = Lexing.from_channelcin in
    let (lines, words, chars)= count 000lexbuf in
    Printf.printf"%d lines, %d words, %d chars\n"lines words chars
  let _ = Printexc.printmain ()
}
12.3. Toy 语言
在这个例子中, 扫描函数toy_lang返回标记类型的值, 但main函数不做相关的事情.
{
  open Printf
  let create_hashtable size init =
    let tbl = Hashtbl.createsize in
    List.iter(fun (key, data)-> Hashtbl.addtbl key data)init;
    tbl
  type token =
    | IF
    | THEN
    | ELSE
    | BEGIN
    | END
    | FUNCTION
    | ID of string
    | OP of char
    | INT of int
    | FLOAT of float
    | CHAR of char
  let keyword_table =
    create_hashtable 8[
      ("if", IF);
      ("then", THEN);
      ("else", ELSE);
      ("begin", BEGIN);
      ("end", END);
      ("function", FUNCTION)
    ]
}
let digit = ['0'-'9']
let id = ['a'-'z' 'A'-'Z']['a'-'z' '0'-'9']*
rule toy_lang = parse
  | digit+ as inum
    {let num = int_of_string inum in
      printf "integer: %s (%d)\n"inum num;
      INT num
    }
  | digit+ '.' digit* as fnum
    {let num = float_of_string fnum in
      printf "float: %s (%f)\n"fnum num;
      FLOAT num
    }
  | id as word
    {try
        let token = Hashtbl.findkeyword_table word in
        printf "keyword: %s\n"word;
        token
      with Not_found ->
        printf "identifier: %s\n"word;
        ID word
    }
  | '+'
  | '-'
  | '*'
  | '/' as op
    {printf "operator: %c\n"op;
      OP op
    }
  | '{' [^ '\n']* '}'   (* 消除一行注释*)
  | [' ' '\t' '\n'](* 消除空白 *)
    {toy_lang lexbuf }
  | _ as c
    {printf "Unrecognized character: %c\n"c;
      CHAR c
    }
  | eof
    {raise End_of_file }
{
  let rec parse lexbuf =
     let token = toy_lang lexbuf in
     (* 在此例中啥事也不做 *)
     parse lexbuf
  let main ()=
    let cin =
      if Array.lengthSys.argv> 1
      then open_in Sys.argv.(1)
      else stdin
    in
    let lexbuf = Lexing.from_channelcin in
    try parse lexbuf
    with End_of_file -> ()
  let _ = Printexc.printmain ()
}