Компьютерлік ғылымда LR талдағыштары

Кіріспе

Компьютерлік ғылымдағы талдаушының түрі

Компьютерлік ғылымда LR талдаушылары – шешілген контекстсіз тілдерді сызықтық уақытта талдайтын төменнен жоғарыға қарай талдаушының бір түрі. LR талдаушыларының бірнеше нұсқалары бар: SLR талдаушылары, LALR талдаушылары, канондық LR(1) талдаушылары, минималды LR(1) талдаушылары және жалпыланған LR талдаушылары (GLR талдаушылары). LR талдаушыларын талдаушы генераторы формальды грамматикадан жасауға болады, ол талдауға тиіс тілдің синтаксисін анықтайды. Олар компьютерлік тілдерді өңдеуде кеңінен қолданылады. LR талдаушысы (солдан оңға, кері ең оң жақ туынды) кіріс мәтінін солдан оңға кері қадам жасамай оқиды (бұл көптеген талдаушылар үшін рас), және кері ең оң жақ туындыны жасайды: ол төменнен жоғарыға қарай талдау жасайды – жоғарыдан төменге LL талдауы немесе арнайы талдау емес. "LR" атауынан кейін көбінесе сандық белгі қойылады, мысалы "LR(1)" немесе кейде "LR(k)". Артқа қайту немесе болжаудан аулақ болу үшін LR талдаушысына бұрынғы символдарды қалай талдауды шешуге дейін k алдын ала қарау символына қарауға рұқсат етіледі. Әдетте k 1-ге тең және айтылмайды. "LR" атауының алдында "SLR" және "LALR" сияқты басқа да белгілер жиі болады. Грамматика үшін "LR(k)" белгісін Кнут "солдан оңға k шегімен аударылатын" деп ұсынған.

L, R және k қасиеттерінің жоғарыдағысы шын мәнінде барлық ығысу-азайту талдаушыларымен, соның ішінде басымдық талдаушыларымен ортақ. Бірақ конвенция бойынша, LR атауы Дональд Кнут ойлап тапқан талдау түрін білдіреді және бұрынғы, аз қуатты басымдық әдістерін (мысалы, Оператор басымдығы талдаушысы) алып тастайды. Себебі LR талдаушысы тапқан нәрсені бекіткенше, кейбір грамматикалық үлгінің толық мысалын көргенше күтеді. LL талдаушысы осы үлгідегі ең сол жақ кіріс символын көрген кезде, не көріп тұрғанын әлдеқайда ертерек шешуі немесе болжауы керек.

Мысалы , төменнен жоғарыға қарай талдау ағашы

LR талдаушысы кіріс мәтінін бір рет алға қарай қарап, сканерлеп және талдайды. Талдаушы талдау ағашын төменнен жоғарыға, солдан оңға қарай, болжамдар жасамай немесе кері қайтпай, бірте-бірте құрастырады. Осы процестің кез келген сәтінде талдаушы кіріс мәтінінің бұрын талданған кіші ағаштарының немесе фразаларының тізімін жинақтайды. Бұл кіші ағаштар әлі біріктірілмеген, себебі талдаушы оларды біріктіретін синтаксистік үлгінің оң жағына жеткен жоқ. Мысал ретінде 6-қадамда тек "A*2" толық емес талданды. Талдау ағашының тек қараңғыланған төменгі сол жақ бұрышы ғана бар. 7 және одан жоғары нөмірленген талдау ағашының түйіндері әлі жоқ. 3, 4 және 6 түйіндері A айнымалысы, * операторы және 2 саны үшін жекеленген кіші ағаштардың түбірлері болып табылады. Бұл үш түбір түйін уақытша талдау стегінде сақталады. Кіріс ағынының талданбаған қалған бөлігі "+ 1" болып табылады.

Әрекеттерді ауыстырып , азайту

Басқа ауысу-азайту талдағыштары сияқты, LR талдағышы ауысу және азайту қадамдарының әртүрлі комбинацияларын орындау арқылы жұмыс істейді. Ауысу қадамы кіріс ағынында бір символға жылжиды. Ауысқан символ жаңа, бір түйіндік талдау ағашын құрайды. Азайту қадамы жақында құрылған талдау ағаштарына толыққан грамматикалық ережені қолданып, оларды жаңа түбірлік символмен бір ағашқа біріктіреді. Егер кірісте синтаксистік қателер болмаса, талдағыш барлық кіріс ағыны өңделгенге және барлық талдау ағаштары толыққанда заңды кірісті көрсететін жалғыз ағашқа дейін азайтылғанға дейін осы қадамдарды жалғастырады. LR талдағыштары басқа ауысу-азайту талдағыштарынан азайтуды қашан орындау керектігі және ұқсас аяқталулары бар ережелердің арасынан қалай таңдау керектігін шешу әдісімен ерекшеленеді. Бірақ соңғы шешімдер мен ауысу немесе азайту қадамдарының тізбегі бірдей болады. LR талдағышының тиімділігінің көп бөлігі оның детерминистік болуынан туындайды. Болжам жасаудан аулақ болу үшін LR талдағышы бұрынғы сканерленген символдармен не істеу керектігін шешу алдында келесі сканерленген символға (оңға қарай) көз жүгізеді. Лексикалық сканер талдағыштан бір немесе бірнеше символға озып жұмыс істейді. Көз жүгізу символдары – талдау шешімінің «оң жақ контексі».

Төменнен жоғары қарай талдау стегі

Басқа ауысу-қайтару талдағыштары сияқты, LR талдағышы да біріктірілген конструкцияның қандай екеніне толық сенімді болу үшін, алдымен конструкцияның барлық бөліктерін сканерлеп, талдағанша күтеді. Содан кейін талдағыш осы біріктірілген конструкция бойынша бірден әрекет етеді, одан әрі күтпейді. Тікелей ағаш мысалында, А тіркесі 1-3 қадамдарда, алдын ала қарау белгісі * көрінерде-ақ, А мәніне, содан кейін Өнімдерге дейін қысқартылады. А-ны қалай өңдеу туралы шешімдер тек талдағыш пен сканердің бұрынғыда көргендеріне негізделеді, оң жақта кейін пайда болатын нәрселер ескерілмейді. Қысқартулар қараңғы белгіден сол жақтағы, соңғы талданған бөліктерді дереу қайта ұйымдастырады. Сондықтан, талданған бөліктердің тізімі стек сияқты жұмыс істейді. Бұл талдау стегі оңға қарай өседі. Стектің негізі сол жақта орналасқан және ең көне талданған фрагментті сақтайды. Әрбір қысқарту қадамы тек оң жақтағы, ең жаңа фрагменттерге ғана әсер етеді. (Бұл жинақтамалы талдау стегі жоғарыдан төмен талдағыштар қолданатын болжамды, солға қарай өсетін талдау стегінен мүлдем өзгеше.)

LR генераторды талдау

Бұл мақаланың осы бөлімін LR анализатор генераторларын қолданушылардың көпшілігі оқымауға болады.

Көзқарас құрылғылары

Күйлер мен өтулер талдау кестесінің жылжу әрекеттері мен goto әрекеттері үшін қажетті барлық ақпаратты береді. Генератор сондай-ақ әрбір қысқарту әрекеті үшін күтілетін алдын ала қарау жиынтықтарын есептеуі керек. SLR талдағыштарында бұл алдын ала қарау жиынтықтары грамматикадан тікелей анықталады, жеке күйлер мен өтулер ескерілмейді. Әрбір бейтерминал S үшін SLR генераторы Follow(S) есептейді, бұл S-тің кез келген пайда болуынан кейін тікелей келуі мүмкін барлық терминал символдарының жиынтығы. Талдау кестесінде S-ке әрбір қысқарту LR(1) алдын ала қарау жиынтығы ретінде Follow(S) қолданады. Мұндай іздеу жиынтықтары LL жоғарыдан төменге қарай талдағыш генераторларында да қолданылады. Follow жиынтықтарын пайдаланған кезде жылжу/қысқарту немесе қысқарту/қысқарту қайшылықтары жоқ грамматика SLR грамматикасы деп аталады. LALR талдағыштары SLR талдағыштарымен бірдей күйлерге ие, бірақ әрбір жеке күй үшін ең аз қажетті қысқарту алдын ала қарауларын анықтаудың күрделірек, дәлдік жолын қолданады. Грамматиканың егжей-тегжейіне байланысты бұл SLR талдау генераторлары есептеген Follow жиынтығымен бірдей болуы мүмкін немесе SLR алдын ала қарауларының кіші жиынтығы болуы мүмкін. Кейбір грамматикалар LALR талдау генераторлары үшін жарамды, бірақ SLR талдау генераторлары үшін жарамсыз. Бұл грамматикада Follow жиынтықтарын пайдаланып жалған жылжу/қысқарту немесе қысқарту/қысқарту қайшылықтары болған кезде, бірақ LALR генераторы есептеген нақты жиынтықты пайдаланғанда қайшылықтар болмаған кезде болады. Грамматика содан кейін LALR(1) деп аталады, бірақ SLR емес. SLR немесе LALR талдағышы қайталанған күйлерді болдырмайды. Бірақ бұл азайту қажет емес, кейде қажетсіз қайшылықтар тудыруы мүмкін. Канондық LR талдағыштары бейтерминалдың қолданылуының сол және оң контекстін жақсы есте сақтау үшін қайталанған (немесе "бөлінген") күйлерді қолданады. Грамматикадағы S символының әрбір пайда болуы өзінің алдын ала қарау жиынтығымен қарастырылуы мүмкін, қысқарту қайшылықтарын шешуге көмектеседі. Бұл тағы бірнеше грамматиканы қамтиды. Өкінішке қарай, бұл грамматиканың барлық бөліктері үшін жасалса, талдау кестелерінің көлемін ұлғайтады. Бұл күйлерді бөлу кез келген SLR немесе LALR талдағышы арқылы қолмен және таңдаулы түрде, кейбір бейтерминалдардың екі немесе одан да көп атаулы көшірмелерін жасау арқылы орындалуы мүмкін. Канондық LR генераторы үшін қайшылықсыз, бірақ LALR генераторында қайшылықтары бар грамматика LR(1) деп аталады, бірақ LALR(1) емес және SLR емес. SLR, LALR және канондық LR талдағыштары кіріс ағыны дұрыс тіл болғанда дәл сол жылжу және қысқарту шешімдерін жасайды. Кірісте синтаксистік қате болған кезде LALR талдағышы қателерді анықтау алдында канондық LR талдағышынан гөрі қосымша (қатерсіз) қысқартуларды жасай алады. Ал SLR талдағышы одан да көп нәрсе жасай алады. Бұл SLR және LALR талдағыштары нақты жағдайдағы шынайы, минималды алдын ала қарау символдарына жомарт суперсет шамасын қолданатынына байланысты болады.

The states and transitions give all the needed information for the parse table's shift actions and goto actions. The generator also needs to calculate the expected lookahead sets for each reduce action. In SLR parsers, these lookahead sets are determined directly from the grammar, without considering the individual states and transitions. For each nonterminal S, the SLR generator works out Follows(S), the set of all the terminal symbols which can immediately follow some occurrence of S. In the parse table, each reduction to S uses Follow(S) as its LR(1) lookahead set. Such follow sets are also used by generators for LL top down parsers. A grammar that has no shift/reduce or reduce/reduce conflicts when using Follow sets is called an SLR grammar. LALR parsers have the same states as SLR parsers, but use a more complicated, more precise way of working out the minimum necessary reduction lookaheads for each individual state. Depending on the details of the grammar, this may turn out to be the same as the Follow set computed by SLR parser generators, or it may turn out to be a subset of the SLR lookaheads. Some grammars are okay for LALR parser generators but not for SLR parser generators. This happens when the grammar has spurious shift/reduce or reduce/reduce conflicts using Follow sets, but no conflicts when using the exact sets computed by the LALR generator. The grammar is then called LALR(1) but not SLR. An SLR or LALR parser avoids having duplicate states. But this minimization is not necessary, and can sometimes create unnecessary lookahead conflicts. Canonical LR parsers use duplicated (or "split") states to better remember the left and right context of a nonterminal's use. Each occurrence of a symbol S in the grammar can be treated independently with its own lookahead set, to help resolve reduction conflicts. This handles a few more grammars. Unfortunately, this greatly magnifies the size of the parse tables if done for all parts of the grammar. This splitting of states can also be done manually and selectively with any SLR or LALR parser, by making two or more named copies of some nonterminals. A grammar that is conflict free for a canonical LR generator but has conflicts in an LALR generator is called LR(1) but not LALR(1), and not SLR. SLR, LALR, and canonical LR parsers make exactly the same shift and reduce decisions when the input stream is the correct language. When the input has a syntax error, the LALR parser may do some additional (harmless) reductions before detecting the error than would the canonical LR parser. And the SLR parser may do even more. This happens because the SLR and LALR parsers are using a generous superset approximation to the true, minimal lookahead symbols for that particular state.

Синтаксистік қателерді қалпына келтіру

LR талдаушылары бағдарламадағы алғашқы синтаксистік қатеге қатысты белгілі бір көмекші қате хабарламаларын шығара алады, күтпеген жаман көзқарас символының орнына келесі кездесуі мүмкін барлық терминал символдарды тізімдеу арқылы. Бірақ бұл талдаушыға кіріс бағдарламасының қалған бөлігін талдап, тәуелсіз қателерді іздеуге көмектеспейді. Егер талдаушы бірінші қатеден нашар қалпына келсе, ол қалған бөлікті дұрыс талдамай, көптеген пайдасыз жалған қате хабарламаларын тудыруы мүмкін. Yacc және bison талдаушы генераторларында талдаушының ағымдағы оператордан бас тартуға, қатеге дейін табылған сөз тіркестерін және көзқарас токендерін жоюға, содан кейін жартылай нүктелер немесе жақшалар сияқты сенімді оператор деңгейіндегі шектеуіште талдауды қайта синхрондауға арналған арнайы механизмі бар. Бұл көбінесе талдаушы мен компиляторға бағдарламаның қалған бөлігін қарауға мүмкіндік береді. Көптеген синтаксистік кодтау қателері – қарапайым қате жазу немесе маңызды символдың жіберілуі. Кейбір LR талдаушылары осы жиі кездесетін жағдайларды анықтап, автоматты түрде жөндеуге тырысады. Талдаушы қате орнындағы әрбір мүмкін символдың қосылуын, жойылуын немесе алмасуын қарастырады. Компилятор әрбір өзгеріс бойынша сынақ талдауын жүргізіп, оның дұрыс жұмыс істейтінін тексереді. (Бұл талдау стегі мен кіріс ағынының көшірмелеріне кері оралуды қажет етеді, бұл әдетте талдаушыға қажет емес.) Ең жақсы жөндеу таңдалады. Бұл өте пайдалы қате хабарламасын береді және талдауды жақсы синхрондауға көмектеседі. Дегенмен, жөндеу кіріс файлын өзгерту үшін жеткілікті сенімді емес. Синтаксистік қателерді жөндеу, талдау кестелері мен нақты деректер стегі бар (LR сияқты) талдаушыларда тұрақты түрде оңайырақ.

LR пазерлерінің нұсқалары

LR талдаушы генераторы талдаушы күйі мен алдын қарау символының әрбір комбинациясы үшін не істеу керектігін анықтайды. Бұл шешімдер әдетте грамматикаға және күйге тәуелсіз жалпы талдаушы циклді басқаратын, тек оқуға арналған деректер кестелері түрінде көрінеді. Бірақ осы шешімдерді белсенді талдаушыға айналдырудың басқа да жолдары бар. Кейбір LR талдаушы генераторлары талдау кестесінің орнына, әр күй үшін жеке тігілген бағдарламалық кодты жасайды. Мұндай талдаушылар кестелік талдаушылардағы жалпы талдаушы циклден бірнеше есе жылдам жұмыс істей алады. Ең жылдам талдаушылар құрастырылған кодты пайдаланады. Рекурсивті өрлеу талдаушысының нұсқасында, нақты талдау стегінің құрылымы, сондай-ақ, кішігірім бағдарлама шақыруларымен қолданылатын жасырын стекпен алмастырылады. Қысқартулар кішігірім бағдарлама шақыруларының бірнеше деңгейін аяқтайды, бұл көптеген тілдерде қиындық тудырады. Сондықтан рекурсивті өрлеу талдаушылары, әдетте рекурсивті түсу талдаушыларына қарағанда баяу, түсініксіз және қолмен өзгертуге қиын болады. Тағы бір нұсқа Prolog сияқты процедуралық емес тілдерде талдау кестесін үлгілерді сәйкестендіру ережелерімен алмастырады. GLR Жалпыланған LR талдаушылары кіріс мәтінінің барлық мүмкін талдауларын табу үшін LR төменнен жоғарыға қарай техникаларын қолданады, тек бір дұрыс талдауды емес. Бұл екіұшты грамматика үшін, мысалы, адам тілдерінде қолданылатыны үшін маңызды. Көптеген жарамды талдау ағаштары бір уақытта, кері қайтусыз есептеледі. GLR кейде қақтығыссыз LALR(1) грамматикасымен оңай сипатталмайтын компьютерлік тілдерге де көмектеседі. LC Сол жақ бұрыш талдаушылары LR төменнен жоғарыға қарай техникаларын қолданады, баламалы грамматика ережелерінің сол жағын анықтау үшін. Баламалар бір ғана мүмкін ережеге дейін тарылған кезде, талдаушы сол ереженің қалған бөлігін талдау үшін жоғарыдан төменге қарай LL(1) техникаларына ауысады. LC талдаушылары LALR талдаушыларына қарағанда кішірек талдау кестелеріне және жақсы қателерді диагностикалау мүмкіндігіне ие. Детерминистік LC талдаушылары үшін кеңінен қолданылатын генераторлар жоқ. Көптеген талдау LC талдаушылары өте үлкен грамматикасы бар адам тілдері үшін пайдалы.

Теория

LR пазерлерін 1965 жылы Дональд Кнут прецеденттік пазерлердің тиімді жалпылануы ретінде ойлап тапты. Кнут LR пазерлері ең нашар жағдайларда да тиімді болатын ең жалпы мақсаттағы пазерлер екенін дәлелдеді. "LR(k) грамматикасын тізбектің ұзындығына пропорционал уақытта тиімді талдауға болады". Кез келген k≥1 үшін "тіл детерминистік [және контекстсіз] болса ғана, LR(k) грамматикасымен жасалуы мүмкін, және керісінше, егер ол LR(1) грамматикасымен жасалса ғана". Басқаша айтқанда, егер тіл тиімді бір реттік талдауға мүмкіндік беретін болса, оны LR(k) грамматикасымен сипаттауға болады. Ал осы грамматиканы әрқашан механикалық түрде баламалы (бірақ үлкен) LR(1) грамматикасына түрлендіруге болады. Демек, LR(1) талдау әдісі теориялық тұрғыдан кез келген қолданылатын тілді өңдеуге жеткілікті қуатты болды. Іс жүзінде, көптеген бағдарламалау тілдерінің табиғи грамматикасы LR(1) грамматикасына жақын. Кнут сипаттаған канондық LR пазерлері тым көп күйлерге ие болды және сол дәуірдегі компьютерлердің шектеулі жадысы үшін іс жүзінде тым үлкен талдау кестелеріне ие болды. LR талдау, Франк ДеРемер SLR және LALR пазерлерін аз күйлермен ойлап тапқанда ғана практикалық болды. LR теориясы және LR пазерлері грамматикадан қалай шығарылатыны туралы толық мәліметтер үшін Aho және Ullman еңбегінің "The Theory of Parsing, Translation, and Compiling" 1-ші томын қараңыз. L тілінің LR(0) грамматикасы бар, егер және тек қана L детерминистік контекстсіз тіл және префикс қасиетіне ие болса. Салдарынан, L тілі детерминистік контекстсіз, егер және тек қана L$ LR(0) грамматикасына ие болса, мұнда "$" L әліпбиінің символы емес.

Нысандар жиынтығы

Әдетте, талдаушының күйін бір ғана элементпен сипаттау мүмкін емес, себебі ол қысқарту үшін қай ережені қолданатынын алдын ала білмейді. Мысалы, Е → Е * B ережесі де болса, Е-ге сәйкес келетін тізбек оқылғаннан кейін Е → Е + B және Е → Е * B элементтерінің екеуі де қолданылады. Сондықтан, талдаушының күйін элементтер жиынтығымен сипаттау ыңғайлы, осы жағдайда { E → E + B, E → E * B } жиынтығы.

Нысанды кеңейту терминал емес элементтерді кеңейту арқылы

Терминал емес элементтің алдында нүкте бар элемент, мысалы E → E + B, талдаушының келесі терминал емес элемент B-ні талдауға дайындалып тұрғанын көрсетеді. Нысан жиынтығы талдаушының талдау процесінде болуы мүмкін барлық ережелерді қамтитынын қамтамасыз ету үшін, B-нің қалай талданатынын сипаттайтын барлық элементтерді де қамтуы тиіс. Яғни, егер B → 1 және B → 0 сияқты ережелер болса, онда элементтер жиынтығына B → 1 және B → 0 элементтері де енуі керек. Жалпы жағдайда, бұл келесідей формулировкаланады: Егер элемент жиынтығында A → v Bw түріндегі элемент болса және грамматикада B → w' ережесі болса, онда B → w' элементі де элемент жиынтығында болуы керек.

Нысандар жиынтығының жабылуы

Осылайша, кез келген элементтер жиынын рекурсивті түрде тиісті элементтерді қосып, нүктемен белгіленген барлық терминал емес элементтер ескерілгенге дейін кеңейтуге болады. Ең кішкентай кеңейту элемент жиынының жабылуы деп аталады және I элемент жиыны болғанда clos(I) деп жазылады. Осы жабық элемент жиындары анализатордың күйлері ретінде алынады, бірақ кестелерге тек бастапқы күйден қол жетімділері ғана енгізіледі.

LR(0) мен SLR және LALR талдаулары туралы ескерту

Жоғарыда көрсетілген процедураның 4-қадамы ғана қысқарту әрекеттерін жасайды, сондықтан барлық қысқарту әрекеттері кестедегі толық жолды иеленеді, кіріс ағынындағы келесі символға қарамастан қысқартуды тудырады. Сондықтан бұл LR(0) талдау кестелері болып табылады: олар ешқандай алдын ала қарау жасамайды (яғни, қысқартуды орындауды шешкенге дейін нөл символға қарамайды). Редукцияларды ажырату үшін алдын ала қарау қажет болатын грамматикаға әртүрлі бағаналарда әртүрлі қысқарту әрекеттерін қамтитын талдау кестесінің қатары қажет, ал жоғарыдағы процедура мұндай қатарларды жасауға қабілетсіз. LR(0) кестесін құру процедурасының жетілдірілген нұсқалары (мысалы, SLR және LALR) толық қатарды иеленбейтін қысқарту әрекеттерін құруға қабілетті. Сондықтан олар LR(0) талдағыштарына қарағанда көбірек грамматиканы талдай алады.