Синтаксистік талдаушы SLR – компьютерлік ғылымдағы тиімді құрал. LR грамматикасын қарапайым алгоритммен жасауға көмектеседі, кестелерді автоматты түрде құрайды.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Компьютерлік ғылымда Simple LR немесе SLR – LR талдаушысының бір түрі, ол кішкентай талдау кестелерімен және салыстырмалы түрде қарапайым талдау генераторы алгоритмімен жұмыс істейді. Басқа LR(1) талдаушылары сияқты, SLR талдаушысы кіріс ағыны бойынша солдан оңға бір рет сканерлеу арқылы, болжау немесе кері қайтарусыз, төменнен жоғарыға қарай дұрыс талдауды табуда өте тиімді. Парсер тілдің формалды грамматикасынан механикалық түрде құрастырылады. SLR және LALR, сондай-ақ Canonical LR талдаушысы сияқты әдістер бірдей әдістерге және ұқсас кестелерге ие; олар тек талдаушы генераторы құралы қолданатын математикалық грамматикалық талдау алгоритмдерімен ғана ерекшеленеді. SLR және LALR генераторлары бірдей өлшемдегі және бірдей талдаушы күйлері бар кестелерді жасайды. SLR генераторлары yacc және Bison сияқты LALR генераторларына қарағанда аз грамматиканы қабылдайды. Көптеген компьютерлік тілдер SLR-дің шектеулеріне оңай сәйкес келмейді. Тілдің табиғи грамматикасын SLR грамматикасына бейімдеу үшін көптеген ұғымдардан бас тарту және грамматиканы өзгерту қажет. Сондықтан LALR генераторлары, біршама күрделі құрал болғанына қарамастан, SLR генераторларына қарағанда әлдеқайда кеңінен қолданылады. SLR әдістері жоғары оқу орындарында компилятор теориясы бойынша оқуда пайдалы кезең болып табылады. SLR және LALR екеуін де Фрэнк ДеРемер Дональд Кнуттың LR талдаушы теориясының алғашқы практикалық қолданысы ретінде әзірледі. Толық LR әдістерімен нақты грамматика үшін жасалған кестелер өте үлкен, сол онжылдықтағы көптеген компьютерлердің жадысынан асып түседі, SLR және LALR әдістерінен 100 есе немесе одан да көп талдаушы күйіне ие.
In computer science, a Simple LR or SLR parser is a type of LR parser with small parse tables and a relatively simple parser generator algorithm. As with other types of LR(1) parser, an SLR parser is quite efficient at finding the single correct bottom up parse in a single left to right scan over the input stream, without guesswork or backtracking. The parser is mechanically generated from a formal grammar for the language. SLR and the more general methods LALR parser and Canonical LR parser have identical methods and similar tables at parse time; they differ only in the mathematical grammar analysis algorithms used by the parser generator tool. SLR and LALR generators create tables of identical size and identical parser states. SLR generators accept fewer grammars than do LALR generators like yacc and Bison. Many computer languages don't readily fit the restrictions of SLR, as is. Bending the language's natural grammar into SLR grammar form requires more compromises and grammar hackery. So LALR generators have become much more widely used than SLR generators, despite being somewhat more complicated tools. SLR methods remain a useful learning step in college classes on compiler theory. SLR and LALR were both developed by Frank DeRemer as the first practical uses of Donald Knuth's LR parser theory. The tables created for real grammars by full LR methods were impractically large, larger than most computer memories of that decade, with 100 times or more parser states than the SLR and LALR methods
Көзқарас құрылғылары
SLR мен LALR арасындағы айырмашылықтарды түсіну үшін олардың көптеген ұқсастықтарын және олардың екеуі де ауысу-қайтару шешімдерін қалай қабылдайтынын түсіну маңызды. (Осы мәліметтер үшін LR анализаторы мақаласын қараңыз, қайтарулардың алдын қарау жиындарына дейін.) SLR мен LALR арасындағы жалғыз айырмашылық – олардың генераторлары кейбір аяқталған өндіріс ережесі табылғанда және қысқартылғанда келесі кездесетін кіріс символдарының алдын қарау жиындарын қалай есептейді. SLR генераторлары қарапайым жуықтау әдісімен, тікелей грамматикаға сүйене отырып есептейді, жеке анализатор күйлері мен өтулердің егжей-тегжейін назарға алмайды. Бұл қазіргі анализатор күйінің ерекше жағдайын елемейді. Егер грамматикада S есімді терминалды емес символ бірнеше жерде қолданылса, SLR оларды жеке-жеке қарастырмай, бірдей қарастырады. SLR генераторы S-тің кез келген нұсқасынан кейін дереу келе алатын барлық терминал символдарының жиынтығын – Follow(S) есептейді. Анализ кестесінде S-ке жасалған әрбір қысқару LR(1) алдын қарау жиыны ретінде Follow(S) жиынын пайдаланады. Мұндай Follow жиындары LL жоғарыдан төменге қарай анализатор генераторларында да қолданылады. Follow жиындарын қолданғанда ауысу/қысқару немесе қысқару/қысқару қақтығыстары болмайтын грамматика SLR грамматикасы деп аталады. LALR генераторлары алдын қарау жиындарын есептеу үшін анализатор күйлерінің графигін және олардың өтулерін зерттеуге негізделген дәлірек әдіс қолданады. Бұл әдіс қазіргі анализатор күйінің ерекше жағдайын ескереді. Ол S есімді терминалды емес символдың грамматикадағы әр кездесуін жеке өңдейді. Бұл есептеудің толық мәліметтері үшін LALR анализаторы мақаласын қараңыз. LALR генераторларымен есептелген алдын қарау жиындары SLR генераторларымен есептелген жуықтау жиындарының ішкі жиыны болып табылады (яғни, олардан жақсы). Егер грамматикада SLR Follow жиындарын қолданғанда кестелік қақтығыстар болса, бірақ LALR Follow жиындарын қолданғанда қақтығыстар болмаса, онда ол LALR грамматикасы деп аталады.
To understand the differences between SLR and LALR, it is important to understand their many similarities and how they both make shift reduce decisions. (See the article LR parser now for that background, up through the section on reductions' lookahead sets.) The one difference between SLR and LALR is how their generators calculate the lookahead sets of input symbols that should appear next, whenever some completed production rule is found and reduced. SLR generators calculate that lookahead by an easy approximation method based directly on the grammar, ignoring the details of individual parser states and transitions. This ignores the particular context of the current parser state. If some nonterminal symbol S is used in several places in the grammar, SLR treats those places in the same single way rather than handling them individually. The SLR generator works out Follow(S), the set of all 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 generators calculate lookahead sets by a more precise method based on exploring the graph of parser states and their transitions. This method considers the particular context of the current parser state. It customizes the handling of each grammar occurrence of some nonterminal S. See article LALR parser for further details of this calculation. The lookahead sets calculated by LALR generators are a subset of (and hence better than) the approximate sets calculated by SLR generators. If a grammar has table conflicts when using SLR follow sets, but is conflict free when using LALR follow sets, it is called a LALR grammar.