All streams
Search
Write a publication
Pull to refresh
73
0
Владимир Лапшин @mefrill

User

Send message
Синтаксис я в Strutext не перенес. У меня есть реализация синтаксического анализатора на основе алгоритма Эрли. Я из него сделал инструмент, примерно аналогичный по функционалу Томита парсеру от Яндекса. Код рабочий, но какие-то вещи надо конечно доработать, что-то в интерфейсе добавить. Самому мне это делать трудно, сейчас времени мало. Если бы были энтузиасты, то я бы выложил код, написал бы про принципы реализации, ну и вместе что-то полезное сделали бы.
Про морфологию напишу. Там есть несколько интересных вещей по аотовской модели. Ну и с технической точки зрения тоже наверное интересно кому-то будет.
Честно говоря, не понимаю, в чем заключается разница между понятиями «Бор» и «ДКА» в данном контексте. Бор здесь — это обычный детерминированный конечный автомат, используемый для хранения словаря (набора слов из некоторого алфавита). Этот автомат здесь, в силу особенностей своего построения, имеет древовидную структуру переходов, но и только — все остальное у него ничем от автомата не отличается. В библиотеке я так и определяю: AcAutomaton наследует класс Trie, который наследует Fsm. Trie полезен сам по себе, например используется для хранения словаря.
Если к целеполагательному алгоритму добавлять и добавлять рефлексии, то на определенном этапе такой алгоритм превращается в сознание.


Чтобы понять, во что нечто превращается, надо иметь понимание о том, что это нечто представляет из себя. В данном случае, необходимо определить, что такое сознание. Для меня лично, сознание — это просто специфическое переживание особой человеческого вида, не более того. Зачем (с эволюционной точки зрения) необходимо это переживание человеческому виду, вопрос отдельный. Может ли иметь схожие переживания машина? Уместно ли вообще говорить о переживаниях машин?

Если стать на бихевиористскую точку зрения и определять наличие сознания по поведенческим признакам, то многие современные машины ведут себя во многих случаях гораздо разумнее многих людей. Хотя здесь вообще порочный круг в определении. Сознание здесь определяется как рациональное поведение в определенном окружении, но это и есть основной метод определения сознательности наблюдаемого объекта.

Если стать на точку зрения объективного идеализма, то нужно признать, что в Мире есть некое объективное Сознание, этакое поле, приникающее всю наше реальность. И человеческий вид, в силу каких-то эволюционных особенностей, приобрел ценное для себя качество это поле воспринимать. Переживание, которое охватывает человека при таком чувствовании, люди называют «сознательностью». Но снова, здесь не совсем понятно, зачем машинам такая способность.
Нашел статьи на русском языке. Статья по синтаксическим топологиям даже перекомпилировал. Правда, не знаю, как ее здесь присоединить. Могу выслать почтой, если необходимо.
Первую статью, в которой задаются сами синтаграммы, я пока не хочу публиковать. За прошедшее время я переосмыслил кое-какие вещи, поэтому хочется заново переформулировать понятия и, заодно, понятия языка и его алфавита. Мне кажется, должно получится что-то интересное.
С работами Прозорова я не знаком. Спасибо за ссылку, почитаю и напишу свое мнение.
Я попытался расширить понятие окрестностной грамматики, надо которым работали Борщев и Хомяков в 70-х годах. Владимир Борисович, кстати, делал доклад по этой работе на Диалоге . Идея та же, что и со шрейдеровскими окрестностными грамматиками. Только они задавали грамматики деревьев вывода контекстно-свободных грамматик. Т.е. они расширили понятие о языке. Язык — это не множество цепочек, но множество синтаксических структур, для КС-грамматик это деревья вывода. Для каждого символа можно задать множество его окрестностей, которые будут уже не цепочки, но «кусты» в дереве. Тогда дерево принадлежит языку в том и только в том случае, если каждая его вершина входит в это дерево вместе с некоторой своей окрестностью (кустом).

Идея здесь на самом деле топологическая. Окрестность — это аналог окрестности точки в топологии, т.е. открытого множества, содержащегося в топологии. Топология и есть ведь набор открытых множеств, заданных для каждой точки пространства. Множество в топологии считается открытым, если каждая точка входит в него вместе с какой-то своей окрестностью. Все это очень похоже на то, что имеется в грамматике. Я понял, что на самом деле в деревьях вывода визуализируется отношение иерархии («быть частью»), которое является основным в КС-грамматике. В цепочках языка имеется отношение непосредственного следования, т.е. «быть рядом». Такие отношения можно рисовать в виде графов, для них я даже придумал специальный термин — синтаграмма. Граф синтаксических отношений цепочки правильный (а значит и сама цепочка принадлежит языку), если каждая вершина этого графа входит в него вместе с некоторой своей окрестностью. Т.е. здесь полный аналог топологии и открытых множеств.

Понятие синтаграммы позволяет абстрагироваться от природы синтаксических отношений. Синтаграммы — это и деревья КС-грамматик, а также и обычные цепочки традиционного формального языка. Но графы — это не множества, поэтому понятия вложения в них другое. Два графа могут вкладываться друг в друга несколькими способами, тогда как для множеств вложение только одно. Значит, математический аппарат топологии сюда
непосредственно применить не получается. Но можно попытаться применить методы теории категорий, т.е. образовать категорию синтаграмм. В этой категории топологией будет как раз окрестностная грамматика. В теории категорий есть аналог понятия топологического пространства — это т.н. топология Гротендика. Но эта топология сама по себе только на основе категории не строится. Для нее необходимо еще одна категория, куда объекты исходной категории будут отображаться. Я понял, что для синтаксиса такая категория естественным образом появляется.

Если для каждой окрестностной синтаграммы задать множество ее смыслов, то получим функтор (отображение) из категории синтаксиса в категорию семантики этого языка. От природы смыслов мы абстрагируемся, просто считаем, что это элементы какого-то множества. С каждой базовой синтаксической конструкцией связано конечно множество смыслов. Причем наблюдается интересная закономерность. Если мы имеем какую-то синтаграмму, например, дерево вывода какого-то предложения в КС-грамматике Хомского, то она имеет покрытие окрестностными синтаграммами для каждой своей вершины. Т.е. имеется такой подъем, когда любая синтаграмма составляется из окрестностей — отображение наверх, к более сложным частям. С другой стороны, в семантике имеется спуск вниз. Если есть какой-то смысл, связанный с составной конструкцией и есть смыслы связанные с его составными частями, то с каждым смыслов в составной конструкции связаны смыслы его частей. Т.е. это отображение вниз в категории семантики.

Это именно то, что требуется для топологии Гротендика, она примерно так и описывается. Надо только, чтобы при составлении правильной конструкции каждая комбинация смыслов его частей задавала однозначно смысл этой составной конструкции. Но это как раз именно то, что в формальной семантике называют «принципов композиционности», когда семантика конструкции определятся семантикой его частей. В теории категорий в интерпретации синтаксиса, как я его описал, этот принцип связан с понятием пучка.

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

Мне кажется, какие-то вещи в этом подходе интересны и сами по себе. Даже в вещах, на первый взгляд, далеких от лингвистики. Например, известную задачу о раскраске карты можно интерпретировать как задачу построения соответствующей окрестностной грамматики. Ну и интерпретация лингвистических вещей в теории категорий может дать возможность использовать интересные методы и подходы из этой области математики.

Сейчас посмотрел, к сожалению, на моем компьютере тексты статей не сохранились. При желании их можно найти, но для понимания надо освоить какие-то понятия теории категорий. Это конечно трудно.
Грамматика — это необязательно автомат. Можно задать грамматику языка, которая не будет алгоритмом, т.е. не предназначена для задания языка. Например, окрестностная грамматика в этом тексте просто описывает синтаксические свойства языка, хотя может быть использована для задания распознающей грамматики очевидным образом. Такой вид грамматик, которые описывают язык, но не определяют алгоритм его задания, я называю описательными грамматиками. Другой вид описательной грамматики — категориальная грамматика Ламбека. Эта грамматика, конечно, превращается в алгоритм распознавания цепочек, т.е. в исчисление, которое применяется к цепочке на основе правил редукции, но важна и сама по себе, как описание синтаксических закономерностей языка.

Грамматики могут быть не только порождающие, как Вы написали выше, но и другого типа (распознающие, перечисляющие). Например, машину Тьюринга можно считать распознающей грамматикой, если использовать первую с вполне определенными довольно узкими целями: для распознавания множества цепочек. В этом смысле, определение грамматики уже определения алгоритма. Интересный вид перечисляющей грамматики — формальные степенные ряды над контекстно-свободными языками. Формализм, на мой взгляд, явно недооцененный.

Резюмируя, грамматика — это не только алгоритм задания языка, но и описание синтаксических закономерностей. В лингвистике, например, принимается во внимание исключительно второй аспект определения, на первый не особо обращают внимание. Конечно, с математической точки зрения важно понимать, как конкретный формализм задает язык, но это не обязательно самое главное в изучении синтаксических свойств языка. Теория алгоритмов изучает закономерности процессов вычислений и, ясно, что любое задание языка протекает во времени и, следовательно, является процессом. Отсюда можно сделать вывод, что любая грамматика, если ее применять как процесс задания языка, неизбежно превращается в один из возможных типов алгоритмов задания множества цепочек. Но грамматика — не алгоритм, но нечто большее. Поэтому я предпочитаю использовать термин «грамматика» вместо термина «автомат».
Под мощностью класса грамматики здесь подразумевается возможность задавать некоторый класс языков. Некоторые языки, которые могут быть заданы перечисляющей грамматикой, не могут быть заданы распознающей грамматикой, хотя обратное утверждение, как Вы верно заметили, всегда выполняется. Т.е. имеется вложение класса распознаваемых языков в класс перечислимых. В теории алгоритмов используются термины рекурсивное и рекурсивно-перечислимое множество. Там утверждение о неэквивалентности этих классов множеств (языков) — одна из основных теорем.
Будет, чуть попозже. Наверное, порождающие грамматики. Можно и про методы синтаксического анализа.
В части теории формальных грамматик статья безграмотная. Такого понятия, как «регулярная грамматика» в иерархии Хомского вообще нет, это автор сам придумал. Есть определение грамматики типа 3. Это грамматика с правилами вида A --> aB, A --> Ba и A --> a. Заметим, что правила с пустой правой частью здесь нет, это правило автор также придумал. Здесь главное, что порождение цепочек языка производится добавлением символа спереди или сзади. Вообще, необязательно даже, чтобы один символ добавлялся, можно сразу несколько, т.е. правила можно и такие сделать: A --> Bw, где w — цепочка из терминальных символов. Это правило легко преобразовать в эквивалентные (с точки зрения порождающей мощности) классического вида для типа 3.

Есть понятие «регулярный язык» — язык, который задается регулярным выражением. Есть также теорема Клини, которая говорит о том, что каждый регулярный язык можно также задать и конечным автоматом и, наоборот, каждый язык, заданный конечным автоматом, можно задать также и регулярным выражением. С другой стороны, есть связь между иерархией Хомского и иерархией вычислительных автоматов. Это соответствие было обнаружено и доказано задолго до того, как регулярные выражения стали использоваться как способ задания формального языка. С методической точки зрения намного проще и понятнее связать регулярные выражения с автоматами.

Для выражений с группированием и обратными ссылками вполне себе подходит модель автомата с магазинной памятью (стеком). Это мощный формализм. Различают детерминированные и недетеминированные автоматы с магазинной памятью. Не так сложно, как мне кажется, построить магазинный автомат для регулярного выражения с обратными ссылками. Автомат с магазинной памятью эквивалентен (в том смысле, что задает тот же язык) контекстно-свободной грамматике. Для контекстно-зависимых грамматик имеется соответствие с т.н. линейно-ограниченными автоматами. Такие автоматы и грамматики могут задавать сложные языки, например, язык L = {(a^n)^2}, т.е. все цепочки этого языка состоят из символов a, число которых равно квадрату чисел натурального ряда: a, aaaa, aaaaaaaaa, .... Попробуйте придумать регулярное выражение для этого языка, мне кажется, довольно трудно.

Вообще, задавать сложный язык регуляркой не хорошо с точки зрения возможности отладки и последующей поддержки. Язык РВ для таких вещей явно не предназначен, получаются монстрообразные выражения, которые трудно даже просто прочитать. Конечно, форматирование помогает, но и оно не всегда является панацеей. Мне кажется, человеческому уму больше подходят иерархические структуры, в этом, видимо, и состоит секрет популярности контекстно-свободных грамматик. Они сейчас используются совсем не в том смысле, который задавал им Хомский изначально (как методы порождения цепочек языка), а скорее как категориальные грамматики, в которых нетерминальные символы обозначают категории, а стрелочка в правиле грамматики — иерархическую связь между категориями.
Да, конечно, некоторые проверки можно отключить опциями. Но, для полноценного использования я скрипт обычно подстраиваю. Какие типичные проблем сразу вспоминаются:
* Проблема с проверкой порядка включения заголовочных файлов. Проверяемый порядок включения таков: файлы стандартной библиотеки C, файлы STL, файлы третьих библиотек (в угловых скобках), файлы проекта (в двойных кавычках). Т.к. в Google не используют Boost, там ничего про него не сказано и программка ругается на такие заголовки. Скрипт приходится менять.
* Т.к. исключения в Google не разрешены, скрипт не знает ключевого слова catch и потому ругается на конструкцию вида catch (...). Скрипт думает, что это вызов функции, а в стиле Google между именами функций и скобками нельзя ставить пробелы. Надо добавить catch в список ключевых слов.
* Проверку копирайта конечно можно отключить, но хотелось бы ее как-то использовать. Я обычно в своих программах использую Doxygen комментарии и для описания файла задаю такой шаблон:
/** Copyright © 2011-2013, CompanyName.
* \file File name
* \brief File description.
* \author Author name.
* \date Date
*/

Не так трудно поменять скрипт, чтобы он проверял наличие таких комментариев в начале файла. С методами/классами я не заморачивался, но можно было бы, при желании.

В общем, было бы здорово иметь такие вещи в качестве параметров.
cpplint.py создан для проверки стиля кодирования компании Google. Этот стиль интересный, но какие-то вещи выглядят явными архаизмами. Например, запрет на использование шаблонов и исключений. Ну, а проверку копирайта в первой строке файла вообще приходится менять для каждой компании. Обычно этот скрипт качают и подгоняют на месте. Было бы интересно добавить в скрипт возможности подгонки стиля по какому-то множеству параметров. Иначе, по крайней мере, для C++, это малорименимо.
Я совсем не против, наоборот, — за! Вообще, эту историю я включил в свой учебник по математической лингвистике, вышедший в 2010 году: В.А. Лапшин, «Лекции по математической лингвистике». Я на протяжении семи лет читал одноименный курс в РГГУ, в Институте Лингвистики, на кафедре Интеллектуальных систем в гуманитарной сфере. Учебник был для этого курса. В общем, не для рекламы, а пользы ради. Там стандартное изложение по регулярным языкам.
В этой работе Хомского не было упоминания о регулярных выражениях. Хомский просто ввел способ описания синтаксической структуры предложений английского языка (порождающие или генеративные грамматики). В то время такие работы были популярны, одна из наиболее известных похожих работ — «Математическое исследование структуры предложения» Ламбека, опубликованная в 1958 году. Вообще, эту работу Хомского очень интересно почитать, там видно, насколько отличен язык научного изложения теории формальных грамматик того времени и сегодняшний язык. Вопросы поднимаются вроде бы одни и те же, а объекты изучения различные. В те времена еще были иллюзии, что естественный язык можно задать относительно небольшой формальной грамматикой, надо только придумать правильный принцип. Вот Хомский и предложил один из таких принципов. Уже потом порождающие грамматики стали использовать для анализа формальный языков, в том числе и для языков программирования.
2

Information

Rating
Does not participate
Location
Москва, Москва и Московская обл., Россия
Date of birth
Registered
Activity