Рубрика «синтаксический анализ» - 2

в 7:46, , рубрики: diy или сделай сам, Go, nlp, грамматика, ИИ, Компиляторы, русский язык, синтаксический анализ

Разбор естественного языка: грамматическая нотация - 1

Я уже довольно давно интересуюсь ИИ, особенно областью, связанной с пониманием машиной текстов, написанных на естественном языке. Как известно, классическая теория анализа текста разделяет этот процесс на три этапа:

  • Морфологический — анализ словоформ и их характеристик (число, падеж, и т.д.);
  • Синтаксический — выделение структуры предложения (отношения между словами);
  • Семантический — выделение смысла исходя из «модели мира»;

Первый этап в целом решён. Мы имеем подробные морфологические словари, покрывающие львиную долю слов, встречающихся в большинстве текстов. Кроме того, для распространённых языков существуют правила, позволяющие с достаточной точностью классифицировать неизвестные словоформы.

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

Из-за отсутствия у меня глубоких знаний в области нейронных сетей я решил следовать более проторенной тропой, а именно разработать BNF-подобную грамматическую нотацию и реализовать анализатор, использующий грамматические правила, описанные с её помощью. С этой точки зрения при разработке практически полезного анализатора основная работа заключается именно в построении достаточной системы правил (что у меня далеко до завершения). В следующем посте я опишу устройство реализованного анализатора, а пока хочу сфокусироваться на разработанной грамматической нотации.
Читать полностью »

в 14:35, , рубрики: .net, IDE, sql, синтаксический анализ, среда разработки, статический анализ кода, текстовые DSL

Введение

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

Выполнение кода на JavaScript из кода, написанного на Java:

import javax.script.*;

public class InvokeScriptFunction {
    public static void main(String[] args) {
        ScriptEngineManager manager = new ScriptEngineManager();
        ScriptEngine engine = manager.getEngineByName("JavaScript");

        // JavaScript code in a String
        String script = "function hello(name) {print('Hello, ' + name);}";

        // evaluate script
        engine.eval(script);
    }
}

Читать полностью »

в 10:43, , рубрики: C99, dom, html, html5, open source, Веб-разработка, Си, синтаксический анализ, метки: , , , , ,

Удачная возможность для веб-разработчиков выучить язык программирования Си — HTML5-парсер Gumbo, реализованный в виде небольшой библиотеки C99 без внешних зависимостей. Парсер создан как строительный блок для создания других инструментов и библиотек, таких как валидаторы, языки шаблонов, инструменты рефакторинга и анализа кода.

Особенности:

  • Полная совместимость со спецификациями HTML5.
  • Устойчивость к некачественным входным данным.
  • Простые API, которые могут быть легко обработаны программами на других ЯП.
  • Поддержка исходных позиций и указателей в оригинальном коде, при навигации по дереву зависимостей.
  • Проходит все тесты html5lib-0.95.
  • Проверен на более чем 2,5 млрд страниц в индексе Google.

Читать полностью »

в 22:12, , рубрики: natural language processing, Алгоритмы, искусственный интеллект, Компьютерная лингвистика, синтаксический анализ, метки: , ,

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

Наша цель заключается в создании парсера русского языка, т.е. программы, которая на вход бы принимала произвольный текст, а на выходе выдавала бы его синтаксическую структуру. Например, так:

"Мама мыла раму":

(предложение
    (именная гр. (сущ мама))
    (глаг. гр. (глаг мыла)
        (именная гр. (сущ раму)))
    (. .)))

Это называется синтаксическим деревом предложения. В графическом виде его можно представить следующим образом (в упрощенном виде):
Парсим русский язык
Читать полностью »

в 14:43, , рубрики: bison, c++, flex, parser, python, Программирование, разработка, синтаксический анализ, метки: , , , ,

Вступление

Уже около двух лет я участвую в OpenSource проекте Source Analyzer, и вот появилась необходимость написать парсер для языка Python, который должен уметь строить граф вызовов (Call Graph) и граф зависимостей классов (Class Graph Dependency). Если точнее, граф строится с помощью других инструментов, а парсер должен лишь подготовить для этих инструментов данные.

Процесс работы над парсером был довольно занятным и мне бы хотелось поделиться с вами приобретенным опытом, а также поведать о некоторых подводных камнях, которые встретились на этапе разработки.
Читать полностью »

в 12:48, , рубрики: ECMAScript, javascript, lalr, Алгоритмы, Компиляторы, парсеры, синтаксический анализ, метки: , , , , ,

Введение

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

Дабы задать контекст, сообщу, что грамматика для анализа — это ECMAScript, так же известный как JavaScript. Конкретная спецификация — ECMA-262, редакция 5.1 от июня 2011 года.
Читать полностью »

в 12:41, , рубрики: lalr, Алгоритмы, Компиляторы, парсеры, синтаксический анализ, метки: , , ,

Предисловие

Добрый день.
Это вторая часть статьи про написание своего генератора LALR-анализаторов. В этой части я расскажу про эволюции от примитивных восходящих синтаксических анализаторов до наиболее актуальных, хотя и не шибко новых, LALR-парсеров. Тем, кто не читал первую статью (ссылки — снизу), советую прочесть хотя бы первую половину последнего раздела. О том небольшом фрагменте кода я буду упоминать несколько раз.

В комментариях к прошлой статье несколько человек интересовались моими мотивами в написании своего компилятора компиляторов. К сожалению, они в этой статье не найдут ответов на этот вопрос. Не скрою, изначально я планировал написать статью без особой теории, но с оправданием задач и целей, ради которых я начал писать генератор, да и хотел поделиться нюансами и особенностями реализации. То есть по объему это довольно прилично: несколько экранов. Но затем я решил всё же описать базовую теорию популистским языком, поэтому статья разрослась до трех частей. Таким образом, дабы не ломать логику изложения, я сначала расскажу про LR/SLR/LALR-анализаторы, а завтра опубликую заключительную, и, думаю, самую интересную часть.
Читать полностью »

в 15:27, , рубрики: c++, lalr, Алгоритмы, Компиляторы, парсеры, синтаксический анализ, метки: , , ,

Введение, или зачем нужны синтаксические анализаторы

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

Эта часть посвящена базису, общей теории computer science. Возможно, что это даже преподаётся в школах/вузах России. Самая мякота пойдет со второй части.

Итак, зачем же кому-то может понадобиться писать парсер и что вообще это такое? Парсер — это код, который наделяет входящий набор символов семантическим смыслом. То есть, происходит анализ этих символов, и на основе этого анализа программа понимает как интерпретировать эти буквы и цифры. Простой пример — «1+2», после или во время процесса парсинга знак "+" это не просто символ плюса, но обозначение бинарноого оператора сложения, а в "+3" это унарный оператор знака числа. Большинству людей это очевидно, машине — нет.

Парсеры используются всюду — в Word'e для анализа приложений, словоформ, формул, etc; практически на любом сайте при валидации входных данных: email'а, телефонного номера, номера кредитки; конфигурационные файлы; сериализованные данные (например, в xml); во многих играх — скриптовые ролики, скрипты ИИ, консоль. В общем, это неотъемлемая часть computer science.

Читать полностью »

в 18:57, , рубрики: алгоритм, грамматика, синтаксический анализ, метки: , ,

Однажды, сидя на кухне со своим ноутбуком, я думал: что бы такое написать. В голову ничего не шло, и я вспомнил свою поделку — синонимайзер. Он был всем хорош — использовал морфологию, умел склонять и спрягать, работал с n-граммами. Но не было в нем одной интересной фичи — перефразирования текста, позволяющего, к примеру, фразу “корова паслась на лугу” переделать в “пятнистая буренка жевала сочную траву на зеленом лугу”. Конечно же, подобного рода преобразования требуют очень большую базу связей между словами и выражениями, отсутствие которой и свело на нет всю работу. Но это уже другая история. Сейчас же я расскажу о том, как решал вопросЧитать полностью »

12
Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js