Кіріспе
Жоғарыдан төменге талдайтын парсер, кірісті солдан оңға қарай талдайды. Компьютер ғылымында LL парсер (солдан оңға, ең сол жақтан туынды) – шектелген контекстсіз тіл үшін жоғарыдан төменге талдайтын парсер. Ол кірісті солдан оңға қарай талдайды, сөйлемнің ең сол жақтан туындысын жасайды. LL парсері, егер ол сөйлемді талдау кезінде k қарау белгісін қолданса, LL(k) парсері деп аталады. Грамматика LL(k) грамматикасы деп аталады, егер одан LL(k) парсерін құруға болады. Формальды тіл LL(k) грамматикасын болса, LL(k) тілі деп аталады. LL(k) тілдерінің жиынтығы, әр k ≥ 0 үшін LL(k+1) тілдерінің жиынтығына дұрыс кіреді. Осыдан туындайтын қорытынды – барлық контекстсіз тілдерді LL(k) парсері тани алмайды. LL парсері LL тұрақты тілді (LLR) деп аталады, егер ол LL тұрақты тілді талдаса. LLR грамматикаларының класы, әр k үшін барлық LL(k) грамматикаларын қамтиды. Әрбір LLR грамматикасы үшін, грамматиканы сызықтық уақытта талдайтын LLR парсері болады. Екі ерекше парсер түрі – LL(*) және LL(шекті). Егер LL(*)/LL(finite) талдау стратегиясы қолданылса, ол LL(*)/LL(finite) деп аталады. LL(*) және LL(шекті) парсерлері функционалдық жағынан PEG парсерлеріне жақын. LL(шекті) парсері, кез келген LL(k) грамматикасын қарау белгілерінің мөлшері және қарау белгілерінің салыстырулары бойынша оптималды түрде талдай алады. LL(*) стратегиясымен талдайтын грамматикалар класы, синтаксистік және семантикалық предикаттарды қолдану арқасында кейбір контекстке сезімтал тілдерді қамтиды және анықталмаған. LL(*) парсерлерін TDPL парсерлері деп қарастыру дұрыс деп ұсынылған. Көптеген қате түсініктерге қарамастан, LL(*) парсерлері жалпы алғанда LLR емес, және құрылымы бойынша орташа есеппен нашар жұмыс істейді (сызықтық уақытқа қарағанда суперсызықтық) және ең нашар жағдайда (сызықтық уақытқа қарағанда экспоненциалды). LL грамматикалары, әсіресе LL(1) грамматикалары, өте маңызды, өйткені осы грамматикалар үшін парсерлерді құру оңай, және көптеген компьютерлік тілдер осы себептен LL(1) болып құрылады. LL парсерлері кестелік болуы мүмкін, яғни LR парсерлеріне ұқсас, бірақ LL грамматикаларын рекурсивті түсу парсерлерімен де талдауға болады. Уэйт пен Гус (1984) пікірінше, LL(k) грамматикасын Стернс пен Льюис (1969) енгізген.
In computer science, an LL parser (Left to right, leftmost derivation) is a top down parser for a restricted context free language. It parses the input from Left to right, performing Leftmost derivation of the sentence. An LL parser is called an LL(k) parser if it uses k tokens of lookahead when parsing a sentence. A grammar is called an LL(k) grammar if an LL(k) parser can be constructed from it. A formal language is called an LL(k) language if it has an LL(k) grammar. The set of LL(k) languages is properly contained in that of LL(k+1) languages, for each k ≥ 0. A corollary of this is that not all context free languages can be recognized by an LL(k) parser. An LL parser is called LL regular (LLR) if it parses an LL regular language. The class of LLR grammars contains every LL(k) grammar for every k. For every LLR grammar there exists an LLR parser that parses the grammar in linear time. Two nomenclative outlier parser types are LL(*) and LL(finite). A parser is called LL(*)/LL(finite) if it uses the LL(*)/LL(finite) parsing strategy. LL(*) and LL(finite) parsers are functionally closer to PEG parsers. An LL(finite) parser can parse an arbitrary LL(k) grammar optimally in the amount of lookahead and lookahead comparisons. The class of grammars parsable by the LL(*) strategy encompasses some context sensitive languages due to the use of syntactic and semantic predicates and has not been identified. It has been suggested that LL(*) parsers are better thought of as TDPL parsers. Against the popular misconception, LL(*) parsers are not LLR in general, and are guaranteed by construction to perform worse on average (super linear against linear time) and far worse in the worst case (exponential against linear time). LL grammars, particularly LL(1) grammars, are of great practical interest, as parsers for these grammars are easy to construct, and many computer languages are designed to be LL(1) for this reason. LL parsers may be table based, i. e. similar to LR parsers, but LL grammars can also be parsed by recursive descent parsers. According to Waite and Goos (1984), LL(k) grammars were introduced by Stearns and Lewis (1969).
Орналастыру
Бір ережені екінші ережеге қойып, тура емес немесе FIRST/FOLLOW қақтығыстарын жою. Бұл FIRST/FIRST қақтығысын тудыруы мүмкін.