Сам себе интерпретатор. Часть 2.
Интерпретируем
Как известно любой алгоритм можно реализовать, используя следование, условный и безусловный переходы.
Логично будет сначала реализовать следование, т.е. разбиение на команды и их обработку. Мы уже договорились, что будем разделять команды точкой с запятой. Для этой цели напишем класс Expression, от слова «выражение».
Для работоспособности такой системы нам понадобится массив для хранения команд, указатель на текущую команду, конструктор, разбивающий текст на команды и метод, при вызове которого, берется следующая команда и выполняется. Моя реализация выглядит так:
Как ты мог заметить, мы еще отслеживаем коментарии, т.е. строка начинающаяся со знака вопроса будет пропускатся. Еще для реализации безусловных переходов мы в конструкторе вызываем анализ на метки. У кого мозги давно схавал рунет напомню, что метка – это имя перед строкой, на которую можно будет перейти по команде GOTO (кто щас будет кидатся старыми носками в меня за использование «плохой» команды – пусть идет в баню, там тепло и веники. Просто с помошью условных IF и безусловных переходов GOTO мы можем организовывать циклы).
Чтобы не откладывать все в долгий и длинный ящик (запомните дети – играть в ящик опасно), я с тобой поделюсь секретом как реализовать класс отвечающий за метки. Вот примерно так выглядит метка в строке:
Здесь «Start» - это метка, а «LABEL» указывает нам на это, чтобы мы могли различать где метки, а где имена переменных. Я, кстати, не зря напомнил про переменные, потому, что реализаци будет очень схожа. Подумай сам, какую инфу несет в себе метка? Ну конечно ее имя и номер строки. Т.е. для хранения будем использовать уже знакомую нам фиговину типа hastable
Единственное различее будет в реализации анализа на метки, это делается просто:
1)Просматриваем, если имя первой лексемы равно «LABEL», то значит тут есть метка.
2)Помещаем следующую лексему (это и будет имя метки) в массив меток и номер строки.
3)Удаляем три первые лексемы (LABEL, имя метки и двоеточие).
4)Возвращаем строку без меток.
Вот и листинг:
А вот теперь сама долгожданная часть, будем интерпретировать команды. Берем первую лексему, и если она имеет тип Command, то тогда уже проверяем что же это за команда:
p
Теперь, написав уже менеджер меток, попробуем реализовать команду безусловного перехода GOTO.
К твоему удивлению это будет очень просто, в одну строчку:
Мы просто переводим указатель текущей команды, на номер, на который указывает метка.
Вот и все, реализовав основную базу, писать интерпретацию команд не так сложно. Осталось только показать наиболее сложно интерпретируемую команду условного перехода IF-THEN-ELSE.
Давай напишем примерный алгоритм:
1)Если это IF то ищем THEN
2)Вырезаем лексемы от IF’a до THEN’a, закидываем в массив с название iff
3)Если нету ELSE, то считываем лексемы от THEN’a до конца и записываем в массив thenn
4)Если есть ветка ELSE, то считываем все лексемы после нее и до конца и записываем в массив elsee
5)Если условие заключенное в IF верно, то выполняем лексемы из массива iff, иначе из массива elsee.
Вот и готово, мы сделали условный и безусловный переход, этого будет достаточно для организации циклов. Остальные типа месседжбокса, ретёрна и прочего реализуются очень просто, просто глянь в исходник. Теперь главное не забыть, в этой же функции сделать проверку на присвоение переменной значения. Просто проходимся по лексемам, если находим равно, проверяем чтобы перед ним стояло ОБЯЗАТЕЛЬНО ПЕРЕМЕННАЯ, затем вычясляем выражение, стоящее справа от знака присвоения и заносим результат в переменную слева от знака. Затем сам знак удаляем, и у нас в итоге останется одна лексема переменной с полученным значением.
Это конец
Пришло время подвести итог и нарисовать обобщенный алгоритм дейтсвия интерпретатора, чтобы полностью происнить как он работает.
1)Получение исходного текста и разбиение его на выражения (то что заканчивается точкой с запятой)
2)Проверка на метки
3)Ищем команды и интерпретируем их
4)Выполняем упрощение от скобок
5)Выполняем упрощение от переменных
6)Выполняем простейшие операции (+-*^ и т.д.)
Вот и весь алгоритм. Как видишь, моя система очень похожа на перамиду. Т.е. идет поблочное упрощение и, имея такую структуру, мы можем добавить сюда какие-то фишки, просто добавив новый блок в зависимости от приоритета. Вся логика заключена в приоритетах блоков и рекурсии.
Как я и обещал, в конце мы сможем написать программу, которую и выполнит наш интерпретатор.
Ну вот теперь реально все :-) Да, статья конечно получилась большая и достаточно сложная, но и тема не из легких. Не отчаивайся если сразу не понял как все работает, просто открой и исходник, просмотри порядок вызова функций, поэксперементируй, выясни что и для чего нужно, попробуй оптимизировать некоторые участки кода – и все станет на свои места. На этом все. Удачной тебе интерпретации!
Как известно любой алгоритм можно реализовать, используя следование, условный и безусловный переходы.
Логично будет сначала реализовать следование, т.е. разбиение на команды и их обработку. Мы уже договорились, что будем разделять команды точкой с запятой. Для этой цели напишем класс Expression, от слова «выражение».
Для работоспособности такой системы нам понадобится массив для хранения команд, указатель на текущую команду, конструктор, разбивающий текст на команды и метод, при вызове которого, берется следующая команда и выполняется. Моя реализация выглядит так:
class Expression//класс делящий весь текст на выражения. выражения отделяются точкой с запятой;
{
public static bool theend;//булево обозначение конца команд
public static ArrayList commands;///массив команд
public static int currentcommand;//текущая команда
public Expression(string text)//конструктор, почти лего:)
{
theend = false;//мы только начали, поэтому конца пока нет
currentcommand =-1;//команды идут с нуля, поэтому предустанавливаем на -1
bool IsComment=false;//это не коментарий, предустановленное значение
commands=new ArrayList();//создаем массив
int start=0;//начальное значение, с которого будем вырезать команды из текста
for (int i = 0; i < text.Length; i++)//перебераем текст
{
if (text[i] == '?')//если встречаем символ вопроса, то это комментарий
{
IsComment = true;
}
if (("\r\n".IndexOf(text[i]) != -1))//если совпадает с вот этими символами то (возврат каретки и пробелы)
{
if (IsComment)//если комент - то пропускаем
{
start = i;
IsComment = false;
}
text=text.Remove(i,1);
i--;
continue;
}
if(text[i]==';')//если доходим до точки с запятой, то конец команды
{
commands.Add(text.Substring(start, i - start+1));//считываем от предыдущего конца до точки с запятой
start = i + 1;//следующая команда будет резатся от сюда
}
}
for (int i = 0; i < commands.Count; i++)//перебираем все строки в массиве и анализируем на метки
commands[i]= CalcLogic.ls.AnalizForLabel(JF_CALC.CalcLogic.GetLeksemsFromString(commands[i].ToString()),i);
}
public bool NextCommand()//метод достающий следующую команду и выполняющую ее
{
currentcommand++;//увеличиваем номер текущей команды
if (currentcommand >= commands.Count)//если номер текущей команды больше доступный, то возвращаем фолс
return false;
else//иначе выполняем ее
{
JF_CALC.CalcLogic.PreAnaliz(JF_CALC.CalcLogic.GetLeksemsFromString(commands[currentcommand].ToString()));
}
return true;
}}
{
public static bool theend;//булево обозначение конца команд
public static ArrayList commands;///массив команд
public static int currentcommand;//текущая команда
public Expression(string text)//конструктор, почти лего:)
{
theend = false;//мы только начали, поэтому конца пока нет
currentcommand =-1;//команды идут с нуля, поэтому предустанавливаем на -1
bool IsComment=false;//это не коментарий, предустановленное значение
commands=new ArrayList();//создаем массив
int start=0;//начальное значение, с которого будем вырезать команды из текста
for (int i = 0; i < text.Length; i++)//перебераем текст
{
if (text[i] == '?')//если встречаем символ вопроса, то это комментарий
{
IsComment = true;
}
if (("\r\n".IndexOf(text[i]) != -1))//если совпадает с вот этими символами то (возврат каретки и пробелы)
{
if (IsComment)//если комент - то пропускаем
{
start = i;
IsComment = false;
}
text=text.Remove(i,1);
i--;
continue;
}
if(text[i]==';')//если доходим до точки с запятой, то конец команды
{
commands.Add(text.Substring(start, i - start+1));//считываем от предыдущего конца до точки с запятой
start = i + 1;//следующая команда будет резатся от сюда
}
}
for (int i = 0; i < commands.Count; i++)//перебираем все строки в массиве и анализируем на метки
commands[i]= CalcLogic.ls.AnalizForLabel(JF_CALC.CalcLogic.GetLeksemsFromString(commands[i].ToString()),i);
}
public bool NextCommand()//метод достающий следующую команду и выполняющую ее
{
currentcommand++;//увеличиваем номер текущей команды
if (currentcommand >= commands.Count)//если номер текущей команды больше доступный, то возвращаем фолс
return false;
else//иначе выполняем ее
{
JF_CALC.CalcLogic.PreAnaliz(JF_CALC.CalcLogic.GetLeksemsFromString(commands[currentcommand].ToString()));
}
return true;
}}
Как ты мог заметить, мы еще отслеживаем коментарии, т.е. строка начинающаяся со знака вопроса будет пропускатся. Еще для реализации безусловных переходов мы в конструкторе вызываем анализ на метки. У кого мозги давно схавал рунет напомню, что метка – это имя перед строкой, на которую можно будет перейти по команде GOTO (кто щас будет кидатся старыми носками в меня за использование «плохой» команды – пусть идет в баню, там тепло и веники. Просто с помошью условных IF и безусловных переходов GOTO мы можем организовывать циклы).
Чтобы не откладывать все в долгий и длинный ящик (запомните дети – играть в ящик опасно), я с тобой поделюсь секретом как реализовать класс отвечающий за метки. Вот примерно так выглядит метка в строке:
LABEL Start:a=10;
Здесь «Start» - это метка, а «LABEL» указывает нам на это, чтобы мы могли различать где метки, а где имена переменных. Я, кстати, не зря напомнил про переменные, потому, что реализаци будет очень схожа. Подумай сам, какую инфу несет в себе метка? Ну конечно ее имя и номер строки. Т.е. для хранения будем использовать уже знакомую нам фиговину типа hastable
Единственное различее будет в реализации анализа на метки, это делается просто:
1)Просматриваем, если имя первой лексемы равно «LABEL», то значит тут есть метка.
2)Помещаем следующую лексему (это и будет имя метки) в массив меток и номер строки.
3)Удаляем три первые лексемы (LABEL, имя метки и двоеточие).
4)Возвращаем строку без меток.
Вот и листинг:
class Labels//класс для меток
{
Hashtable labels;//для хранения меток
public Labels()//конструктор
{
labels = new Hashtable();
}
public void Clear()//очищаем метки
{
labels.Clear();
}
public bool AddLabel(string name, int number)//добавляем метку
{
if (labels[name] == null)
labels.Add(name, number);
return true;
}
public int GetNumberFromLabelName(string name)//получаем номер команды (строки) по имени метки
{
if (labels[name] != null)
return int.Parse(labels[name].ToString())-1;
else return -1;
}
public string AnalizForLabel(ArrayList leksemsarray, int numstr)//анализируем на метку
{
if (((Leksem)leksemsarray[0]).name == "LABEL")//если начинается с LABEL, то ищем метку
{
AddLabel(((Leksem)leksemsarray[1]).name, numstr);//добавляем метку и номер строки
leksemsarray.RemoveAt(0);//удаляем LABEL
leksemsarray.RemoveAt(0);//удаляем имя метки
leksemsarray.RemoveAt(0);//удяляем двоеточие
}
//далее преобразуем лексемы в строки...
string s="";
for (int i = 0; i < leksemsarray.Count; i++)
s += ((Leksem)leksemsarray[i]).name+" ";
s += ";";
return s;
}}
{
Hashtable labels;//для хранения меток
public Labels()//конструктор
{
labels = new Hashtable();
}
public void Clear()//очищаем метки
{
labels.Clear();
}
public bool AddLabel(string name, int number)//добавляем метку
{
if (labels[name] == null)
labels.Add(name, number);
return true;
}
public int GetNumberFromLabelName(string name)//получаем номер команды (строки) по имени метки
{
if (labels[name] != null)
return int.Parse(labels[name].ToString())-1;
else return -1;
}
public string AnalizForLabel(ArrayList leksemsarray, int numstr)//анализируем на метку
{
if (((Leksem)leksemsarray[0]).name == "LABEL")//если начинается с LABEL, то ищем метку
{
AddLabel(((Leksem)leksemsarray[1]).name, numstr);//добавляем метку и номер строки
leksemsarray.RemoveAt(0);//удаляем LABEL
leksemsarray.RemoveAt(0);//удаляем имя метки
leksemsarray.RemoveAt(0);//удяляем двоеточие
}
//далее преобразуем лексемы в строки...
string s="";
for (int i = 0; i < leksemsarray.Count; i++)
s += ((Leksem)leksemsarray[i]).name+" ";
s += ";";
return s;
}}
А вот теперь сама долгожданная часть, будем интерпретировать команды. Берем первую лексему, и если она имеет тип Command, то тогда уже проверяем что же это за команда:
p
ublic static double PreAnaliz(ArrayList leksems)
{
ArrayList next = new ArrayList();
//////ИЩЕМ КОММАНДЫ/////////////
if(((Leksem)leksems[0]).Type==Leksem.LeksemType.Command)
{
switch (((Leksem)leksems[0]).name)
{
{
ArrayList next = new ArrayList();
//////ИЩЕМ КОММАНДЫ/////////////
if(((Leksem)leksems[0]).Type==Leksem.LeksemType.Command)
{
switch (((Leksem)leksems[0]).name)
{
Теперь, написав уже менеджер меток, попробуем реализовать команду безусловного перехода GOTO.
К твоему удивлению это будет очень просто, в одну строчку:
case "GOTO":
JF_CALC.Expression.currentcommand = ls.GetNumberFromLabelName(((Leksem)leksems[1]).name);
return 0.0;
break;
JF_CALC.Expression.currentcommand = ls.GetNumberFromLabelName(((Leksem)leksems[1]).name);
return 0.0;
break;
Мы просто переводим указатель текущей команды, на номер, на который указывает метка.
Вот и все, реализовав основную базу, писать интерпретацию команд не так сложно. Осталось только показать наиболее сложно интерпретируемую команду условного перехода IF-THEN-ELSE.
Давай напишем примерный алгоритм:
1)Если это IF то ищем THEN
2)Вырезаем лексемы от IF’a до THEN’a, закидываем в массив с название iff
3)Если нету ELSE, то считываем лексемы от THEN’a до конца и записываем в массив thenn
4)Если есть ветка ELSE, то считываем все лексемы после нее и до конца и записываем в массив elsee
5)Если условие заключенное в IF верно, то выполняем лексемы из массива iff, иначе из массива elsee.
case "IF"://а тут будем иф вычеслять, ппц сложно 
ArrayList iff=new ArrayList();
ArrayList thenn=new ArrayList();
ArrayList elsee=new ArrayList();
/////////////////////Ищем Then////////
for (int i = 1; i < leksems.Count; i++)
{
if (((Leksem)leksems[i]).name == "THEN")//находим then и заполняем условное выражение
{
leksems.RemoveAt(i);
for (int j = 1; j <i; j++)
{
iff.Add(leksems[1]);
leksems.RemoveAt(1);
}
i = 0;
}
if (((Leksem)leksems[i]).name == "ELSE" || i==leksems.Count-1)//находим else и заполняем then'овское выражение
{
if (((Leksem)leksems[i]).name == "ELSE")//если есть else :)
{
leksems.RemoveAt(i);
for (int j = 1; j < i; j++)//заполняем вен
{
thenn.Add(leksems[1]);
leksems.RemoveAt(1);
}
i = leksems.Count;
for (int j = 1; j <i; j++)//заполняем вен
{
elsee.Add(leksems[1]);
leksems.RemoveAt(1);
}
//заполняем елсе
}
else//если нету :(
{
for (int j = 1; j <=i; j++)
{
thenn.Add(leksems[1]);
leksems.RemoveAt(1);
}
}
i = 0;
leksems.Clear();
}
}
if (GetExpressionFromBrackets(iff) == 1.0)//проверяем блок иф
{
PreAnaliz(thenn);//выполняем блок иф
return 0.0;
}
else if (elsee.Count >= 1)//если есть блок елсе
{
PreAnaliz(elsee);//выполняем блок елсе
return 0.0;
}
else
return 0.0;
break;
ArrayList iff=new ArrayList();
ArrayList thenn=new ArrayList();
ArrayList elsee=new ArrayList();
/////////////////////Ищем Then////////
for (int i = 1; i < leksems.Count; i++)
{
if (((Leksem)leksems[i]).name == "THEN")//находим then и заполняем условное выражение
{
leksems.RemoveAt(i);
for (int j = 1; j <i; j++)
{
iff.Add(leksems[1]);
leksems.RemoveAt(1);
}
i = 0;
}
if (((Leksem)leksems[i]).name == "ELSE" || i==leksems.Count-1)//находим else и заполняем then'овское выражение
{
if (((Leksem)leksems[i]).name == "ELSE")//если есть else :)
{
leksems.RemoveAt(i);
for (int j = 1; j < i; j++)//заполняем вен
{
thenn.Add(leksems[1]);
leksems.RemoveAt(1);
}
i = leksems.Count;
for (int j = 1; j <i; j++)//заполняем вен
{
elsee.Add(leksems[1]);
leksems.RemoveAt(1);
}
//заполняем елсе
}
else//если нету :(
{
for (int j = 1; j <=i; j++)
{
thenn.Add(leksems[1]);
leksems.RemoveAt(1);
}
}
i = 0;
leksems.Clear();
}
}
if (GetExpressionFromBrackets(iff) == 1.0)//проверяем блок иф
{
PreAnaliz(thenn);//выполняем блок иф
return 0.0;
}
else if (elsee.Count >= 1)//если есть блок елсе
{
PreAnaliz(elsee);//выполняем блок елсе
return 0.0;
}
else
return 0.0;
break;
Вот и готово, мы сделали условный и безусловный переход, этого будет достаточно для организации циклов. Остальные типа месседжбокса, ретёрна и прочего реализуются очень просто, просто глянь в исходник. Теперь главное не забыть, в этой же функции сделать проверку на присвоение переменной значения. Просто проходимся по лексемам, если находим равно, проверяем чтобы перед ним стояло ОБЯЗАТЕЛЬНО ПЕРЕМЕННАЯ, затем вычясляем выражение, стоящее справа от знака присвоения и заносим результат в переменную слева от знака. Затем сам знак удаляем, и у нас в итоге останется одна лексема переменной с полученным значением.
Это конец
Пришло время подвести итог и нарисовать обобщенный алгоритм дейтсвия интерпретатора, чтобы полностью происнить как он работает.
1)Получение исходного текста и разбиение его на выражения (то что заканчивается точкой с запятой)
2)Проверка на метки
3)Ищем команды и интерпретируем их
4)Выполняем упрощение от скобок
5)Выполняем упрощение от переменных
6)Выполняем простейшие операции (+-*^ и т.д.)
Вот и весь алгоритм. Как видишь, моя система очень похожа на перамиду. Т.е. идет поблочное упрощение и, имея такую структуру, мы можем добавить сюда какие-то фишки, просто добавив новый блок в зависимости от приоритета. Вся логика заключена в приоритетах блоков и рекурсии.
Как я и обещал, в конце мы сможем написать программу, которую и выполнит наш интерпретатор.
?Решение квадратного уравнения ax^2+bx+c=0
a=4;
b=4;
c=1;
D=b^2-4*a*c;
IF D>0 THEN GOTO DVAKORNYA;
IF D==0 THEN GOTO ODINKOREN;
IF D<0 THEN GOTO NETKORNEY;
LABEL DVAKORNYA: x1=((0-b)+D^(1/2))/(2*a);
x2=((0-b)+D^(1/2))/(2*a);
MSGBOX x1;
MSGBOX x2;
RETURN 0;
LABEL ODINKOREN: x1=(0-b)/(2*a);
MSGBOX x1;
RETURN 0;
LABEL NETKORNEY: MSGBOX 666;
RETURN 0;
a=4;
b=4;
c=1;
D=b^2-4*a*c;
IF D>0 THEN GOTO DVAKORNYA;
IF D==0 THEN GOTO ODINKOREN;
IF D<0 THEN GOTO NETKORNEY;
LABEL DVAKORNYA: x1=((0-b)+D^(1/2))/(2*a);
x2=((0-b)+D^(1/2))/(2*a);
MSGBOX x1;
MSGBOX x2;
RETURN 0;
LABEL ODINKOREN: x1=(0-b)/(2*a);
MSGBOX x1;
RETURN 0;
LABEL NETKORNEY: MSGBOX 666;
RETURN 0;
Ну вот теперь реально все :-) Да, статья конечно получилась большая и достаточно сложная, но и тема не из легких. Не отчаивайся если сразу не понял как все работает, просто открой и исходник, просмотри порядок вызова функций, поэксперементируй, выясни что и для чего нужно, попробуй оптимизировать некоторые участки кода – и все станет на свои места. На этом все. Удачной тебе интерпретации!
- Просмотров: 2251
Версия для печати
#1 
Vanger |
Vanger |
Дата публикации: 27 марта 2009 00:27 | ICQ: --
цитировать
цитировать
#3 Vanger |
Vanger | 
исходник для статьи здесь:
http://coderszone.info/339-sam-sebe-interpretator.html
если интересуют исходники пхп - лучше погуглить, у нас на сайте их нет
исходник для статьи здесь:
http://coderszone.info/339-sam-sebe-interpretator.html
если интересуют исходники пхп - лучше погуглить, у нас на сайте их нет
http://coderszone.info/339-sam-sebe-interpretator.html
если интересуют исходники пхп - лучше погуглить, у нас на сайте их нет
исходник для статьи здесь:
http://coderszone.info/339-sam-sebe-interpretator.html
если интересуют исходники пхп - лучше погуглить, у нас на сайте их нет
Дата публикации: 19 августа 2009 14:00 | ICQ: --
цитировать
цитировать
а к этой - ни одного
я начал про пхп тут почитывать (ухаха, админ сервера, и только только начал пхп изучать). в пхп начиная с 4й версии применяется интерпретация кода для более оптимального его выполнения
исходники пхп должны быть открытыми, кому интересно - гляньте и сообщите что там да как, плз