更改Lexing.lexbuf的状态

Question

我正在用Ocamlex为Brainfuck编写一个lexer，为了实现它的循环，我需要更改lexbuf的状态，以便它可以返回到流中的前一个位置。

Brainfuck(可跳过)的背景信息

在Brainfuck中，一个循环是由一对带有以下规则：

• [->继续并评估下一个令牌
• ]->如果当前单元格的值不为0，则返回到匹配的[

因此，以下代码评估为15:

+++ [ > +++++ < - ] > .

上面写着：

• 在第一个单元格中，指定3(递增3次)
• 进入循环，移动到下一个单元格
• 分配5(递增5次)
• 移回第一个单元格，并从其值中减去1
• 点击最后的方括号，现在当前单元格(第一个)等于2，因此跳回[并再次进入循环
• 继续，直到第一个单元格等于0，然后退出循环
• 移动到第二个单元格并用.输出值

第二个单元格中的值会增加到15(以5递增3次)。

问题：

基本上，我写了两个函数来处理推送和弹出brainfuck.mll文件头部分中最后一个[的最后一个位置，即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用于跟踪当前位置，以便您可以在错误消息等中使用它。将其设置为一个新值不会使lexer实际返回到文件中的早期位置。事实上，我有99%的把握，无论你做什么，你都不能让lexer循环像那样

因此，您不能像尝试的那样使用ocamllex来实现整个解释器。您可以做的(以及ocamllex的设计目的)是将输入的字符流转换为令牌流。

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

Lexing Brainfuck的帮助要小得多，因为所有Brainfuc克代币都只由一个字符组成。因此，找出每个令牌的结束位置和下一个令牌的开始位置是不可行的，找出令牌的类型只意味着将字符与"["、"+"等进行比较。因此，Brainfuck lexer所做的唯一有用的事情就是丢弃空白和注释。

因此，lexer要做的是将输入[,[+-. lala comment ]>]转换为类似LOOP_START, IN, LOOP_START, INC, DEC, OUT, LOOP_END, MOVE_RIGHT, LOOP_END的东西，其中LOOP_START等属于一个可区分的并集，您(或者您的解析器生成器，如果您使用它的话)定义并生成lexer输出。

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

如果您想手动进行解析，您可以在循环中手动调用lexer的token函数来获取所有令牌。为了实现循环，您必须将已经消耗的令牌存储在某个地方，以便能够进行循环。最终，这将是更多的工作，而不仅仅是将输入读入字符串，但对于学习练习来说，我想这并不重要。

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