Граматикалық қателерді жою үшін chart parser-ді пайдаланыңыз. Бұл динамикалық бағдарламалау арқылы жұмыс істейді, кері іздеуді болдырмай, нәтижелі шешімдер ұсынады.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Екі мәнді грамматикаларға арналған талдаушының түрі
Type of parser for ambiguous grammars
Компьютер ғылымында, диаграммалық талдаушы – екі мәнді грамматикаларға (табиғи тілдердің грамматикасын қоса) қолайлы талдаушының түрі. Ол динамикалық бағдарламалау тәсілін пайдаланады – жартылай болжамдық нәтижелер «диаграмма» деп аталатын құрылымда сақталады және қайта қолданылуы мүмкін. Бұл кері іздеуді жояды және комбинаторлық өрбудің алдын алады. Диаграммалық талдаудың авторы ретінде Мартин Кей есімді ғалым белгілі.
In computer science, a chart parser is a type of parser suitable for ambiguous grammars (including grammars of natural languages). It uses the dynamic programming approach—partial hypothesized results are stored in a structure called a chart and can be re used. This eliminates backtracking and prevents a combinatorial explosion. Chart parsing is generally credited to Martin Kay.
Диаграммалық талдаулардың түрлері
Көп қолданылатын тәсіл – Витерби алгоритмінің бір түрін пайдалану. Ерли анализаторы – есептеу лингвистикасында негізінен талдау үшін қолданылатын диаграммалық анализатордың бір түрі, және оның авторының атымен аталған. Тағы бір диаграммалық талдау алгоритмі – Кокке-Янгер-Касами (CYK) алгоритмі. Диаграммалық анализаторлар компьютерлік тілдерді талдау үшін де қолданылуы мүмкін. Ерли анализаторлары, әсіресе, компиляторларды құрастырушыларда қолданылған, олардың кез келген контекстсіз грамматиканы қолдану мүмкіндігі белгілі бір тіл үшін грамматика жазуды жеңілдетеді. Дегенмен, олардың төмен тиімділігі көптеген компиляторлық жұмыстарда олардан бас тартуға әкелді. Екі бағытты диаграммалық талдауда диаграмманың жиектері алға немесе артқа бағытталған болып белгіленеді, және жиектерді біріктіру үшін олардың қай бағытта бағытталуы керек екеніне қатысты ережелер сақталады. Инкременттік диаграммалық талдауда диаграмма мәтінді пайдаланушы өңдеген сайын біртіндеп құрастырылады, мәтіндегі әр өзгеріс диаграммадағы ең аз мүмкін өзгеріске әкеледі. Диаграммалық анализаторлар жоғарыдан төменге және төменнен жоғарыға, сондай-ақ активті және пассивті болып ажыратылады.
A common approach is to use a variant of the Viterbi algorithm. The Earley parser is a type of chart parser mainly used for parsing in computational linguistics, named for its inventor. Another chart parsing algorithm is the Cocke Younger Kasami (CYK) algorithm. Chart parsers can also be used for parsing computer languages. Earley parsers in particular have been used in compiler compilers where their ability to parse using arbitrary Context free grammars eases the task of writing the grammar for a particular language. However their lower efficiency has led to people avoiding them for most compiler work. In bidirectional chart parsing, edges of the chart are marked with a direction, either forwards or backwards, and rules are enforced on the direction in which edges must point in order to be combined into further edges. In incremental chart parsing, the chart is constructed incrementally as the text is edited by the user, with each change to the text resulting in the minimal possible corresponding change to the chart. Chart parsers are distinguished between top down and bottom up, as well as active and passive.