Ваш словарный запас немного странный. Большинство парсеров предназначены для распознавания синтаксиса языка. обычно определение языка определяет некоторое понятие терминалов и явно исключает «пробелы», состоящие из неинтересных последовательностей текста между текстом терминалов, часто включая пробелы, табуляции и различные виды независимых комментариев. Таким образом, слово «терминал», используемое при синтаксическом анализе, обычно означает «те языковые атомы, которые не являются пробелами». Вы неявно определили его для включения пробелов, и я думаю, что это вызывает ваше огорчение.
С этой точки зрения, самый простой способ избежать загромождения определения грамматики, используемого вашим синтаксическим анализатором, с пробелами, состоит в том, чтобы просто заставить лексер не передавать синтаксическому анализатору пробелы. Тогда вашей грамматике не нужно указывать, как они обрабатываются (и да, грамматики, которые это делают, действительно беспорядочны), синтаксическому анализатору не нужно беспокоиться о них, и они не отображаются в дереве.
Если вы создаете компилятор или интерпретатор, то проще всего игнорировать пробелы.
Если вы создаете анализатор реинжиниринга (см. наш инструментарий реинжиниринга программного обеспечения DMS, тогда важен захват комментариев (по крайней мере) в AST, так как в конечном итоге требуется регенерировать текст из построенных AST, и полезно, если восстановленный текст также содержит комментарии.[Вы можете сделать это другими способами, но это не так. как легко].
Лексер DMS создает «микро» токены, которые являются вашей концепцией языковых токенов, пробелов и комментариев внутри. Он отбрасывает микротокены пробелов, потому что они просто ничего не добавляют (см. обсуждение выше). Как и следовало ожидать, он передает парсеру обычные токены. Он приклеивает токены комментариев к предыдущему или последующему языковому токену, в зависимости от типа токена и места встречи; для C, /* ... */ видно до того, как к нему присоединена лексема, и // ... комментарий, прикрепленный к предшествующей лексеме (с некоторыми более тонкими деталями, которые здесь не обсуждаются). Тогда синтаксический анализ по-прежнему видит только языковые токены, так что грамматика не усложняется без нужды, и если вся информация, связанная с токеном, помещается в дерево, комментарии идут своим чередом.
Теперь людям часто нужны «абстрактные» синтаксические деревья; они хотят исключить такие вещи, как "(" и ")". Схема, которую я описал выше, прикрепляла комментарии даже к конкретным токенам, подобным этим. Теперь есть сложность: если вы оставите маркеры ( .. ) вне дерева, вложенные комментарии исчезнут. Упс. Таким образом, синтаксические анализаторы DMS делают сложную вещь: комментарии, прикрепленные к токенам, которые имеют логическое место в дереве, но на самом деле их там нет («устраненные терминалы»), переносятся на узел родительского дерева с аннотацией о том, что они принадлежат отсутствующему дочернему токену. Да, реализация этого действительно PITA. Хорошей новостью является то, что нам пришлось сделать это только один раз в общем механизме синтаксического анализа DMS, и это работает для многих, многих языков. Но это означает, что вы должны быть готовы создать необычный («реинжиниринговый») синтаксический анализатор, и у нас была для этого коммерческая мотивация.
РЕДАКТИРОВАТЬ: неясно, почему ОП хочет этого, но он настаивает на захвате пробелов в дереве. Поскольку он не сказал нам, почему, я собираюсь предположить: ему нужна точная информация о столбцах для токенов/узлов дерева. Это несложно сделать: научите лексер отслеживать положение (строка/столбец) и отмечать каждый токен (микротокены, такие как комментарии, тоже) начальной/конечной позицией, и пусть синтаксический анализ сохраняет эту информацию в дерево. Этот способ также позволяет избежать пробелов в дереве. (DMS также делает это, потому что при сообщении о проблемах полезна точная информация, а при повторной генерации кода часто желательно возвращать код в исходное положение (по крайней мере, в тот же столбец).
EDIT2: если OP настаивает на захвате пробелов, он может рассмотреть возможность изучения анализа GLR без сканера. Это сохраняет каждый символ во входном потоке, включая пробелы.
person
Ira Baxter
schedule
07.08.2011