-2

我正在研究上下文无关的语法，并且我有一个返回（语法的终端值）的函数

例如：我有导致 (AB) 的非终端函数，来自调用 say ((A cat) (B happy np) (AB sad)) 所以技术上 A 和 B 是语法的非终端。现在我希望能够获得终端（猫快乐 np 悲伤）

(define terminals
  (lambda (lsts)
    (cond
     ((null? lsts) lsts)
     ((not(member? (car(car lsts)) (n-terminals lsts)))
      (cons (car(car lsts)) (terminals (car (cdr lsts)))))
     (else (terminals (cdr lsts))))))

PS：上面描述了n端的功能。成员？是一个布尔函数，如果项目是列表的成员，则返回 true，否则返回 false。我的函数返回一个空的 lst。我在这里想念什么？

4

1 回答 1

1

问题在于您在找到终端符号时所做的事情。这里确实有两个不同的问题。

首先，您只查看每条规则的第一个符号。您的lsts变量是规则列表；每个规则都是一个符号列表。因此(car (car lsts))，您将获得第一条规则的第一个符号。

第二个问题是找到终端符号后如何递归。通常，您传递terminals一个列表列表。但是，如果您找到了一个终端符号（即以 开头的符号(member? ...)），您将传递它(car (cdr lsts))。我们知道lsts是一个列表列表。(cdr lsts)列表列表（当然也可以是空列表）也是如此。这意味着(car (cdr lsts))只是一个普通的列表。

我认为解决此问题的最简单方法是将其分解为两个功能。首先，编写一个从单个规则获取终端的函数。也就是说，不是专注于整个输入，而是((A cat) (B happy np) (A B sad))一次专注于一个规则，例如(B happy np). 所以写一个给定的函数(B happy np)给你(happy np)。接下来，编写一个函数，将该函数应用于每个规则lsts并组合所有输出。（您可能会发现append这里的功能很有用。）

将它写在两个单独的函数中应该会使问题更容易考虑。生成的代码也将更简单，更易于阅读，这是一个奖励。

此外，一个无关的风格问题：你可以（并且应该）写

(define foo
  (lambda (args) ...))

作为

(define (foo args)
  ...)

这两个表达具有相同的含义，但第二个更容易阅读和使用更频繁。

编辑：正如我在评论中所说，我将首先计算非终端列表并将其用于一次执行一行的函数。您可以通过嵌套两个函数并利用 Scheme 的词法作用域来简化使用：

(define (terminals rules)
  (let ((non-terminals (n-terminals rules)))
    (define (helper rule) ; this takes a rule and returns all its terminal symbols
       ... ; you can use non-terminals in here
    )
    ; now here you have to call helper on every rule and combine the results
  ))

另一种选择是将其分解为两个未嵌套的函数并传入非终结符号列表：

(define (terminals-from-rule rule non-terminals)
  ... ; implement, using non-terminals as the list of non-terminal symbols
)
(define (terminals rules)
  ... ; here you need to calculate the list of non-terminals and pass
      ; it into each call to terminals-from-rule along with the rule.
)
于 2012-10-12T16:59:49.557 回答