Кіріспе
Компьютерлік ғылымның ресми тіл теориясында сол рекурсия – рекурсияның ерекше түрі, онда тізбек сол тілдің өзіне жататын тізбекке (сол жағында) және жұрнаққа (оң жағында) жіктелуі арқасында сол тілдің бір бөлігі ретінде танылады. Мысалы, оны да сома болатын және қолайлы жұрнақпен бөлуге болады, сондықтан ол сома ретінде танылуы мүмкін. Контекстсіз грамматика бойынша, егер оның бір өндірісіндегі ең сол жақ символ өзі болса (тікелей сол рекурсия жағдайында) немесе алмастырулардың бірнеше тізбегі арқылы оған айналдырылса (көрінеу сол рекурсия жағдайында), онда терминалды емес символ сол рекурсивті болып саналады.
Тікелей емес сол жақ рекурсия
Жанама сол рекурсия сол рекурсияның анықтамасы бірнеше алмастырулар арқылы орындалғанда пайда болады. Ол келесі үлгіге сәйкес келетін ережелер жиынтығын қамтиды:
where are sequences that can each yield the empty string, while may be any sequences of terminal and nonterminal symbols at all. Note that these sequences may be empty. The derivation
then gives as leftmost in its final sentential form.
мұнда бос тізбекке айнала алатын тізбектер, ал кәдімгі және терминалдық емес символдардың кез келген тізбектері болуы мүмкін. Бұл тізбектер бос болуы мүмкін. Осыдан кейін туынды соңғы сөйлем түрінде сол жақтан басталады.
where are sequences that can each yield the empty string, while may be any sequences of terminal and nonterminal symbols at all. Note that these sequences may be empty. The derivation
then gives as leftmost in its final sentential form.
Қолданылуы
Сол жақты рекурсия көбінесе сол жақтан ассоциативті операцияларды жасау үшін қолданылатын тәсіл ретінде танылады: a+b c d+e өрнегі (((a+b) c) d)+e түрінде есептелінеді. Бұл жағдайда, есептеу ретін үш грамматикалық ереже арқылы синтаксистік тұрғыдан қол жеткізуге болады. Бұл ережелер a+b c d+e өрнегін a+b c d және e-ден құралған деп талдауға мүмкіндік береді, ал a+b c d өрнегі өз кезегінде a+b c және d-ден, ал a+b c өрнегі a+b және c-ден тұрады, және т.б.
These only allow parsing the a+b c d+e as consisting of the a+b c d and e, where a+b c d in turn consists of the a+b c and d, while a+b c consists of the a+b and c, etc.
Сол жақ рекурсияны өшіру
Сол рекурсия көбінесе синтаксистік талдағыштар үшін қиындық тудырады, себебі ол оларды шексіз рекурсияға түсіреді (әсіресе жоғарыдан төменге қарай талдайтын жағдайда) немесе олар оны қабылдамайтын қалыпты формадағы ережелерді күтеді (көптеген төменнен жоғарыға қарай талдайтын жағдайда). Сондықтан, грамматика көбінесе сол жақ рекурсияны жою мақсатымен алдын ала өңделеді.
Жоғарғыдан төменге талдаудағы сол рекурсияны қосқанда
Сол жақты рекурсияны қамтитын формальді грамматика LL(k) талдауышы немесе басқа да қарапайым рекурсивті түсу талдауышымен талдаылмайды, егер ол әлсіз эквивалентті оң жақты рекурсивті формаға түрлендірілмесе. Керісінше, LALR талдауыштары үшін сол жақты рекурсия қолайлы, себебі ол оң жақты рекурсияға қарағанда стекті аз пайдалануға мүмкіндік береді. Дегенмен, күрделі жоғарыдан төменге қарай талдауыштар қысқарту арқылы жалпы контекстсіз грамматиканы іске асыра алады. 2006 жылы Фрост және Хафиз екі мәнді грамматиканы тікелей сол жақты рекурсивті өндіріс ережелерімен үйлестіретін алгоритмді сипаттады. Бұл алгоритм, 2007 жылы Фрост, Хафиз және Каллаганның жұмысымен, полиномиал уақыт ішінде тікелей де, жанама да сол жақты рекурсияны қамтитын толыққанды талдау алгоритміне кеңейтілді, сондай-ақ жоғары екі мәнді грамматикалар үшін талдау ағаштарының потенциалды экспоненциалды санының ықшам полиномиал өлшемді бейнелерін жасады. Авторлар кейіннен алгоритмді Haskell бағдарламалау тілінде жазылған талдауыш комбинаторлары жиынтығы ретінде іске асырды.