Зачем и о чём. Рано или поздно в Ñвоей работе мы ÑталкиваемÑÑ Ñ Ð·Ð°Ð´Ð°Ñ‡Ð°Ð¼Ð¸ Ñложной обработки текÑта, требующих раÑÐ¿Ð¾Ð·Ð½Ð°Ð²Ð°Ð½Ð¸Ñ ÐºÐ°ÐºÐ¸Ñ…-либо Ñзыковых понÑтий: форматирование кода по принÑтым правилам, проверка ÑоответÑÑ‚Ð²Ð¸Ñ Ð½Ð°Ð·Ð²Ð°Ð½Ð¸Ð¹ подпрограмм, переменных, поÑтоÑнных каким-то ÑоглашениÑм, разбор конфигурационных файлов, а то и уÑовершенÑтвование иÑпользуемых Ñзыков Ð¿Ñ€Ð¾Ð³Ñ€Ð°Ð¼Ð¼Ð¸Ñ€Ð¾Ð²Ð°Ð½Ð¸Ñ Ð¿ÑƒÑ‚Ñ‘Ð¼ напиÑÐ°Ð½Ð¸Ñ Ð¿Ñ€ÐµÐ¿Ñ€Ð¾Ñ†ÐµÑÑоров. Ðти задачи вÑтречаютÑÑ Ð´Ð¾Ð²Ð¾Ð»ÑŒÐ½Ð¾ чаÑто, но как правило предлагаемое решение подразумевает изучение довольно Ñ‚ÑжеловеÑных инÑтрументов. Как правило, Ñто YACC или что-то подобное. ПоÑле изучениÑ, что Ñто означает Ð´Ð»Ñ Ð½Ð°Ð¿Ð¸ÑÐ°Ð½Ð¸Ñ ÐºÐ¾Ð´Ð°, обычно выÑÑнÑетÑÑ, что предлагаемый подход мало того, что плохо ÑтыкуетÑÑ Ñ Ñ‚ÐµÐ¼, как мы обычно разрабатываем наши программы. Ð’ итоге в лучшем Ñлучае задача откладываетÑÑ "до лучших времён", а в худшем - пишетÑÑ ÐºÐ¾Ð´ "к Ñлучаю" на оÑнове регулÑрных выражений, а то и проÑто подÑчитывающий разноÑÑ‚ÑŒ чиÑла открывающих и закрывающих Ñкобок. ÐижеÑледующее - попытка раÑÑказать о более проÑÑ‚Ñ‹Ñ… подходах, которые возможно воплотить ÑамоÑтоÑтельно в том виде, в котором Ñто может быть удобно. ПоÑтановка задачи. ИÑÑледователи еÑтеÑтвенных Ñзыков обратили внимание на то, что задача Ð¿Ð¾Ð½Ð¸Ð¼Ð°Ð½Ð¸Ñ Ñзыка легко раÑпадаетÑÑ Ð½Ð° раÑпознавание и оÑмыÑление, иÑтолкование. Так, многим извеÑтны Ñледующие отрывки, воÑпринимающиеÑÑ ÐºÐ°Ðº напиÑанные руÑÑким Ñзыком, но Ñовершенно беÑÑмыÑленные Ñ Ð¾Ð±Ñ‹Ð´ÐµÐ½Ð½Ð¾Ð¹ точки зрениÑ: "Ð“Ð»Ð¾ÐºÐ°Ñ ÐºÑƒÐ·Ð´Ñ€Ð° штеко будланула бокра и курдÑчит бокрёнка." "ÐšÑƒÐ´Ð¼Ð°Ñ‚Ð°Ñ Ð±Ð¾ÐºÑ€Ð° штеко будланула тукаÑтенького бокрёночка." "Ð“Ð»Ð¾ÐºÐ°Ñ ÐºÑƒÐ·Ð´Ñ€Ð° штеко кудланула бокра и курдÑчит бокрёнка." "Калушата приÑÑпали и БутÑвку ÑÑ‚Ñ€Ñмкали. И подудонилиÑÑŒ. РКалуша волит: <<Оее! Оее! БутÑвка-то некузÑваÑ!>>" "ВаркалоÑÑŒ. Хливкие шорьки ПырÑлиÑÑŒ по наве, И хрюкотали зелюки, Как мюмзики в мове." Ðти примеры показывают, что под Ñзыком Ñкорее Ñледует понимать множеÑтво предложений, которые его ÑоÑтавлÑÑŽÑ‚, а то ÑмыÑловую чаÑÑ‚ÑŒ раÑÑматривать отдельно. Ð’ еÑтеÑтвенном Ñлучае Ð¿Ñ€ÐµÐ´Ð»Ð¾Ð¶ÐµÐ½Ð¸Ñ Ñзыка Ñледуют каким-то правилам, которые мы называем грамматичеÑкими. Именно так мы и будем понимать нашу задачу: определить, Ñледует ли Ð·Ð°Ð´Ð°Ð½Ð½Ð°Ñ Ñтрока заданному набору правил. КонтекÑтно-Ñвободные грамматики. Ð”Ð»Ñ Ð¿Ñ€Ð¾Ñтоты мы пропуÑтим череÑчур Ñложные правила и перейдём Ñразу к таким, которые доÑтаточно проÑÑ‚Ñ‹ Ð´Ð»Ñ Ñ€Ð°Ð±Ð¾Ñ‚Ñ‹ и доÑтаточно Ñложны, чтобы опиÑывать почти вÑе наиболее чаÑто вÑтречаемые Ñзыки. Ð”Ð»Ñ Ñтого введём неÑколько Ñтрогих понÑтий. Мы раÑÑматриваем Ñтроки, поÑледовательноÑти конечной длины (возможно - нулевой), ÑоÑтавленные из конечного набора знаков. Знаками не обÑзательно ÑвлÑÑŽÑ‚ÑÑ Ð±ÑƒÐºÐ²Ñ‹, пробелы и знаки препинаниÑ, Ñто могут быть целые Ñлова, точки и тире, октеты бит или даже Ñетевые пакеты обозримого чиÑла видов. СоответÑтвенно, мы можем раÑпознавать не только Ñзык, похожий на еÑтеÑтвенный, но и Ñзык Морзе, Ñзык Ñетевых пакетов и даже Ñзык Ñетевых протоколов, где предложениÑми ÑвлÑÑŽÑ‚ÑÑ Ð¾ÑмыÑленные ÑеанÑÑ‹ ÑвÑзи. ПоÑледовательноÑти знаков мы обозначаем Ñимволами. Терминальный Ñимвол ÑоответÑтвуют ровно одному знаку определённого вида. "Терминальный" здеÑÑŒ означает, что Ñимвол не имеет подробного внутреннего ÑÑ‚Ñ€Ð¾ÐµÐ½Ð¸Ñ Ð² понÑтиÑÑ… грамматики. Ðетерминальные Ñимволы могут ÑоответÑтвовать пуÑтым Ñтрокам, а также поÑледовательноÑÑ‚Ñм (конечной длины) других Ñимволов. Правила - Ñто законы того, какие Ñтроки Ñимволов ÑоответÑтвуют нетерминальным Ñимволам. Ð”Ð»Ñ ÐºÐ¾Ð½Ñ‚ÐµÐºÑтно-Ñвободных грамматик правила запиÑываютÑÑ Ð² виде: S -> _, еÑли Ñимволу может ÑоответÑтвовать пуÑÑ‚Ð°Ñ Ñтрока, и S -> S_0 ... S_{n-1}, где S_0 ... S_{n-1} - терминальные или нетерминальные Ñимволы. Как работает КСГ ПодразумеваетÑÑ, что контекÑтно-ÑÐ²Ð¾Ð±Ð¾Ð´Ð½Ð°Ñ Ð³Ñ€Ð°Ð¼Ð¼Ð°Ñ‚Ð¸ÐºÐ° работает Ñледующим образом. 1. СущеÑтвует выделенный начальный Ñимвол S^{(0)}, иÑполнÑющий обÑзанноÑÑ‚ÑŒ понÑÑ‚Ð¸Ñ "предложение" или "Ñлово." 2. Мы Ñоздаём Ñтроку, ÑоÑтоÑющую из начального Ñимвола: S^{(0)} 3. Мы выбираем произвольный нетерминальный Ñимвол из нашей Ñтроки S^{(k)}_0 ... S^{(k)}_i ... S^{(k)}_{l} выбираем любое правило, "раÑкрывающее" Ñтот Ñимвол S^{(k)}_i = S -> S_0 ... S_n и заменÑем в Ñтроке выбранный Ñимвол ÑоглаÑно выбранному правилу. S^{(k)}_0 ... S^{(k)}_{i-1} S_0 ... S_n S^{(k)}_{i-1} ... S^{(k)}_{l} ЕÑли правило производит пуÑтую Ñтроку, то Ñто ÑоответÑтвует проÑтому удалению нетерминала. 4. ПовторÑем предыдущий шаг до тех пор, пока в Ñтроке вÑтречаютÑÑ Ð½ÐµÑ‚ÐµÑ€Ð¼Ð¸Ð½Ð°Ð»ÑŒÐ½Ñ‹Ðµ Ñимволы. Как только получаем Ñтроку, не Ñодержащую нетерминальных Ñимволов, мы получаем Ñтроку, ÑвлÑющуюÑÑ "предложением" или "Ñловом" Ñзыка. Метод Унгера. Каждое правило S -> S_0 ... S_{n-1} имеет прÑмое иÑтолкование: Ð²Ñ…Ð¾Ð´Ð½Ð°Ñ Ð¿Ð¾Ð´Ñтрока от точки p_0 до точки p_n Ñледует правилу, еÑли ÑущеÑтвует разбиение на подÑтроки точками p_1 ... p_{n-1}, так что p_0 <= p_1 <= ... <= p_{n-1} <= p_n, где подÑтроки опиÑываютÑÑ ÑоответÑтвующими Ñимволами, подÑтрока между точками p_0 и p_1 опиÑываетÑÑ Ñимволом S_0, подÑтрока между точками p_1 и p_2 опиÑываетÑÑ Ñимволом S_1 ... подÑтрока между точками p_{n-1} и p_n опиÑываетÑÑ Ñимволом S_{n-1}. Под "точкой" здеÑÑŒ понимаетÑÑ Ð¼ÐµÑто между Ð´Ð²ÑƒÐ¼Ñ Ñледующими знаками, а также перед Ñамым первым и поÑле Ñамого поÑледнего. ПодÑтрока между точками p_0 и p опиÑываетÑÑ Ñимволом S, еÑли ÑущеÑтвует правило S -> S_0 ... S_{n-1}, опиÑывающее Ñту подÑтроку. ПодÑтрока между точками p_0 и p опиÑываетÑÑ Ñ‚ÐµÑ€Ð¼Ð¸Ð½Ð°Ð»ÑŒÐ½Ñ‹Ð¼ Ñимволом T, еÑли p = p_0 + 1 и терминальный Ñимвол ÑоответÑтвует знаку между Ñтими точками. ПодÑтрока между точками p_0 и p опиÑываетÑÑ Ð¿Ñ€Ð°Ð²Ð¸Ð»Ð¾Ð¼ S -> _, где _ обозначает пуÑтую Ñтроку, еÑли p = p_0. Строка принадлежит Ñзыку, еÑли она опиÑываетÑÑ Ð½Ð°Ñ‡Ð°Ð»ÑŒÐ½Ñ‹Ð¼ Ñимволом. Изложенное выше можно запиÑать формально и более наглÑдно: r(S -> S_0 ... S_{n-1}, w, p_0, p_{n-1}) := 0 <= p_0 <= ... <= p_{n-1} <= l & s(S_0, w, p_0, p_1) & s(S_1, w, p_1, p_2) ... & s(S_{n-1}, s, p_{n-1}, p_n), s(S, w, p_0, p) := r(S -> S_0 ... S_{n-1}, w, p_0, p), r(S -> _, w, p_0, p) := p = p_0, s(T, w, p_0, p) := t(S) & p = p_0 + 1 & w[p_0] ~ T, где w - Ð·Ð°Ð´Ð°Ð½Ð½Ð°Ñ Ñтрока, l - её длина, w[i] - i-й (отÑÑ‡Ð¸Ñ‚Ñ‹Ð²Ð°Ñ Ñ Ð½ÑƒÐ»Ñ) знак Ñтроки, Ñимвол T - терминальный. Так как целочиÑленные переменные ограничены неравенÑтвом 0 <= p <= l, возможно решить Ñти "уравнениÑ" перебором. Более того, Ñти Ð¾Ð¿Ñ€ÐµÐ´ÐµÐ»ÐµÐ½Ð¸Ñ ÑƒÐ¶Ðµ запиÑаны в виде поиÑка по конечному проÑтранÑтву: r(S -> _, w, p_0, p) := p = p_0, r(S -> S_0 ... S_{n-1}, w, p_0, p_{n-1}) := {(p_0, ..., p_{n-1}) in [0,l]^n | 0 <= p_0 <= ... <= p_{n-1} <= l & s(S_0, w, p_0, p_1) & s(S_1, w, p_1, p_2) ... & s(S_{n-1}, w, p_{n-1}, p_n)} /= O. s(T, w, p_0, p) := p = p_0 + 1 & w[p_0] ~ T. s(S, w, p_0, p) := r(S -> S_0 ... S_{n-1}, w, p_0, p). ЕдинÑтвенное, за чем надо Ñледить, Ñто за возможноÑтью ухода в беÑконечную рекурÑию. Однако Ñто легко предотвратить, доÑтаточно запомнить при входе в процедуру, что мы уже ÑопоÑтавлÑем заданный Ñимвол Ñ Ð·Ð°Ð´Ð°Ð½Ð½Ð¾Ð¹ подÑтрокой и вернуть "нет" при повторном входе. Ðто ÑоответÑтвует обрубанию рекурÑии вида A -> B A C, где B ÑопоÑтавлÑетÑÑ Ñ Ð¿ÑƒÑтой Ñтрокой. Очевидно, что ответ Ð´Ð»Ñ A в таком Ñлучае может дать лишь какое-то другое правило, а Ð´Ð»Ñ Ñ‚ÐµÐºÑƒÑ‰ÐµÐ³Ð¾ ответ уже извеÑтен, и Ñтот ответ - "нет." Обратим внимание, что раз уж мы запоминаем, ÑопоÑтавлÑли ли мы Ñимвол Ñ Ð¿Ð¾Ð´Ñтрокой, то мы можем запомнить и итог Ñтого ÑопоÑтавлениÑ. Ðто намного улучшает ÑкороÑÑ‚ÑŒ раÑпознаваниÑ, так как мы поÑтоÑнно ÑопоÑтавлÑем одни и те же Ñимволы Ñ Ð¾Ð´Ð½Ð¸Ð¼Ð¸ и теми же подÑтроками. СобÑтвенно, вот Ñта Ð½ÐµÐ±Ð¾Ð»ÑŒÑˆÐ°Ñ Ð¾Ð¿Ñ‚Ð¸Ð¼Ð¸Ð·Ð°Ñ†Ð¸Ñ Ð¸ ÑвлÑетÑÑ Ð¿Ñ€Ð¸Ñ‡Ð¸Ð½Ð¾Ð¹ того, почему алгоритм Унгера почти не упоминаетÑÑ Ð² учебной литературе, кроме как Ñ Ð¿Ñ€Ð¸Ð¼ÐµÑ‡Ð°Ð½Ð¸ÐµÐ¼ "очень медленный." Дело в том, что Ñта Ð¾Ð¿Ñ‚Ð¸Ð¼Ð¸Ð·Ð°Ñ†Ð¸Ñ Ð¿Ñ€ÐµÐ²Ñ€Ð°Ñ‰Ð°ÐµÑ‚ алгоритм, требующий ÑкÑпоненциального времени, в алгоритм, требующий полиномиального времени, что делает его вполне отвечающим ÑложноÑти задачи. ИÑпользование "мемоизации," Ð·Ð°Ð¿Ð¾Ð¼Ð¸Ð½Ð°Ð½Ð¸Ñ Ñ€ÐµÐ·ÑƒÐ»ÑŒÑ‚Ð°Ñ‚Ð¾Ð² вычиÑлений Ð´Ð»Ñ ... Комбинаторы парÑеров Ðлгоритм Унгера, конечно, хорош, но вÑÑ‘ же поÑмотрим, как мы его можем улучшить. Прежде вÑего обратим внимание на то, что мы можем вычиÑлить конец подÑтроки, ÑопоÑтавлÑемой Ñ Ð·Ð°Ð´Ð°Ð½Ð½Ñ‹Ð¼ Ñимволом, по её началу, то еÑÑ‚ÑŒ мы можем раÑÑматривать p и s как отображениÑ, дающие итогом множеÑтва возможных концов подÑтрок, ÑопоÑтавлÑющихÑÑ Ñ Ñимволом или правилом: r'(R, w, p_0) = {p | r(R, w, p_0, p)}, s'(S, w, p_0) = {p | s(S, w, p_0)}. или r'(S -> S_0 ... S_{n-1}, w, p_0) := {p | r(S -> S_0 ... S_{n-1}, w, p_0, p)}. s'(S, w, p_0) := {p | s(S, w, p_0, p)}. ИÑходные предикаты выражаютÑÑ Ñ‡ÐµÑ€ÐµÐ· принадлежноÑÑ‚ÑŒ множеÑтву: r(S -> S_0 ... S_{n-1}, w, p_0, p) <=> p <- {p | r(S -> S_0 ... S_{n-1}, w, p_0, p)}. s(S, w, p_0, p) <=> p <- {p | s(S, w, p_0, p)}. Тогда наши уÑÐ»Ð¾Ð²Ð¸Ñ Ð¼Ð¾Ð¶Ð½Ð¾ перепиÑать в виде: r'(S -> _, w, p_0) = {p | r(S -> _, w, p_0, p)} = {p | p = p_0} = {p_0}. r'(S -> S_0 ... S_{n-1}, w, p_0) = {p | r(S -> S_0 ... S_{n-1}, w, p_0, p)} = {p_n | 0 <= p_0 <= ... <= p_{n-1} <= l & s(S_0, w, p_0, p_1) & s(S_1, w, p_1, p_2) ... & s(S_{n-1}, w, p_{n-1}, p_n)} = {p_n | p_1 <- s'(S_0, w, p_0) & p_2 <- s'(S_1, w, p_1) ... & p_n <- s'(S_{n-1}, w, p_{n-1})} Ð’ поÑледнем выражении мы можем раÑпознать повторÑющийÑÑ Ð¼Ð¾Ñ‚Ð¸Ð²: {y | x <- X & y <- f(x)} = U {f(x) | x <- X} = u(m(f, X)), где m(f, X) - поточечное отображение множеÑтва X, u(Y) - объединение множеÑтва множеÑтв. ПоÑле Ð²Ð²ÐµÐ´ÐµÐ½Ð¸Ñ Ñтих очевидных обозначений, мы приходим к r'(S -> S_0 ... S_{n-1}, w, p_0) = {p_n | p_1 <- s'(S_0, w, p_0) & p_2 <- s'(S_1, w, p_1) ... & p_n <- s'(S_{n-1}, w, p_{n-1})} = u(m((p +-> s(S_{n-1}, w, p)), {p_{n-1} | p_1 <- s'(S_0, w, p_0) & p_2 <- s'(S_1, w, p_1) ... & p_{n-1} <- s'(S_{n-2}, w, p_{n-2})})) = u(m((p +-> s'(S_{n-1}, w, p)), u(m((p +-> s'(S_{n-2}, w, p)), ... u(m((p +-> s'(S_1, w, p)), s'(S_0, w, p_0))))))) Ðто можно обобщить ещё дальше, еÑли заметить, что f(x) = u({f(x)}) = u(m(f, {x})), откуда s'(S_0, w, p_0) = u(m((p +-> s'(S_0, w, p)), {p_0})). Тогда r'(S -> S_0 ... S_{n-1}, w, p_0) = u(m((p +-> s'(S_{n-1}, w, p)), u(m((p +-> s'(S_{n-2}, w, p)), ... u(m((p +-> s'(S_1, w, p)), u(m((p +-> s'(S_0, w, p)), {p_0})))))))). ВыглÑдит уÑтрашающе, но еÑли приÑмотретьÑÑ, Ñто Ð¾Ð±Ñ‹Ñ‡Ð½Ð°Ñ ÐºÐ¾Ð¼Ð¿Ð¾Ð·Ð¸Ñ†Ð¸Ñ Ñ„ÑƒÐ½ÐºÑ†Ð¸Ð¹ вида z_i(x) := u(m((p +-> s'(S_i, w, p)), x)) r'(S -> S_0 ... S_{n-1}, w, p_0) = (z_{n-1} o ... o z_0)({p_0}). Ð”Ð»Ñ Ñимволов мы получаем: s'(T, w, p_0) = {p | s(T, w, p_0, p)} = {p | p = p_0 + 1 & w[p_0] ~ T}, то еÑÑ‚ÑŒ s'(T, w, p_0) = {p_0}, когда w[p_0] ~ T, и s'(T, w, p_0) = {} в противном Ñлучае s'(S, w, p_0) = {p | s(S, w, p_0, p)} = {p | r(S -> S_0 ... S_{n-1}, w, p_0, p)} = {p | p <- r'(S -> S_0 ... S_{n-1}, w, p_0)} = U {r'(S -> S_0 ... S_{n-1}, w, p_0)} Итого, мы получили ÑпоÑоб, как по грамматике поÑтроить набор взаимнорекурÑивных функций, ÑопоÑтавлÑющих Ñимволы и правила. Более того, можно пойти дальше и ввеÑти две операции, комбинирующие раÑпознаватели так, что правилу S -> S_0 ... S_{n-1} ÑоответÑтвует раÑпознаватель r" = s"_0 * ... * s"_{n-1}, а раÑпознаватель Ñимвола S комбинирует вÑе отноÑÑщиеÑÑ Ð¿Ñ€Ð°Ð²Ð¸Ð»Ð°: s = r"_0 + ... + r"_{m-1}. К примеру, еÑли мы раÑпознаём функциÑми вида r', отображающими точку во множеÑтво точек, то (r'_A * r'_B)(p) = u(m(r'_B, r'_A(p))) = u(m(r'_B, u(m(r'_A, {p})))). (r'_1 + r'_2)(p) = u({r'_1(p), r'_2(p)}) = r'_A(p) U r'_B(p). ЕÑли же мы раÑпознаём функциÑми вида r', отображающими множеÑтво точек во множеÑтво точек, то (r'_A * r'_B)(P) = u(m(r'_B, u(m(r'_A, P)))). (r'_1 + r'_2)(P) = u({u(m(r'_1, P)), u(m(r'_2, P))}) = u(u(m(r'_1, P)), u(m(r'_2, P))) = m(r'_1, P) U m(r'_2, P). УСТРÐÐЕÐИЕ ЛЕВОЙ РЕКУРСИИ! GLL. Ðтот ÑпоÑоб опиÑан в "turning failures into list of successes" Монады? Ðтот ÑпоÑоб Ñтрадает от ÑÐ²Ð°Ð»Ð¸Ð²Ð°Ð½Ð¸Ñ Ð² беÑконечную левую рекурÑию Ñильнее. УÑтранение левой рекурÑии возможно, но непроÑто. Мы вернёмÑÑ Ðº Ñтому чуть позже. Рпока... Обратим внимание на то, что как правило нам не нужны неоднозначноÑти, так как они порождают неопределённоÑÑ‚ÑŒ. ЕÑли мы видим, что какаÑ-то ÑловоÑочетание началоÑÑŒ, то мы хотим точно, однозначно знать, где оно заканчиваетÑÑ. Из Ñтого Ñледует, что функции r'(R, w, p) и s'(S, w, p) возвращают множеÑтва из одного Ñлемента либо пуÑтые. ПоÑледнее обÑтоÑтельÑтво очень Ñильно упрощает напиÑание кода, так как позволÑет иÑпользовать более проÑтые типы данных (опциональный тип, где поддерживаетÑÑ), что в оÑобенноÑти на Ñзыках Ñ Ð¿Ð»Ð¾Ñ…Ð¾Ð¹ поддержкой Ñложных типов данных. ДетерминиÑÑ‚Ñкий подход, PEG. ÐеÑÐ¼Ð¾Ñ‚Ñ€Ñ Ð½Ð° то, что однозначные грамматики Ñильно упрощают жизнь, оÑтаётÑÑ Ð²Ð¾Ð¿Ñ€Ð¾Ñ Ð²Ð¸ÑÑщего "иначе:" if a = 0 then if b = 0 then this else that может быть разобрано как if a = 0 then (if b = 0 then this) else that или как if a = 0 then (if b = 0 then this else that) Ð’Ð¾Ð¿Ñ€Ð¾Ñ Ð¾ принадлежноÑти "иначе" возникает из-за неоднозначноÑти грамматик, Ñодержащих такие правила: statement = "if", expression, "then", statement, "else", statement; statement = "if", expression, "then", statement. ÐŸÐ¾Ð´Ð¾Ð±Ð½Ð°Ñ Ð½ÐµÐ¾Ð´Ð½Ð¾Ð·Ð½Ð°Ñ‡Ð½Ð¾ÑÑ‚ÑŒ разрешаетÑÑ Ð¾Ð±Ñ‹Ñ‡Ð½Ð¾ правилом наиболее длинной подÑтроки: при возникновении неоднозначноÑти первенÑтво отдаётÑÑ Ð½Ð°Ð¸Ð±Ð¾Ð»ÐµÐµ длинной подÑтроке, ÐºÐ¾Ñ‚Ð¾Ñ€Ð°Ñ Ð¼Ð¾Ð¶ÐµÑ‚ быть раÑпознана. Однако в грамматике так, как мы её определили, не ÑущеÑтвует понÑÑ‚Ð¸Ñ Ð¿ÐµÑ€Ð²ÐµÐ½Ñтва: вÑе правила равны и дейÑтвуют одновременно и одинаково. ЕÑли же поÑмотреть Ñ Ð´Ñ€ÑƒÐ³Ð¾Ð¹ Ñтороны, то чуть выше мы пришли к такой запиÑи правил раÑпознаваниÑ, которые опиÑывают Ñзык не хуже прежних: s = (s_A * s_B) + (s_C * s_D). Ðта запиÑÑŒ допуÑкает определение "+" иначе, чем через объединение множеÑтв, важно то, чтобы оно было чем-то похоже. Ð’ чаÑтноÑти, мы можем отброÑить второе значение, еÑли удовлетворены первым. ЕÑли мы определим "+" таким образом, то получим, что (s_A + s_B)(p) = s_A(p), еÑли s_A(p) /= {} (s_A + s_B)(p) = s_B(p), еÑли s_A(p) = {}. LL(1).