Являются ли синтаксические выделения языков программирования с использованием регулярных выражений?

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

Теперь, недавно, было объявлено Rainbow.js синтаксис highlighter. Его посылка описана как очень простая:

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

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

Теперь возникает вопрос: есть ли что-то, что мне не хватает? В частности:

Возможно ли подсветка синтаксиса с регулярными выражениями?
Является ли это экземпляром применяемого правила 80/20, где достаточно, чтобы регулярные выражения могли быть полезными?

Ответ 1

Выделение синтаксиса с использованием regexp - это старое искусство. Я думаю, что даже Emacs и vi начали этот путь.

Я понял, что подсветка синтаксиса - это, по сути, задача с той же сложностью, что и разбор языка, [...]

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

Несколько иной подход к этому: анализ языка часто представляет собой двухэтапный процесс: лексирование (разделение потока байтов на поток "токенов" ) и реальный синтаксический анализ (приведение потока токенов в некоторую сложную структуру - часто Абстрактное синтаксическое дерево). Лексинг обычно делается с использованием ---- регулярных выражений. Для этого см. Документы flex. И что в основном все базовые синтаксические маркеры должны понимать.

Конечно, есть угловые случаи, которые не могут поймать regexp. Типичный пример:

foo(bla, bar);

Здесь foo может быть вызовом статического метода или метода экземпляра или макроса или чего-то еще. Но ваш маркер регулярного выражения не может этого вывести. Он может добавлять только цвета для "общего вызова".

Итак: Это правило 100/0, если ваши требования являются низкоуровневыми (то есть без приведенного выше примера) и обычно правило 90/10 для вещей реального мира.

Ответ 2

Вы можете сделать подсветку синтаксиса, используя регулярные выражения как часть решения. Более конкретно, как часть "лексера", который разбивает входной текст на символы. Это на самом деле способ работы большинства компиляторов/интерпретаторов.

Чтобы сделать это, используя регулярное выражение , тем не менее, задает проблемы. Рассмотрим случай соответствия строки в Python. Python позволяет ограничивать строки с помощью одиночных кавычек ' или двойных кавычек ". Кроме того, он позволяет многострочные строки ( "синтаксис heredoc" ) с использованием тройных кавычек, ''' или """.

Итак, какие части следующих строк являются строками, а какие нет? Можете ли вы построить регулярное выражение, которое правильно идентифицирует строковые литералы str1 - str6?

str1 = "hello, world!"

str2 = 'hello, world!'

str3 = "The canonical test program is 'Hello World'."

str4 = '"Why," Peter said, "That\ ludicrous. Who would do that?"'

str5 = """The heredoc syntax is handy for cases where you don't want to escape strings. "Very convenient."
"""

str6 = """Code sample:
s1 = "hi!"
s2 = 'Hi!'
S3 = '''
- apples
- oranges
- bananas
'''
"""

Аргумент, что "вы не можете (анализировать HTML-процессы) с помощью регулярного выражения, потому что (языки программирования HTML) имеют вложенные структуры - они не являются регулярными" - это не совсем так - современные регулярные выражения (особенно в Perl ) имеют более выразительную силу, чем строго регулярные выражения в смысле компьютерной науки. Но только потому, что вы можете использовать регулярные выражения, это не значит, что вы должны.

Изменить: проблема совпадения строк выше не так уж плоха, если ваш аромат регулярного выражения поддерживает обратные ссылки в шаблоне поиска. Возможно, будет многострочное регулярное выражение, подобное ('|"|'''|""").+?\1.

Изменить 2: пример угловых случаев в синтаксисе hilighting, смотрите не дальше, чем синтаксис StackOverflow для кода выше.

Ответ 3

В принципе, нет.

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

Regex не режет горчицу для такой задачи.

Ответ 4

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

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

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

Например, у меня есть язык, на котором есть по существу два набора ключевых слов (из-за того, что происходит встраивание языка домена). Правила подсветки синтаксиса Vim, которые я написал, правильно распознают контекст и раскрашивают ключевые слова по-разному. Обратите внимание, что между этими наборами ключевых слов существует некоторое совпадение: одно и то же слово, другое значение в другом контексте.

Пример этого см.: http://www.kylheku.com/cgit/txr/tree/genman.txr. Если вы ищете синтаксис (do, вы обнаружите, что один экземпляр окрашен в фиолетовый цвет, а другой зеленый. Они разные: один - на языке извлечения текста, а другой - во встроенный диалект Lisp. Выделение синтаксиса Vim достаточно мощно, чтобы обрабатывать смесь языков с разными наборами ключевых слов. (Да, хотя это выполняется через Интернет, на самом деле процесс Vim выполняет подсветку синтаксиса.)

Или рассмотрите что-то вроде оболочки, где у вас может быть синтаксис типа строкового литерала, например "foo bar", но внутри там вы можете иметь подстановку команд, внутри которой вы должны рекурсивно распознавать и раскрашивать синтаксис оболочки: "foo $(for x in *; do ...; done) bar".

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