Русские вычислители

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » Русские вычислители » О языках программирования » рекурсивный подъём


рекурсивный подъём

Сообщений 1 страница 8 из 8

1

Как видно из русской википедии - это неизвестная у нас техника разбора текста.

Нет трёх статей:
1) вообще про разбор подъемом;
2) про алгоритм рекурсивного подъёма;
3) про комбинирование рекурсивного подъема с рекурсивным спуском.

Так в английской википедии есть две статьи про направление анализа:
https://en.wikipedia.org/wiki/Top-down_parsing
https://en.wikipedia.org/wiki/Bottom-up_parsing
и два способа реализации разбора в этих направлениях:
https://en.wikipedia.org/wiki/Recursive_descent_parser
https://en.wikipedia.org/wiki/Recursive_ascent_parser

В русской википедии статья всего одна:
https://ru.wikipedia.org/wiki/Нисходящий_синтаксический_анализ
и способ реализации описан только один:
https://ru.wikipedia.org/wiki/Метод_рекурсивного_спуска

Это говорит о том, что уровень осознания механизмов анализа текста в русскоязычной среде ниже (иначе бы текстов было больше и в этих текстах были бы рассмотрены различные варианты и связанные с ними особенности).

В частности в английской википедии приводится следующий аргумент:
- табличные парсеры увеличивают значение константы в оценке сложности алгоритма анализа и приводится аналогия:
разница между табличными анализаторами, и непосредственно закодированными такая же как между интерпретируемым и скомпилированным кодом.

Впервые рекурсивный подъем описан в 1986-м году в работе
Thomas Penello "Very fast LR parsing"
то есть отставание составляет 2016-1986=30 лет.

Почему вообще подъём лучше спуска?
В случае спуска мы предполагаем, что всё уже заранее известно и нужно достичь корневого нетерминала грамматики. Такого рода анализаторы никогда не смогут создавать в себе новые понятия (если и смогут, то после развития альтернативной теории и через костыли). А нам нужно другое - возможность строить гипотезы про смысл непонятных слов.

0

2

Отличная идея, мне нравится.

ВежливыйЛис написал(а):

Это говорит о том, что уровень осознания механизмов анализа текста в русскоязычной среде ниже (иначе бы текстов было больше и в этих текстах были бы рассмотрены различные варианты и связанные с ними особенности).

Восходящий разбор описан в:
Ф.Льюис, Д.Розенкранц, Р.Стирнз. Теоретические основы проектирования компиляторов 1979
Карпов Ю. Г основы построения трансляторов 2005 г.

--------------------------
Вот что пишет Мартыненко Б. К.:

Часть II посвящена описанию двух классов контекстно-свободных языков:
LL(k) и LR(k) ввиду их практической важности. Первый является наибольшим
естественным классом языков, допускающих детерминированный нисходящий
разбор посредством k-предсказывающего алгоритма анализа. Второй
представляет столь же естественный класс языков, допускающих
детерминированный восходящий разбор посредством канонического
анализатора Д. Кнута. Тот и другой имеют линейную сложность по времени.
Как известно, метод Кнута используется в инструменте YACC — популярном
построителе синтаксических анализаторов, а также в более развитых
модификациях этого технологического средства. Фактически в них
используются LR(1)-грамматики с дополнительными оптимизирующими
ограничениями — так называемые LALR(1)-грамматики. Последние
обсуждаются в конце этой части. В части II рассматриваются также некоторые
классы синтаксически-управляемых трансляций с входными языками
упомянутых классов и соответствующие алгоритмы их реализации. Последние
описываются с достаточной для практики полнотой и обоснованием
корректности и оценок сложности.

0

3

П.С.
Не забывайте, что английскую википедию пишут преподаватели. Их заставляют это делать вузы. Так как им за это идут налоговые вычеты.
А у нас пишет, кто попало и без какого либо стимула.

Отредактировано Павиа (04.11.2016 11:16:02)

0

4

ВежливыйЛис написал(а):

Как видно из русской википедии - это неизвестная у нас техника разбора текста.

Всё-таки это иностранная энциклопедия, пусть даже с поддержкой русского языка, и связывать её наполнение с уровнем знания в российском сообществе не совсем корректно. Но по смыслу Вы правы, хороших отечественных ресурсов по теме описания и проектирования языков очень мало. Практически это единичные курсы, которые опубликованы на площадках наших ВУЗов.

http://neerc.ifmo.ru/wiki/index.php?title=Теория_формальных_языков

http://neerc.ifmo.ru/wiki/index.php?title=Методы_трансляции

http://ermak.cs.nstu.ru/trans/

0

5

Инженер

Но по смыслу Вы правы, хороших отечественных ресурсов по теме описания и проектирования языков очень мало. Практически это единичные курсы, которые опубликованы на площадках наших ВУЗов.

Теория компиляторов настолько оторвана от практике. Что мне она уже неинтересна.

0

6

Павиа

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

0

7

http://anonym-mouse.livejournal.com/1294.html

К этому добавлю от себя. К моему удивлению, первые комментаторы перевода в ru_programming просто не поняли о чем речь в этом отрывке (!!!)

А речь идет о логике программирования вообще. Человеческий язык в огромной степени "встроен" в наш мозг, и его структуры отражают структуры мышления самым точным и тонким образом. Ученым нужно делать не ЯМР-сканы мозга, а копаться в устройстве человеческой речи.

Поэтому ИДЕАЛЬНЫЙ язык программирования должен позволять ЕСТЕСТВЕННЫЙ для человека лингвистический разбор задачи на куски и их изложение.

Изложенные в заметке парадигмы - императивная (пойди, возьми, положи, повернись, вернись) и "объектно-ориентированная" - не охватывают всего. Упомянута функциональная. На псевдо-Лиспе она выглядит примерно так:
(цель - вынести мусор):
(или
         (и
           (засунуть (переместить (взять мешок) в_гараж) (поднять крышку_бака))
           (вернуться)
           (лечь на диван)
         )
         (сообщить о провале операции)
     )

"взять мешок" дает "существительное", состояние (вроде "мешок в руках"), которое может стать дополнением глагольной формы "переместить что куда", далее оно вложено в "засунуть что куда", где последнее "куда" также получилась из вложенного "поднять что", и так далее

Когда существительное (состояние и т.д.) образуется в результате действий над предыдущим состоянием или предметом (которых, _исходных_ предметов и их собраний, в программе относительно мало) - и вместо того, чтобы давать ему имя, мы анонимно вкладываем его в следующее по цепочке действие

В этом есть что-то очень увлекательное для мозга, и такое программирование доставляет удовольствие и имеет огромные преимущества по сравнению с выморочными, ублюдочными объектами, насилующими естественное мышление и логику, так хорошо осмеянными в заметке.

Однако осталась нерассмотренной еще одна крупная парадигма: декомпозиция задачи установкой целей. Неважно, цель выражается глагольной формой или сочетанием, или фразой существительного.

(цель) ДОМ :- (зависит от) крыша, стены, окна, двери

Крыша:- стропила, черепица

стропила:- дерево_подготовить, конструкцию_поднять, конструкцию_собрать

конструкцию_собрать:
    (конкретные вычисления-операторы через и, или, ...)

Это - логическое программирование, Пролог.
Заметьте, что я не занимаюсь выстраиванием линейной последовательности исполнения, как в случае декларативного программирования с функциями. Я думаю локально, о соседнем уровне, оставляя глобальные увязки программе.

Альтернативный подход предлагает нам Smalltalk. Мы описываем объект и его свойства. Последний глагол вычисляет необходимое. Вычисление происходит через анализ- эта функция разбирает код на составляющие и сама решает как вычислять какие приоритеты у операторов.
Объект может быть глаголом. Мы можем написать цепочку глаголов ровно как и объектов.
Бросать.Вывод.Дверь(передать.Мусор)
Это уже существует в существующих языках.

В юникоде есть такая вещь как неразрывный пробел.  Точку можно очень просто заменить этим пробелом. Слова будут сцеплены. А разбор предложения поручить как Smalltalk классам. Это позволит не изобретать сложный парсер.

Отредактировано Павиа (06.11.2016 22:22:16)

0

8

В естественных язык связки логические свободно-направленные, а не сужено-функциональные.
Поэтому предложение вроде "равны А и Б"/"А равно Б" либо вызывает откат (в примитивных языках это называется исключением), либо связывает значения (остаётся правилом, если ни одно еще не определено).
Функциональщина заточена под машинную архитектуру разделения вычислений, а не человеческий язык.

Это - логическое программирование, Пролог.
Заметьте, что я не занимаюсь выстраиванием линейной последовательности исполнения, как в случае декларативного программирования с функциями. Я думаю локально, о соседнем уровне, оставляя глобальные увязки программе.

Видимо слабое знакомство с Прологом. Там строго последовательное исполнение логических связок: пролог прямой, например, как Паскаль, но есть откаты и последовательный перебор соответствий по списку.
Т.е. вместо
try
//основная ветка
except
//перехват всех исключений
end;

логика:-
%основная ветка
!.%если нужен запрет других случаев при удачном прохождении какой-то ветки/её части
логика:-
%перехват исключений предыдущих случаев

А сопоставление параметров покрывают все перегрузки функций, ООП-методы и т.д.
Не объяснение/понимание этой разницы не позволяет большинству работать с Прологом, а так можно хоть за день-два научиться (несинтоксичен).
А вот с реализациями печаль, возможностей мало, сам язык никто давно не допиливал, хотя какой-то % он на рынке занимает и потягается в обработке данных с SQL, XML, JSON и прочим встроенной простотой их описания и сразу собственным механизмом БД (даже два их).

По частоте скорее всего после 1С  программы кириллицей какие-нибудь студенты пишут как раз на нём.

0

Быстрый ответ

Напишите ваше сообщение и нажмите «Отправить»



Вы здесь » Русские вычислители » О языках программирования » рекурсивный подъём