racket - 如何向 Racket 中的词法分析器添加状态？

Question

我正在尝试为 Racket 中的 sed 语言编写一个词法分析器(例如“s/find/replace/”)。我遇到的一个问题是处理这样一个事实:许多 token 没有确定的形式并且可以改变。例如，我可以将上面的示例写为“ssfindsreplaces”，其中使用字母“s”而不是“/”。

我已经开始编写一个词法分析器，例如，

(define sed-lexer
  (lexer-srcloc
   ["\n" (token 'NEWLINE lexeme)]
   ["/" (token 'DIVIDER lexeme]
   [(:or "s" "y" "d" "p") (token 'CMD lexeme)]
   [(:* (complement "/") (token 'LITERAL lexeme)]))

但这在多个层面上都失败了:

• 该命令只能出现在开头(在这个简化的示例中)。读取命令后，我想忽略命令大小写，直到出现换行符。
• DIVIDER 标记不能始终设置为斜杠。

我可以想象这个问题的解决方案可能是向这个词法分析器添加状态。例如，词法分析器从“开始”状态开始，在该状态中查找命令，然后进入“divider1”状态，查找分隔符字符。这里似乎存在这样的功能http://pygments.org/docs/lexerdevelopment/ 。鉴于 Racket 生态系统中的工具，解决此问题的最佳方法是什么？

Answer 1

词法分析器只是一个使用输入端口并返回 token 的函数。如果(br-)parser-tools/lex对你来说还不够，你可以自己编写(应该不难)。

理论上，有限状态机和正则表达式具有相同的表达能力，所以我认为您实际上可以使用parser-tools/lex来完成您想要的。由于您需要如何将大小写拆分为所有可能的“分隔符”(因为纯正则表达式不具有反向引用能力)，因此它看起来非常乏味。我认为你提到的 pygments 也会有类似的问题。

另一种可能性是使用比正则表达式更强大的东西。由于 sed 语法非常简单，您甚至可以立即解析它，而无需先进行词法分析。这是我使用解析器组合器库 Megaparsack 快速编写的一个蹩脚版本

#lang racket

(require megaparsack megaparsack/text
         data/monad data/applicative)

(struct substitution (search replace flags) #:transparent)

(define substitution/p (do (char/p #\s)
                           [divider <- any-char/p]
                           [search <- (many/p (char-not/p divider))]
                           (char/p divider)
                           [replace <- (many/p (char-not/p divider))]
                           (char/p divider)
                           [flags <- (many/p (char-in/p "gIp"))]
                           (pure (substitution search replace flags))))

(define dummy-command/p (string/p "dummy-command"))

(define line/p (or/p substitution/p
                     dummy-command/p))

(define program/p (do [result <- (many/p line/p #:sep (char/p #\newline))]
                      eof/p
                      (pure result)))

(pretty-print
 (parse-result!
  (parse-string program/p
                "s/hello/world/\ndummy-command\ns|search|replace|gp")))

#|

Result:

(list
 (substitution '(#\h #\e #\l #\l #\o) '(#\w #\o #\r #\l #\d) '())
 "dummy-command"
 (substitution
  '(#\s #\e #\a #\r #\c #\h)
  '(#\r #\e #\p #\l #\a #\c #\e)
  '(#\g #\p)))

|#