Из журнала Info Guide #7, Рязань, 06.2005 Распознавание и вычисление арифметических выражений 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 ) ------+----------------------------------- С |( + / + * ( + * + т | ( + * ( + е | + * к | + ------+----------------------------------- Выход | 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