Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
В информатике, парсинг выявляет грамматическую структуру линейного входного текста как первый шаг к пониманию его значения. Построчный анализ (снизу вверх) сначала распознает детали самого низкого уровня, затем структуры среднего уровня, а общую структуру верхнего уровня – последней.
In computer science, parsing reveals the grammatical structure of linear input text, as a first step in working out its meaning. Bottom up parsing recognizes the text's lowest level small details first, before its mid level structures, and leaving the highest level overall structure to last.
Снизу вверх против сверху вниз
Название "снизу вверх" происходит от концепции дерева разбора, в котором наиболее детальные части находятся внизу перевернутого дерева, а более крупные структуры, составленные из них, – в последовательно более высоких слоях, пока в верхней части или "корне" дерева одна единица не описывает весь входной поток. Разбор снизу вверх обнаруживает и обрабатывает это дерево, начиная с нижнего левого конца, и постепенно продвигается вверх и вправо. Парсер может оперировать с уровнями иерархии структуры – низким, средним и высшим – не создавая фактического дерева данных; дерево тогда лишь подразумевается в действиях парсера. Разбор снизу вверх терпеливо ждет, пока не отсканирует и разберет все части некоторой конструкции, прежде чем определить, что представляет собой комбинированная конструкция. Противоположностью этому является разбор сверху вниз, в котором сначала определяется (или предполагается) общая структура ввода, прежде чем приступать к частям среднего уровня, оставляя завершение всех деталей самого нижнего уровня на потом. Парсер сверху вниз обнаруживает и обрабатывает иерархическое дерево, начиная с вершины, и постепенно продвигается сначала вниз, а затем вправо. Разбор сверху вниз быстро определяет, что такое конструкция, на раннем этапе, когда был просканирован только самый левый символ этой конструкции и ни одна из ее частей еще не разобрана. Разбор левого угла – это гибридный метод, который работает снизу вверх вдоль левых границ каждого поддерева и сверху вниз по остальной части дерева разбора. Если в грамматике языка есть несколько правил, которые могут начинаться с одних и тех же левых символов, но иметь разные окончания, то эта грамматика может быть эффективно обработана детерминированным разбором снизу вверх, но не может быть обработана сверху вниз без предположений и отката. Таким образом, парсеры снизу вверх на практике обрабатывают несколько более широкий диапазон грамматик языков программирования, чем детерминированные парсеры сверху вниз. Разбор снизу вверх иногда выполняется с использованием отката, но гораздо чаще он выполняется с помощью парсера сдвига-свертки, такого как LALR-парсер.
The bottom up name comes from the concept of a parse tree, in which the most detailed parts are at the bottom of the upside down tree, and larger structures composed from them are in successively higher layers, until at the top or "root" of the tree a single unit describes the entire input stream. A bottom up parse discovers and processes that tree starting from the bottom left end, and incrementally works its way upwards and rightwards. A parser may act on the structure hierarchy's low, mid, and highest levels without ever creating an actual data tree; the tree is then merely implicit in the parser's actions. Bottom up parsing patiently waits until it has scanned and parsed all parts of some construct before committing to what the combined construct is. The opposite of this is top down parsing, in which the input's overall structure is decided (or guessed at) first, before dealing with mid level parts, leaving completion of all lowest level details to last. A top down parser discovers and processes the hierarchical tree starting from the top, and incrementally works its way first downwards and then rightwards. Top down parsing eagerly decides what a construct is much earlier, when it has only scanned the leftmost symbol of that construct and has not yet parsed any of its parts. Left corner parsing is a hybrid method that works bottom up along the left edges of each subtree, and top down on the rest of the parse tree. If a language grammar has multiple rules that may start with the same leftmost symbols but have different endings, then that grammar can be efficiently handled by a deterministic bottom up parse but cannot be handled top down without guesswork and backtracking. So bottom up parsers in practice handle a somewhat larger range of computer language grammars than deterministic top down parsers do. Bottom up parsing is sometimes done by backtracking. But much more commonly, bottom up parsing is done by a shift reduce parser such as a LALR parser.