如何为一个fslex规则模式返回多个标记？

Question

使用fslex，我想为一个模式返回多个标记，但我不知道如何实现。即使使用另一个返回多个标记的规则函数也可以适用于我。

我尝试使用类似于以下内容的语法：

let identifier = [ 'a'-'z' 'A'-'Z' ]+

// ...

rule tokenize = parse
// ...
| '.' identifier '(' { let value = lexeme lexbuf
                       match operations.TryFind(value) with
                      // TODO: here is the problem:
                      // I would like to return like [DOT; op; LPAREN]
                      | Some op -> op
                      | None    -> ID(value) }

| identifier         { ID (lexeme lexbuf) }
// ...

我在这里要解决的问题是仅在标识符位于.和(之间时，才匹配预定义的令牌（请参见：操作映射）。否则，匹配应返回为ID。

我对fslex相当新，因此我很高兴能得到任何指向正确方向的指针。

- kongo2002

---

该死，我总是混淆这两个;-) 不过我希望问题还是有些意义的。 - kongo2002

这个问题可以解决（虽然不应该这样做，你可能需要重新设计你的词法分析器）- 如果没有其他人解决，我一旦有一个舒适的键盘，就会发布解决方案。 - Ramon Snir

Answer 1

好的，这就是答案。

每个词法规则（即rule <name> = parse .. cases ..）都定义了一个函数<name>：LexBuffer<char>- > 'a，其中'a可以是任何类型。通常，您返回标记（可能由 FsYacc 为您定义），然后可以像这样解析文本：

let parse text =
    let lexbuf = LexBuffer<char>.FromString text
    Parser.start Lexer.tokenize lexbuf

Parser.start是解析函数（来自您的FsYacc文件），类型为(LexBuffer<char> -> Token) -> LexBuffer<char> -> AST（Token和AST是您的类型，没有什么特别之处）。

在您的情况下，您想要<name>：LexBuffer<char> ->'a list，那么您只需要这样做：

let parse' text =
    let lexbuf = LexBuffer<char>.FromString text
    let tokenize =
        let stack = ref []
        fun lexbuf ->
        while List.isEmpty !stack do
            stack := Lexer.tokenize lexbuf
        let (token :: stack') = !stack // can never get match failure,
                                        // else the while wouldn't have exited
        stack := stack'
        token
    Parser.start tokenize lexbuf

这只是简单地保存您的词法分析器提供的标记，并逐个将它们提供给解析器（并在需要时生成更多标记）。

- Ramon Snir

---

谢谢您的见解！我想这基本上就是我要问的内容，尽管我有一种感觉（就像您上面提到的那样），我必须修改我的词法分析器逻辑。但我在这一点上卡住了，我害怕。 - kongo2002

我曾经写过一两个类似的词法分析器（F#编译器也会拦截标记并对其进行一些修改），但通常这意味着你在总体设计上缺少了某些东西。顺便说一下，如果你只想解决这个特定的场景，我可以发布一个替代方案。 - Ramon Snir

Answer 2

尝试让语义分析（如“...只有标识符在.和（之间时”）不要出现在你的词法分析器（fslex）中，而是留给解析器（fsyacc）处理。例如，一种选项是让你的词法分析器不了解操作：

let identifier = [ 'a'-'z' 'A'-'Z' ]+    
// ...
rule tokenize = parse
// ...
| '.' { DOT }
| '(' { LPAREN }
| identifier { ID (lexeme lexbuf) }
// ...

然后在fsyacc中，使用如下规则解决问题：

| DOT ID LPAREN { match operations.TryFind($2) with
                  | Some op -> Ast.Op(op)
                  | None    -> Ast.Id($2) }

针对评论的更新：

也许你可以在词法分析器中加入以下内容：

let identifier = [ 'a'-'z' 'A'-'Z' ]+   
let operations =
  [
    "op1", OP1
    "op2", OP2
    //...
  ] |> Map.ofList 

// ...
rule tokenize = parse
// ...
| '.' { DOT }
| '(' { LPAREN }
| identifier 
  { 
    let input = lexeme lexbuf
    match keywords |> Map.tryFind input with
    | Some(token) -> token
    | None -> ID(input) 
  }
// ...

并且在你的解析器中：

| DOT ID LPAREN { ... }
| DOT OP1 LPAREN { ... }
| DOT OP2 LPAREN { ... }

因此，您在解析器中强制执行规则，即ID和operation必须出现在DOT和LPAREN之间，同时保持词法分析器的简单性（提供仅涉及每个令牌相互关系有效性的少量令牌流）。

- Stephen Swensen

---

这也是我想到的，但我想在解析器中使用ID后面的令牌。比如DOT OP1 LPAREN ... 等等。 - kongo2002

感谢您的输入 - 您的更新版本看起来与我目前拥有的版本几乎相同。这种方法的问题在于，如果操作标记不在DOT和LPAREN之间，我无法将其用作ID。 - kongo2002

实际上效果基本相同，但更符合使用lex和yacc工具时所规定的设计模式。我稍后会更新我的答案，提供将“operation”视为“ID”的解决方案。 - Stephen Swensen

实际上，我撤回之前的话，我没有一个即时能提供给你最新规则的好解决方案。但是现在我再想一下，最好的方法还是采用我在答案中提供的第一种方法：使用fslex进行词法分析，使用fsyacc进行语法分析，并在您用于处理解析器生成的AST的自定义语义分析函数中执行语义分析（例如DOT OP1 LPAREN ...）。 - Stephen Swensen

谦虚地说，我个人在使用fslex和fsyacc方面的大部分经验都来自于我的项目http://code.google.com/p/nl-compiler/。研究F#编译器本身对我来说是一次很好的学习经历：https://github.com/fsharp/fsharp。但可能对我影响最大的是http://www.amazon.com/Modern-Compiler-Implementation-Andrew-Appel/dp/0521607647（不是用F#而是父语言ML）。 - Stephen Swensen

Answer 3

针对这个特定情况，以下解决方案可能更好：

...

rule tokenize = parse
...
| '.' { DOT }
| '(' { LPAREN }
| identifier { ID (lexeme lexbuf) }

...

使用方法：

let parse'' text =
    let lexbuf = LexBuffer<char>.FromString text
    let rec tokenize =
        let stack = ref []
        fun lexbuf ->
        if List.isEmpty !stack then
            stack := [Lexer.tokenize lexbuf]
        let (token :: stack') = !stack // can never get match failure,
                                        // else the while wouldn't have exited
        stack := stack'
        // this match fixes the ID to an OP, if necessary
        // multiple matches (and not a unified large one),
              // else EOF may cause issues - this is quite important
        match token with
        | DOT ->
          match tokenize lexbuf with
          | ID id ->
            match tokenize lexbuf with
            | LPAREN ->
              let op = findOp id
              stack := op :: LPAREN :: !stack
            | t -> stack := ID id :: t :: !stack
          | t -> stack := t :: !stack
        | _ -> ()
        token
    Parser.start tokenize lexbuf

如果ID被DOT和LPAREN包围，则这将修复它们为操作。仅在这种情况下使用。

P.S.：我有3个单独的匹配，因为一个统一的匹配将要求使用Lazy <_>值（这将使其更难读），或者在一个序列上失败[DOT; EOF]，因为它会期望第三个额外的标记。

- Ramon Snir

---

谢谢您的努力。我现在需要理解您在这里所做的事情 :-) - kongo2002