0

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

Brainfuck 的背景信息（可跳过）

在 Brainfuck 中，循环由一对方括号完成，规则如下：

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

因此，以下代码的计算结果为 15：

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

上面写着：

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

第二个单元格中的值将增加到 15（以 5 为增量增加 3 次）。

问题：

基本上，我编写了两个函数来处理在文件[的标题部分中推送和弹出最后一个位置的最后一个位置，即将 lexbuf 的当前位置推送和弹出到命名：brainfuck.mllpush_curr_ppop_last_pint list refloopstack

{ (* 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 ... *)
}

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

4

1 回答 1

4

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

所以你不能ocamllex像你试图做的那样使用来实现整个解释器。您可以做的（以及 ocamllex 的设计目的）是将输入的字符流转换为令牌流。

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

Lexing Brainfuck 的帮助要小得多，因为所有 Brainfuck 标记无论如何都只包含一个字符。因此找出每个标记的结束位置和下一个标记的开始位置是无操作的，找出标记的类型只是意味着将字符与“[”、“+”等进行比较。所以 Brainfuck 词法分析器所做的唯一有用的事情就是丢弃空格和注释。

因此，您的词法分析器要做的是将输入[,[+-. lala comment ]>]转换为类似LOOP_START, IN, LOOP_START, INC, DEC, OUT, LOOP_END, MOVE_RIGHT, LOOP_END, whereLOOP_START等属于您（或您的解析器生成器，如果您使用的话）定义并生成词法分析器输出的可区分联合。

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

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

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

于 2017-10-12T21:16:22.107 回答