Здравствуйте, Павел Кузнецов, Вы писали:
>> Почему грамматика Оберона-2 не является LL(1)?
ПК>Фактически, это синтаксическая неразличимость между type guard (*) и вызовом процедуры. Это некоторым образом аналогично неоднозначности с угловыми скобками в C++ (аргументы шаблона vs. операции < и >), требующей знания контекста (значения идентификаторов в разбираемом выражении).
Мне кажется, что грамматика принадлежит классу LL(1),
если парсер "забегает" вперед не более, чем на одну лексему.
Именно так и поступает компилятор Оберона. Он нигде не просматривает
входной поток более чем на одну лексему вперед.
Если это не LL(1), то к какому классу отнести такую грамматику?
Она определенно не является ни LR(k), ни LL(2), ни LL(3) etc.
Действительно, две ветки синтаксического разбора в следующем определении
начинаются с левой круглой скобки, но это не приводит к просмотру вперед
более, чем на один символ (т.е. для определения ветки следующая за скобкой
лексема не требуется).
Но существует одно качество, которое нельзя купить, — это надежность. Цена надежности — погоня за крайней простотой. Это цена, которую очень богатому труднее всего заплатить.
AVC,
> Мне кажется, что грамматика принадлежит классу LL(1), если парсер "забегает" вперед не более, чем на одну лексему.
...для определения того, по какой из альтернативных веток разбора пойти; в случае наличия неоднозначности разбора, неустранимой путем заглядывания на k лексем вперед, грамматика LL(k) не является. Т.е. ни одна неоднозначная грамматика не является LL(k).
> Именно так и поступает компилятор Оберона. Он нигде не просматривает входной поток более чем на одну лексему вперед.
Значит он:
a) или не является LL(1) автоматом, а построен по другим принципам, и, соответственно, грамматика LL(1) не является;
b) или разбирает надмножество Оберона-2.
(см. ниже)
> Если это не LL(1), то к какому классу отнести такую грамматику? Она определенно не является ни LR(k), ни LL(2), ни LL(3) etc.
Если пытаться устранить указанную неоднозначность средствами грамматики мы вообще придем к КЗ. Соответственно, на практике выделяют некоторую грамматику, порождающую надмножество Оберона-2, и устраняют неоднозначности и недопустимые конструкции на этапе "семантичесокого" анализа, или же делают это с помощью "ручного" разрешения конфликтов, например, "подглядыванием" в таблицу символов по ходу разбора, как это делается для подобных неоднозначностей в C++.
Так или иначе, говоря о том, что грамматика Оберона-2 является LL(1), нужно уточнять, о какой именно грамматике идет речь. "Официальная" LL(k) не является.
> Действительно, две ветки синтаксического разбора в следующем определении >
> начинаются с левой круглой скобки, но это не приводит к просмотру вперед более, чем на один символ (т.е. для определения ветки следующая за скобкой лексема не требуется).
В данном случае это приводит к принципиальной неразрешимости того, по какой из веток пойти; вне зависимости от дальности заглядывания вперед. Т.е. это вообще не LL(k).
Posted via RSDN NNTP Server 1.9
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Здравствуйте, AVC, Вы писали:
AVC>Точно. Уволить их всех. AVC>Но смысл был в том, что future time вполне можно выразить и без future tense. AVC>Например: AVC>
AVC>I am leaving tomorrow.
согласен. Просто это усложняет понимание — чтобы понять, о каком времени идет речь, надо знать смысл слова tomorrow (которое к тому же стоит в конце предложения).
Теоретически, можно вообще обойтись без специальных конструкций для разных времен — но это еще больше усложнит понимание.
Здравствуйте, AVC, Вы писали:
AVC>Но смысл был в том, что future time вполне можно выразить и без future tense.
Нет. Cмысл в том, что грамматически future tense вообще отсутствует. Кстати, в русском языке глаголы несовершенного вида тоже не имеют будущего времени.
...Ремесло
Поставил я подножием искусству;
Я сделался ремесленник: перстам
Придал послушную, сухую беглость
И верность уху. Звуки умертвив,
Музыку я разъял, как труп. Поверил
Я алгеброй гармонию. Тогда
Уже дерзнул, в науке искушенный,
Предаться неге творческой мечты.
...
Не! не могу противиться я доле
Судьбе моей: я избран, чтоб его
Остановить -- не то мы все погибли,
Мы все, жрецы, служители музыки,
Не я один с моей глухою славой...
Что пользы, если Моцарт будет жив
И новой высоты еще достигнет?
Подымет ли он тем искусство? Нет;
Оно падет опять, как он исчезнет...
Человек не машина, не математическая модель и не парсер, ему удобно то, что он считает удобным, ни больше ни меньше. А Вирт как обычно подменяет понятия.
Здравствуйте, Павел Кузнецов, Вы писали:
>> Где здесь неоднозначность? Скобки вокруг выражения versus вокруг списка аргументов?
ПК>Доступ к элементу массива vs. вызов функции. Можно, правда, попробовать "отбиться", если не вводить в грамматику оба нетерминала "вызов-функции" и "доступ-к-элементу-массива", а ограничиться одним "функтор" (может, ты об этом и говорил?). В этом случае тоже будут вопросы, но они уже будут зависеть от конкретики языка: в каких выражениях могут встречаться типы, функции и массивы; что из этого может быть шаблонами; где могут встречаться объявления, и где -- выражения, и всегда ли их можно будет отличить друг от друга и т.п.
Да, именно: не различать массивы и функции. В конце концов, васик с фортраном обходятся.
Опять же, удобно будет многомерные индексы делать; сейчас в С++ для этого приходится извращаться вокруг адаптеров оператора[].
Применимость и арность оператора() в любом случае требует контекстной зависимости — но уже после синтаксического разбора. Так что нет проблем с применимостью и арностью шаблонного метаоператора[] (или <>, если продолжить традиции С++).
А различать объявления, определения и выражения — вообще говоря, было бы полезно. Ради такого дела можно и ключевые слова ввести.
>> Эта же задача возникает в парсере мат.выражений...
ПК>Там такой неоднозначности нет, т.к. скобка после идентификатора может и должна присутствовать только в случае вызова функции. Т.е. просмотра на одну лексему вперед достаточно, чтобы понять, что перед нами -- вызов функции.
Вот именно. А контроль за арностью — это уже задача следующего уровня.
То есть, LL(немного)-язык с шаблонами — вполне достижим. Хотя, возможно, уже неактуален?
Здравствуйте, Трурль, Вы писали:
Т>...Кстати, в русском языке глаголы несовершенного вида тоже не имеют будущего времени.
Это куда она пропала? В русском языке есть две формы будущего времени: простая и составная. Для глаголов несовершенного вида используется составная форма: будет делать. У совершенного вида — сделает. Другое дело, что у глаголов совершенного вида в русском языке нет настоящего времени.
Здравствуйте, Пацак, Вы писали:
П>Человек не машина, не математическая модель и не парсер, ему удобно то, что он считает удобным, ни больше ни меньше.
// make c readable#define O printf
#define R return
#define Z static
#define P(x,y) {if(x)R(y);}
#define U(x) P(!(x),0)
#define SW switch
#define CS(n,x)case n:x;break;
#define CD default
#define DO(n,x){I i=0,_i=(n);for(;i<_i;++i){x;}}
Здравствуйте, Дарней, Вы писали:
Т>>Нет. Cмысл в том, что грамматически future tense вообще отсутствует.
Д>Тем не менее, будущее время в языке есть, хотя и выражается только с помощью вспомогательного глагола.
Фразу "есть в языке" можно понимать как "выразимо средствами языка" или "отражено грамматикой языка". В первом случае класс того, что "есть в языке" гораздо шире. Например, в русском нет давнопрошедшего времени, но выразить его вполне возможно.
ПК> Фактически, это синтаксическая неразличимость между type guard (*) и вызовом процедуры.
Вот фрагмент парсера Component Pascal:
...
ELSIF sym = lparen THEN
IF (x.obj # NIL) & (x.obj.mode IN{XProc, LProc, CProc, TProc}) THEN typ := x.obj.typ
ELSIF x.typ.form = ProcTyp THEN typ := x.typ.BaseTyp
ELSIF x.class = Nproc THEN EXIT (* standard procedure *)ELSE typ := NIL
END;
IF typ # DevCPT.notyp THEN
DevCPS.Get(sym);
IF typ = NIL THEN(* type guard *)IF sym = ident THEN
qualident(obj);
IF obj.mode = Typ THEN DevCPB.TypTest(x, obj, TRUE)
ELSE err(52)
END
ELSE err(ident)
END
ELSE(* function call *)
pre := NIL; lastp := NIL;
DevCPB.PrepCall(x, fpar);
IF (x.obj # NIL) & (x.obj.mode = TProc) THEN DevCPB.CheckBuffering(x.left, NIL, x.obj.link, pre, lastp)
END;
ActualParameters(apar, fpar, pre, lastp);
DevCPB.Call(x, apar, fpar);
IF pre # NIL THEN DevCPB.Construct(Ncomp, pre, x); pre.typ := x.typ; x := pre END;
IF level > 0 THEN DevCPT.topScope.link.leaf := FALSE END
END;
CheckSym(rparen)
ELSE EXIT
END
ELSE EXIT
END
работа всегда идет не более чем с одним единственным словом sym.
DevCPS — сканер
DevCPS.Get(sym); — считывание следующего слова.
Сергей,
> ПК> Фактически, это синтаксическая неразличимость между type guard (*) и вызовом процедуры.
> Вот фрагмент парсера Component Pascal: >
> ...
> IF typ = NIL THEN(* type guard *)
> <...>
> ELSE(* function call *)
> <...>
> END;
>
> работа всегда идет не более чем с одним единственным словом sym.
На этом основании эта грамматика LL(1) не становится, т.к. процитированное выше обращение к таблице символов во время разбора выходит за рамки операций, доступных LL-автомату. Не всякий парсер, разбирающий синтаксис, оперируя по одной лексеме за раз, является LL-парсером/автоматом.
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Здравствуйте, Трурль, Вы писали:
Т>Просто этот самый "кто-то" считает, что именно в таком виде С становится читаемым.
И кто же этот коварный "кто-то"? Покажи пальчико плз. Ладно пальцем некультурно, лучше ссылкой. Насколько я знаю define стали вчерашним днем с момента появления C++. Не говоря уж про C#, в котором (Vlad2 меня поправит если что) их вообще нет. Может хватит бегать со страшилками двадцатилетней дваности?
Здравствуйте, Пацак, Вы писали:
П>И кто же этот коварный "кто-то"? Покажи пальчико плз. Ладно пальцем некультурно, лучше ссылкой. Насколько я знаю define стали вчерашним днем с момента появления C++. Не говоря уж про C#, в котором (Vlad2 меня поправит если что) их вообще нет. Может хватит бегать со страшилками двадцатилетней дваности?
Вот насчет двадцатилетней давности — это похоже на правду. В те времена набрать с клавиатуры текст программы было довольно-таки напряжно: удаленный доступ, скорость 1200 б/с счастьем считалась. Ошибки в наборе исправлять — тоже целое дело. Поэтому в данном конкретном случае такой подход можно понять. Единственный раз в жизни попробовал. Причем на гораздо более высокой скорости.
Кстати, программа, которую я вводил, писалась на Паскале. Кажется, с тех пор я его стараюсь избегать. Наверное, Паскаль и не виноват, но ассоциация осталась.
Здравствуйте, Трурль, Вы писали:
Т>Фразу "есть в языке" можно понимать как "выразимо средствами языка" или "отражено грамматикой языка". В первом случае класс того, что "есть в языке" гораздо шире. Например, в русском нет давнопрошедшего времени, но выразить его вполне возможно.
Здравствуйте, Павел Кузнецов, Вы писали:
> работа всегда идет не более чем с одним единственным словом sym.
ПК>На этом основании эта грамматика LL(1) не становится, т.к. процитированное выше обращение к таблице символов во время разбора выходит за рамки операций, доступных LL-автомату. Не всякий парсер, разбирающий синтаксис, оперируя по одной лексеме за раз, является LL-парсером/автоматом.
Спорить не буду. Наверное Вам виднее если Вы так утверждаете. Просто я всегда думал что если текст парсится методом рекурсивного спуска с чтением только одного слова, то грамматика — LL(1). Ну нет так нет... Кстати, а название у таких грамматик есть? Если нет, то давайте такие грамматики условно назвать RDP(1), где RDP происходит от Recursive Descend Parsing.
Здравствуйте, Сергей Губанов, Вы писали:
СГ>Здравствуйте, Павел Кузнецов, Вы писали:
>> работа всегда идет не более чем с одним единственным словом sym.
ПК>>На этом основании эта грамматика LL(1) не становится, т.к. процитированное выше обращение к таблице символов во время разбора выходит за рамки операций, доступных LL-автомату. Не всякий парсер, разбирающий синтаксис, оперируя по одной лексеме за раз, является LL-парсером/автоматом.
СГ>Спорить не буду. Наверное Вам виднее если Вы так утверждаете. Просто я всегда думал что если текст парсится методом рекурсивного спуска с чтением только одного слова, то грамматика — LL(1). Ну нет так нет... Кстати, а название у таких грамматик есть? Если нет, то давайте такие грамматики условно назвать RDP(1), где RDP происходит от Recursive Descend Parsing.
Несколько неверный термин, правильнее видимо Recursive descent parser
(descend в английском не есть существительное... )
Перекуём баги на фичи!
)
