bison - AST, CST и сотоварищи

ник "спамерка" не вызывает большого желания советовать что-то по лексическим анализаторам :) целее будем..

// wbr

Тогда посоветуйте anonymous'у.

// Даже капча выпала lanter -> lantern -> s/светило/святило.

Как построить AST? В C++ с помощью оператора new, в C - с помощью функции malloc().

А причем тут выделение памяти под объекты?

Это тоже самое что скажем на вопрос "Как использовать указатели?", ответить "с помощью оператора new, в C - с помощью функции malloc()". Хотя тут как раз было бы близко.

> А причем тут выделение памяти под объекты?

При том, что AST состоит из объектов. Вот и создавай их в терминалах EBNF.

> Это тоже самое

Нет. Ты фундаментально не догоняешь.

> Нет. Ты фундаментально не догоняешь.

думаю мы говорим просто немножко о разных задачках и ты о более простой.

Всем спасибо. Проблему решил.

Почитать.. ну хотя бы википедию, ссылку http://en.wikipedia.org/wiki/Abstract_syntax_tree, особенно PDF по ней с обзором AST : http://jerry.cs.uiuc.edu/~plop/plop2003/Papers/Jones-ImplementingASTs.pdf http://www.ansa.co.uk/ANSATech/95/Primary/155101.pdf

В целом, картина такова: есть входной поток текста -- программа на входном языке. Язык описывается грамматикой. Транслятор -- это программа, которая по указанной грамматике строит внутреннее представление программы и переводит его в пригодный для исполнения вид. Один и тот же язык можно написать несколькими грамматиками, то есть описать неоднозначно. Да и на разных языках можно написать одинаковые программы (которые будут оттранслированы в такую же точно структуру). Такую структуру, независимую от представления, в памяти представляет семантическое дерево (в общем виде) или в более частном, AST (абстрактные операции с одинаковой заданной семантикой).

Картина "в целом" транслятора: лексер (токенайзер) разбирает входной поток текста на поток токенов (лексем); парсер разбирает этот поток лексем и строит дерево вывода (в конкретном синтаксисе, зависимом от грамматики и её особенностей); Это проверка синтаксиса, не семантики. Из дерева вывода выкидываются лишние узлы, узлы проверяются на инварианты (вроде проверки типа выражения в оп. присваивания и типа переменной, которой присваиваем), проверяем семантику, и получаем AST. Потом трансформациями из AST получаем AST оптимизированный (вроде оптимизации подвыражений и т.п.), семантически эквивалентный старому. Потом получаем конечный AST, который используется для конечной кодогенерации (исполняемого кода (раскраска графа, и т.п. для регистрового байткода), или текста (для трансформаций текст-в-текст)).

//тот анонимус

Семантическое дерево генерируется явно не частно, практически чуть ли не единственной реализацией есть Интерстон и компилятор С++ Е. Зуева. Чаще генерируются AST, причём ASTы могут быть построены разные, преобразованием к более удобному для кодогенерации или для конкретного этапа транслятора (например, в примерах ANTLR+DLR (CLI для динамических языков) -- зачем-то AST построенного выражения преобразуется к более удобному для DLR виду).

point того поста был в том, что построить просто дерево вывода СST (или сделать интерпретатор языка, исполняя сразу нужную инструкцию) -- это ещё полдела. Если понадобится оптимизатор или один или несколько кодогенераторов или преобразования из входного языка через метаязык в несколько выходных, то CST не удобен. А AST для этого более удобен, и если есть Tree Grammar, как в ANTLR, или "грамматика = программа = исполняемая спецификация" как в комбинаторных монадических парсерах на Хаскелле, то там этот AST создаётся автоматически, генератором парсеров.

ну то есть надо строить его врукопашную, да. Вот в том же YACC++, не говоря уже о ANTLR и прочих, этот AST строится по единой спецификации генератором парсеров, автоматически.