Всем привет!
У меня такая задача: нужно написать парсер для текстового редактора, для подсветки синтаксиса, построения свёрток по функциям/классам/циклам в функциях и тому подобного, а также для парсинга по запросу, например, для определения ближайшего блока begin/end, в котором курсор стоит, чтобы парные конструкции подсвечивать.
Вот, и нужно, чтобы парсер мог быть инкрементальный, то есть, сохранял состояние своё через определённые промежутки в тексте, чтобы парсить постепенно, только то, что должно быть на экране, то есть, допарсивать вниз по запросу...
Ну и, главное, хардкодить парсеры не хочется, а хочется, чтобы юзер их мог сам делать для своего языка, или готовый донастраивать.
Хочется конфигурировать парсер некой формальной грамматикой вроде BNF, с которой парсер мог бы:
1. Восстанавливаться после мелких ошибок в тексте
2. Не запоминать последовательность терминальных токенов, выданных лексером, то есть, не возвращаться назад
3. Парсить по рекурсивным правилам, вроде приведённых ниже правил для паскалевского юнита, но иметь возможность как-то парсить по вложенным правилам, если корневое правило обломалось (например, в случае неправильного заголовка паскалевского юнита).
У меня сейчас сделан лексер на регекспах, он выдаёт терминальные токены, сохраняет состояние своё, можно блоки определять, в которых подсхемы будут (ну там подсхема для комментариев, строк, и т.п.), инкрементальность есть, работает достаточно быстро... То есть, с этим всё прекрасно. Примерно как в фаромском парсере сделано — схемы, в них правила на регекспах, правила порождают токены, токены расцвечиваются. Есть ещё правила для подсхем — описывается начало и конец подсхемы, тоже регекспами, и внутри там всё то же...
Но лексер не может структуру текста анализировать, само собой.
Ну и вот, возникает мысль использовать токены, которые он выдаёт, так я пока сделал так: сделал немножко специальный синтаксис в регексповом движке, и могу строить регекспы из этих токенов, и правила из них. Ну и запоминаю цепочку токенов, выданных лексером, и держу её, пока какое-нибудь правило не совпадёт. И по этим правилам выдаю свёртки в дерево.
Но тут как-то получатся плохо, и вот почему:
1. В регекспах бывают возвраты назад, поэтому приходится в каждом сохраняемом состоянии парсера держать цепочку токенов, выданных лексером, либо вообще всю чепочку токенов держать, до последнего сохранённого состояния парсера. Память жрётся...
Ну, тут можно либо регексповый движок переделать, чтобы он был ДКА, у ДКА вроде возвратов не бывает, но это не самое главное..
2. Непонятна сама идея описания грамматики для такого парсера. Тут ведь, в редакторе, текст обычно с ошибками... Полностью без ошибок он перед компиляцией может быть, а пока он редактируется, он формальному описанию языка, на BNF, например, обычно не соответствует.
Вот BNF — он ведь рекурсивный, и вся грамматика может выводиться из одного правила, например, для чего-то вроде Паскаля:
<UnitInterface> ::=
unit <Identifier>";"
<InterfaceSection>
<ImplementationSection>
<InterfaceDecl> ::=
<ConstSection> |
<TypeSection>
....
Ну и вот, предположим, я после "uses" написал что-то, не соответствующее грамматике, например, "BEBEBE!!!", а потом у меня идут типы, функции, и всё такое прочее.
Если у меня обычный парсер — для компилятора или интерпретатора, то он выдаст на этом месте ошибку, и остановится — текст не соответствует правилу <UnitInterface>...
Для редактора же это будет означать, что свёртки и всё прочее, построенное по этой грамматике, будут существовать лишь в абсолютно правильном тексте, а это никуда не годится.
Нужно как-то оптимистичнее парсить, и как-то проскакивать места, не соответствующие грамматике (я ведь и не всегда хочу полную грамматику языка описывать — если я хочу только свёртки делать для функций, то типы, классы, и грамматику внутри функций мне описывать не хочется...)
Пока единственное, что приходит на ум — это добавить в BNF правило-"точку" из регекспов, которое будет проверяться после всех правил, и будет означать любой токен, или просто проскакивать токен, на котором обломались все возможные правила, и пробовать следующий?
Есть ли какие-то методы для формального описания таких "нестрогих" грамматик?
И вот ещё — тот же BNF — он рекурсивный. Это значит, что правило срабатывает, когда все его под-правила срабатывают, то есть, я не могу размечать текст, пока не пройду его полностью..
И вот, если вместо слова "unit" в начале паскалевского юнита я напишу "medved", то весь юнит, в остальном правильный, размечен не будет, потому что корневое правило сразу обломается. С другой стороны, если я в начале явовского класса вместо "class" напишу "clazz", пущай его содержимого я и не получу, и найду только следующий класс, правильный, не жалко...
Как бы с этим справиться?
Пока придумывается только прописывание рядом с корневым правилом ещё и некоторых возможных его мелких под-правил, чтобы, если заголовок юнита будет неправильным, функции и типы всё же находились...
Здравствуйте, eaglus, Вы писали:
E>Всем привет! E>У меня такая задача: нужно написать парсер для текстового редактора, для подсветки синтаксиса, построения свёрток по функциям/классам/циклам в функциях и тому подобного, а также для парсинга по запросу, например, для определения ближайшего блока begin/end, в котором курсор стоит, чтобы парные конструкции подсвечивать...
Тебе можно использовать обычный парсер, но каждый раз при свертке по некоторому правилу можно размечать текст в соответствии с данным правилом. Для этого в грамматике надо сделать один начальный нетерминал, который содержит дочерними все те локальные конструкции, что тебе надо распознавать. Что-то типа
S --> Class_Def | Unit_def | Func_def ...
Каждый раз напускай свой парсер на локальный кусок текста и смотри по какой конструкции будет произведена свертка. Если не хочешь ждать конца конструкции, то надо переделать правило для нее самой. Это же надо сделать и для конструкций с ошибками. Например, для обработки конструкции, где вместо начального "unit" стоит какая-то фигня, надо ввести правило такого вида
Unit_def --> ("фигня" | unit) "остальная часть конструкции"
"фигня" -- это такой специальный токен конечно.
Также можно ввести правила для кусков определений типа
Class_Def_без_скобки --> class { class_internal
Class_Def_без_точки_с_запятой --> class { class_internal }
Class_Def --> class { class_internal };
Все зависит от того, как ты сам захочешь показывать неполные конструкции и в каких случаях. Идея держать состояние парсера мне не нравится, лучше запоминать последовательность токенов и по запросу их распарсивать. Наверняка ты там текст в токенах держишь? Если нет, то это удивительно, т.к. из по любому парсить приходится. Видимая часть текста в токенах распарсивается по требованию, выделяются конструкции и форматируются. Допустимые ошибки заложены в грамматике.
eaglus wrote: > > Есть ли какие-то методы для формального описания таких "нестрогих" > грамматик?
Насчет организации грамматики уже написали — вам не нужно отслеживать
всю структуру языка, то есть все правила будут выскокоуровневыми. Кроме
того, есть два предложения:
1) Использовать отсечки как в прологе. Отсечка обозначает точку к
которой проиваодится возврат. Например в правиле:
S = 'unit' ! identifier ';'
парсер, встретив во входном потоке слово 'unit' не возвращается назад —
правило считается выполненным.
2) Использовать правила синхронизации или разбиения на выражения при
возникновении ошибки, как в yacc. Например, предыдущее выражение
запишется так:
S = 'unit' ! ( identifier ';' | error ';' )
Здесь запись error ';' обозначает, что при возникновении ошибки, правило
считается выполненым, ошибка игнорируется ее и входной поток читается до
символа точки с запятой. Конечно, в качестве синхронизирующей
последовательности можно использовать регулярное выражение.
Так же можно применять одно правило синхронизации ко нескольким
выражениям, и совместить это с отсечками. Что-то наподобие:
S = 'procedure' {{ identifier arg-decl }} ';'
S = 'function' {{ identifier arg-decl }} ';'
S = 'class' {{ identifier '{' }} '}.*;'
Здесь лексема {{ показывает начало отсечки, а то, что следует за }} —
правило синхронизации.
