Рубрика «парсеры» - 2

в 17:21, , рубрики: javascript, грамматика, парсеры, синтаксический разбор

Дуглас Крокфорд

2007-02-21

Введение

В 1973 году на первом ежегодном симпозиуме «Принципы языков программирования» (Principles of Programming Languages Symposium) Вон Пратт представил статью «Нисходящий парсер с операторным предшествованием» (Top Down Operator Precedence). В этой статье Пратт описал метод синтаксического разбора, который объединяет лучшие стороны рекурсивного спуска и метода операторного предшествования Флойда. Метод Пратта очень похож на рекурсивный спуск, но требует меньше кода и работает гораздо быстрее. Пратт заявил, что его метод прост в освоении, реализации и использовании, необычайно эффективен и очень гибок. Благодаря своей динамичности он может использоваться для расширяемых языков.

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

Есть и другое объяснение: этот метод наиболее эффективен для динамических, функциональных языков программирования и использовать его в статическом, процедурном языке куда сложнее. Свою статью Пратт иллюстрирует на примере Lisp и играючи строит синтаксические деревья по потоку лексем. Но методы синтаксического разбора не особо ценятся в сообществе Lisp-программистов, которые проповедуют спартанский отказ от синтаксиса. С момента создания Lisp предпринималось немало попыток придать этому языку богатый синтаксис в стиле ALGOL: CGOL Пратта, Lisp-2, MLISP, Dylan, Interlisp's Clisp, оригинальные М-выражения Маккарти и так далее. Но все они провалились. Для Lisp-сообщества согласованность программ и данных оказалась важнее выразительного синтаксиса. С другой стороны, подавляющее большинство программистов любит синтаксис, поэтому сам Lisp так и не стал популярен. Методу Пратта нужен динамический язык, но сообщество динамических языков исторически не пользовалось синтаксисом, который так удобно реализуется методом Пратта.
Читать полностью »

в 11:20, , рубрики: beautiful soup, lxml, nimbus, python, Блог компании FVD Media, Веб-разработка, парсеры, разработка, метки: , , , , , ,

Одна из ключевых возможностей Nimbus Note — это сохранение и/или редактирование заметок в виде html-документа. И заметки эти создаются/редактируются в браузере или на мобильных устройствах. После чего — отправляются на сервер. А как подсказывает профессиональная паранойя — информации пришедшей от пользователя доверять нельзя. Т.к. там может быть всё что угодно: XSS, документ, превращающий вёрстку в мечту абстракциониста или вообще ни разу не текст. Следовательно, данные пришедшие от пользователя нуждаются в предварительной обработке. В этой статье я опишу некоторые особенности нашего решения данной проблемы.

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

в 6:29, , рубрики: python, интерпретатор, парсеры, Питон, с нуля

Простой интерпретатор с нуля на Python #4

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

Содержание

Простой интерпретатор с нуля на Python #1
Простой интерпретатор с нуля на Python #2
Простой интерпретатор с нуля на Python #3
Простой интерпретатор с нуля на Python #4

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

в 10:36, , рубрики: python, интерпретатор, парсеры, Питон, с нуля

Простой интерпретатор с нуля на Python #2

Содержание

Простой интерпретатор с нуля на Python #1
Простой интерпретатор с нуля на Python #2
Простой интерпретатор с нуля на Python #3
Простой интерпретатор с нуля на Python #4

В предыдущей статье мы рассматривали сам язык IMP и основную структуру интерпретатора. Также, мы тщательно рассмотрели лексер. В этой статье мы будем писать небольшой парсер для нашего языка. Он будет извлекать AST (abstract syntax tree) из списка токенов, сгенерированных лексером. Библиотека комбинатора будет независимая, то есть с помощью нее можно будет написать парсер для любого языка.

Что такое комбинаторы парсеров?

Есть очень много способов написать парсер. Самым простым и быстрым способом сделать это являются комбинаторы.

Вы можете считать парсер функцией, которая принимает поток токенов. Если успешно, то парсер будет «съедать» немного токенов из потока. Функция вернет часть финального AST вместе с остальными токенами. Комбинатор — это функция, которая производит парсер, как его результат, обычно после приема одного или нескольких анализаторов (парсеров) в качестве входных данных, отсюда и название — «комбинатор». Вы можете использовать комбинаторы для создания законченного парсера для языка, как IMP, путем создания множества маленьких парсеров для каждой части языка.
Читать полностью »

в 15:48, , рубрики: .net, Компиляторы, ненормальное программирование, парсеры, самопал, фатальный недостаток, метки: , , , ,

В прошлом топике я рассказывал о том, как мы с другом решили ради развлечения написать свой встраиваемый язык программирования для платформы .NET. У первой версии был серьезный недостаток — парсер был реализован на F# с помощью сторонней библиотеки. Из-за этого требовалась куча зависимостей, парсер работал медленно, а поддержка его была крайне муторным занятием.

Очевидно, что парсер нужно было переписать на C#, но при мысли о написании парсера с нуля вдруг находилась дюжина других срочных дел. Таким образом таск перекидывался и откладывался практически полгода и казался непосильным, а в итоге был сделан за 4 дня. Под катом я расскажу об удобном способе, позволившим реализовать парсер достаточно сложной грамматики без использования сторонних библиотек и не тронуться умом, а также о том, как это позволило улучшить язык LENS.

Но обо всем по порядку.
Читать полностью »

в 4:14, , рубрики: functional programming, javascript, parser, peg, парсеры, функциональное программирование, метки: , , , , ,

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

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

Как и раньше, в посте будет множество гиперссылок и кода. А ещё больше — кириллических букв.

Всё как в старые добрые времена. Добро пожаловать, друг.

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

в 9:31, , рубрики: api, freebase, Linked data, owl, rdf, semantic web, sparql, онтологии, открытые данные, парсеры, парсинг контента, Семантическая Сеть, метки: , , , , , , , , , ,

Одной из причин причина слабого использования Linked Data-баз знаний в обычных, ненаучных приложениях является то, что мы не привыкли придумывать юзкейсы, видя перед собой только данные. Трудно спорить с тем, что сейчас в России производится крайне мало взаимосвязанных данных. Однако это не значит, что разработчик, создающий приложение для русскоязычной аудитории совсем уж отрезан от мира семантического веба: кое-что всё-таки у нас есть.
image
Основными источниками данных для нас являются международные базы знаний, включающие русскоязычный контент: DBpedia, Freebase и Wikidata. В первую очередь это справочные, лингвистические и энциклопедические данные. Каждый раз когда вам в голову приходит мысль распарсить кусочек википедии или викисловаря — ущипните себя как следует и вспомните о том, что всё, что хранится в категориях, инфобоксах или таблицах, уже распарсено и доступно через API с помощью SPARQL или MQL-интерфейса.

Я попробую привести несколько примеров полезных энциклопедических данных, которые вы не найдете нигде, кроме Linked Data.

Эта статья — первая из цикла Базы знаний. Следите за обновлениями.

  • Часть 1 — Введение
  • Часть 2 — Freebase: делаем запросы к Google Knowledge Graph
  • Часть 3 — Dbpedia — ядро мира Linked Data
  • Часть 4 — Wikidata — семантическая википедия

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

в 7:26, , рубрики: ABBYY, Блог компании ABBYY, диалог, искусственный интеллект, искуственный интеллект, Компьютерная лингвистика, парсеры, метки: , , , ,

image30 мая – 3 июня в подмосковном пансионате «Бекасово» пройдет крупнейшая российская конференция по компьютерной лингвистике «Диалог». Подробно о том, что такое «Диалог» и почему ABBYY организует эту конференцию, мы подробно писали здесь.

В этом году главными темами станут:

Оценка тональности текста (sentiment analysis). Для решения этой проблемы (как понять отношение автора к тому, что он описывает) используются как методы, основанные на лингвистических правилах, так и методы компьютерного обучения на больших тестовых коллекциях документов (в которых эксперты вручную расставили оценки тональности, а компьютер пытается разобраться, какие именно свойста тестового текста связаны с оценкой, чтобы на их основе оценивать новые тексты). Думаю, многие сталкивались с «правильными» оценками тональности статей в российских системах мониторинга СМИ (не будем называть имён), так что тема очень актуальная. Читать полностью »

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

Введение

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

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

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

Предисловие

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

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

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