用OCaml的进行形式文法解析

本来是想写这篇的，因为OCaml确实在这一个领域很出色的语言。虽然ML代码结构看上去比C语言要清晰易读许多，不过说实在的自己的大脑还是实在没养成按照写公式一样的写出代码来。结果就是在FP中还是用了已经比较熟悉的Scheme进行试验了，感觉写Scheme就像玩橡皮泥，在拿捏和拼装之后，一个原本还较陌生的逻辑就写出来了。这里的意思是说对于我这篇所要达到的目的，还是用Scheme给先写出来的。这不是关于语言特性的，而是关于思维的波长正好和问题一致而已。如果一定要牵涉到语言层面的影响的话，只能说我是在问题和语言都初次为一个情景而组合的，暂时还达不到追求美感的境界。就像听音乐，不管音乐是好好听，音质高就会很有震撼了。

于是本文成了草稿的回收了，那个另一个版本的半成品（至少是半成品，有个完整的结构也好啊）写在别出了，过段时间在整理过来。当然，不要指望这些文字里有什么东西，个人日志什么的（至少像我这里的几篇）写起来还是很随意的。

这里所用的示例是最简单的整数四则运算表达式的处理，目的包括求值和转化为前缀形式的语法树。



在OCaml手册中有对ocamllex/ocamlyacc的描述，并给出了这样一个例子。虽然写法上还是是依照lex/yacc的，不过鉴于OCaml的语言风格所以看起来似乎要直观一些。

于是这里就直接大篇幅的引用过来了。

http://caml.inria.fr/pub/docs/manual-ocaml/manual026.html
12.6 A complete example
The all-time favorite: a desk calculator. This program reads arithmetic expressions on standard input, one per line, and prints their values.

Here is the grammar definition:
/* File parser.mly */
%token INT
%token PLUS MINUS TIMES DIV
%token LPAREN RPAREN
%token EOL
%left PLUS MINUS /* lowest precedence */
%left TIMES DIV /* medium precedence */
%nonassoc UMINUS /* highest precedence */
%start main /* the entry point */
%type main
%%
main:
expr EOL { $1 }
;
expr:
INT { $1 }
| LPAREN expr RPAREN { $2 }
| expr PLUS expr { $1 + $3 }
| expr MINUS expr { $1 - $3 }
| expr TIMES expr { $1 * $3 }
| expr DIV expr { $1 / $3 }
| MINUS expr %prec UMINUS { - $2 }
;

Here is the definition for the corresponding lexer:
(* File lexer.mll *)
{
open Parser (* The type token is defined in parser.mli *)
exception Eof
}
rule token = parse
[' ' '\t'] { token lexbuf } (* skip blanks *)
| ['\n' ] { EOL }
| ['0'-'9']+ as lxm { INT(int_of_string lxm) }
| '+' { PLUS }
| '-' { MINUS }
| '*' { TIMES }
| '/' { DIV }
| '(' { LPAREN }
| ')' { RPAREN }
| eof { raise Eof }
Here is the main program, that combines the parser with the lexer:

(* File calc.ml *)
let _ =
try
let lexbuf = Lexing.from_channel stdin in
while true do
let result = Parser.main Lexer.token lexbuf in
print_int result; print_newline(); flush stdout
done
with Lexer.Eof ->
exit 0

To compile everything, execute:
ocamllex lexer.mll # generates lexer.ml
ocamlyacc parser.mly # generates parser.ml and parser.mli
ocamlc -c parser.mli
ocamlc -c lexer.ml
ocamlc -c parser.ml
ocamlc -c calc.ml
ocamlc -o calc lexer.cmo parser.cmo calc.cmo

这里把四种运算符都写在定义层次的产生式上了，然后额外的指定了结合顺序和优先级。



在OCaml中另一个用于功能类似的模块是CamlP4，作为库它基于Stream类型提供了用于词法与语法解析的功能，并同时自身也在OCaml中充当了预处理的角色。

递归下降的形式可以用camlp4可以写为这样的形式：
http://www.codecodex.com/wiki/index.php?title=Recursive_descent_parsing
(* File parser.ml *)
let rec factor = parser
| [< ''('; e = expr; '')' >] -> e
| [< 'c >] -> int_of_string (String.make 1 c)
and term = parser
| [< e1 = factor; e = term_aux e1 >] -> e
and term_aux e1 = parser
| [< ''*'; e2 = term >] -> e1 * e2
| [< ''/'; e2 = term >] -> e1 / e2
| [< >] -> e1
and expr = parser
| [< e1 = term; e = expr_aux e1 >] -> e
and expr_aux e1 = parser
| [< ''+'; e2 = expr >] -> e1 + e2
| [< ''-'; e2 = expr >] -> e1 - e2
| [< >] -> e1
let rec statement = parser
| [< e = expr; '';'; ''.'; stream >] ->
Printf.printf "= %d\n%!" e;
statement stream
let rec read() = match input_char stdin with
| ' ' | '\t' | '\n' -> [< read() >]
| c -> [< 'c; read() >]
let () = statement (read())

然后执行如下的编译命令
ocamlc -g -dtypes -pp camlp4o parser.ml -o parser

其原理仍然是基本的递归下降文法解析，特别的地方在于parser是对stream进行的模式匹配和处理，使用语言糖使得函数的定义和生成式的书写有申明式编程的感觉。其他语言如Haskell里也有类似的模块存在，语法糖长相的差异不是问题的说。



关于递归下降语法解析，编译原理方面的书（TC++PL里怎么也会有呢？）都会给出示例的，比如像下面这个：
http://en.wikipedia.org/wiki/Recursive_descent_parser
What follows is an implementation of a recursive descent parser for the above language in C. The parser reads in source code, and exits with an error message if the code fails to parse, exiting silently if the code parses correctly.
Notice how closely the predictive parser below mirrors the grammar above. There is a procedure for each nonterminal in the grammar. Parsing descends in a top-down manner, until the final nonterminal has been processed. The program fragment depends on a global variable, sym, which contains the next symbol from the input, and the function getsym, which updates sym when called.
The implementations of the functions getsym and error are omitted for simplicity.

typedef enum {ident, number, lparen, rparen, times, slash, plus,
minus, eql, neq, lss, leq, gtr, geq, callsym, beginsym, semicolon,
endsym, ifsym, whilesym, becomes, thensym, dosym, constsym, comma,
varsym, procsym, period, oddsym} Symbol;
Symbol sym;
void getsym(void);
void error(const char msg[]);
void expression(void);
int accept(Symbol s) {
if (sym == s) {
getsym();
return 1;
}
return 0;
}
int expect(Symbol s) {
if (accept(s))
return 1;
error("expect: unexpected symbol");
return 0;
}
void factor(void) {
if (accept(ident)) {
;
} else if (accept(number)) {
;
} else if (accept(lparen)) {
expression();
expect(rparen);
} else {
error("factor: syntax error");
getsym();
}
}
void term(void) {
factor();
while (sym == times || sym == slash) {
getsym();
factor();
}
}
void expression(void) {
if (sym == plus || sym == minus)
getsym();
term();
while (sym == plus || sym == minus) {
getsym();
term();
}
}
void condition(void) {
if (accept(oddsym)) {
expression();
} else {
expression();
if (sym == eql || sym == neq || sym == lss || sym == leq || sym == gtr || sym == geq) {
getsym();
expression();
} else {
error("condition: invalid operator");
getsym();
}
}
}
void statement(void) {
if (accept(ident)) {
expect(becomes);
expression();
} else if (accept(callsym)) {
expect(ident);
} else if (accept(beginsym)) {
do {
statement();
} while (accept(semicolon));
expect(endsym);
} else if (accept(ifsym)) {
condition();
expect(thensym);
statement();
} else if (accept(whilesym)) {
condition();
expect(dosym);
statement();
}
}
void block(void) {
if (accept(constsym)) {
do {
expect(ident);
expect(eql);
expect(number);
} while (accept(comma));
expect(semicolon);
}
if (accept(varsym)) {
do {
expect(ident);
} while (accept(comma));
expect(semicolon);
}
while (accept(procsym)) {
expect(ident);
expect(semicolon);
block();
expect(semicolon);
}
statement();
}
void program(void) {
getsym();
block();
expect(period);
}

在这个解析过程中，是根据下一位的单词进行解析状态的判断的。
比如说在读到1+1时，下一位是+（1+1+）或者*（1+1*）就要按照不同的语法树解析。


关于OCaml做这方面应用的还有一个优势是ADT（抽象数据类），很方便用来描述类型的并级。
并且OCaml的纯静态类型是在编译时擦除变量类型的，这也一个简单且基础的类型机制。
此外将虽然句法解析的能力包括了词法解析，但是将两者分开来的话能都使得实现变得简单。
比如整数运算到浮点数的扩充，就可以放在词法解析的过程中先识别。
上面的示例还有一些可以扩充的方面，比如顺便增加一下条件语句和赋值语句什么的。

那么就顺便说下OCaml中类型的复合，有：
Tuple/Recode —— int*char，{num: int; denum: int}；
Enum/Union —— Int|Char，Int of int；
Variant Type —— 'a t；
Module/Class —— 有点像C++中的模板
Signature —— 这个是作为参数使用的类型
其中类型用tpye定义，并允许定义中递归。
此外的arrary和list类型可以看作已有复合方式的再一次复合，虽然说会单独被实现的。
使用ADT的好处是在解析文本后生成的节点都用类型的Union来表示，
至于OCaml的特有特性Polymorphic variants则可让系统自行定义类型的联合。


最后强调一点，一定要看到下面这句话哦，不然出什么问题就会麻烦了
——以上的内容仅娱乐目的，不保证内容一定正确哦。
http://rosettacode.org/wiki/Y_combinator