1

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

特别值得注意的是，我正在尝试根据 Scheme 规范的规则对标识符进行 lex 识别（显然，我不知道自己在做什么）——并且其中有一些关于标识符的语言要求它们后面跟一个定界符。我现在的方法是拥有一个delimited_identifier包含其中一个delimiter字符的正则表达式，它不应该被主词法分析器使用……然后一旦匹配，该词素的读取就会被恢复Sedlexing.rollback（好吧，我的包装器） ，在传递给只吃实际标识符的子词法分析器之前，希望将缓冲区中的定界符作为不同的词位被父词法分析器吃掉。

我正在使用Menhir和Sedlex，主要是综合来自@smolkaj的ocaml-parsingexample-repo 和RWO 的解析章节的示例；这是我当前解析器和词法分析器的最简单简化：

%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 }

%%

……和……</p> 

(** 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)

（是的，它基本上是一个无操作/最简单的事情。我正在努力学习！: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:
...

我对解析和词法分析以及所有这些都是新手；任何的建议都受欢迎。我敢肯定这只是一个新手的错误，但是……</p>

谢谢！

4

1 回答 1

3

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

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

在这个定义_中匹配由所有可能的字符组成的语言中最短的单词。换句话说，_总是匹配空词μ而不消耗其输入的任何部分，将解析器发送到无限循环。

于 2018-03-03T10:23:57.887 回答