Я нашел этот ответ на вопрос о 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 (). Хуже того, программист не может сказать, в каком контексте он будет вызываться, читая его.
В целом, добавление действий в ваш анализатор ввода работает для очень простых переводов, где:
- порядок вывода конструкций совпадает с порядком ввода
- все конструкции могут быть сгенерированы из информации, проанализированной до того момента, когда вам нужно их выплюнуть
Помимо этого вам понадобится промежуточная форма - AST обычно является лучшей формой. Использование грамматики для описания структуры AST аналогично использованию грамматики для разбора входного текста. Формализованные описания в предметно-ориентированном языке высокого уровня, таком как ANTLR, лучше, чем парсеры, написанные вручную. Действия внутри древовидной грамматики имеют очень четкий контекст и могут легко получить доступ к информации, переданной из вызова ссылок. Переводы, которые манипулируют деревом для многопроходных переводов, также намного проще, используя древовидную грамматику.