Устройство для синтаксического анализа программ Советский патент 1985 года по МПК G06F17/27 

Изобретение относится к вычислительной технике и может быть использовано для предварительной обработки дискретной информации, а именно для преобразования инфиксной записи алегбраической формулы в постфиксную, что широко используется при создании специализированных вычислительных средств, предназначенных для моделирования динамических объектов, описываемых полиноминальными уравнениями, а также при определении последовательности вычислений сложных алгебраических выражений в операционных системах.

Цель изобретения - расширение функциональных возможностей за счет обеспечения преобразования инфиксной записи в постфиксную.

На фиг. 1 изображена структурная схема устройства; на фиг. 2 - структурная схема блока микропрограммного управления; на фиг. 3 - временная диаграмма работы устройства.

На схемах обозначен блок 1 микропрограммного управления., узел 2 ввода кодов, буферный регистр 3, узлы 4, 5 считывания, блок 6 вывода, блок 7 регистров, мультиплексор 8, блоки 9, 10, 11 и 12 сравнения, узлы 13, 14, 15 и 16 памяти, узел 17 постоянной памяти, регистр 18 адреса, узел 19 формирования адреса, регистр 20 микрокоманд, триггер 21, счетчик 22, генератор 23 импульсов.

Узел 19 Служит для формирования адреса следующей микрокоманды, на его входы поступает информация из регистра 20 микрокоманд, в котором хранится текущая микрокоманда, с выхода счетчика 22 (символов) для анализа его содержимого на ноль, с выходов узлов 13, 14, 15 и 16 памяти. Триггер 21 служит для установки управляющих потенциалов на выходе блока 1, управляющие импульсы поступают на входы триггера от регистра 20 микрокоманд. Счетчик 22 (символов) служит для организации работы устройства, перед началом работы в счетчике устанавливается число символов исходной записи. Сигнал вычитания единицы поступает на вход счетчика из регистра 20 микрокоманды, и при равенстве нулю хранящегося в счетчике числа устройство заканчивает работу.

Узел 2 ввода кодов представляет собой память, в которой записываются коды символов исходной записи. Сигналы чтения, прибавления единицы к счетчику адреса, обнуления счетчика адреса поступают из блока 1.

Буферный регистр 3 служит для промежуточного хранения информации, в регистре записывается код символа при чтении этого кода из узла 2 ввода кодов. Регистр сбрасывается по сигналу, поступающему из блока 1.

Узлы 4 и 5 считывания служат для передачи информации соответственно из буферного регистра 3 и блока 7 регистров на выход устройства через блок 6. Управляющие импульсы, поступающие из блока 1, пропускают информацию, поступающую на узлы 4 и 5 считывания.

Блок 6 служит для объединения одноименных разрядов кодов, поступающих с выходов узлов 4 и 5, и вывода их на

0 выход устройства.

Блок 7 регистров служит для промежуточного хранения информации и состоит из сдвиговых регистров, количество которых равно числу двоичных разрядов в коде. Информация, поступающая на вход блока регистров, записывается в нулевые разряды регистров по синхроимпульсу, поступающему из блока 1. Одновременно с записью происходит сдвиг информации вправо (из младших разрядов регистров в старшие).

0 Сдвиг влево осуществляется по сигналу из блока 1, при этом информация, записанная в нулевых разрядах регистров, уничтожается.

Каждый из блоков 9-12 состоит из связанных между собой узла памяти и схемы

сравнения. Узел памяти подключен к одному из входов схемы сравнения, к другому входу которой подключен выход мультиплексора 8. По сигналу запуска, поступающему от блока 1, происходит сравнение кода, поступающего с выхода мультиплексора 8, и кодов, заданных в-блоках сравнения. Нри совпадении кодов блок сравнения вырабатывает сигнал равенства кодов. Этот сигнал поступает на вход соответствующего узла памяти и там запоминается.

Назначение выходов и входов блока 1 следующее. Первый выход, включащий в себя три двоичных разряда, поступающих из регистра 20 микрокоманды, подключен к входу узла 2 ввода кодов и служит для выдачи сигналов чтения, прибавления единицы к счетчику адреса и обнуления счетчика адреса. Второй выход подключен к входу буферного регистра 3 и служит для выдачи сигнала сброса, поступающего из регистра 20 микрокоманды. Третий и четвертый выходы подключены соответственно к входам узлов 4 и 5 считывания и служат для выдачи управляющих импульсов, поступающих из регистра микрокоманды 20. Пятый выход подключен к входам узлов 13-16 памяти и служит для выдачи сигнала сброса их, поступающего из регистра микрокоманды 20. Шестой выход подключен к входам блоков 9-12 и служит для выдачи сигнала запуска работы блоков сравнения. Седьмой выход, включающий в себя два двоичных разряда, подключен к входу блока 7 регистров и служит для выдачи синхроимпульса записи и сигнала сдвига влево. Восьмой выход подключен к входу мультиплексора 8 и служит для управления этим

мультиплексором при помощи сигнала, поступающего с выхода триггера 21.

Первый, второй, третий, четвертый входы блока подключены соответственно к выходам узлов 13, 14, 15, 16 и служат для анализа информации, хранящейся в этих узлах. Пятый вход служит для запуска работы устройства, а также для начальной установки счетчика 22 (символов).

Устройство выполняет преобразование инфиксной записи в постфиксную или так называемую «польскую запись. Входной информацией в устройстве является формула, описывающая операнды, участвующие в операциях, знаки операций и порядок выполняемых действий. Формула записывается с соблюдением следующих ограничений вся формула должна быть заключена в скобки; порядок действий указывается скобками; операнды обозначаются символическими идентификаторами.

Постфиксная запись характеризуется тем, что не требует скобок и четко определяет порядок действий. Правила перевода из инфиксной записи в постфиксную сформулированы следующим образом: идентификаторы в «польской записи следуют в том порядке, что и в инфракрасной записи: знаки действий в «польской записи следуют в том порядке, в каком они должны вычисляться (слева направо); знаки действий располагаются непосредственно за своими операндами.

Алгоритм преобразования инфиксной записи в постфиксную следующий.

Выбирается очередной символ записи. Происходит проверка, не является ли он последним в записи. Если нет, то осуществляется переход к щагу 2, в противном случае алгоритм заканчивает работу.

Если выбранный импульс является открывающей скобкой («(«) ,то происходит переход к щагу 3, если идентификатором, то происходит переход к шагу 4, если знаком действия, то происходит переход к шагу 5, если закрывающей скобкой ()), то происходит переход к шагу 6.

Символ записывается в рабочее поле. Происходит переход к шагу 1.

Символ записывается в постфиксную запись. Если предыдущий символ является знаком действия, то осуществляется переход к шагу 7, в противном случае происходит переход к шагу 1.

Символ записывается в рабочее поле. Происходит переход к шагу 1.

Знаки действия, записанные в рабочем поле, записываются в постфиксную запись в порядке, обратном порядку занесения в рабочее поле. Осуществляется переход к шагу 1.

Знак действия помещается в постфиксную запись. Уменьшается количество элементов в рабочем поле. Осуществляется .переход к шагу 1.

Устройство работает следующим образом. Выборка очередного символа записи означает чтение очередного кода символа из узла 2 и занесение его в буферный регистр 3. Занесение символа в рабочее поле означает запись кода символа в блоке 7 регистров. Занесение символа в «польскую запись означает передачу кода символа на вход устройства. Перед началом работы по входам ввода программ в блоки 9-

0 12 заносятся соответственно коды символов, используемых идентификаторов, знаков действия, открываюшей скобки, закрывающей скобки.

По включении питания сбрасывается счетчик адреса узла 2 ввода кодов, счетчик 22

(символов) блока 1, буферный регнистр 3, узлы 13-16 памяти.

В узел 2 заносится исходная запись, после чего в счетчике адреса узла 2 ввода кодов находится адрес последнего символа

Q записи, в счетчике (символов) блока 1 - число символов исходной записи. По сигналу «Пуск, поступающему на вход блока 1, устройство начинает работу.

По сигналу с выхода блока 1 сбрасывается счетчик адреса узла 2 ввода кодов.

5 Происходит анализ на ноль содержимого счетчика 22 (символов).

Если содержимое счетчика не равно нулю, то устройство продолжает работать, в противном случае сигналами с выходов блока 1 сбрасываются счетчик адреса узла

° 2 ввода кодов, буферный регистр 3, узлы 13- 16 памяти. Таким образом, устройство под готавливается к работе.

Сигналом «Чтение с выхода блока 1 в буферный регистр 3 считывается код

5 очередного символа записи из узла 2. Сигналом с выхода блока 1 выход буферного регистра 3 подключается к входу мультиплекорса 8. Осуществляется запуск работы блоков 9-12. Происходит, анализ содержимого узлов 13-16.

0 Если выбранный символ является открывающей скобкой, т.е. установлен в единицу узел 15 памяти, то по сигналу с выхода блока 1 код символа, записанный в буферном регистре 3, записывается в блок 7 ре- гистров. По сигналам с выходов блока 1 происходит прибавление единицы к счетчику адреса узла 2, сброс буферного регистра 3, сброс узлов памяти. Таким образом, устройство переходит к выборке кода очередного символа.

0 Если выбранный символ является идентификатором, т. е. установлен в единицу узел 15 памяти, то по сигналу с выхода блока 1 код символа, записанный в буферном регистре 3, через узел 4 считывания, блок 6 передается на выход устройства. По сигналу

5 с выхода блока 1 сбрасываются узлы памяти. Выход блока 7 регистров подключается к входу мультиплексора 8. Сигналом с выхода блока 1 осуществляется запуск работы блоков 9-12. Происходит анализ содержимого узлов памяти. Если символ, записанный последним в блок 7 регистров, является знаком действием, т.е. установлен в единицу, то по сигналу с выхода блока 1 код этого символа через узел 5 считывания и блок 6 передается на выход устройства. По сигналу с выхода блока 1 происходит сдвиг влево в блоке 7 регистров. Устройство переходит к выборке следующего символа, как было описано выше. Если символ, записанный последним в блок 7 регистров, не является знаком действия, то устройство переходит к выборке следуюпдего символа, как было описано выше.

Если выбранный символ является знаком действия, т. е. установлен в единицу узел 14 памяти, то по сигналу с блока 1 код этого символа, записанный в буферном регистре 3, записывается в блок 7 регистров. Устройство переходит к выборке следующего символа, как было описано выше.

Если выбранный символ является закрывающей скобкой, т. е. установлен в единицу узел 16 памяти, происходит анализ кода символа, записанного последним в блок 7 регистров, как было описано выше. Если этот символ является знаком действия, его код передается на выход устройства, как было описано выше. По сигналу с выхода

блока 1 происходит сдвиг влево в блоке 7 регистров. Происходит анализ следующего символа, записанного в блоке 7 регистров. Таким образом, коды знаков действия, записанные в блок 7 регистров, передаются на выход устройства в порядке, обратном порядку их записи в блок 7 регистров, до тех пор,пока код символа, выдаваемый на выход блока 7, не будет являться кодом закрывающей скобки. В этом случае по сигналу с выхода блока I происходит сдвиг влево в блоке 7 регистров и устройство переходит к выборке следующего символа, как было описано выше.

Всякий раз, когда устройство переходит к выборке следующего символа, по сигналу из регистра 20 микрокоманд содержимое

0 счетчика (символов) блока I уменьшается на единицу. Устройство повторяет цикл работы, начиная с анализа на ноль содержимого счетчика 22. Если содержимое счетчика (символов) равно нулю, устройство заканчивает работу как было описано выше.

УСТРОЙСТВО ДЛЯ СИНТАКСИЧЕСКОГО АНАЛИЗА ПРОГРАММ, содержащее узел ввода кодов, информационный вход которого является первым информационным входом устройства, первый и второй узлы считывания, выходы которых соединены соответственно с входами блока вывода, выход которого является выходом устройства, четыре блока сравнения, первые информационные входы которых соединены с вторым информационным входом устройства, а выходы подключены соответственно к информационным входам первого, второго, третьего и четвертого узлов памяти, отличающееся тем, что, с целью расширения функциональных возможностей за счет обеспечения преобразования инфиксной записи в постфиксную, в него введены блок регистров, буферный регистр, блок микропрограммного управления и мультиплексор, выход которого подключен к вторым информационным входам с первого по четвертый блоков сравнения, первый и второй информационные входы мультиплексора соединены соответственно с выходами разрядов буферного регистра и информационным выходом блока регистров, информационный вход буферного регистра соединен с выходом узла ввода кодов, вход считывания которого подключен к первому выходу блока микропрограммного управления, второй, третий и четвертый выходы которого подключены соответственно к установочному входу буферного регистра, к разрешающему входу первого узла считывания и к разрешающему входу второго узла считывания, пятый выход блока микропрограммного управления подключен к установочным входам узлов памя(Л ти, выходы которых соединены соответственно с первым, вторым, третьим и четвертым входами блока микропрограммного управления, пятый вход которого является входом пуска устройства, шестой выход блока микропрограммного управления подключен к входам стробирования блоков сравнения, седьмой и восьмой выходы соединены соответственно с синхронизируоо ющим входом блока регистров и с разре00 шающим входом мультиплексора, информа ционные входы блока регистров и первого СП узла считывания соединены с выходами разрядов буферного регистра, выход блока ел регистров соединен с информационным входом второго узла считывания.

ВыходРМК