Кіріспе
Талдау техникасы
Компьютерлік ғылымда жоғарыдан төменге қарай талдау – бұл талдау ағашының ең жоғарғы деңгейіне бастап, формалды грамматиканың қайта жазу ережелерін қолдану арқылы ағашты төменге қарай құру стратегиясы. LL талдағыштары – жоғарыдан төменге қарай талдау стратегиясын қолданатын талдағыш түрі. Жоғарыдан төменге қарай талдау – белгісіз деректер арақатынастарын жалпы талдау ағашы құрылымдарын болжау арқылы, содан кейін белгілі негізгі құрылымдардың болжаммен сәйкес келіп-келмейтінін қарастыру стратегиясы. Бұл табиғи және компьютерлік тілдерді талдау кезінде қолданылады. Жоғарыдан төменге қарай талдауды берілген формалды грамматика ережелерін жоғарыдан төменге қарай кеңейту арқылы кіріс ағынының сол жақтан ең көп туындыларын іздеуге тырысу ретінде қарастыруға болады. Екіұштылықты шешу үшін инклюзивті таңдау грамматика ережелерінің оң жағындағы барлық баламаларды кеңейтуге мүмкіндік береді. Жоғарыдан төменге қарай талдаудың қарапайым нұсқалары сол рекурсивті грамматикалар үшін тоқтамайды, ал кері іздеулі талдау екіұшты CFG-лер үшін кіріс ұзындығына қатысты экспоненциалды уақыт күрделілігіне ие болуы мүмкін. Дегенмен, Фрост, Хафиз және Каллаган жасаған күрделірек жоғарыдан төменге қарай талдағыштар екіұштылықты және сол рекурсияны көп уақытта шешеді және потенциалды экспоненциалдық көлемдегі талдау ағаштарының көпмүшелік өлшемді бейнелерін құрайды.
Top down parsing in computer science is a parsing strategy where one first looks at the highest level of the parse tree and works down the parse tree by using the rewriting rules of a formal grammar. LL parsers are a type of parser that uses a top down parsing strategy. Top down parsing is a strategy of analyzing unknown data relationships by hypothesizing general parse tree structures and then considering whether the known fundamental structures are compatible with the hypothesis. It occurs in the analysis of both natural languages and computer languages. Top down parsing can be viewed as an attempt to find left most derivations of an input stream by searching for parse trees using a top down expansion of the given formal grammar rules. Inclusive choice is used to accommodate ambiguity by expanding all alternative right hand sides of grammar rules. Simple implementations of top down parsing do not terminate for left recursive grammars, and top down parsing with backtracking may have exponential time complexity with respect to the length of the input for ambiguous CFGs. However, more sophisticated top down parsers have been created by Frost, Hafiz, and Callaghan, which do accommodate ambiguity and left recursion in polynomial time and which generate polynomial sized representations of the potentially exponential number of parse trees.
Жоғарғыдан төменге талдаудағы сол рекурсияны қосқанда
Сол рекурсияны қамтитын формальді грамматиканы, егер олар әлсіз эквивалентті оң рекурсивті формаға түрлендірілмесе, қарапайым рекурсивті түсу талдағышымен талдау мүмкін емес. Дегенмен, соңғы зерттеулер сол рекурсивті грамматикаларды (барлық басқа жалпы CFG түрлерімен бірге) қиындатылған жоғарыдан төменге қарайғы талдағышта, қысқарту әдісін қолдану арқылы қолдауға болатынын көрсетеді. Фрост пен Хафиз 2006 жылы кіріс ұзындығы мен ағымдағы кіріс позициясына қатысты тереңдік шектеулерін қою арқылы, үнемі өсіп келе жатқан тікелей сол рекурсивті талдауды қысқартатын және түсініксіз грамматикаларды қолдайтын тану алгоритмін сипаттады. Бұл алгоритм 2007 жылы Фрост, Хафиз және Каллаган тарапынан полиномиалдық уақытта жанама (бұрын есептелген контекстті ағымдағы контекстпен салыстыру арқылы) және тікелей сол рекурсияны қолдайтын, сондай-ақ жоғары екіұшты грамматикалар үшін потенциалды экспоненциалдық санды талдау ағаштарының ықшам полиномиалдық өлшемді бейнелерін жасау үшін толыққанды талдау алгоритміне кеңейтілді.
Жоғарыдан төменге қарай талдаудың уақыт пен кеңістіктегі күрделілігі
Жоғарыдан төменге талдаушы екіұшты CFG-ге қатысты екіұшты кірісті талдауға тырысқанда, барлық мүмкін талдау ағаштарын жасау үшін CFG-нің барлық баламаларын сынап көруге экспоненциалдық қадамдар саны (кірістің ұзындығына қатысты) қажет болуы мүмкін, бұл ақырында экспоненциалдық жад кеңістігін талап етеді. Бір-біріне рекурсивті функциялар жиыны ретінде құрылған жоғарыдан төменге талдаушылардағы экспоненциалдық уақыт күрделілігі мәселесін 1991 жылы Норвиг шешті. Оның әдісі Эрли алгоритміндегі (1970) динамикалық бағдарламалау және күй жиынтықтарын, сондай-ақ Кокке, Янгер және Касамидің CYK алгоритміндегі кестелерді пайдалануға ұқсас. Басты идея – p талдаушысын j позициясында қолдану нәтижелерін жаттау және дәл сол жағдай қайта туындағанда оларды қайта пайдалану. Фрост, Хафиз және Каллаган.
PEG грамматикасының тағы бір түрі болып табылатын PEG-ті пайдаланып, пакрат талдаушылары элегантты және қуатты талдау алгоритмін ұсынады. Parsing expression grammar дегеніне қараңыз.