Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > LL(1)-грамматики

Автор: GreatStream 3.6.2006, 22:06

Помогите плиззз с примерами LL(1)-грамматик, это могут быть какие угодно примеры: Грамматика,задающая вещественные числа с фиксированной точкой со знаком, грамматика задающая натуральные числа со знаком и т.д, главное, чтобы в форме LL(1)-грамматики или научите плиизззз как преобразовать грамматику и привести ее к LL(1) виду, формализованных алгоритмов приведения произвольной грамматики нет, но как-то ведь их приводят к LL(1)-виду.

Автор: Void 3.6.2006, 22:36

Пример LL(1) грамматики: грамматика арифметических выражений. Цитата expression ::= expression '+' term | expression '-' term | term term ::= term '*' factor | term '/' factor | factor factor ::= '(' expression ')' | number Цитата(GreatStream @  4.6.2006,  00:06 ) формализованных алгоритмов приведения произвольной грамматики нет И быть не может, потому что есть грамматики, не сводящиеся к LL(1). Для приведения к LL(1)-виду может понадобится устранение леворекурсивных правил и левая факторизация. По всем вопросам рекомендуется курить «Дракона» Ахо, Ульмана и Сети. Можно и двухтомник Ахо, Ульмана «Теория синтаксического анализа, перевода и компиляции».

Автор: GreatStream 4.6.2006, 12:28

Цитата expression ::= expression '+' term | expression '-' term | term term ::= term '*' factor | term '/' factor | factor factor ::= '(' expression ')' | number Прости, может я чего-то не понимаю, но это не есть LL(1)-грамматика, так как в ней присутствует левая рекурсия, к тому же пример с арифметическими выражениями у меня уже есть, а надо что-нить такое, ну например: грамматика задающая вещественные числа со знаком и фиксированной точкой. Если есть возможность где-нить посмотреть или видел где-нить дай знать плизз, очень надо. А Ахо и Ульмана я смотрел, там по LL(1)-грамматикам тоже в качестве примера только гр-ка арифметических выражений, у Молчанова та же херь

Автор: Void 4.6.2006, 16:42

Цитата(GreatStream @  4.6.2006,  14:28 ) грамматика задающая вещественные числа со знаком и фиксированной точкой. Это будет автоматная грамматика. Т.е. она, конечно, разбирается LL(1)-парсерами, но, думаю, не совсем то, что нужно. Цитата(GreatStream @  4.6.2006,  14:28 ) но это не есть LL(1)-грамматика, так как в ней присутствует левая рекурсия Устранимая. Цитата expression ::= term more_terms more_terms ::= '+' term more_terms | '-' term more_terms | ε term ::= factor more_factors more_factors ::= '*' more_factors | '*' more_factors | ε factor ::= '(' expression ')' | number Цитата(GreatStream @  4.6.2006,  14:28 ) А Ахо и Ульмана я смотрел, там по LL(1)-грамматикам тоже в качестве примера только гр-ка арифметических выражений, у Молчанова та же херь Возьми грамматику Оберона. Вирт специально проектировал язык с LL(1) грамматикой. Ну или просто дополни арифметические выражения простенькими операторами, вроде if..then..else..end (именно с end, так как обычная конструкция с dangling else LL(1) не является).

Автор: GreatStream 4.6.2006, 16:53

Дык видишь есть уже про арифметические операции, надо что-то другое. А у тебя могет есть какая-нить литература в электронном виде или могет знаешь полезные линки. Я пытался найти что-то кроме Ахо, Ульмана, попадаю на сайты непонятного происхождения, на которых контент непонятно от куда взят, видел просто ссылки на Вирта, но так и не нашел его в сети, что в еблиотеку что-ли прийдется ползти? И что за грамматика Оберона?

Автор: Void 4.6.2006, 17:13

Цитата(GreatStream @  4.6.2006,  18:53 ) Дык видишь есть уже про арифметические операции, надо что-то другое. В чем проблема придумать простейший язык? Ну хотя бы вариант S-выражений: Цитата s-expression ::= '(' atom-list ')' atom-list ::= atom more_atoms more_atoms ::= atom more_atoms | ε atom ::= s-expression | identifier Цитата(GreatStream @  4.6.2006,  18:53 ) И что за грамматика Оберона?   Оберон — это http://www.oberon.ethz.ch/ такой. С http://www.oberon.ethz.ch/EBNF.html грамматикой. Цитата(GreatStream @  4.6.2006,  18:53 ) Я пытался найти что-то кроме Ахо, Ульмана Зачем? Чего не хватает в их книге? Кучи готовых примеров на все случаи жизни?  Поищи лекции Серебрякова по построению компиляторов.

Автор: GreatStream 4.6.2006, 19:43

Спасибки, слушай, я вижу ты занимался этой темой, могет у тебя примеры реализованных распознавателей есть: нисходящий без возвратов или с возвратами, реализованный на Delphi или Paskal?   Не а вдруг? Был бы признателен! Лекции Серебрякова я поищу обязательно. Thanks!

Автор: Void 4.6.2006, 19:52

Цитата(GreatStream @  4.6.2006,  21:43 ) могет у тебя примеры реализованных распознавателей есть Увы, нет. Околокомпиляторными вопросами занимаюсь по сей день, но для построения синтаксических анализаторов либо пользовался генераторами, либо писал recursive-descent парсеры, но уж никак не на Pascal/Delphi  А примеров реализации алгоритмов в сети выше крыши.

Автор: GreatStream 5.6.2006, 11:23

Ну не скажи

Автор: GreatStream 6.6.2006, 17:07

Могет есть у кого реализованные распознаватели с возвратами и без?

Автор: Sardar 6.6.2006, 18:11

GreatStream, неужели сложно найти и скурить: http://algolist.manual.ru/download.php?path=/syntax/compilat.zip Там примеры на C, которые просто переделать на паскаль/дельфи.

Автор: GreatStream 6.6.2006, 22:53

спасибо

Автор: GreatStream 7.6.2006, 13:42

Могет у кого ешо што интересное есть, тема то ведь интересная

Автор: GreatStream 15.6.2006, 16:20

Ребята, могет у кого еще есть распознаватели какие-нить? Кстати кто-нить знает по какому принципу в распознавателе с возвратом происходит удаление возвратов? А? Добавлено @ 16:21  В смысле по какому принципу идет преобразование алгоритмов в алгоритмы без возвратов?

Автор: GreatStream 19.6.2006, 16:26

Блин нихто не знает что ли, мне сказали что какой-то чувак рассматривал способы избавления от возвратов!!! Добавлено @ 16:29  Его фамилия на Г то ли Гринберг то ли как-то так, может кто-нить знает кто он? И где его книжгу мона достать?

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)