Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Каноникалық LR талдаушысы (LR(1) талдаушысы деп те аталады) – компьютерлік ғылымда бағдарламалау тілдерін талдау және өңдеу үшін қолданылатын төменнен жоғары талдау алгоритмінің бір түрі. Ол LR талдау техникасына негізделген, бұл техника "солдан оңға қарай, оң жақтан кері шығару" дегенді білдіреді. Формальды түрде, каноникалық LR талдаушысы – k=1 болғандағы, яғни бір қарастыру терминалы бар LR(k) талдаушысы. Бұл талдаушының ерекшелігі – k>1 кез келген LR(k) грамматикасын LR(1) грамматикасына түрлендіруге болады. Дегенмен, k-ны азайту үшін кері алмастырулар қажет, ал кері алмастырулардың көбеюі грамматиканы жылдам үлкен, қайталанатын және түсінуге қиын жасайды. LR(k) барлық детерминистік контекстсіз тілдерді өңдей алады. HYACC және LRSTAR.
A canonical LR parser (also called a LR(1) parser) is a type of bottom up parsing algorithm used in computer science to analyze and process programming languages. It is based on the LR parsing technique, which stands for "left to right, rightmost derivation in reverse." Formally, a canonical LR parser is an LR(k) parser for k=1, i. e. with a single lookahead terminal. The special attribute of this parser is that any LR(k) grammar with k>1 can be transformed into an LR(1) grammar. However, back substitutions are required to reduce k and as back substitutions increase, the grammar can quickly become large, repetitive and hard to understand. LR(k) can handle all deterministic context free languages. HYACC, and LRSTAR.
Тарих
1965 жылы Дональд Кнут LR(k) (солдан оңға, оң жақтан ең соңғы туынды) талдаушысын ойлап тапты, ол бұрынғы басымдық талдаушыларының жалпылама түрі ретінде, жылжыту-қайтару талдаушысының бір түрі. Бұл талдаушы барлық детерминистік контекстсіз тілдерді тануға қабілетті және кіріс файлда кездесетін операторлардың сол және оң жақ туындыларын құра алады. Кнут k=1 үшін тілді тану қуаты ең жоғары деңгейге жететінін дәлелдеді және LR(k), k > 1 грамматикасын LR(1) грамматикасына түрлендіру әдісін ұсынды. LALR(1) талдаушылары LR талдаушысының ең көп тараған нұсқасы болды. Дегенмен, 1977 жылы Дэвид Пейджер жаңа типтегі LR(1) талдаушыны, кейбір адамдар "Минималды LR(1) талдаушысы" деп атайды, енгізді. Ол LR(1) талдаушыларын жасауға болатынын көрсетті, олардың жад талаптары LALR(1) талдаушыларымен шайқасады. Соңғы кездегі кейбір талдау генераторлары Минималды LR(1) талдаушыларын ұсынады, олар жад қажеттіліктерімен қатар, LALR(1) талдау генераторларына тән құпия қақтығыс мәселесін де шешеді. Сонымен қатар, Минималды LR(1) талдаушылары жылжыту-қайтару амалдарын қолдана алады, бұл оларды Canonical LR(1) талдаушыларынан жылдам етеді.
In 1965 Donald Knuth invented the LR(k) parser (Left to right, Rightmost derivation parser) a type of shift reduce parser, as a generalization of existing precedence parsers. This parser has the potential of recognizing all deterministic context free languages and can produce both left and right derivations of statements encountered in the input file. Knuth proved that it reaches its maximum language recognition power for k=1 and provided a method for transforming LR(k), k > 1 grammars into LR(1) grammars. LALR(1) parsers have been the most common implementations of the LR Parser. However, a new type of LR(1) parser, some people call a "Minimal LR(1) parser" was introduced in 1977 by David Pager who showed that LR(1) parsers can be created whose memory requirements rival those of LALR(1) parsers. Recently, some parser generators are offering Minimal LR(1) parsers, which not only solve the memory requirement problem, but also the mysterious conflict problem inherent in LALR(1) parser generators. In addition, Minimal LR(1) parsers can use shift reduce actions, which makes them faster than Canonical LR(1) parsers.
LR(1) талдау кестелерін құру
LR(1) талдау кестелері LR(0) талдау кестелерімен ұқсас түрде құрастырылады, бірақ әрбір элементте алдын ала қарау терминалы болады. Яғни, LR(0) талдағыштарынан айырмашылығы, өңделіп жатқан элементтен кейін басқа терминал келсе, басқа әрекет орындалуы мүмкін.
LR(1) parsing tables are constructed in the same way as LR(0) parsing tables with the modification that each Item contains a lookahead terminal. This means, contrary to LR(0) parsers, a different action may be executed, if the item to process is followed by a different terminal.