Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > LISP > LISP + JAVA


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

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

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

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

Автор: semka 27.3.2007, 07:37
Вообще я не очень понял, вы собираетесь прямо на байт-кодах компилятор писать?
Может посмотреть в сторону yacc (Yet another Compiler Compiler) или ему подобных средств?
Вот неплохая статья http://www.defmacro.org/ramblings/lisp-in-haskell.html, автор вообще-то java программист и все примеры с Хаскеля переносит на "офункционаленную" Java (старается, по-крайней мере).
Удачи (:

Автор: ilnar 27.3.2007, 15:20
Цитата

Вообще я не очень понял, вы собираетесь прямо на байт-кодах компилятор писать?


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

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

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

Автор: ilnar 27.3.2007, 21:51
ноно.. без офтопа плиз..

Автор: adejneka 28.3.2007, 05:39
Посмотрите описание компилятора Linj: http://www.evaluator.pt/downloads/tutorial.html

Автор: ilnar 28.3.2007, 08:14
спасибо.. темная ссылочка..

Автор: ilnar 28.3.2007, 21:09
помгите плиз с описанием проекта на новел форже...

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

спс заранее

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

Любой LALR парсер (тот же http://www2.cs.tum.edu/projects/cup/) схавает любой синтаксис, включая такокй простой как у LISP'а. Если тебе по душе отделение автоматов парсера от собственно кода, то http://www.devincook.com/goldparser класнючая вещь, там же http://www.devincook.com/goldparser/grammars/index.htm и для лиспа тоже.
Хотя мне ближе менее гибкий, но привычный и человекочитаемый https://javacc.dev.java.net/.

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

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

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

Код
//для Java к примеру
int a = 100 * Math.random();

//AST:
(def:int
 (=
   (const 100)
   (call
      (reference-method 'random'
        (reference-class 'Math')
      )
    )
 )
)

//генеря байткод бежим от корня
push-int 100 -- const 100
push-object @Math  -- имена Math и random
invoke-static @random -- в пуле констант, здесь ссылки
mul
//на верхушке стека значение a


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

Автор: ilnar 31.3.2007, 13:18
мона о парсерах поподробней?..

Автор: ilnar 15.4.2007, 21:35
подскажите пожалуйста..

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

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


???

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

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

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

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

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

Автор: Sardar 16.4.2007, 22:49
Значит ты решил писать собственный парсер, это хорошо в плане опыта smile
Прочесть http://softcraft.ru/translat/lect/content.shtml.

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

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

Код
       []
   [a] [b]
 [b]     [a] 
[b][a]   [b]
 *   ^     [a]
               *

где * конец разбора, ^ прыгнуть на родительскую вершину


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

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

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

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

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

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

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

мы идем от простого:
пока наш компилятор должен "разбираться" с простыми арифметическими операциями..
(
Цитата

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

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

вотЪ

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


 

Автор: ilnar 21.4.2007, 08:33
ну же..
.
ответьте пожалуйста!!!

Автор: Sardar 21.4.2007, 14:35
Цитата(ilnar @  17.4.2007,  07:52 Найти цитируемый пост)
ну типа (+ 1 (* 2 3))

Ну зачем тебе в префиксной нотации скобки? Порядок вычислений задаёться порядком следования операндов и операторов. К примеру полностью ручной парсер за 20 миинут:
Код

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xml:lang="en" lang="en" xmlns="http://www.w3.org/1999/xhtml">
<head>
<script type="text/javascript">

function Tokenizer(str) {
    this.data = str;
    this.current = null;
    this.pos = 0;
}
Tokenizer.prototype.getCurrent = function() {
    return this.current? this.current: this.nextToken();
}
Tokenizer.prototype.nextToken = function() {
   var lit = /^(\s+)|([a-zA-Z_]+)|([+\-*\/])|([0-9]+)/, m, ret;
   while(this.data.length > 0) {
      m = lit.exec(this.data);
      if(!m) throw "Illegal character data: '" + this.data.charAt(0) + "' at position: " + this.pos;
      this.pos += m[0].length;
      this.data = this.data.substr(m[0].length);
      if(m[2]) ret = {type: 'name', value: m[2]};
      else if(m[3]) ret = {type: 'operator', value: m[3]};
      else if(m[4]) ret = {type: 'number', value: parseInt(m[4])};
      else continue;
      break;
   }
   if(!ret) ret ={type:'EOF'};
   return this.current = ret;
}

function parseExpression(tk) {
   var ret = Operator.tryParse(tk);
   if(ret == null) ret = Value.tryParse(tk);
   if(ret == null) throw "Syntax exception at: " + tk.pos;
   return ret;
}

function Operator(op, exp1, exp2) {
   this.op = op;
   this.exp1 = exp1;
   this.exp2 = exp2;
}
Operator.tryParse = function(tk) {
   var tok = tk.getCurrent();
   if(tok.type != 'operator') return null;
   tk.nextToken();
   var exp1 = parseExpression(tk);
   tk.nextToken();
   var exp2 = parseExpression(tk);
   tk.nextToken();
   return new Operator(tok.value, exp1, exp2);
}
Operator.prototype.toString = function() {
   return '(' + this.exp1.toString + ' ' + this.op + ' ' + this.exp2.toString + ')';
}
Operator.prototype.evaluate = function(ctx) {
   switch(this.op) {
     case '*': return this.exp1.evaluate(ctx) * this.exp2.evaluate(ctx);
     case '/': return this.exp1.evaluate(ctx) / this.exp2.evaluate(ctx);
     case '+': return this.exp1.evaluate(ctx) + this.exp2.evaluate(ctx);
     case '-': return this.exp1.evaluate(ctx) - this.exp2.evaluate(ctx);
     default: throw "Unexpected operator type. Internal error.";
   }
}

function Value(tok) {
   if(tok.type == 'name') this.variable = tok.value;
   else this.value = tok.value;
}
Value.tryParse = function(tk) {
   var tok = tk.getCurrent();
   if(tok.type != 'name' && tok.type != 'number') return null;
   return new Value(tok);
}
Value.prototype.toString = function() {
   return this.variable? this.variable: this.value;
}
Value.prototype.evaluate = function(ctx) {
   if(this.variable && ctx[this.variable] == undefined) throw "Unknown variable: " + this.variable;
   return this.variable? ctx[this.variable]: this.value;
}


function execute() {
    var tk = new Tokenizer(document.getElementById('expr').value);
    var exp = parseExpression(tk);
    if(tk.getCurrent().type != 'EOF') throw "Unexpected construction at position: " + tk.pos;
    if(!exp) alert("Empty imput");
    else {
        var ctx = {};
        var imps = document.getElementById('vars').getElementsByTagName('input');
        for(var i =0; i< imps.length; i+=2) if(imps[i].value) ctx[imps[i].value] = parseInt(imps[i+1].value);
        alert(exp.evaluate(ctx));
    }
}

</script>
</head>
<body>

<form>
Expression: <input type="text" id="expr" size="80"><br>
<div id="vars">
 name: <input type="text">  value: <input type="text"><br>
 name: <input type="text">  value: <input type="text"><br>
 name: <input type="text">  value: <input type="text"><br>
 name: <input type="text">  value: <input type="text"><br>
</div>
<input type="button" onclick="execute()" value="Execute">
</form>

</body>
</html>

Сохрани в текстовом файле и открой браузером.

Имем токенизер, имем ноды AST дерева, которые сами парсят поток токенов. Этакий предсказываюший анализатор, по идее такой же как и классический стековый нализатор (в роли не терминалов вызовы методов). Таким образом можно парсить в принципе что угодно, только для lookahead шага потребуеться возвращать токены  обратно в поток, ну и конечно же сам такой парсер не очень эффективен.

Автор: ilnar 21.4.2007, 15:18
))

спасибо ..

жаль, что я html не знаю(((


придется разбираться ..

Автор: adejneka 21.4.2007, 18:57
Цитата(Sardar @ 21.4.2007,  14:35)
Ну зачем тебе в префиксной нотации скобки?

Для поддержки функций с переменным числом параметров. Например, (+ 1 2 3 (* x 4 7 8) (* x 3 4 5)). Или с фиксированным, но неизвестным на этапе компиляции: (+ 1 2 (funcall (car some-list) 3 4 5) 6 7).

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)