正则表达式提取S表达式？

Question

我想知道是否可以使用单个正则表达式对 lisp 中的 define 表达式进行传递解析，例如使用以下输入：

#lang sicp
(define (square x) (* x x))
(define (average x y) (/ (+ x y) 2))

; using block scope
(define (sqrt x)
   ; x is always the same -- "4" or whatever we pass to it, so we don't need that
   ; in every single function that we define, we can just inherit it from above.
   (define (improve guess) (average guess (/ x guess)))
   (define (good-enough? guess) (< (abs (- (square guess) x)) 0.001 ))
   (define (sqrt-iter guess) (if (good-enough? guess) guess (sqrt-iter (improve guess))))
   (sqrt-iter 1.0)
)

(sqrt 4)

我想强调以下以 define 开头的三个过程（函数范围过程的 none）。我在想的过程（如果我要迭代地做）是：

删除评论。
用\(\s*define
使用平衡括号直到不平衡 ) 结束我们的过程。对于正则表达式，类似于：(?:\([^)]*\))*，尽管我确信它会随着 * 的贪婪而变得更加复杂。

这甚至没有考虑到我可能有一个我们也想忽略的字符串 "( define )"。

是否可以为此构建一个正则表达式，或者太复杂了？这是我的起点，离完成还有很长的路要走：https://regex101.com/r/MlPmOd/1.

Answer 1

作为序言，引用杰米·扎温斯基 (Jamie Zawinski) 的名言：

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

您问题的唯一答案是 'no'。正则语言——正则表达式可以识别的语言——是context-free语言的真子集，s-expressions的书写形式是context-free但不是正则。所以没有正则表达式可以识别 s-expression.

的书面形式

要看到这一点，请考虑 s-expressions 的一个非常小的子集：

n = () | ( n)

所以 n 由集合 {(), (()), ((())), ...} 组成，其中左边的数每个字符串中的括号和右括号是相等的。这样的语言不能被正则表达式识别，因为你需要计算parens。

备注

一些在各种编程语言中称为 'regular expressions' 的实例实际上比正则表达式更强大，因此可以识别类比正则语言更大的语言。 jwz 的引述仍然适用：仅仅因为，也许，你可以并不意味着你应该。
在我看来，所有的程序员都应该学习足够多的形式语言理论，这样才会有危险。我不知道什么是好的现代参考资料，但我是从灰姑娘的书中学到的：Hopcroft & Ullman，自动机理论、语言和计算简介。
在我看来，所有 Lisp 程序员都应该为 s-expressions 写一个玩具 reader，因为这是了解真正的 reader 是如何工作的好方法，而不是需要很长时间。

正则表达式提取S表达式？

Regex to extract S expression?

regex

lisp

sicp

备注