10.14489/vkit.2022.08.pp.058-064

DOI: 10.14489/vkit.2022.08.pp.058-064

Амелина О. В., Гордиенко А. П., Чижов А. В.
МЕТОДЫ ВЫЧИСЛЕНИЯ АТРИБУТОВ В НИСХОДЯЩЕМ ТАБЛИЧНО-УПРАВЛЯЕМОМ СИНТАКСИЧЕСКОМ АНАЛИЗАТОРЕ
(с. 58-64)

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

Ключевые слова: синтаксически управляемая трансляция; атрибутные грамматики; LL(1)-разбор; упорядочивание вычисления атрибутов.

Amelina O. V., Gordienko A. P., Chizhov A. V.
ATTRIBUTE EVALUATION METHODS IN A TOP-DOWN TABLE-DRIVEN PARSER
(pp. 58-64)

Abstract. The article outlines methods for efficient computation of attributes in a table-driven top-down parsing process. This methods are based on the introduction of a stack of attributes into the parser. Semantic actions using this stack are defined by one of three methods. The first method is based on the fact that two parsers: table-driven and recursive descent parsers have the same use of depth first traversal. Therefore, the mechanisms for computing attributes in recursive descent are also applicable in a table-driven parser. Then the attribute stack will act like a frame stack of function calls. The second method assumes that the attribute stack is the memory of an abstract machine. For the source language of the translator, the structural-operational semantics is specified, which puts the translation result in line with the language constructions. The semantic actions of the translation scheme are implemented as analyzing and applying rules of an abstract machine built on the basis of structural-operational semantics. The third method assumes that an abstract syntax tree in postfix form will be formed in the attribute stack. Semantic actions for the attribute stack are built in such a way that the expressions formed on the stack are evaluated as far as possible. The article shows that the application of the three proposed methods to the scheme of translation of arithmetic expressions gives the same result. The proposed methods can significantly reduce the amount of memory used and make the design of the translator more understandable.

Keywords: Syntax directed translation; Attribute grammar; LL(1)-parser; Ordering the evaluation of attributes.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

О. В. Амелина, А. П. Гордиенко, А. В. Чижов (Орловский государственный университет имени И. С. Тургенева, г. Орёл, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

O. V. Amelina, A. P. Gordienko, A. V. Chizhov (Orel State University named after I. S. Turgenev, Orel, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Ахо А. В., Лам М. С., Сети Р., Ульман Дж. Д. Компиляторы: принципы, технологии и инструментарий / пер. с англ. 2-е изд. М.: Вильямс, 2008. 1184 с.
2. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов / пер. с англ. М.: Мир, 1979. 655 с.
3. Karel Müller. Attribute-Directed Top-Down Parsing // Lecture Notes in Computer Science. 1992. V. 641. P. 37 – 43.
4. Гордиенко А. П. Вычисление атрибутов в процессе нисходящего таблично-управляемого разбора // Информационные системы и технологии. 2015. № 3(89). С. 5 – 9.
5. Hennessy M. The Semantics of Programming Languages: An Elementary Introduction Using Structural Operational Semantics. New York: John Wiley & Son Ltd, 1990. 170 p.

Eng

1. Aho A. V., Lam M. S., Seti R., Ul'man Dzh. D. (2008). Compilers: principles, technologies and tools. 2nd ed. Moscow: Vil'yams. [in Russian language]
2. L'yuis F., Rozenkrants D., Stirnz R. (1979). Theoretical Foundations of Compiler Design. Moscow: Mir. [in Russian language]
3. Karel Müller. (1992). Attribute-Directed Top-Down Parsing. Lecture Notes in Computer Science, Vol. 641, pp. 37 – 43.
4. Gordienko A. P. (2015). Attribute Computation in Top-Down Wheel-Driven Parsing. Informatsionnye sistemy i tekhnologii, 89(3), pp. 5 – 9. [in Russian language]
5. Hennessy M. (1990). The Semantics of Programming Languages: An Elementary Introduction Using Structural Operational Semantics. New York: John Wiley & Son Ltd.

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 500 руб. (в том числе НДС 20%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа скопируйте doi статьи:

10.14489/vkit.2022.08.pp.058-064

и заполните форму

Отправляя форму вы даете согласие на обработку персональных данных.

Eng

This article is available in electronic format (PDF).

The cost of a single article is 500 rubles. (including VAT 20%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please copy the article doi:

10.14489/vkit.2022.08.pp.058-064

and fill out the form