Возвращаясь к предыдущей статье, хотелось бы сразу отметить вопрос о том, что многие из внешних команд нашего Бейсика реализовать достаточно легко в рамках любимого языка. К примеру, команду LOAD «имя файла». Можно заранее договориться, что длина программы не будет превышать в исходном виде 100-200 строчек. Мало? В аналогах Бейсика для современного Андроида вообще есть ограничения в 1 Кб, так что не так уж и мало. Таким образом, исходная программа (в виде строк) может храниться в массиве, который легко загружать, выводить на экран и сохранять. Длину строки при этом можно ограничить в 70 знаков, каждая строка должна иметь номер. Редактирование файла можно свести к элементарному действию, если вспомнить о технологии редактора EDLINE, бывшего некогда столь популярным. Проще говоря, это строчный текстовый редактор, где каждая строка хранится под номером. Соответственно, все команды используют эти номера строк для следующих действий:
Загрузить файл Вывести часть файла на экран со строки X по строку Y Удалить часть файла с указание номеров строк Переименовать номера с указанием шага Произвести поиск в строке Сохранить/напечатать блок текста с указанными номерами Подгрузить часть файла в память Сохранить файл И т.д.
Как видите, нет нужды организовывать довольно сложный экранный редактор, да большинство Бейсиков и не работает в таком режиме. А вышеупомянутый редактор написать – дел на час.
С самой командой RUN тоже проблем быть не должно. Тут интересно другое: исходный текст Бейсика слишком избыточен, чтобы его каждый раз анализировать заново при выполнении: приходится убирать лишние пробелы, определять команды, переводить строки в числовые значения. В этом случае программу стараются преобразовать в промежуточный компактный формат, причем на этапе ввода каждой строки. Каждый применяет свою систему: хранение данных и команды в древовидных структурах, сокращенная запись и т.д. Как бы вы, к примеру, оптимизировали хранение таких команд: for j=1 to 20: print “шаг “,j:next j? Первое, что приходит на ум – убрать лишние разделители, оставив только минимум, да заменить команды FOR, TO, PRINT, NEXT сокращенными командами-кодами. И еще можно выделить постоянные строки в кавычках в отдельный массив, присвоив каждой отдельный внутренний номер. Переменной j можно выделить даже указатель на ее ячейку (m[‘J’] тип 3 – из предыдущей статьи).
Но простота разбора команд Бейсика обманчива до тех пор, пока мы не сталкиваемся со сложными выражениями. Команды типа j =j + 3 вычисляются легко, а вот над j = sin(x) + (1/3 + (a + 5)^3)/1.7 придется подумать. Или вот над такой конструкцией – if (a >= b) and ((c = 4) or (c < 4)). Сразу возникает мысль об упрощении этих выражений, причем с использованием приоритетов операций. Первое выражение нужно разложить в таком порядке:
$e1 = A + 5 {e = выражение, внутренняя переменная номер 1} $e2 = $e1 ^ 3 $e3 = 1/3 $e4 = $e3 + $e2 $e5 = $e4 / 1.7 $e6 = sin(x) $e7 = $e6 + $e5 j = $e7
Это примитивный вариант, но уже по нему видно, что каждое выражение содержит либо единичный вызов функции, либо одну операцию – +, -, *, /, ^. Такое преобразование обычно делают с использованием связанных стеков операций и приоритетов. В простейшем же случае, чтобы не запутаться, можно программно считать количество скобок и операций. Это дольше вычислять, зато нагляднее выглядит.
Приведем вам интересную ссылку, чтобы вы ознакомились с вариантами вычисления математических выражений – algolist.manual.ru/syntax/parsear.php. Алгоритм Рутисхаузера кажется более простым в использовании. В нем нужно пронумеровать лексемы по порядку. Если вы заметили, то в примере по этой ссылке даются только имена переменных, а не числа, которые могут занимать несколько знакомест. Итак, идея такова: каждой лексеме (самостоятельному элементу языка) нужно присвоить порядковый номер. Делаем:
1 2 … 19 20 sin( x ) + ( 1 / 3 + ( a + 5 ) ^ 3 ) / 1.7
Теперь присвоим приоритеты следующим образом:
- Если это число, функция или открывающая скобка – +1 к приоритету.
- Если это знак операции или закрывающая скобка – -1 от приоритета.
1 2 … 19 20 sin( x ) + ( 1 / 3 + ( a + 5 ) ^ 3 ) / 1.7 0 1 2 3 2 1 2 3 2 3 2 3 4 3 4 3 2 3 2 1 2
После этой расстановки нужно раз за разом искать приоритет с высшим номером, затем выделить его, знак операции после него и соответствующий первоначальному приоритету. Это будет называться «тройкой», которую затем нужно заменять на временную переменную, запоминать и вычислять ее. На каждом проходе количество лексем и значений приоритетов будет меняться, причем нужно предусмотреть выбрасывание лишних оставшихся скобок:
Ищем максимальный: 4, после него идут 3 и 4 = $e1 = a + 5 = вычисляем.
1 2 3 … 16 17 sin( x ) + ( 1 / 3 + $e1 ^ 3 ) / 1.7 0 1 2 3 2 1 2 3 2 3 2 3 2 3 2 1 2
Следующая тройка – 1/3, затем $e1^3, и т.д. Попробуйте закончить разбор выражения самостоятельно – должно получиться всё правильно. Конечно, в виде программы это было бы интереснее, но дойдем и до нее.
Логические выражения, по-видимому, будут считаться практически так же, только у них есть одна интересная особенность – выход по короткому условию, и это мы рассмотрим в следующей статье. |