Роль синтаксического анализатора заключается в том, чтобы превратить текст в абстрактное синтаксическое дерево с минимальными трудностями. В предыдущем эпизоде ANTLR 4 нас полностью подвел, поскольку он просто генерирует конкретное синтаксическое дерево.
Поэтому нам нужно что-то с этим делать, и вот несколько различных паттернов проектирования, которые можно использовать для получения абстрактного синтаксического дерева или, по крайней мере, лучшего конкретного синтаксического дерева.
Насколько я знаю, ничего подобного нигде не задокументировано, поскольку документация по ANTLR 4 до боли похожа только на Java, а многие методы, которые я буду использовать, специфичны для Python и даже не будут работать в Java.
Абстрактные и конкретные синтаксические деревья
Итак, что такое различные типы синтаксических деревьев, и почему это имеет значение?
Возьмем очень простой язык для разбора только математических выражений, и наша программа будет 2 + 3 * 4.
Вот возможное абстрактное синтаксическое дерево для этого (игнорируя пространства имен для этих классов, отладочную информацию, такую как номера строк и т.д.):
Add(
Number(2),
Multiply(
Number(3),
Number(4)
)
)
Если мы приходим к такому дереву, то часть синтаксического анализа завершена, и мы можем двигаться дальше по программе. Это дерево абстрактного синтаксиса — все несущественные детали удалены, осталась только осмысленная структура, и структура дерева соответствует логической структуре программы.
С другой стороны, Concrete Syntax Tree вместо этого возвращает дерево, которое очень точно повторяет структуру грамматики. Конкретное дерево синтаксиса для той же программы может выглядеть следующим образом:
Expr(
Expr(
Term(
Factor(
Number("2")
),
),
),
Operator("+"),
Term(
Term(
Factor(
Number("3")
)
),
Operator("*"),
Factor(
Number("4")
)
)
)
Это определенно не то, чего мы хотим! Почти каждый генератор синтаксического анализатора, включая старые версии ANTLR, генерирует результаты в стиле AST, потому что это всегда конечная цель, а CST — это промежуточное представление, созданное по пути, и большинство синтаксических анализаторов даже не утруждают себя его построением.
ANTLR 4 почему-то принял безумное решение не делать этого и предоставлять только CST, оставляя за нами право преобразовать его в AST. Это означает, что любая программа, использующая ANTLR 4, должна включать множество утомительных шаблонов для преобразования CST в AST. Или работать непосредственно с CST, что совершенно непрактично, за исключением некоторых игрушечных случаев.
Даже для этой простой программы CST уже был довольно плох, но чем сложнее грамматика, тем сложнее становится CST, даже для одного и того же AST. Если ваша таблица операторов имеет 15 уровней старшинства (как в C), это означает 15 дополнительных уровней бессмысленных тривиальных узлов в CST! Абсолютное безумие!
Аннотированная грамматика
Еще в ANTLR 1-3 способ получения AST заключался в том, чтобы поместить некоторые действия в саму грамматику. Обычно действие выполняло некоторую часть построения AST. Поскольку построение AST очень тесно связано с синтаксическим деревом, это обычно прекрасно работает.
В ANTLR 4 довольно сложно поместить действия в грамматику, но они предоставили несколько функций частичной замены, которые мы можем использовать, чтобы получить хотя бы лучший CST.
Итак, возьмем нашу Math.g4:
grammar Math;
expr : expr ('+' | '-') term
| term;
term : term ('*' | '/') factor
| factor;
factor : '(' expr ')'
| number
| identifier;
number: NUM;
identifier: ID;
ID : [a-zA-Z_] [a-zA-Z0-9_]* ;
NUM : '-'? [0-9]+ ( '.' [0-9]*)?;
WS : [ trn]+ -> skip; // ignore all whitespace
И добавьте несколько #-аннотаций к альтернативным ветвям, а также a=/b=-аннотации к частям совпадения, получив следующее:.
grammar Math;
expr : a=expr '+' b=term # Add
| a=expr '-' b=term # Sub
| a=term # TrivialExpr
;
term : a=term '*' b=factor # Mul
| a=term '/' b=factor # Div
| a=factor # TrivialTerm
;
factor : '(' a=expr ')' # TrivialParensExpr
| a=NUM # Number
| a=ID # Identifier
;
ID : [a-zA-Z_] [a-zA-Z0-9_]* ;
NUM : '-'? [0-9]+ ( '.' [0-9]*)?;
WS : [ trn]+ -> skip; // ignore all whitespace
Давайте посмотрим на получившийся CST и насколько он улучшился:
Sum(
TrivialExpr(
TrivialTerm(
Number("2")
),
),
Mul(
TrivialTerm(
Number("3")
),
Number("4")
)
)
Это не совсем AST, так как Number не знают, что они должны преобразовывать содержимое своих строк в float, и у нас есть несколько Trivial* узлов, но мы сделали несколько хороших шагов к нашей цели.
Давайте обновим как версию Listener, так и версию Visitor, чтобы использовать новые CST.
Обновленный Слушатель с улучшенным CST
#!/usr/bin/env python3
from antlr4 import *
from MathLexer import MathLexer
from MathParser import MathParser
from MathListener import MathListener
import sys
class MathProgram(MathListener):
def exitNumber(self, node):
value = float(node.getText())
self.stack.append(value)
def exitIdentifier(self, node):
value = self.getVar(node.getText())
self.stack.append(value)
def exitAdd(self, node):
b = self.stack.pop()
a = self.stack.pop()
self.stack.append(a + b)
def exitSub(self, node):
b = self.stack.pop()
a = self.stack.pop()
self.stack.append(a - b)
def exitMul(self, node):
b = self.stack.pop()
a = self.stack.pop()
self.stack.append(a * b)
def exitDiv(self, node):
b = self.stack.pop()
a = self.stack.pop()
self.stack.append(a / b)
def getVar(self, name):
if name not in self.vars:
self.vars[name] = float(input(f"Enter value for {name}: "))
return self.vars[name]
def run(self, node):
self.stack = []
self.vars = {}
ParseTreeWalker().walk(self, node)
result = self.stack[0]
print(result)
def parseFile(path):
lexer = MathLexer(FileStream(path))
stream = CommonTokenStream(lexer)
parser = MathParser(stream)
tree = parser.expr()
MathProgram().run(tree)
if __name__ == "__main__":
path = sys.argv[1]
parseFile(path)
Это больше кода, но он намного чище того, что мы имели раньше. Здесь нет грамматических проверок типа len(node.children) == 3 или node.children[1].getText() == "*". Мы знаем, какая ветвь совпала, а некоторые ветви, которые мы должны были проверять раньше (все Trivial), мы теперь можем игнорировать, поскольку их действие по умолчанию все равно ничего не делает.
Это не потребовало дополнительной работы со стороны кода Python, и мы даже не использовали аннотации a= и b= (они предназначены только для шаблона посетителя).
Один вопрос все еще остается — паттерн listener очень специфичен для того вида обработки, который мы хотим сделать. Для нашей математической программы мы могли бы обойтись простым использованием self.stack и обрабатывать вещи по порядку, но в общем случае это будет не так просто.
Обновленный Visitor с улучшенными CST
Для Visitor потребуется некоторое мета-программирование на Python. Нам нужно будет реализовать немного магический MathProgram.eval для выполнения маршрутизации в зависимости от типа каждого узла, а также для автоматического пропуска тривиальных узлов.
Но остальная часть MathProgram на самом деле очень хороша, и почти повторяет то, что должна делать AST-обработка MathProgram.
#!/usr/bin/env python3
from antlr4 import *
from MathLexer import MathLexer
from MathParser import MathParser
import sys
class MathProgram:
def __init__(self, program):
self.program = program
def evalAdd(self, node):
return self.eval(node.a) + self.eval(node.b)
def evalSub(self, node):
return self.eval(node.a) - self.eval(node.b)
def evalMul(self, node):
return self.eval(node.a) * self.eval(node.b)
def evalDiv(self, node):
return self.eval(node.a) / self.eval(node.b)
def evalNumber(self, node):
return float(node.getText())
def evalIdentifier(self, node):
return self.getVar(node.getText())
def getVar(self, name):
if name not in self.vars:
self.vars[name] = float(input(f"Enter value for {name}: "))
return self.vars[name]
def eval(self, node):
if not isinstance(node, ParserRuleContext):
raise Exception(f"{node} must be a node, not a {type(node)}")
name = "eval" + type(node).__name__[:-7]
if name[:11] == "evalTrivial":
return self.eval(node.a)
return self.__getattribute__(name)(node)
def run(self):
self.vars = {}
result = self.eval(self.program)
print(result)
def parseFile(path):
lexer = MathLexer(FileStream(path))
stream = CommonTokenStream(lexer)
parser = MathParser(stream)
tree = parser.expr()
MathProgram(tree).run()
if __name__ == "__main__":
path = sys.argv[1]
parseFile(path)
Хорошо, что здесь происходит:
- Раньше мы знали типы каждого подвыражения (например,
Term), поэтому мы могли вызватьevalTermизevalExpr. Но все это были глупые типы, и они нам не нужны. Теперь, когдаTermбыл разделен междуMul,DivиTrivialTerm,evalExprне может знать, каким будетnode.b. - и поэтому, чтобы вызвать нужный метод, мы используем метод
eval, который проверяет тип узла и вызывает то, что ему нужно - Если бы у нас был AST,
evalAdd,evalSub,evalMulиevalDivбыли бы такими же, как сейчас, огромная победа! - мы могли бы реализовать кучу методов типа
evalTrivialExpr(self, node): return self.eval(node.a), но я сделал методevalавтоматически обрабатывающим все эти методы — это автоматически решает самую большую разницу между нашим «улучшенным CST», который имеет эти дополнительные узлы, и настоящим «AST», который их не имеет.
Интересно, что в некоторых языках можно реализовать несколько методов с одним и тем же именем, и они будут отправляться по динамическому типу аргумента, так что мы можем реализовать def eval(self, node : DivContext) и т.д., и он выберет правильный. На самом деле это не так часто встречается — большинство языков не поддерживают это вообще, или поддерживают только статическую версию, и дело в том, что мы не знаем тип аргумента статически.
А в некоторых других языках мы можем легко добавить дополнительные методы к этим сгенерированным классам, что было бы еще одним способом сделать это более чисто. Это даже можно сделать в Python, но это немного муторно.
Есть способы сделать это с помощью менее агрессивного мета-программирования, например, с помощью кучи операторов ininstance или словаря с ключом по классу, но я думаю, что этот способ наиболее лаконичен.
Абстрактное дерево синтаксиса
Ну, а как насчет того, чтобы пойти дальше идеи лучшего конкретного синтаксического дерева, и просто построить совершенно новое AST. Это лучший способ, если вам нужно сделать много обработки. Вы можете оставить CST позади и работать просто с очень красивым AST.
Вот один из способов сделать это:
#!/usr/bin/env python3
from antlr4 import *
from MathLexer import MathLexer
from MathParser import MathParser
from collections import namedtuple
import sys
AddNode = namedtuple("AddNode", ["a", "b"])
SubNode = namedtuple("SubNode", ["a", "b"])
MulNode = namedtuple("MulNode", ["a", "b"])
DivNode = namedtuple("DivNode", ["a", "b"])
NumberNode = namedtuple("NumberNode", ["value"])
IdentifierNode = namedtuple("IdentifierNode", ["name"])
class MathAstBuilder:
def buildAdd(self, node):
return AddNode(self.build(node.a), self.build(node.b))
def buildSub(self, node):
return SubNode(self.build(node.a), self.build(node.b))
def buildMul(self, node):
return MulNode(self.build(node.a), self.build(node.b))
def buildDiv(self, node):
return DivNode(self.build(node.a), self.build(node.b))
def buildNumber(self, node):
return NumberNode(float(node.getText()))
def buildIdentifier(self, node):
return IdentifierNode(node.getText())
def build(self, node):
if not isinstance(node, ParserRuleContext):
raise Exception(f"{node} must be a node, not a {type(node)}")
name = "build" + type(node).__name__[:-7]
if name[:12] == "buildTrivial":
return self.build(node.a)
return self.__getattribute__(name)(node)
class MathProgram:
def __init__(self, program):
self.program = program
def evalAdd(self, node):
return self.eval(node.a) + self.eval(node.b)
def evalSub(self, node):
return self.eval(node.a) - self.eval(node.b)
def evalMul(self, node):
return self.eval(node.a) * self.eval(node.b)
def evalDiv(self, node):
return self.eval(node.a) / self.eval(node.b)
def evalNumber(self, node):
return node.value
def evalIdentifier(self, node):
return self.getVar(node.name)
def getVar(self, name):
if name not in self.vars:
self.vars[name] = float(input(f"Enter value for {name}: "))
return self.vars[name]
def eval(self, node):
name = "eval" + type(node).__name__[:-4]
return self.__getattribute__(name)(node)
def run(self):
self.vars = {}
result = self.eval(self.program)
print(result)
def parseFile(path):
lexer = MathLexer(FileStream(path))
stream = CommonTokenStream(lexer)
parser = MathParser(stream)
cst = parser.expr()
ast = MathAstBuilder().build(cst)
MathProgram(ast).run()
if __name__ == "__main__":
path = sys.argv[1]
parseFile(path)
Шаг за шагом:
- нам нужно определить каждый тип узлов AST — обычно их намного меньше, чем типов узлов CST (обычно около половины).
- Поскольку они очень простые, мы можем использовать
collections.namedtuple, чтобы определить сразу много типов. - мы также можем использовать словари для представления узлов и т.д. — AST может быть любым, каким вы захотите
- затем у нас есть
MathProgram— в данном случае это то же деревоeval, что и раньше, но это только потому, что это такой простой вид программы. Обычно эта часть была бы самой сложной частью вашей программы и содержала бы всю фактическую логику.
Абстрактное синтаксическое дерево с соответствующими классами
Если вам не нравится MathProgram.eval и вы хотите, чтобы в вашей программе использовались правильные классы и никакой магии помимо парсинга, вот еще один способ сделать AST. Весь код в логике в обычных методах ООП:
#!/usr/bin/env python3
from antlr4 import *
from MathLexer import MathLexer
from MathParser import MathParser
from collections import namedtuple
import sys
class AddNode:
def __init__(self, a, b):
self.a = a
self.b = b
def eval(self, context):
return self.a.eval(context) + self.b.eval(context)
class SubNode:
def __init__(self, a, b):
self.a = a
self.b = b
def eval(self, context):
return self.a.eval(context) - self.b.eval(context)
class MulNode:
def __init__(self, a, b):
self.a = a
self.b = b
def eval(self, context):
return self.a.eval(context) * self.b.eval(context)
class DivNode:
def __init__(self, a, b):
self.a = a
self.b = b
def eval(self, context):
return self.a.eval(context) / self.b.eval(context)
class NumberNode:
def __init__(self, value):
self.value = value
def eval(self, context):
return self.value
class IdentifierNode:
def __init__(self, name):
self.name = name
def eval(self, context):
return context.getVar(self.name)
class MathAstBuilder:
def buildAdd(self, node):
return AddNode(self.build(node.a), self.build(node.b))
def buildSub(self, node):
return SubNode(self.build(node.a), self.build(node.b))
def buildMul(self, node):
return MulNode(self.build(node.a), self.build(node.b))
def buildDiv(self, node):
return DivNode(self.build(node.a), self.build(node.b))
def buildNumber(self, node):
return NumberNode(float(node.getText()))
def buildIdentifier(self, node):
return IdentifierNode(node.getText())
def build(self, node):
if not isinstance(node, ParserRuleContext):
raise Exception(f"{node} must be a node, not a {type(node)}")
name = "build" + type(node).__name__[:-7]
if name[:12] == "buildTrivial":
return self.build(node.a)
return self.__getattribute__(name)(node)
class MathProgram:
def __init__(self, program):
self.program = program
def getVar(self, name):
if name not in self.vars:
self.vars[name] = float(input(f"Enter value for {name}: "))
return self.vars[name]
def run(self):
self.vars = {}
result = self.program.eval(self)
print(result)
def parseFile(path):
lexer = MathLexer(FileStream(path))
stream = CommonTokenStream(lexer)
parser = MathParser(stream)
cst = parser.expr()
ast = MathAstBuilder().build(cst)
MathProgram(ast).run()
if __name__ == "__main__":
path = sys.argv[1]
parseFile(path)
Абстрагирование конкретного синтаксического дерева
И последний шаблон проектирования: как насчет того, чтобы не строить новое AST, а взять существующее CST, но «абстрагировать» его, удалив все тривиальные узлы и выполнив все специфические для узлов исправления, например, преобразование строк в числа? Это очень просто в Python, поскольку он очень динамичен. Конечно, это было бы совершенно невозможно в Java с ее жесткой статической системой типов.
#!/usr/bin/env python3
from antlr4 import *
from MathLexer import MathLexer
from MathParser import MathParser
import sys
class MathAbstractify:
def abstractifyAdd(self, node):
node.a = self.abstractify(node.a)
node.b = self.abstractify(node.b)
def abstractifySub(self, node):
node.a = self.abstractify(node.a)
node.b = self.abstractify(node.b)
def abstractifyMul(self, node):
node.a = self.abstractify(node.a)
node.b = self.abstractify(node.b)
def abstractifyDiv(self, node):
node.a = self.abstractify(node.a)
node.b = self.abstractify(node.b)
def abstractifyNumber(self, node):
node.value = float(node.getText())
def abstractifyIdentifier(self, node):
node.name = node.getText()
def abstractify(self, node):
if not isinstance(node, ParserRuleContext):
raise Exception(f"{node} must be a node, not a {type(node)}")
name = "abstractify" + type(node).__name__[:-7]
if name[:18] == "abstractifyTrivial":
return self.abstractify(node.a)
else:
return self.__getattribute__(name)(node) or node
class MathProgram:
def __init__(self, program):
self.program = program
def evalAdd(self, node):
return self.eval(node.a) + self.eval(node.b)
def evalSub(self, node):
return self.eval(node.a) - self.eval(node.b)
def evalMul(self, node):
return self.eval(node.a) * self.eval(node.b)
def evalDiv(self, node):
return self.eval(node.a) / self.eval(node.b)
def evalNumber(self, node):
return node.value
def evalIdentifier(self, node):
return self.getVar(node.name)
def getVar(self, name):
if name not in self.vars:
self.vars[name] = float(input(f"Enter value for {name}: "))
return self.vars[name]
def eval(self, node):
if not isinstance(node, ParserRuleContext):
raise Exception(f"{node} must be a node, not a {type(node)}")
name = "eval" + type(node).__name__[:-7]
return self.__getattribute__(name)(node)
def run(self):
self.vars = {}
result = self.eval(self.program)
print(result)
def parseFile(path):
lexer = MathLexer(FileStream(path))
stream = CommonTokenStream(lexer)
parser = MathParser(stream)
tree = parser.expr()
tree = MathAbstractify().abstractify(tree)
MathProgram(tree).run()
if __name__ == "__main__":
path = sys.argv[1]
parseFile(path)
Шаг за шагом:
- Теперь программа состоит из двух частей —
MathAbstractifyдля преобразования CST в AST, иMathProgramдля ее выполнения - для тривиальных узлов,
MathAbstractify.abstractifyпросто удаляет узел и возвращает то, что являетсяMathAbstractify.abstractifyдочерним узлом — таким образом, результирующее дерево не будет иметь тривиальных узлов - для узлов, требующих специальной обработки, таких как
NumberиIdentifier, мы делаем это, и присваиваем результаты соответствующим полям - код в
MathAbstractify.abstractifyочень повторяющийся, и есть много способов сделать его более кратким, например, иметь словарь с полями каждого узла для обновления, но я не хотел усложнять это еще больше - после этого наша
MathProgramпрактически не отличается от нашей первой версии абстрактного синтаксического дерева — нет необходимости иметь дело с тривиальными узлами, и все в узлах предварительно вычислено.
Этот шаблон, возможно, самый хакерский из всех, но мы получаем большинство преимуществ AST без необходимости определять все типы узлов. MathAbstractify также может быть намного более лаконичным, чем то, что я сделал здесь.
Должны ли вы теперь использовать Python ANTLR 4?
Я думаю, что с этими паттернами проектирования, это гораздо лучший опыт, чем с официальной кодовой документацией в стиле Java, которую рекомендуют.
ANTLR 4 по-прежнему является, вероятно, самым мощным генератором парсеров, и он заслуживает гораздо лучшего API, чем тот, который он получил.
Ни один из этих шаблонов проектирования, которые я представил здесь, не является настолько чистым, как то, что мы могли бы иметь, если бы ANTLR 4 поддерживал прямую генерацию AST, но их полезно рассмотреть в зависимости от типа программы, которую вы пишете. Я определенно не рекомендую следовать ни одному из официальных шаблонов в стиле Java, которые я показал в предыдущем эпизоде.
Код
Все примеры кода для этой серии будут находиться в этом репозитории.
Код для эпизода Abstract Syntax Trees with Python ANTLR 4 доступен здесь.