Сол рекурсия - Left recursion

Ішінде ресми тіл теориясы туралы Информатика, сол жақтағы рекурсия ерекше жағдай болып табылады рекурсия мұнда жол сол тілден (сол жақта) және жұрнақпен (оң жақта) ыдырауымен тілдің бөлігі ретінде танылады. Мысалы, қосынды ретінде тануға болады, өйткені оны бөлуге болады , сонымен бірге қосынды және , қолайлы жұрнақ.

Жөнінде контекстсіз грамматика, а термиялық емес сол-рекурсивті болып табылады, егер оның өндірістерінің біріндегі сол жақтағы таңба өзі болса (тікелей сол жақтағы рекурсия жағдайында) немесе оны кейбір алмастырулар тізбегі арқылы жасауға болады (жанама сол рекурсия жағдайында).

Анықтама

Грамматика сол жақтағы рекурсивті болып табылады, егер ол терминальды емес таңба болса ғана а-дан шығуы мүмкін жіберілген форма сол жақтағы символ ретінде.[1] Символикалық түрде,

,

қайда бір немесе бірнеше ауыстырулар жасау операциясын көрсетеді, және терминалды және терминальды емес символдардың кез-келген реттілігі.

Тікелей рекурсия

Тікелей сол рекурсия анықтаманы тек бір алмастырумен қанағаттандыра алатын кезде пайда болады. Ол үшін форманың ережесі қажет

қайда бұл терминал емес және терминалдар тізбегі. Мысалы, ереже

тікелей сол-рекурсивті болып табылады. Солдан оңға рекурсивті түсіру талдаушысы бұл ереже келесідей көрінуі мүмкін

жарамсыз Өрнек() {  Өрнек();  матч('+');  Мерзім();}

және мұндай код орындалған кезде шексіз рекурсияға түседі.

Жанама сол рекурсия

Жанама сол рекурсия бірнеше ауыстырулар арқылы сол рекурсияның анықтамасын қанағаттандырғанда пайда болады. Бұл үлгі бойынша ережелер жиынтығын талап етеді

қайда әрқайсысы нәтиже бере алатын тізбектер болып табылады бос жол, ал терминалдық және терминальды емес символдардың кез-келген реттілігі болуы мүмкін. Бұл тізбектер бос болуы мүмкін екенін ескеріңіз. Туынды

содан кейін береді оның соңғы сенсорлық түрінде сол жақта.

Сол жақтағы рекурсияны жою

Сол рекурсия көбінесе талдаушыларға қиындықтар туғызады, өйткені бұл оларды шексіз рекурсияға әкеледі (көп жағдайда сияқты жоғарыдан төмен қарай талдаушылар ) немесе олар бұған тыйым салатын қалыпты формадағы ережелерді күткендіктен (көп жағдайда сияқты) төменнен жоғары қарай талдаушылар, оның ішінде CYK алгоритмі ). Сондықтан, сол жақтағы рекурсияны жою үшін грамматика алдын-ала өңделеді.

Тікелей рекурсияны жою

Тікелей сол рекурсияны жоюдың жалпы алгоритмі келтірілген. Бұл әдіс бірнеше рет жетілдірілді.[2]Сол жақтағы рекурсивті емес , форманың кез-келген ережелерін тастаңыз және қалғандарын қарастыру:

қайда:

  • әрқайсысы - бұл терминалдар мен терминалдардың бос емес тізбегі, және
  • әрқайсысы деп басталмайтын терминал емес терминалдар тізбегі .

Оларды екі қойылыммен ауыстырыңыз, біреуі үшін :

және басқа жаңа термиялық емес жиынтық (көбінесе «құйрық» немесе «демалыс» деп аталады):

Бұл процесті сол жақта тікелей рекурсия қалмағанша қайталаңыз.

Мысал ретінде ережелер жинағын қарастырайық

Сол жақтағы рекурсияны болдырмау үшін оны қайта жазуға болады

Барлық сол рекурсияны жою

A құру арқылы топологиялық тапсырыс сол жақтағы жанама рекурсияны жою үшін жоғарыда аталған процестерді созуға болады[дәйексөз қажет ]:

Кірістер Грамматика: бейтерминалдар жиынтығы және олардың өндірістері
Шығу Бір тілде шығарылатын, бірақ сол рекурсиясыз өзгертілген грамматика
  1. Әрбір термиялық емес үшін :
    1. Итерация грамматиканы өзгеріссіз қалдырғанша қайталаңыз:
      1. Әр ереже үшін , терминалдар мен бейтерминалдар тізбегі бола отырып:
        1. Егер терминалды емес басталады және :
          1. Келіңіздер болуы оның жетекшісіз .
          2. Ережені алып тастаңыз .
          3. Әр ереже үшін :
            1. Ережені қосыңыз .
    2. Үшін тікелей сол жақ рекурсияны алып тастаңыз жоғарыда сипатталғандай.

Бұл алгоритмнің терминальді емес реттеуге өте сезімтал екенін ескеріңіз; оңтайландыру көбінесе осы тапсырысты жақсы таңдауға бағытталған.[түсіндіру қажет ]

Ұңғымалар

Жоғарыда келтірілген түрлендірулер грамматика арқылы қалыптасқан тілді сақтағанымен, олар өзгеруі мүмкін ағаштарды талдау бұл куәгер жолдарды тану. Сәйкес бухгалтерлік есеппен, ағашты қайта жазу түпнұсқаларын қалпына келтіре алады, бірақ егер бұл қадам алынып тасталса, айырмашылықтар талдаудың семантикасын өзгерте алады.

Ассоциативтілік әсіресе осал; сол жақ-ассоциативті операторлар, әдетте, жаңа грамматикаға сәйкес оң ассоциативті құрылымдарда пайда болады. Мысалы, осы грамматикадан бастап:

сол рекурсияны жою үшін стандартты түрлендірулер мынаны береді:

«1 - 2 - 3» жолын бірінші грамматикамен LALR талдаушысында (сол жақ рекурсивті грамматиканы басқара алатын) талдағанда, талдау моделі пайда болады:

Қосарлы азайтуды сол-рекурсивті талдау

Бұл талдау ағашы сол жақтағы терминдерді дұрыс семантикасын топтастырады (1 - 2) - 3.

Екінші грамматикамен талдауға мүмкіндік береді

Екі есе азайтуды оң-рекурсивті талдау

бұл дұрыс түсіндірілген, білдіреді 1 + (-2 + (-3)), сондай-ақ дұрыс, бірақ енгізілімге аз адал және кейбір операторлар үшін іске асыру әлдеқайда қиын. Оң жақтағы терминдер ағашта қалай тереңірек болатынына назар аударыңыз, өйткені оң-рекурсивті грамматика оларды қалай ұйымдастырады 1 - (2 - 3).

Жоғарыдан төмен қарай талдауда сол рекурсияны орналастыру

A ресми грамматика сол рекурсияны қамтуы мүмкін емес талданды а LL (k) -сервер немесе басқа аңғалдық рекурсивті түсіру талдаушысы егер ол а-ға ауыстырылмаса әлсіз эквивалент оң-рекурсивті форма. Керісінше, сол жақ рекурсияға басымдық беріледі LALR талдаушылары өйткені бұл стектің төмен қолданылуына әкеледі оң рекурсия. Алайда, жоғарыдан төменге қарай талдаушылар жалпыға бірдей қолдана алады контекстсіз грамматика қысқарту арқылы. 2006 жылы Аяз бен Хафиз сәйкес келетін алгоритмді сипаттады анық емес грамматикалар тікелей сол-рекурсивті өндіріс ережелері.[3] Бұл алгоритм толықтай кеңейтілді талдау жанама, сонымен қатар тікелей сол рекурсияны орналастыру алгоритмі көпмүшелік және 2007 жылы Аяз, Хафиз және Каллаганның екіұшты грамматикалары үшін талдауға болатын экспоненциалды санның ықшам полиномдық өлшемдерін құру.[4] Содан кейін авторлар алгоритмді жиынтығы ретінде іске асырды талдаушы комбинаторлар жазылған Хаскелл бағдарламалау тілі.[5]

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Ресми тіл теориясы және талдау туралы ескертпелер, Джеймс Пауэр, Ирландия Ұлттық университетінің компьютерлік ғылымдар бөлімі, Мейнут Майнут, Килдаре, Ирландия.JPR02
  2. ^ Мур, Роберт С. (мамыр 2000). «Контекстсіз грамматикадан сол рекурсияны жою» (PDF). 6-шы қолданбалы табиғи тілді өңдеу конференциясы: 249–255.
  3. ^ Аяз, Р .; Р.Хафиз (2006). «Көпмүшелік уақыттағы екіұштылық пен солға рекурсияны орналастырудың жаңа жоғарыдан төменге бөлінетін алгоритмі». ACM SIGPLAN ескертулері. 41 (5): 46–54. дои:10.1145/1149982.1149988., автор қол жетімді http://hafiz.myweb.cs.uwindsor.ca/pub/p46-frost.pdf Мұрағатталды 2015-01-08 Wayback Machine
  4. ^ Аяз, Р .; Р.Хафиз; П. Каллаган (маусым 2007). «Екі жақты солға-рекурсивті грамматикаға жоғары-төмен модульдік және тиімді талдау» (PDF). Бөлшектеу технологиялары бойынша 10-шы халықаралық семинар (IWPT), ACL-SIGPARSE: 109–120. Архивтелген түпнұсқа (PDF) 2011-05-27.
  5. ^ Аяз, Р .; Р.Хафиз; П. Каллаган (қаңтар 2008). Екі жақты солға-рекурсивті грамматикаларға арналған саралаушы комбинаторлар (PDF). 10 Халықаралық декларативті тілдердің практикалық аспектілері (PADL) симпозиумы, ACM-SIGPLAN. Информатика пәнінен дәрістер. 4902. 167–181 бет. дои:10.1007/978-3-540-77442-6_12. ISBN  978-3-540-77441-9.

Сыртқы сілтемелер