代码之家  ›  专栏  ›  技术社区  ›  Pandemonium

更改词法分析的状态。lexbuf公司

  •  0
  • Pandemonium  · 技术社区  · 7 年前

    我正在写一个lexer Brainfuck 使用ocamlex并实现其循环,我需要更改lexbuf的状态,以便它可以返回到流中的前一个位置。

    Brainfuck的背景信息(可跳过)

    在Brainfuck中,一个循环是由一对方括号和 以下规则:

    • [
    • ] -&燃气轮机;如果当前单元格的值不是0,则返回到匹配的 [

    因此,以下代码的计算结果为15:

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

    内容如下:

    • 在第一个单元格中,指定3(增加3倍)
    • 输入loop,移动到下一个单元格
    • 移回第一个单元格,并从其值中减去1
    • 点击结束方括号,现在当前单元格(第一个)等于2,因此跳回到 [ 然后再次进入循环
    • 继续,直到第一个单元格等于0,然后退出循环
    • .

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

    问题:

    [ brainfuck.mll 文件,即 push_curr_p pop_last_p 将lexbuf的当前位置推到 int list ref 已命名 loopstack :

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

    其他规则运行得很好,但似乎忽略了这一点 [ ] . 问题显然在 循环堆栈 以及我如何获得和设置 lex_curr_p 状态希望有任何线索。

    1 回复  |  直到 7 年前
        1
  •  4
  •   sepp2k    7 年前

    lex_curr_p 用于跟踪当前位置,以便您可以在错误消息等中使用它。将其设置为新值不会使lexer实际上返回到文件中的早期位置。事实上,我99%确信,无论你做什么,你都不能让lexer循环像那样。

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

    在其他语言中,这意味着翻译字符流,如 var xyz = /* comment */ 123 进入令牌流,如 VAR, ID("xyz"), EQ, INT(123)

    由于所有Brainfuck代币都只包含一个字符,所以对Brainfuck进行词法分析的帮助要小得多。因此,找出每个标记的结束位置和下一个标记的开始位置是不可行的,而找出标记的类型只意味着将字符与“[”、“+”等进行比较。因此,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实际上可以节省一些工作(你不再需要一个堆栈来跟踪哪一个) [ ] ).