改变 Lexing.lexbuf 的状态

Question

我正在使用 Ocamllex 为 Brainfuck 编写一个词法分析器，为了实现它的循环，我需要更改 lexbuf 的状态，以便它可以 returns 到流中的先前位置。

Background info on Brainfuck (skippable)

in Brainfuck, a loop is accomplished by a pair of square brackets with the following rule:

[ -> proceed and evaluate the next token

] -> if the current cell's value is not 0, return to the matching [

Thus, the following code evaluates to 15:
+++ [ > +++++ < - ] > .
it reads:

In the first cell, assign 3 (increment 3 times)

Enter loop, move to the next cell

Assign 5 (increment 5 times)

Move back to the first cell, and subtract 1 from its value

Hit the closing square bracket, now the current cell (first) is equals to 2, thus jumps back to [ and proceed into the loop again

Keep going until the first cell is equals to 0, then exit the loop

Move to the second cell and output the value with .

The value in the second cell would have been incremented to 15 (incremented by 5 for 3 times).

问题：

基本上，我写了两个函数来处理 brainfuck.mll 文件 header 部分中最后一个 [ 的最后位置的压入和弹出，即 push_curr_p 和 pop_last_p 将 lexbuf 的当前位置推送和弹出到名为 loopstack:

的 int list ref

{ (* Header *)
  let tape = Array.make 100 0
  let tape_pos = ref 0
  let loopstack = ref []

  let push_curr_p (lexbuf: Lexing.lexbuf) =
    let p = lexbuf.Lexing.lex_curr_p in
      let curr_pos = p.Lexing.pos_cnum in
        (* Saving / pushing the position of `[` to loopstack *)
        ( loopstack := curr_pos :: !loopstack
        ; lexbuf
        )

  let pop_last_p (lexbuf: Lx.lexbuf) =
    match !loopstack with
    | []       -> lexbuf
    | hd :: tl ->
      (* This is where I attempt to bring lexbuf back *)
      ( lexbuf.Lexing.lex_curr_p <- { lexbuf.Lexing.lex_curr_p with Lexing.pos_cnum = hd }
      ; loopstack := tl
      ; lexbuf
      )
}

{ (* Rules *)
  rule brainfuck = parse
  | '['  { brainfuck (push_curr_p lexbuf) }
  | ']'  { (* current cell's value must be 0 to exit the loop *)
           if tape.(!tape_pos) = 0
           then brainfuck lexbuf
           (* this needs to bring lexbuf back to the previous `[`
            * and proceed with the parsing 
            *)
           else brainfuck (pop_last_p lexbuf)
         }
  (* ... other rules ... *)
}

其他规则工作得很好，但它似乎忽略了 [ 和 ]。问题显然出在 loopstack 以及我如何获取和设置 lex_curr_p 状态。将不胜感激任何线索。

Answer 1

lex_curr_p 用于跟踪当前位置，以便您可以在错误消息等中使用它。将它设置为一个新值不会使词法分析器实际返回到文件中较早的位置。事实上，我 99% 确定无论你做什么，你都不能像那样创建词法分析器循环。

所以您不能像您尝试的那样使用 ocamllex 来实现整个解释器。您可以做的（以及 ocamllex 旨在做的）是将输入的字符流转换为标记流。

在其他语言中，这意味着将 var xyz = /* comment */ 123 这样的字符流翻译成 VAR, ID("xyz"), EQ, INT(123) 这样的标记流。因此，词法分析以三种方式提供帮助：它找到一个标记的结束位置和下一个标记的开始位置，它将标记分类为不同的类型（标识符与关键字等）并丢弃不需要的标记（白色 space 和注释） .这可以大大简化进一步的处理。

Lexing Brainfuck 的用处要小得多，因为所有 Brainfuck 标记都只包含一个字符。因此，找出每个标记的结束位置和下一个标记的开始位置是空操作，找出标记的类型只是意味着将字符与“[”、“+”等进行比较。所以 Brainfuck 词法分析器唯一有用的是丢弃 whitespace 和 comments.

所以你的词法分析器会做的是将输入 [,[+-. lala comment ]>] 变成类似 LOOP_START, IN, LOOP_START, INC, DEC, OUT, LOOP_END, MOVE_RIGHT, LOOP_END 的东西，其中 LOOP_START 等属于你（或者你的解析器生成器，如果你使用一个）定义并生成词法分析器输出。

如果您想使用解析器生成器，您需要在解析器的语法中定义标记类型，并让词法分析器生成这些类型的值。然后解析器就可以解析令牌流了。

如果您想手动进行解析，您可以在循环中手动调用词法分析器的 token 函数来获取所有标记。为了实现循环，您必须将已经使用的令牌存储在某个地方以便能够循环返回。最后，它最终会比仅将输入读入字符串要多得多，但对于学习练习，我认为这无关紧要。

就是说，我会建议一直使用解析器生成器来创建 AST。这样你就不必为循环创建一个令牌缓冲区，并且拥有一个 AST 实际上可以为你节省一些工作（你不再需要一个堆栈来跟踪哪个 [ 属于哪个 ]） .

改变 Lexing.lexbuf 的状态

Changing the State of Lexing.lexbuf

ocaml

lex

ocamllex