смышленный препод нашего инста подкинул задачку на автомат, так сказать..
тока вот толком не объяснил, как Ето сделать..

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

пока читаем книжку - КНИГА ДРАКОНА, спецификацию лиспа, байт кодов Явашных..
не маленькая.. а времени как всегда и у всех не хватает..

вопрос не маленький.. 
помогите с написанием некоторых станд функций Лиспа на байт кодах..
как ето делается?

Вообще я не очень понял, вы собираетесь прямо на байт-кодах компилятор писать?
Может посмотреть в сторону yacc (Yet another Compiler Compiler) или ему подобных средств?
Вот неплохая статья Writing A Lisp Interpreter In Haskell, автор вообще-то java программист и все примеры с Хаскеля переносит на "офункционаленную" Java (старается, по-крайней мере).
Удачи (:

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

Смотри ка, а ведь пальцем в небо....
м/п ссылка твоя до меня так и не дошла...

а найти я тебя сумела... , Ильнар!

ноно.. без офтопа плиз..

Посмотрите описание компилятора Linj: http://www.evaluator.pt/downloads/tutorial.html

спасибо.. темная ссылочка..

помгите плиз с описанием проекта на новел форже...

построение аст дерева на яве? наверно использовать нада класс множества - set??

спс заранее

Странно, препод должен был натаскать вас по теме, прежде чем задание давать, может не верно понял? ;-)

Любой LALR парсер (тот же CUP) схавает любой синтаксис, включая такокй простой как у LISP'а. Если тебе по душе отделение автоматов парсера от собственно кода, то GoldParser класнючая вещь, там же грамматики и для лиспа тоже.
Хотя мне ближе менее гибкий, но привычный и человекочитаемый javacc.

Парсером собираешь дерево выражений (AST). На этом этапе лучше остановиться и реализовать для каждого типа ноды метод eval(context), который бы вычислял значение ноды. Затем проверь как всё выполняется.

Интересней будет при генерации байткода. Сначала анализируем дерево, находим все вызовы функций и складываем их в пул констант. Их проще транслировать в статичные методы класса. Затем распознаём всё "примитивные" функции, на которые в Java есть прямые опкоды, всё остальное будет реально вызываться как статичные методы некоторого runtime класса.

Советую не париться с оптимизатором, тупо сделай метод compile(canvas), в каждой ноде, пусть генерит собственный байткод. Например:



Ещё лучше трансливать  LISP в Java и пользоваться существующим компилером. Это не только совместимость с будущими JVM, но и просто гораздо проще реализовать.

мона о парсерах поподробней?..

подскажите пожалуйста..

как создать и , что еще важнее, как юзать ниболе простенькую таблицу символов для лиспа на яве..

или др варианты, если они возможны...


???

буду очень рад за любую конструктивную инфу..

Смотря что ты понимаешь под таблицей символов. Это хештаблица(java.util.HashMap). Чем подробнее опишешь задачу, тем подробнее будет помощь.

НУ на первом этапе анализа нам необходимо токены (лексический анализ) записывать в В ТАБЛИЦУ, с которыми в последующем будет работать синтаксический анализатор, итогом работы которого, насколько я понял, также должна быть ТАБЛИЦА..

вот о их создании и использовании я  и писал..

вариант нужен наиболее простой (но рабочий), ибо знаний маловато..

Значит ты решил писать собственный парсер, это хорошо в плане опыта 
Прочесть это.

Никакой "таблицы" составлять не надо, твоя задача сворачивать поток символов до лексем. На входе имеем поток байтов, который проходит через декодировщик, что выдаёт поток символов в юникоде. Далее имеем автомат (граф ссылками, таблицей, как угодно), что и распознаёт токены (собирает символы до токенов). Это лексический анализ, на выходе поток лексем.

Что бы понять как работает токенизер, нарисуй на бумаге граф. К примеру нужно распознать: aba*b (abb, abab, abaab и т.д.) и baba. Нарисуй точку, от неё два ребра помеченные a и b. Под ребрами новые вершины, от которых новые рёбра помеченные классом символов (в нашем случае два класса, по одному символу в каждом). Выйдет:



Ну а далее берёшь входные символы и на каждом следующем выбираешь ребро в графе, пока не упрёшься в *. В этот момент токен найден, начинаем снова с корня графа. Если для текущего символа ребра не нашлось, то кидаем ошибку синтаксиса.

После токенизера из потока байтов (символов) имеем поток лексем, где большинство ключевых слов уже в своих лексемах. Ключевые разбирают на этапе лескического анализа ради человека (читаемость), потому как для транслятора абсолютно по барабану, он разбирает контекстами (while while do while=do(); end нормально распознаётся). Лексемы идут на вход синтаксического анализатора, на этом месте уже нужно знать что такое контекстно-свободные грамматики, терминалы, не терминалы, развёртка/свёртка. Впрочем ты это должен был знать и на лексическом анализаторе   В синтаксическом то же самое, только те терминалами выступают лексемы.

Парсер LL(n) написать проще (LL(1) - простейшие реги), вбей в гугл. Суть в том, что "потребляем" все терминалы с лева на право, пока не упрёмся в не-терминал. Не-терминал далее заменяется подходящим правилом развёртки, с правилом может ассоциироваться действие. Вот в таком действии и определяем кода конкретная инструкция готова и что с ней делать. Если по одной входной лексеме существует более одного правила, то тебе потребуется прочесть следующую лексему, что бы найти одно единственное правило развёртки. Максимальное количество лексем, требуемых для однозначного выбора называют степенью LL грамматики, обозначается как LL(n), где n собственно и есть то самое количество.

На практике если и используются LL парсеры, то LL(1) в целях эффективности, а там где нужно парсер прочитывает более одной лексемы. Это называется look ahead приёмом, вот такие look ahead задаются тем кто составляет грамматику. Тебе этого достаточно, что бы распознать почти любой синтаксис (по моему все популярные языки программирования включаются). Если хочется большего, то перейдёшь к LALR(n) парсерам, где терминалы наоборот сворачиваются в не-терминалы. Этот принцип сложней.

На выходе парсера получаем поток событий (делай то, делай это). Ну собственно по событиям и собираем инфу в AST дерево (абстрактное синтаксическое дерево). После анализа уже согласно правилам языка добавляем аннотации к AST и разворачиваем все эффекты "по умолчанию" допустимые в языке. На выходе полностью формальное (однозначное, контекстно не зависимое) представление исходника в виде дерева. Его можно тут же выполнить, если в каждом узле сделать метод "выполнить себя", вызывающий рекурсивно дочерние узлы. Можно пробежаться транслятором и сгенерить "ассемблерный код" (твой набор инструкций, стековый, регистровый, как угодно). Такой оттранслированный код проще выполнять, в простейшем случае весь интерпретатор это одна switch конструкция.

Ну вроде всё на пальцах, ключевые для поиска тоже дал, осталось начитаться нормальной литературы на эту тему ;-)

я подобное уже прочитал в КНИГЕ ДРАКОНА.. 
правда там не так разжевано))) за что и СПАСИБО..

мы идем от простого:
пока наш компилятор должен "разбираться" с простыми арифметическими операциями..
(... это конечно хорошо, тока препод несколько отбил желание.. хочется просто сделать наиболее простой вариант и шоб работал..)
ну типа (+ 1 (* 2 3))

на данном этапе наш "лексический анализатор" разбивает на токены, т.е на выходе получаем следующее 
[ (, +, 1, (, *, 2, 3, ) ] затем проходя "синтаксический анализатор": [ +, 1, [ *, 2, 3] ]

вотЪ

нельзя ль работать "вот с Этим"??