Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік ғылымда Сети-Уллман алгоритмі – Рави Сети және Джеффри Д. Уллманның, осы алгоритмді ойлап тапқандардың есімімен аталатын, абстрактілі синтаксистік ағаштарды мүмкіндігінше аз тіркегіштерді қолданатын машиналық кодқа түрлендіруге арналған алгоритм.
In computer science, the Sethi–Ullman algorithm is an algorithm named after Ravi Sethi and Jeffrey D. Ullman, its inventors, for translating abstract syntax trees into machine code that uses as few registers as possible.
Шолу
Арифметикалық өрнектер үшін кодты жасау кезінде компилятор өрнекті нұсқамалар саны және белгілі бір кіші ағашты бағалау үшін қажетті регистрлер саны тұрғысынан қалай аударудың ең тиімді жолын анықтауы керек. Әсіресе, бос регистрлер жетіспесе, бағалау реті жасалған кодтың ұзындығына әсер етуі мүмкін, себебі әртүрлі реттелулер аралық мәндердің жадқа құйылуына және кейін қалпына келтірілуіне себеп болуы мүмкін. Сети-Улман алгоритмі (Сети-Улман нөмірлеуі деп те аталады) мүмкіндігінше аз нұсқамалар мен жадқа сілтемелерді қажет ететін кодты құрады (операторларға қатысты коммутативтілік және ассоциативтілік қағидалары ең көп жағдайда қолданылады, бірақ дистрибутивтік заңдар қолданылмайды). Алгоритм, егер қолданылған өрнектер үшін коммутативтілік немесе ассоциативтілік қағидалары қолданылмаса, да сәтті орындалады, сондықтан арифметикалық түрлендірулерді қолдану мүмкін емес. Алгоритм сондай-ақ ортақ қосымша өрнектерді пайдаланбайды және жалпы бағытталған ациклдік графтар түрінде ұсынылған өрнектерге тікелей қолданылмайды.
When generating code for arithmetic expressions, the compiler has to decide which is the best way to translate the expression in terms of number of instructions used as well as number of registers needed to evaluate a certain subtree. Especially in the case that free registers are scarce, the order of evaluation can be important to the length of the generated code, because different orderings may lead to larger or smaller numbers of intermediate values being spilled to memory and then restored. The Sethi–Ullman algorithm (also known as Sethi–Ullman numbering) produces code which needs the fewest instructions possible as well as the fewest storage references (under the assumption that at the most commutativity and associativity apply to the operators used, but distributive laws i. e. do not hold). The algorithm succeeds as well if neither commutativity nor associativity hold for the expressions used, and therefore arithmetic transformations can not be applied. The algorithm also does not take advantage of common subexpressions or apply directly to expressions represented as general directed acyclic graphs rather than trees.
Жетілдірілген Сети-Уллман алгоритмі
Сети-Уллман алгоритмінің жетілдірілген нұсқасында арифметикалық өрнектер ең бастысы қолданылатын операторлардың алгебралық қасиеттерін пайдаланып түрлендіріледі.
In an advanced version of the Sethi–Ullman algorithm, the arithmetic expressions are first transformed, exploiting the algebraic properties of the operators used.