如何使用ocamllex/Menhir基于空格正确进行分词？

我正在用OCaml编写一个简单的Shell，语法规则如下：

/*
  program: command*
  command: WORD WORD* redirection*
  redirection: NUMBER? > FILENAME | < FILENAME
*/

对应的lexer代码：

let whitespace = [' ' '\t']+
let word = [^ '<' '>']+
let filename = [^ '\x00']+
let number = ['0' - '9']+
let newline = '\n' | "\r\n"

rule token = parse
| whitespace | newline { token lexbuf }
| number as lxm { NUMBER(int_of_string lxm) }
| word as lxm { WORD lxm }
| filename as lxm { FILENAME lxm }
| eof { EOF } 
| _ as lxm { raise @@ SyntaxError("Unexpected char" ^ (String.make 1 lxm)) }

Menhir解析器代码：

%{
    open Ast
%}

%token <int> NUMBER
%token <string> WORD
%token <string> FILENAME
%token LEFTARROW
%token RIGHTARROW
%token EOF
%start program

%type <Ast.redirection> redirection
%type <Ast.command> command
%type <Ast.program> program

%%

redirection:
| LEFTARROW f = FILENAME { 0, f }
| opt = option(NUMBER) RIGHTARROW f = FILENAME { 
    match opt with
    | None -> 1, f
    | Some n -> n, f
 }

command:
| executable = WORD args = list(WORD) redirections = list(redirection) { {executable; args; redirections} }

program:
| commands = list(command) EOF { commands }

工具函数parse_string：

let parse_string program_string =
  let lexbuf = Lexing.from_string program_string in
  Parser.program Lexer.token lexbuf

AST定义：

type redirection = int * string
  
type command = {
  executable : string;
  args : string list;
  redirections : redirection list;
}

type program = command list

输入字符串"ls -l"时，我期望得到{executable = "ls"; args = ["-l"]; redirections = []}，但实际得到单个WORD"ls -l"。修改word规则为[^ '<' '>' ' ' '\t']后，又出现"foo bar"被识别为FILENAME而非两个WORD的问题——这是因为ocamllex遵循最长匹配规则，宽泛的filename规则会优先匹配更长的字符串。现在需要解决如何正确实现基于空格的分词，同时支持带引号的文件名。

1. 重构词法规则 #

ocamllex的匹配逻辑是先选最长匹配，长度相同时选定义靠前的规则，所以核心问题是filename规则范围太广，覆盖了普通WORD的场景。重新定义规则如下：

let whitespace = [' ' '\t']+
let newline = '\n' | "\r\n"
let number = ['0'-'9']+
(* 普通无空格WORD：排除空白符、箭头、引号 *)
let plain_word = [^ ' ' '\t' '<' '>' '"' '\'']+
(* 带引号的字符串：支持双/单引号包裹，内部允许空格，暂不处理转义 *)
let quoted_word = '"' [^ '"']* '"' | '\'' [^ '\'']* '\''
(* WORD包含普通词和带引号的词 *)
let word = plain_word | quoted_word

rule token = parse
| whitespace | newline { token lexbuf }
| number as lxm { NUMBER(int_of_string lxm) }
| '<' { LEFTARROW }
| '>' { RIGHTARROW }
(* 优先匹配WORD，不再单独用FILENAME token *)
| word as lxm { WORD lxm }
| eof { EOF }
| _ as lxm { raise @@ SyntaxError("Unexpected char: " ^ String.make 1 lxm) }

2. 修改解析器规则 #

文件名本质是特殊场景下的WORD，不需要单独定义FILENAME token，直接在重定向规则中使用WORD即可：

%{
    open Ast
%}

%token <int> NUMBER
%token <string> WORD
%token LEFTARROW
%token RIGHTARROW
%token EOF
%start program

%type <Ast.redirection> redirection
%type <Ast.command> command
%type <Ast.program> program

%%

redirection:
| LEFTARROW f = WORD { 0, remove_quotes f }
| opt = option(NUMBER) RIGHTARROW f = WORD { 
    let fname = remove_quotes f in
    match opt with
    | None -> 1, fname
    | Some n -> n, fname
 }

command:
| executable = WORD args = list(WORD) redirections = list(redirection) { 
    { 
      executable = remove_quotes executable;
      args = List.map remove_quotes args;
      redirections
    } 
}

program:
| commands = list(command) EOF { commands }

3. 添加引号处理辅助函数 #

需要一个工具函数移除字符串两端的引号（如果存在）：

(* 移除字符串两端的引号（双/单引号都支持） *)
let remove_quotes s =
  let len = String.length s in
  if len >= 2 then
    match s.[0], s.[len-1] with
    | '"', '"' | '\'', '\'' -> String.sub s 1 (len-2)
    | _ -> s
  else
    s

关键逻辑说明 #

• 分词优先级：先跳过空白符，再匹配数字、箭头符号，最后匹配WORD，避免宽泛规则提前抢占匹配权。
• 空格分隔：通过plain_word规则排除空白符，确保空格会被当作分隔符，不会被包含在单个WORD中。
• 带空格文件名支持：通过quoted_word规则允许引号包裹带空格的字符串，再通过辅助函数去掉引号，既满足文件名需求，又不影响普通命令参数的拆分。

测试输入"ls -l"会被拆分为两个WORD："ls"和"-l"，解析后得到期望的AST；输入echo "hello world" > output.txt会正确识别命令参数和重定向规则。

内容的提问来源于stack exchange，提问作者Lou Falkes