[ИУ9] Основы информатики

Домашнее задание №6

Реализуйте разбор арифметического выражения, записанного в традиционной инфиксной нотации, и его преобразование к выражению, записанному на языке Scheme. Выражения могут включать в себя числа (целые и с плавающей запятой, в том числе — в экспоненциальной форме), переменные (имена переменных могут состоять из одной или нескольких латинских букв), арифметические операции (+, −, *, / и ^), унарный минус и круглые скобки.

Задание выполните в три этапа:

1. Лексический анализатор

Разработайте лексическую структуру языка (грамматику разбора арифметического выражения на токены) и запишите ее в БНФ перед главной процедурой лексера. Процедура должна называться 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 ")")

2. Синтаксический анализатор

Синтаксический анализатор должен строить дерево разбора согласно следующей грамматике, учитывающей приоритет операторов:

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)

3. Преобразователь дерева разбора в выражение на Scheme

Реализуйте процедуру 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