Тіліңізді талдау! Бағдарламалаудағы "төменнен жоғары" талдау әдісі – мәтінді құрылымдық деңгейлер бойынша түсінуге көмектеседі. Пай өңдеу, синтаксис, тілдер.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы 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.