如何在 OCaml 词法分析器中执行 'lookahead' / 如何回滚词素？

Question

好吧，我正在用 OCaml 编写我的第一个解析器，我立即以某种方式设法制作了一个带有无限循环的解析器。

特别要注意的是，我正在尝试根据 Scheme 规范的规则对标识符进行词法分析（很明显，我不知道自己在做什么）——其中有一些关于标识符的语言要求它们是后跟一个分隔符。我现在的方法是使用一个包含 delimiter 字符之一的 delimited_identifier 正则表达式， 不应被主词法分析器消耗 ……然后一旦匹配，该词位的读取将由 Sedlexing.rollback（好吧，my wrapper thereof）还原，然后再传递给 only 吃掉实际标识符的子词法分析器，希望将分隔符留在缓冲区中，以供父词法分析器作为不同的词素使用。

我正在使用 Menhir and Sedlex, mostly synthesizing the examples from @smolkaj's ocaml-parsing example-repo and RWO's parsing chapter; here's the simplest reduction of my current parser and lexer:

%token LPAR RPAR LVEC APOS TICK COMMA COMMA_AT DQUO SEMI EOF
%token <string> IDENTIFIER
(* %token <bool> BOOL *)
(* %token <int> NUM10 *)
(* %token <string> STREL *)

%start <Parser.AST.t> program

%%

program:
  | p = list(expression); EOF { p }
  ;

expression:
  | i = IDENTIFIER { Parser.AST.Atom i }

%%

……和……

(** Regular expressions *)
let newline = [%sedlex.regexp? '\r' | '\n' | "\r\n" ]
let whitespace = [%sedlex.regexp? ' ' | newline ]
let delimiter = [%sedlex.regexp? eof | whitespace | '(' | ')' | '"' | ';' ]

let digit = [%sedlex.regexp? '0'..'9']
let letter = [%sedlex.regexp? 'A'..'Z' | 'a'..'z']

let special_initial = [%sedlex.regexp?
   '!' | '$' | '%' | '&' | '*' | '/' | ':' | '<' | '=' | '>' | '?' | '^' | '_' | '~' ]
let initial = [%sedlex.regexp? letter | special_initial ]

let special_subsequent = [%sedlex.regexp? '+' | '-' | '.' | '@' ]
let subsequent = [%sedlex.regexp? initial | digit | special_subsequent ]

let peculiar_identifier = [%sedlex.regexp? '+' | '-' | "..." ]
let identifier = [%sedlex.regexp? initial, Star subsequent | peculiar_identifier ]
let delimited_identifier = [%sedlex.regexp? identifier, delimiter ]


(** Swallow whitespace and comments. *)
let rec swallow_atmosphere buf =
   match%sedlex buf with
   | Plus whitespace -> swallow_atmosphere buf
   | ";" -> swallow_comment buf
   | _ -> ()

and swallow_comment buf =
   match%sedlex buf with
   | newline -> swallow_atmosphere buf
   | any -> swallow_comment buf
   | _ -> assert false

(** Return the next token. *)
let rec token buf =
   swallow_atmosphere buf;
   match%sedlex buf with
   | eof -> EOF

   | delimited_identifier ->
     Sedlexing.rollback buf;
     identifier buf

   | '(' -> LPAR
   | ')' -> RPAR

   | _ -> illegal buf (Char.chr (next buf))

and identifier buf =
   match%sedlex buf with
   | _ -> IDENTIFIER (Sedlexing.Utf8.lexeme buf)

（是的，这基本上是一个空操作/最简单的事情 rn。我正在努力学习！:x）

不幸的是，这种组合导致解析自动机中的无限循环：

State 0:
Lookahead token is now IDENTIFIER (1-1)
Shifting (IDENTIFIER) to state 1
State 1:
Lookahead token is now IDENTIFIER (1-1)
Reducing production expression -> IDENTIFIER 
State 5:
Shifting (IDENTIFIER) to state 1
State 1:
Lookahead token is now IDENTIFIER (1-1)
Reducing production expression -> IDENTIFIER 
State 5:
Shifting (IDENTIFIER) to state 1
State 1:
...

我不熟悉解析和词法分析以及所有这些；任何的建议都受欢迎。我确定这只是一个新手错误，但是......

谢谢！

Answer 1

如前所述，在词法分析器中实现过多的逻辑不是一个好主意。但是，无限循环不是来自回滚，而是来自您对 identifier:

的定义

 identifier buf =
   match%sedlex buf with
   | _ -> IDENTIFIER (Sedlexing.Utf8.lexeme buf)

在此定义中 _ 匹配语言中可能包含所有可能字符的最短单词。换句话说，_ 总是匹配空词 μ 而不会消耗其输入的任何部分，从而使解析器陷入无限循环。

如何在 OCaml 词法分析器中执行 'lookahead' / 如何回滚词素？

How do I preform 'lookahead' in an OCaml lexer / how do I rollback a lexeme?

parsing

ocaml

lr

ocamllex

menhir