Мне не нужна помощь в решении этого вопроса, однако я хотел бы точно знать, о чем он просит. И чтобы лучше понять, о чем он просит, я спрашиваю, может ли кто-нибудь предоставить мне пример ввода и соответствующий вывод.
Write and certify a recursive procedure check which inputs an sexp s
and a list varlst
of identifiers and decides whether s belongs to the class of fully
parenthesized infix +-expressions fpip defined as follows:
var ::= a | b | c | d | e | f | g
fpip ::= var | (fpip + fpip)
Пример допустимых выражений "fpip":
a
(a + b)
((a + b) + (c + d))
Объяснение:
Первое определение "var" говорит вам, что это может быть один из символов a ... g.
Второе определение «fpip» говорит, что у вас есть либо «var», либо составное выражение (fpip + fpip). Таким образом, это означает, что a является допустимым "fpip", так как a является допустимым "var". Это также означает, что (a + b) является допустимым "fpip". Кроме того, используя «fpip» вместо «var» в составном выражении, вы получаете вложенность, например допустимый «fpip» ((a + b) + (c + d)).
В качестве подсказки. Ваша процедура будет отражать определение. Он проверит, является ли аргумент переменной, и если нет, ему нужно проверить, соответствует ли он второму определению, которое включает два рекурсивных вызова для проверки того, что каждая часть также действительна.
Что не очень хорошо объяснено, так это цель varlist. Я предполагаю, что он представляет выделенные переменные и что «var» должен быть не только a ... g, чтобы быть действительным, но и чтобы идентификаторы также существовали в varlist, чтобы он был действительным. Это обоснованное предположение, так как я сделал свою долю переводчиков, но я думаю, что это должно было быть указано более четко. например. возможно:
(fpip? 'c '(b a q)) ; ==> #f (c is in "var" definition but not in varlist)
(fpip? 'a '(b a q)) ; ==> #t (a is in "var" definition and in varlist)
(fpip? 'q '(b a q)) ; ==> #f (q is not in "var" definition)