Распознавание и вычисление
арифметических выражений
Vitamin/CAIG/2001
В данной статье будут затронуты темы
компиляторов и трансляторов, в частности,
вычисление арифметического выражения по
его символьной записи. Например, как ко─
мпьютер может вычислить выражение типа
(10+20)*30-40? Человек, глядя на это выра─
жение, сразу скажет ответ. А как быть,если
в выражении присутствует огромное число
скобок? Тут даже самый одарённый математик
задумается,хотя само выражение может реша─
ться очень просто. А компьютер не обладает
человеческим интеллектом,как это ни груст─
но,он умеет только считать. Вот и надо его
научить считать подобные вещи. Этим мы с
вами сейчас и займемся.
Начнем с лексического анализа.Лексичес─
кий анализ всегда предшествует синтаксиче─
скому анализу и заключается в предварите─
льной обработке выражения и его перекоди─
ровании к виду, удобному для синтаксичес─
кого анализа. Лексический анализ принято
отделять от синтаксического по двум причи─
нам:
- для сокращения времени компиляции;
- синтаксис лексем всегда проще,чем син─
таксис программ.
Лексический анализ сводится к разбиению
текста программы на лексические единицы
(лексемы) - конструкции, выступающие как
терминальные символы для синтаксического
анализа.Лексемы ещё иногда называют симво─
лами или атомами.Т.е.,символы "(","10","+"
ничего компьютеру не говорят. Для него это
просто данные. Причем разной длины. А наша
задача - преобразовать их в удобочитаемый
для компьютера вид. Этим и занимается
лексический анализ. Синтаксический анализ
(проверку на корректность выражения) обыч─
но делают после лексического.В данной ста─
тье он подробно рассматриваться не будет,
но пару слов позже скажу.
Лексему можно представить в виде пары
(класс,значение).Значение может быть непо─
средственным или представлять собой ссылку
на некоторую таблицу, в которой хранятся
значения лексем. В частности,для нашей за─
дачи необходимо использование трех типов
лексем: разделители, операции и числовые
константы.Пусть у нас имеются таблицы раз─
делителей и операций. Вот они:
Разделитель Индекс Операция Индекс
пробел 0 < цикл.сдвиг влево 0
# решетка 1 > цикл.сдвиг вправо 1
% процент 2 ! исключающее ИЛИ 2
( скобка1 3 & логическое И 3
) скобка2 4 ~ инверсия 4
| логическое ИЛИ 5
- вычитание 6
+ сложение 7
= сравнение 8
/ деление 9
* умножение 10
. мл.часть операнда 11
' ст.часть операнда 12
При этом в поле значения лексемы храни─
тся индекс операции или разделителя. Для
числовых констант также имеется таблица
значений, которая создается по ходу анали─
за. Далее будем обозначать лексему сочета─
нием вида БукваЦифра, например, знак минус
будет кодироваться как O6 (Operation 6),
разделитель скобка1 будет кодироваться как
D3 (Delimiter 3). Лексемы констант будут
иметь префикс N (Number).
Задача лексического анализа достаточно
простая, сложность может составлять только
анализ многосимвольных лексем (в нашем
случае,числа). Здесь можно применить метод
проб. На вход программе подаются символы,и
она проверяет их на предмет принадлежности
к классу разделителей.Если удачно,на выход
поступает соответствующая лексема. Если
неудача, происходит проверка на принадлеж─
ность к классу операций.И так далее.Вычле─
нение символьных констант происходит путем
определения их левых и правых границ.Далее
константы переводятся в числовой вид и за─
носятся в таблицу констант. При этом, если
такая константа в таблице уже есть, то она
не заносится заново, а возвращается индекс
уже существующей константы.
Примечание 1. Так как рассматриваемая
задача достаточно ограничена, я не буду
рассматривать другие классы лексем.Это мо─
гут быть идентификаторы (если используются
переменные), ключевые слова,метки,символь─
ные константы (это если на вход поступает
текст более высокого уровня,чем ассемблер)
и т.д. При этом необходимо также выделять
другие многосимвольные конструкции: те же
ключевые слова,метки,а также многолитерные
операции и разделители.
Раз уж мы затронули тему языков более
высокого уровня (рассматриваемая задача
распознавания арифметических выражений яв─
ляется частным случаем понятий трансляции
и компиляции, причем именно с языков высо─
кого уровня), стоит вернуться к обещанной
теме синтаксического анализа.Частично кон─
троль правильности выражения выполняется
уже на уровне лексического анализа. Обычно
это проверка на допустимое сочетание сим─
волов при объявлении констант, идентифика─
торов и т.д. Но текст программы, абсолютно
правильный с точки зрения лексики, может
быть неправильным синтаксически. В нашем
случае сюда входит контроль последователь─
ности символов (чтобы операции находились
в разрешенных сочетаниях), числа скобок в
арифметических выражениях.Задача синтакси─
ческого анализа достаточно сложна и решае─
тся путем составления грамматики входного
языка и разбора набора лексем рекурсивным
алгоритмом в соответствии с грамматикой. В
нашем же случае можно ограничиться вышеу─
казанными операциями.
Следующим этапом распознавания является
перевод выражения в формате лексем в обра─
тную польскую запись.Обратная польская за─
пись (ОПЗ) представляет собой одну из форм
записи выражений и операторов, отличитель─
ной особенностью которой является то, что
все аргументы (или операнды) расположены
перед операцией (оператором).
Например,выражение,записанное в обычной
скобочной записи,
(a+d)/c+b*(e+d),
будучи представлено в ОПЗ, получает вид:
ad+c/bed+*+.
Обратная польская запись получила широ─
кое распространение благодаря своему осно─
вному преимуществу: выражение (оператор),
записанное в виде ОПЗ,может быть выполнено
за один просмотр цепочки слева направо. В
системном программировании широко применя─
ется обработка цепочек символов, поэтому
необходимы алгоритмы получения ОПЗ по при─
нципу обработки строк:преобразование вход─
ной строки в выходную,которая является об─
ратной польской записью.
Для построения ОПЗ можно использовать
дерево выражения.В вершинах дерева находя─
тся операции (операторы), а листьями явля─
ются аргументы. Например, для приведённого
примера дерево будет выглядеть так:
(+)
/
(/) (*)
/ /
(+) c b (+)
/ /
a d e d
При этом в вершине каждого поддерева
находится операция, которая будет выполня─
ться последней.Для преобразования дерева в
линейную запись используется просмотр де─
рева, начиная от самого нижнего левого ли─
ста, слева направо. После просмотра всех
листов происходит переход к корню, и т.д.
Связав готовую ОПЗ с этим деревом, вы без
труда вычислите алгоритм преобразования.
Но формализовать этот алгоритм, чтобы
он был понятен машине,очень сложно.Поэтому
для этого используются другие способы.Наи─
более известным из таких алгоритмов являе─
тся алгоритм Дейкстры. В нём используется
стек,куда помещаются операции. Каждой опе─
рации приписывается свой приоритет. Кроме
этого, определяются правила работы со сте─
ком.
1) Входная строка просматривается слева
направо.
2) Если рассматриваемый символ является
операндом, то он переносится в выходную
строку, иначе обрабатывается стеком следу─
ющим образом:
- Если стек пуст, операция заносится в
стек.
- Если в стеке верхний элемент (опера─
ция) имеет более высокий приоритет,то
рассматриваемая операция проталкивае─
тся в стек.
- Если в стеке верхний элемент (опера─
ция) имеет более низкий приоритет, то
из стека выталкиваются все элементы
(операции) до тех пор, пока не встре─
тится операция с приоритетом выше,чем
у рассматриваемой операции,после чего
эта операция проталкивается в стек.
- Если входной символ "(", то он про─
талкивается в стек.
- Если входной символ ")", то он выта─
лкивает из стека все знаки до ближай─
шей ")". Сами скобки взаимно уничто─
жаются и в выходную строку не попада─
ют.
Таблица приоритетов операций:
Операции | Приоритет
. ' ~ | 0
* / | 1
+ - | 2
= | 3
& ! | | 4
< > | 5
Рассмотрим пример работы алгоритма:
Вход |( a + d ) / c + b * ( e + d ) <end>
------+-----------------------------------
С |( + / + * ( + * +
т | ( + * ( +
е | + *
к | +
------+-----------------------------------
Выход | a d + c / b e d + * +
По окончании входного потока на выход
передаются все символы из стека до тех
пор, пока стек не освободится. В итоге по─
лучаем, что на выходе присутствуют только
операции и их аргументы. Данная запись на─
зывается обратной потому,что операция сто─
ит после операндов (есть ещё и прямая, где
операция предшествует операндам,но нам она
не нужна).
Примечание 2. Таким образом, т.е.согла─
сно алгоритму Дейкстры, можно перевести в
ОПЗ не только арифметическое выражение, но
и программу на ЯВУ (Языке Высокого Уров─
ня).При этом нужно определить дополнитель─
ные классы лексем: описание и вызов функ─
ций, описание и адресация массивов, услов─
ные и безусловные переходы. В результате
получится описание на языке низкоуровневых
конструкций, как нельзя лучше приспособ─
ленных к дальнейшей трансляции в машинный
код. Подробную информацию можно получить в
литературе по данной теме.
Следующим,и последним,шагом будет непо─
средственно вычисление выражения. Как вы,
наверное, уже успели убедиться, вычисление
по ОПЗ получается легким и быстрым, выпол─
няемым за один проход. Алгоритм вычисления
вкратце таков:
1) Если на вход поступает операнд (конс─
танта), то он заносится в стек.
2) Если на вход поступает оператор,то из
стека извлекается необходимое число опера─
ндов и выполняется операция. Результат за─
носится обратно в стек.Необходимо помнить,
что в стеке операнды хранятся в обратном
порядке.
3) После завершения на вершине стека бу─
дет лежать ответ.
Вот и всё.Далее идет пример программной
реализации всего вышеописанного. Программа
имеет ряд особенностей:
- все числа имеют 16-битный формат;
- при построении ОПЗ не учитываются уна─
рные + и - ;
- константы могут быть в трех системах
счисления;
- поддерживаются все основные арифмети─
ческие операции и логические;
- приоритет операций описан в таблице,
т.е.циклический сдвиг,например,выполняется
после всех остальных операций;
- логические операции имеют одинаковый
приоритет и выполняются слева направо;
- синтаксический анализ реализован час─
тично (нет контроля числа скобок), поэтому
лучше задавать корректные выражения, иначе
возможно переполнение стека.
После запуска программа показывает на
экране исходное выражение,ответ,запись вы─
ражения в виде лексем и ОПЗ в виде лексем.
Ред.: Полный вариант программы см. в
приложении (COUNT.H), здесь приводим толь─
ко основные фрагменты.
...
CALL LEXIC ;вызов лексич.анализ-ра
RET C ;была ошибка
LD HL,DESTIN ;вывод лексем
LD DE,#4800 ;символьной записи
CALL WRITE_LEX
CALL BPR_CNV ;перевод в ОПЗ
RET C ;была ошибка
LD HL,BPR_BUF ;вывод лексем ОПЗ
LD DE,#5000
CALL WRITE_LEX
CALL EVALUATE ;вычисление
;результат - в BC
LD HL,STRIN
LD E,4
DOANSW XOR A
DUP 4
RL C,B
RLA
EDUP
ADD A,48
CP 58
JR C,ADOK
ADD A,7
ADOK LD (HL),A
INC HL
DEC E
JR NZ,DOANSW
LD HL,SOURCE
LD DE,#4000
CALL PRINT
LD HL,STRING
LD DE,#40C0
PRINT LD A,(HL)
AND A
RET Z
CALL WR_SYM
INC HL
JR PRINT
STRING DB "Answer is: #"
STRIN DB "0000",0
;Классы лексем
OPERATION=1 ;операция
DELIMITER=OPERATION+1 ;разделитель
NUMBER=DELIMITER+1 ;числовая константа
SOURCE=#C000 ;строка выражения
DESTIN=#E000 ;лексический анализ
BPR_BUF=#D000 ;обратная польская запись
DIGITS=#8000 ;буфер числовых констант
;---------- Лексический анализ -----------
LEXIC
LD (RETSP+1),SP ;сохр.адр.возврата
LD HL,SOURCE
LD IX,DESTIN
XOR A ;настройка
LD (DIGITS),A
LD B,A
LD C,A
LEXCYC LD A,(HL) ;последний символ строки
LD (IX),A
AND A
RET Z
CALL IS_DELIM ;это разделитель?
JR C,NODELIM
INC HL ;заносим
LD (IX),DELIMITER
LODCONT LD (IX+1),A
LD B,(IX)
LD C,A
INC IX,IX
JR LEXCYC
NODELIM CALL IS_OPER ;это операция?
JR C,NOOPER
INC HL ;заносим
LD (IX),OPERATION
JR LODCONT
NOOPER CALL IS_DIGIT ;это числ.константа?
JP C,ERROR ;если нет,тогда ошибка
LD (IX),NUMBER
JR LODCONT
;Проверки принадл-сти лексем разл. классам
IS_DELIM
EXX
LD HL,DELIMITERS
IS_TST LD C,0
CONSEAR INC (HL)
DEC (HL)
JR Z,ENDLST
CP (HL)
JR NZ,NOEL
LD A,C
EXX
RET
NOEL INC L
INC C
JR CONSEAR
ENDLST EXX
SCF
RET
IS_OPER
EXX
LD HL,OPERATIONS
JR IS_TST
IS_DIGIT
EXA
LD A,B
CP DELIMITER
JR NZ,NODELM
LD A,C ;если предыдущий символ=
DEC A ;указатель сист.счисления.
JP Z,HEX ;шестнадцатеричной
DEC A
JP Z,BIN ;двоичной
NODELM EXA
CP "0
RET C ;если это не число
CP "9"+1
JR C,ISDIG
CCF
RET
ISDIG LD E,0 ;счетчик допустимых симв-в
DIGOK INC E
INC HL
LD A,(HL)
CP "0
JR C,ENDDIG
CP "9"+1
JR C,DIGOK
CP "A
JR C,ENDDIG
CP "Z"+1
JP C,ERROR
CP "a
JR C,ENDDIG
CP "z"+1
JP C,ERROR
CP 128
JP NC,ERROR
ENDDIG
PUSH HL
;перевод из строки (HL) в число HL'
...
ENDDECOD
EXX ;занесение в список констант
PUSH IX
LD IX,DIGITS
LD E,0
LD A,(NUMBERS)
AND A
JR Z,ADDNUM ;ни одной нет,заносим
LD B,A
DOSEAR LD A,(IX) ;поиск
CP L
JR NZ,NEXNUM
LD A,(IX+1)
CP H
JR Z,RETNUM ;нашли - не заносим,но
;возвращаем индекс
NEXNUM INC E
INC IX,IX
DJNZ DOSEAR
ADDNUM LD (IX),L ;добавл-е нов.константы
LD (IX+1),H
LD A,(NUMBERS) ;увелич-ем их число
INC A
LD (NUMBERS),A
RETNUM POP IX
LD A,E ;возврат индекса константы
AND A
EXX
POP HL
RET
;Шестнадцатеричная константа
HEX DEC IX,IX ;нужно удалить специфи-
;катор из выходной строки
ISHEX LD E,-1
DEC HL
HEXOK INC E ;счетчик числа символов
INC HL
LD A,(HL)
CP "0
JR C,ENDHEX
CP "9"+1
JR C,HEXOK
CP "A
JR C,ENDHEX
CP "Z"+1
JP C,HEXOK
CP "a
JR C,ENDHEX
CP "z"+1
JP C,HEXOK
CP 128
JP NC,ERROR
ENDHEX
LD A,E ;ни одного симв.нет=>ошибка
AND A
JR Z,ERROR
PUSH HL
EXX
LD HL,0
EXX
LD A,E ;возврат к первому символу
BAKHEX DEC HL
DEC A
JR NZ,BAKHEX
DOHEX LD A,(HL) ;занесение тетрад,нач.со
SUB "0 ;старших.Если в числе более
CP 10 ;4 тетрад,лишние теряются
JR C,H1
SUB 7
H1 EXX
RLA
RLA
RLA
RLA
DUP 4
RLA
RL L,H
EDUP
EXX
INC HL
DEC E
JR NZ,DOHEX
JP ENDDECOD
;Двоичная константа
BIN ;аналогично разбору
... ;шестнадцатеричных констант
JP ENDDECOD
ERROR LD A,2 ;индикация ошибки
OUT (-2),A
RETSP LD SP,0 ;и возврат
SCF
RET
;Перевод в обратную польскую запись (ОПЗ)
BPR_CNV
LD (RETSP+1),SP ;настройка
LD IX,DESTIN
LD HL,BPR_BUF
LD BC,0
PUSH BC ;инициализация стека -
;занесение маркера конца стека
BPR_CYC LD A,(IX) ;чтение по одной лексеме
LD E,(IX+1)
AND A
JR Z,FINISH ;больше лексем нет
LD D,A
CP DELIMITER
JR Z,DELIMS ;разделитель
CP OPERATION
JR Z,OPERA ;операция
OUT_LEX LD (HL),D ;вывод лексем на выход
INC HL
LD (HL),E
INC HL
NEXSY INC IX,IX
JR BPR_CYC
DELIMS LD A,E ;разбор разделителей
AND A
JR Z,NEXSY ;пробел - пропускаем
SUB 3 ;открывающая скобка -
JR Z,PUSHA ;занесение в стек
DEC A
JR Z,POPA ;закрывающая скобка
OPERA POP BC
PUSH BC ;элемент с вершины стека
CALL GET_PRIO ;его приоритет
LD C,E ;текущий элемент
LD B,D
PUSH BC ;занесение в стек (*)
LD E,A
CALL GET_PRIO ;и его приоритет
CP E ;если приоритет меньше,
JR C,NEXSY ;то занести(*:уже есть)
POP DE ;иначе - текущий элемент
POP BC ;и элемент с вершины
LD (HL),B ;верхний эл-т - на выход
INC HL
LD (HL),C
INC HL
JR OPERA ;выталкиваем до тех пор,
;пока не встретится лексема
;с меньшим приоритетом
PUSHA PUSH DE ;лексему в стек (скобка)
JR NEXSY
POPA ;закрывающая скобка - выталкивание
POP DE ;всех эл-тов до ближайшей
LD A,D ;открывающей
CP DELIMITER
JR NZ,COUT
LD A,E ;открывающая скобка
CP 3 ;тоже выталкивается,
JR Z,NEXSY ;но не выводится
COUT LD (HL),D
INC HL
LD (HL),E
INC HL
JR POPA
FINISH POP DE ;завершение трансляции -
LD (HL),D ;выталкивание всех
INC HL ;эл-тов из стека и вывод.
LD (HL),E
INC HL
LD A,D
AND A
JR NZ,FINISH
RET
;взятие приоритета лексемы
GET_PRIO ;BC=LEXEM, A<=PRIO
LD A,B
CP OPERATION
JR Z,OP_PRIO
CP DELIMITER
JR NZ,OTHER
LD B,'DEL_PRIO
LD A,C
ADD A,DEL_PRIO
LD C,A
LD A,(BC)
RET
OTHER LD A,-1 ;наивысший приоритет у
RET ;"лишних" лексем (обычно
;это маркер конца стека)
OP_PRIO
LD B,'OPR_PRIO
LD A,C
ADD A,OPR_PRIO
LD C,A
LD A,(BC)
RET
;------ Вычисление выражения по ОПЗ ------
EVALUATE
LD (RETSP+1),SP ;настройка
LD IX,BPR_BUF
DOEVAL LD D,(IX)
LD E,(IX+1)
LD A,D
AND A
JR NZ,CONTEV
POP BC ;конец выражения
RET
CONTEV CP NUMBER
JR NZ,NONUM
LD D,0 ;число - занесение в стек
LD HL,DIGITS ;поиск в буфере
EX DE,HL
ADD HL,HL
ADD HL,DE
LD E,(HL)
INC HL
LD D,(HL)
PUSSHA PUSH DE
INC IX,IX
JR DOEVAL
NONUM CP OPERATION ;остались только
;операторы, разделителей
JP NZ,ERROR ;в ОПЗ быть не должно!
;Выполн.опер-й над эл-тами с вершины стека
;(одним или 2-мя,при этом на вершине стека
;лежит _второй_ операнд
LD A,E
AND A
JR NZ,SH_R
POP BC,DE ;циклический сдвиг влево
DOSHL LD A,D
RLA
RL E,D
DEC BC
LD A,B
OR C
JR NZ,DOSHL
JR PUSSHA
SH_R DEC A
JR NZ,XOR_
POP BC,DE ;циклич.сдвиг вправо
...
JR PUSSHA
XOR_ DEC A
JR NZ,AND_
POP BC,DE ;битовое исключающее ИЛИ
...
JR PUSSHA
AND_ DEC A
JR NZ,CPL_
POP BC,DE ;битовое ИЛИ
...
JR PUSSHA
CPL_ DEC A
JR NZ,OR_
POP DE ;побитовая инверсия
...
JR PUSSHA
OR_ DEC A
JR NZ,MINUS
POP BC,DE ;битовое И
...
JR PUSSHA
MINUS DEC A
JR NZ,PLUS
POP DE,HL ;вычитание
AND A
SBC HL,DE
EX DE,HL
JR PUSSHA
PLUS DEC A
JR NZ,EQUAL
POP DE,HL ;сложение
ADD HL,DE
EX DE,HL
JR PUSSHA
EQUAL DEC A
JR NZ,DIVIDE
;сравнение двух чисел. Результат:0 или 1
POP BC,HL
...
JP PUSSHA
DIVIDE DEC A
JP NZ,MULT
POP BC,DE ;деление с округлением
...
JP PUSSHA
MULT DEC A
JP NZ,LOPART
POP DE,BC ;умножение
...
JP PUSSHA
LOPART DEC A
JR NZ,HIPART
POP DE ;нижняя часть слова
LD D,0
JP PUSSHA
HIPART DEC A
JP NZ,ERROR
POP DE ;верхняя часть слова
LD E,0
JP PUSSHA
;Сервисная ф-ция вывода лексем для записи.
WRITE_LEX
... ;берёт слова из HL, байт 0=end
WR_SYM ... ;печать симв. A на экран в DE
ORG '($-1)+1*256
DELIMITERS DB " #%()",0 ;разделители
OPERATIONS DB "<>!&~|-+=/*.'",0 ;операции
NUMBERS DB 0 ;число констант
;приоритеты разделителей и операций
DEL_PRIO DB 0,0,0, 6,6
OPR_PRIO DB 5,5, 4,4,0,4, 2,2, 3, 1,1, 0,0
ORG SOURCE
DB <выражение> ,0
