Кампілятар: у чым розніца паміж LL (0) і LR (0) аналізатарамі? Ці ёсць такі разбор, як LL (0) парсер?


адказ 1:

Здаецца, гэтае пытанне сканцэнтравана на аналізатарах LL (0), таму давайце вызначым яго. LL (0) аналізатар разбірае злева направа з 0 лексемамі ў пачатку вытворчасці, каб вызначыць, якую вытворчасць выкарыстоўваць. Што азначае гэты маркер 0? Гэта азначае, што аналізатар не можа выкарыстаць тэкст для аналізу, каб вызначыць, якую вытворчасць выкарыстоўваць. Гэта азначае, што аналізатар не можа зрабіць выбар. Гэта трэба ведаць, перш чым пачаць дакладна аналізаваць парадак лексем, якія ён будзе аналізаваць. Парадак токенаў павінен быць вызначаны. Гэта значыць, што аналізатар можа прааналізаваць толькі адзін парадак. Такім чынам, у вас можа быць аналізатар, які піша "Прывітанне, свет!" Прымаецца. з такой граматыкай:

Мэта: клічнік «Прывітанне», касмічны «свет»;

Звярніце ўвагу, што дапускаюцца толькі варыяцыі таго, як лексер адпавядае лексемам.

(Я спадзяюся, што пазначэнні відавочныя - гэта, па сутнасці, той, які я выкарыстоўваю ў Yacc ++. Цытаваныя радкі з'яўляюцца лексемамі, як і любыя нявызначаныя ідэнтыфікатары.)

Парсер заўсёды чакае аднолькавага парадку жэтонаў. Не павінна быць толькі адно правіла, як гэта зрабіў наш першы прыклад. Гэта можа выглядаць так.

Мэта: прывітанне, частка касмічнай часткі;

Прывітанне: Hallo1;

прывітанне1: "прывітанне";

Канчатковая частка: апошняя частка свету;

Міравая частка: "Мір";

апошняя частка: "!";

Аднак варта ўлічыць, што ні адно з правілаў не ўтрымлівае "або" (|) аператараў і існуе толькі адно правіла для не-тэрмінала. Такім чынам, аналізатар можа ведаць, як адпавядаць кожнаму правілу без выкарыстання дыскрымінацыйных лексем (лексем, якія выбіраюць, у якім кірунку ідзе аналізатар), робячы граматыку LL (0).

Ці можна цяпер выкарыстоўваць рэкурсіўную прадукцыю і ўсё яшчэ мець граматыку LL (0)? Адказ не. Паглядзім, што адбудзецца, калі ў нас ёсць рэкурсіўнае правіла.

Мэта: "х" мэта "у";

Памятайце, што мы дазваляем толькі адно правіла на неканферэнцыйных і не "ці" аператараў. Такім чынам, калі мы падыходзім да рэкурсіўнага закліку да мэты, мы павінны знайсці спосаб вярнуцца да гэтага рэкурсіўнага выкліку, бясконцага цыкла. Дакажыце сабе, што не важна, як мы размяшчаем гэты званок, ці рэкурсія ўскосная. Гэта заўсёды прыводзіць да бясконцай пятлі.

Такім чынам, граматыка LL (0) павінна прааналізаваць абмежаваны спіс лексем, дакладна канечны спіс (той самы спіс кожны раз).

Звярніце ўвагу на розніцу ў значэнні LR (0). Аналізатар LR (k) можа выкарыстоўваць любую колькасць лексем у межах вытворчасці, каб адрозніць яго плюс да k лексем ад кантэксту, у якім памяншаецца вытворчасць, каб вызначыць, ці варта яго скарачаць. У выпадку LR (0) ніякіх дадатковых токенаў нельга выкарыстоўваць, каб вызначыць, ці варта іх памяншаць. Гэта проста трэба вырашыць на аснове лексем, якія звычайна памяншаюцца. Вось простая граматыка LR (0):

Мэта: "х" | "(" Брама ")";

У гэтай граматыцы разбіраецца "х", акружаны шэрагам дужак. Звярніце ўвагу, што маркер "х" і токен "(" можна выкарыстоўваць, каб вызначыць, якое правіла ўжыць. 0 у LR (0) не абмяжоўвае выкарыстанне лексем у межах правілаў, як і 0. У LL (0). Адзінае, што абмяжоўвае яго, - гэта выкарыстанне лексем (у кантэксце, як правіла, для некаторых выпадкаў, якія не належаць да канца), калі вы выбіраеце зніжэнне. Гэтай граматыцы не патрэбны ніякі кантэкст, спыніць свой выбар на зніжэнні. У першай альтэрнатыве ён памяншаецца, убачыўшы "х", а ў другім - пасля ")". Лексемы ўнутры правіла вызначаюць, калі правіл трэба скараціць.


адказ 2:

Парлятары LL (0) азначаюць, што яны апрацоўваюць паток токенаў злева направа, выкарыстоўваючы крайні левы вытворны без прадбачання. Тэарэтычна, LL (0) аналізатары магчымыя, але нават калі яны існуюць, я не бачу для іх вялікай карысці. LL (0) аналізатары павінны прадказаць, якія вытворчасці выкарыстоўваць на аснове бягучага не-тэрмінала з нулявым прагнозам. У такіх граматыках на кожны не-тэрмінал можа быць прызначана толькі адна прадукцыя, і не павінна быць рэкурсіі.

Аналізатары LR (0) азначаюць, што яны апрацоўваюць паток токенаў злева направа, выкарыстоўваючы вытворную ў крайняй правай частцы з выглядам наперад. Гэта азначае, што яны будуюць дрэва аналізу знізу ўверх, а аналагі LL (0) будуюць дрэва аналізу зверху ўніз.