Древовидная структура для АСТ

Question

Я пытаюсь написать переводчик на C #, и я нахожусь на стадии разбора. Я понял, что должен сгенерировать абстрактное синтаксическое дерево на этом этапе, но я не знаю, как его представить в C #.

В настоящее время я просто использую List<object>, но у меня такое ощущение, что я делаю это неправильно.

Большое спасибо.

Answer 1

Я предлагаю вам продолжать использовать List<object> до тех пор, пока вы четко не поймете, какие ограничения это накладывает и каковы ваши требования. Или, поскольку вы пишете интерпретатор LISP, создайте парный класс и используйте его с object, null, эквивалентным '():

public sealed class Pair
{
    public object Car ;
    public object Cdr ;
}

Разберите ваши входные данные непосредственно в S-выражение, и ваш переводчик будет работать непосредственно с этим. В конце концов, LISP существовал до ASTs!

Answer 2

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

Однако, делая шаг назад, интерпретация строго не требуетАСТ.Многие более ранние интерпретаторы буквально читали каждую строку кода в том виде, в каком они встречались, анализируя и выполняя ее на лету, с помощью циклов и т. Д., Реализованной через систему стеков закладок.Я подозреваю, что языки оболочки, такие как bash и cmd.exe, все еще работают сегодня.

Answer 3

Большинство реализаций узла AST довольно просты.

Они представляют собой структуру (ок, ок, «класс»), содержащую тип узла (обычно целое число), список дочерних элементов (список в порядке; высокопроизводительные реализации имеют набор членов для статистически общего 1-го числа).2-е, 3-е дочерние элементы) и некоторые дополнительные поля для переноса значений, специфичных для экземпляра узла AST (например, значение «5» для узла AST «целочисленная константа»).Чтобы обеспечить эффективную навигацию по дереву от любого узла к родителям, часто существует специальная ссылка на родительский узел.

Что сложнее - решить какой набор узлов AST у вас должен быть,Для большой грамматики это неудобно, так как вам нужно будет определить набор из нескольких сотен из них, и будет возникать отток при изменении грамматики в ваших попытках сделать это правильно.

Простой трюкпросто определить один узел AST на правило грамматики.(Большинство будет называть это "конкретным синтаксическим деревом").Но это безмозгло, и вы ничего не упускаете.

Наш набор инструментов для реинжиниринга программного обеспечения DMS следует этой простой идее, генерируя типы узлов AST непосредственно из правил грамматики.Он дополнительно оптимизирует: листовые узлы AST, которые не несут значений, не представлены в дереве, узлы для унарных производств отсутствуют в дереве, а у формирующих список производств есть дочерний стиль List, в то время как другие типы узлов имеютфиксированные типы слотов для детей.В итоге вы получите то, что довольно близко к «абстрактному» синтаксическому дереву.Все это автоматически создается генератором синтаксического анализатора DMS, так что вам даже не нужно думать.

DMS также имеет полный, хорошо протестированный интерфейс C # 4.0.Как только вы преодолеете головную боль при определении AST, вы захотите проанализировать / преобразовать / сгенерировать его, и остальная часть DMS внезапно станет очевидно полезной.