Обобщенный анализ потока?

Question

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

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

Вы можете использовать шаблон, как это для синтаксического анализа вызовов функций (с использованием синтаксиса C-стиль):

(pattern (:var (:class ident)) (:class left-paren) (:optional (:var object)) (:star (:class comma) (:var :object)) (:class right-paren))

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

Возможно, что-то подобное будет полезно?

Answer 1

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

Smalltalk - примечательное исключение, отправка с богатой иерархией классов Stream, которая в сочетании с классами Collection позволяет вам делать некоторые впечатляющие материалы. В то время как большинство Smalltalks также поставляются с поддержкой регулярных выражений (чистая реализация ST Vassili Bykov - популярный выбор), классы regex, к сожалению, не интегрированы с классами Stream так же, как классы Collection. Это означает, что использование потоков и регулярных выражений в Smalltalk обычно включает чтение строк символов из потока, а затем тестирование этих строк отдельно с помощью шаблонов регулярных выражений - не сортировка «чтение следующих n символов до совпадения шаблона» или «чтение следующих n символов, совпадающих этот шаблон "типа функционально вы, вероятно, имеете в виду.

Я думаю, что мощный поток API в сочетании с мощной поддержкой регулярных выражений будет отличным. Тем не менее, я думаю, что у вас возникнут проблемы с обобщением различных типов потоков. Поток чтения на символьной строке будет представлять собой несколько трудностей, но потоки файлов и TCP будут иметь свои собственные исключения и задержки, которые вам придется обрабатывать грациозно.

Answer 2

Посмотрите на scala.util.regexp, как документацию по API, так и пример кода на http://scala.sygneca.com/code/automata. Я думаю, что позволить вычислительному лингвисту сопоставлять строки слов, например, искать часть речевых образов.

Answer 3

Это принцип большинства синтаксических парсеров, которые работают в два этапа. Первая фаза - это лексер, где идентификаторы, языковые ключевые слова и другие специальные символы (арифметические операторы, фигурные скобки и т. Д.) Идентифицируются и разбиваются на объекты токена, которые обычно имеют числовое поле, указывающее тип лексемы, и необязательно другое поле, указывающее текст лексемы.

Во второй фазе синтаксический синтаксический анализатор работает с объектами Token, сопоставляя их только магическим числом, для разбора фраз. (Программное обеспечение для этого включает в себя Antlr, yacc/bison, Scala's cala.util.parsing.combinator.syntactical library и множество других). Эти две фазы не должны полностью зависеть друг от друга - вы можете получить свои объекты Token из любого места, что вам нравится. Магический номер числа кажется важным, однако, потому что магические числа присваиваются константам, и именно они позволяют выразить грамматику на читаемом языке.

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