Реализуйте разбор арифметического выражения, записанного в традиционной инфиксной нотации, и его преобразование к выражению, записанному на языке Scheme. Выражения могут включать в себя числа (целые и с плавающей запятой, в том числе — в экспоненциальной форме), переменные (имена переменных могут состоять из одной или нескольких латинских букв), арифметические операции (+
, −
, *
, /
и ^
), унарный минус и круглые скобки.
Задание выполните в три этапа:
Разработайте лексическую структуру языка (грамматику разбора арифметического выражения на токены) и запишите ее в БНФ перед главной процедурой лексера. Процедура должна называться tokenize
, принимать выражение в виде строки и возвращать последовательность токенов в виде списка. Лексемы исходной последовательности должны быть преобразованы:
имена переменных и знаки операций — в символические константы Scheme,
числа — в числовые константы Scheme соответствующего типа,
скобки — в строки "("
и ")"
.
Пробельные символы должны игнорироваться лексером. Если исходная последовательность включает в себя недопустимые символы, лексер должен возвращать #f
.
Примеры вызова лексера:
(tokenize "1")
⇒ (1)
(tokenize "-a")
⇒ (- a)
(tokenize "-a + b * x^2 + dy")
⇒ (- a + b * x ^ 2 + dy)
(tokenize "(a - 1)/(b + 1)")
⇒ ("(" a - 1 ")" / "(" b + 1 ")")
Синтаксический анализатор должен строить дерево разбора согласно следующей грамматике, учитывающей приоритет операторов:
Expr ::= Term Expr' .
Expr' ::= AddOp Term Expr' | .
Term ::= Factor Term' .
Term' ::= MulOp Factor Term' | .
Factor ::= Power Factor' .
Factor' ::= PowOp Power Factor' | .
Power ::= value | "(" Expr ")" | unaryMinus Power .
где терминалами являются value
(число или переменная), круглые скобки и знаки операций.
Синтаксический анализатор реализуйте в виде процедуры parse
, принимающую последовательность токенов в виде списка (результат работы tokenize
) и возвращающую дерево разбора, представленное в виде вложенных списков вида (операнд-1 знак-операции операнд-2)
для бинарных операций и (− операнд)
для унарного минуса. Числа и переменные в списки не упаковывайте. Многократно вложенные друг в друга списки из одного элемента вида (((имя-или-число)))
не допускаются.
Разбор осуществляйте методом рекурсивного спуска. Если исходная последовательность не соответствует грамматике, парсер должен возвращать #f
.
При построении дерева разбора соблюдайте общепринятую ассоциативность бинарых операторов: левую для сложения, вычитания, умножения и деления и правую для возведения в степень. Вложенность списков должна однозначно определять порядок вычисления значения выражения.
Примеры вызова парсера:
; Ассоциативность левая
;
(parse (tokenize "a/b/c/d"))
⇒ (((a / b) / c) / d)
; Ассоциативность правая
;
(parse (tokenize "a^b^c^d"))
⇒ (a ^ (b ^ (c ^ d)))
; Порядок вычислений задан скобками
;
(parse (tokenize "a/(b/c)"))
⇒ (a / (b / c))
; Порядок вычислений определен только
; приоритетом операций
;
(parse (tokenize "a + b/c^2 - d"))
⇒ ((a + (b / (c ^ 2))) - d)
Реализуйте процедуру tree->scheme
, преобразующую дерево, возвращенное процедурой parse
, в выражение на языке Scheme. Полученное выражение должно быть пригодно для вычисления его значения интерпретатором языка Scheme.
Для возведения в степень используйте встроенную процедуру Scheme expt
. Не передавайте более двух аргументов встроенным процедурам для арифметических операций.
Примеры вызова конвертера:
(tree->scheme (parse (tokenize "x^(a + 1)")))
⇒ (expt x (+ a 1))
(eval (tree->scheme (parse (tokenize "2^2^2^2")))
(interaction-environment))
⇒ 65536