Что такое парсер дерева в ANTLR и обязан ли я его написать?

StackOverflow https://stackoverflow.com/questions/697755

Вопрос

Я пишу лексер/парсер для небольшого подмножества C в ANTLR, который будет запускаться в среде Java.Я новичок в мире языковых грамматик, и во многих учебниках ANTLR создается AST — абстрактное синтаксическое дерево. Должен ли я его создать и почему?

Это было полезно?

Решение 2

я нашел этот ответ на вопрос о jGuru, написанный Теренсом Парром, создателем ANTLR.Я скопировал это объяснение со связанного сайта здесь:

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

Представьте себе простую задачу перевода: вы хотите распечатать HTML-страницу с заголовком «Есть n элементов», где n — количество идентификаторов, найденных во входном потоке.Идентификаторы должны быть напечатаны после заголовка следующим образом:

<html>
<head>
<title>There are 3 items</title>
</head>
<body>
<ol>
<li>Dog</li>
<li>Cat</li>
<li>Velociraptor</li>
</body>
</html>

из ввода

Dog
Cat
Velociraptor

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

Хорошо, теперь вы знаете, что дерево подходит для чего угодно, кроме простых переводов.Учитывая AST, как получить от него выходные данные?Представьте себе простые деревья выражений.Один из способов — создать узлы в конкретных классах дерева, таких как PlusNode, IntegerNode и т. д.Затем вы просто просите каждый узел распечатать себя.Для ввода 3+4 у вас будет дерево:

+ | 3 -- 4

и занятия

class PlusNode extends CommonAST {
  public String toString() {
    AST left = getFirstChild();
    AST right = left.getNextSibling();
    return left + " + " + right;
  }
}

class IntNode extends CommonAST {
  public String toString() {
    return getText();
  }
}

Учитывая дерево выражений, вы можете преобразовать его обратно в текст с помощью t.toString().ТАК, что в этом плохого?Кажется, отлично работает, да?Кажется, в данном случае это работает хорошо, потому что это просто, но я утверждаю, что даже в этом простом примере древовидные грамматики более читабельны и представляют собой формализованные описания именно того, что вы закодировали в PlusNode.toString().

expr returns [String r]
{
    String left=null, right=null;
}

: #("+" left=expr right=expr) {r=left + " + " + right;}
| i:INT                       {r=i.getText();}
;

Обратите внимание, что подход к конкретному классу («гетерогенный AST») фактически кодирует полный анализатор рекурсивного спуска для #(+ INT INT) вручную в toString().Ребята, занимающиеся генераторами синтаксических анализаторов, это должно заставить вас съежиться.;)

Основной слабостью гетерогенного подхода AST является невозможность удобного доступа к контекстной информации.В анализаторе с рекурсивным спуском контекст легко доступен, поскольку его можно передать в качестве параметра.Вы также точно знаете, какое правило может вызывать какое другое правило (например, является ли это выражение условием WHILE или условием IF?), просматривая грамматику.Вышеупомянутый класс PlusNode существует в обособленном, изолированном мире, где он понятия не имеет, кто будет вызывать его метод toString().Хуже того, программист не может сказать, в каком контексте он будет вызван при чтении.

Таким образом, добавление действий в ваш анализатор входных данных работает для очень простых переводов, где:

  1. порядок выходных конструкций такой же, как порядок ввода
  2. все конструкции могут быть сгенерированы из информации, проанализированной до момента, когда вам нужно будет их выплюнуть

Помимо этого, вам понадобится промежуточная форма — обычно лучшей формой является AST.Использование грамматики для описания структуры AST аналогично использованию грамматики для анализа входного текста.Формализованные описания на предметно-ориентированном языке высокого уровня, таком как ANTLR, лучше, чем парсеры, написанные вручную.Действия в древовидной грамматике имеют очень четкий контекст и могут удобно получать доступ к информации, передаваемой при вызове правил.Переводы, которые манипулируют деревом для многопроходных переводов, также намного проще с использованием древовидной грамматики.

Другие советы

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

По сути, с ANTLR при анализе источника у вас есть несколько вариантов.Вы можете сгенерировать код или AST, используя правила перезаписи в своей грамматике.Ан АСТ по сути, это представление вашего источника в памяти.Отсюда вы можете многое сделать.

В ANTLR есть многое.Если вы еще этого не сделали, я бы порекомендовал получить книга.

Я думаю, что создание АСТ является необязательным.А Абстрактное синтаксическое дерево полезен для последующей обработки, такой как семантический анализ анализируемой программы.

Только вы можете решить, нужно ли вам его создавать.Если ваша единственная цель — синтаксическая проверка, вам не нужно ее создавать.В javacc (аналогично ANTLR) есть полезность называется JJДерево это позволяет генерировать AST.Я полагаю, что в ANTLR это тоже необязательно.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top