15.3.1 Описание простого алгоритмического языка
Рассмотрим более сложный пример реализации интерпретатора. Расширим язык
арифметических выражений в простой алгоритмический язык, который будет
содержать операторы: цикла, присваивания, печати, условного и составного. Ниже
приведена грамматика этого алгоритмического языка :
Анализ грамматики показывает, что правила с номерами 17-26 описывают
арифметические выражения. Кроме того правила 13-15 относятся также к классу
арифметических выражений и описывают операции отношения. Правила 1-11 описывают
операторы алгоритмического языка. Составной оператор необходим для объединения
нескольких операторов (правила 1-3). Условный оператор (правила 4- 6)
организует ветвления в программе. Оператор цикла (правило 6 ) предназначен для
многократного выполнения некоторой последовательности операторов. Оператор
печати обеспечивает печать строк символов и значения переменных. Ниже приведены
два примера программ на простом алгоритмическом языке:
| Таблица 15.2: Грамматика алгоритмического языка |
| 1 |
<Statement> => { <Statements> |
| 2 |
<Statements>=> <Statement> <Statements> |
| 3 |
<Statements> => } |
| 4 |
<Statement> => if (<Express>) <Statement> <Else> |
| 5 |
<Else> => else <Statement> | $ |
| 6 |
<Statement> => while( <Express> ) <Statement> |
| 7 |
<Statement> => <Ident> = <Express> |
| 8 |
<Express> => print <ListExpress> |
| 9 |
<ListExpress> => <Express> <ListExpress> |
| 10 |
<ListExpress> => ,<Express>< ListExpress> |
| 11 |
<ListExpress>=> $ |
| 12 |
|
| 13 |
<Express>=> <ExpressTest> < <Express> |
| 14 |
<Express>=> <ExpressTest> < <Express> |
| 15 |
<Express>=> <ExpressTest> |
| 16 |
|
| 17 |
<ExpressTest>=> <ExpressAdd> + <ExpressTest> |
| 18 |
<ExpressTest>=> <ExpressAdd> - <ExpressTest> |
| 19
|
<ExpressTest>=> <ExpressAdd> |
| 20 |
|
| 21 |
<ExpressAdd>=> <ExpressMult> * <ExpressAdd> |
| 22
|
<ExpressAdd>=> <ExpressMult> / <ExpressAddt> |
| 23 |
<ExpressAdd>=> <ExpressMult> |
| 24 |
|
| 25
|
<ExpressMult>=> (<ExpressTest>) |
| 26 |
<ExpressMult>=> sin <ExpressFunc> |
| 27
|
<ExpressMult>=> <Ident> |
| 28 |
<ExpressMult>=> <Const> |
Пример №1. Вычисление арифметической прогрессии
{
print "sum = 1 + 2+3+· · · + 500"
i=0
while(i < 500)
{
sum=sum+i
i=i+1
}
print "sum=",sum
}
15.3.2 Реализация интерпретатора
Для реализации воспользуемся интерпретатором арифметических выражений. И добавим
несколько дополнительных функций. Прежде всего это служебные функции skipchar и
eof. Описание функций приведено ниже.
//пропуск
символа во входной строке
void
skipchar() { if(*ch!=’\0’) ch++; }
//проверка достижения конца входной
строки
int eof() { return (*ch==’\0’); }
Добавим функцию ExpressTest, которая производит разбор выражения
с операциями отношения (больше ’>’, меньше ’<’, равно ’==’,
неравно ’!= ’). Кроме того, в каждую функцию, которая производит
разбор и вычисление, вводится параметр run. Этот параметр необходим
для указания выполнения или не выполнения вычислений. Если run равен
1, то вычисления производятся. Если нет, то не производятся.
Поскольку интерпретатор последовательно производит разбор исходного текста программы, то необходимо задать такой
механизм, когда вычисления производятся в зависимости от логики программы.
Поэтому введен параметр run, который указывает, когда надо производить
вычисления, а когда не надо. Параметр run устанавливается в следующих случаях:
при первоначальном запуске, при разборе условного оператора и оператора цикла.
Ниже приведен текст функции ExpressTest.
void
ExpressTest(int run) // вычисление выражения для операций отношения
{
double f1, f2;
ExpressAdd(run); //вычислить
значение первого операнда
while(1)
{
if(match(">")) //если больше
{
ExpressAdd(run); //вычислить
значение для второго операнда
if(run)
{
f2=Pull(); f1=Pull(); //взять
значения слагаемых из стека
Push(f1>f2); //положить сумму в
стек
}
}
else
if(match("<")) //если меньше
{
ExpressAdd(run);
//взять значение второго операнда
if(run)
{
f2=Pull(); f1=Pull(); //взять
значения из стека
Push(f1 < f2); //положить
разность в стек
}
}
else
if(match("==")) //если это равно
{
ExpressMult(run); //взять значение
второго операнда
if(run)
{
f1=Pull(); f2=Pull(); //взять
значения из стека
Push(f2==f1); //положить разность
в стек
}
}
if(match("!=")) //если не равно
{
ExpressMult(run); //взять значение
второго операнда
if(run)
{
f1=Pull(); f2=Pull(); //взять
значения из стека
Push(f2!=f1); //положить разность
в стек
}
}
else break;
}
}
Для разбора и выполнения оператора печати используется функция do_print. Текст этой функции приведен ниже. В
теле этого оператора записывается список, в котором через запятую перечисляются
строки символов или выражения. Строки символов ограниченны кавычками. Для
записи служебных символов используется обратная косая черта.
void do_print(int run)
{
double r;
while(1) //цикл пока не выведены все элементы списка
печати
{
if(match("\"")) //это строка символов
{
while(!eof())//пока не конец входной строки
{
if(*ch==’\"’) { ch++;
break;} //если это конец строки
if(*ch==’\\’) ch++; //если это обратная косая черта, то сдвинуть
if(run)
printf("%c",*ch);
//печать
ch++; //следующий символ
}
}
else
{
ExpressTest(run);//разобрать
выражение
if(run)
{
r=Pull();
printf("%g ",r); //печать значения
выражения
}
}
if(match(",")) continue; //продолжить, если список еще не пуст
break; //иначе выход
}
printf("\n");
}
Функция разбора условного оператора и выполнения. Правила выполнения просты: если run установлен в 1, то
разобрать и выполнить выражение условия. Если результат выражения не равен
нулю, то разобрать и выполнить операторы, следующие за закрывающей круглой
скобкой. В противном случае производится просто разбор. Если есть ключевое
слово else, то в зависимости от результата r, производится или не производятся
вычисления, разбор производится в любом случае.
void
do_if(int run)//разбор и выполнение оператора if
{
double r;
if(match("("))//разобрать и вычислить условное выражение
{
ExpressTest(run);
match(")");
if(run)//если выполнение установлено
{
r=Pull();
if(r!=0) Statement(1); else Statement(0);//выполнить или не выполнить в зависимости от
результата
}
else Statement(run); //разобрать без выполнения
if(match("else"))//если есть else
{
if(run) //выполнение включено
{
if(r==0) Statement(1); //если результат равен нулю, то выполнить оператор
else Statement(0);//иначе провести разбор без выполнения
}
else Statement(run);//провести разбор
}
}
}
Функция разбора и выполнения оператора цикла. Если параметр run установлен в ноль, то производится
синтаксический разбор оператора цикла. В противном случае производится разбор и
выполнение. Первоначально вычисляется условное выражение в скобках, далее в
зависимости от значения тело цикла разбирается и выполняется, или только
разбирается. В любом случае выход из цикла выполнения производится после
разбора тела цикла. Особую роль играет локальная переменная chv, которая хранит
значение указатель на текущий символ при входе в функцию. После разбора и
выполнения тела цикла необходимо восстановить текущий указатель на начало
цикла, это и обеспечивает переменная chv. Поскольку эта переменная локальная,
то возможно рекурсивное использование функции do_while. Рекурсия будет
организована если в исходном тексте программы будет несколько вложенных
операторов цикла.
void do_while(int run)
{
double r;
char
*chv=ch;
while(1)
{
if(match("("))//разобрать условие
{
ExpressTest(run);
match(")");
if(run)//выполнение включено
{
r=Pull();
if(r!=0)
{
Statement(1);//выполнить тело
цикла
ch=chv; //продолжить выполение
цикла
}
else //условие не выполенено
{
Statement(0); //разобрать тело
цикла без выполнения
break; //выход из цикла
}
}
else //разобрать тело цикла без выполнения
{
Statement(run);
break;
}
} //endif
}
//endwhile
}
Функция разбора и выполнения составного оператора.
void do_compaund(int run)
{
while(!eof())
{
if(match("}"))
break;
Statement(run);
}
}
Функция разбора всех операторов алгоритмического языка
void Statement(int run)
{
if(match("if")) do_if(run); //разобрать и выполнить условный оператор
else
if(match("while"))
do_while(run);//разобрать и выполнить оператор цикла
else
if(match("{"))
do_compaund(run);//разобрать и выполнить
составной оператор
else
if(match("print"))
do_print(run);//разобрать и выполнить
оператор печати
else
AssignOp(run);//разобрать и
выполнить оператор присваивания
}
Рассмотрим несколько примеров работы интерпретатора
1. Строка записи программы для вычисления арифметической прогрессии
char prog0[]
= "{ \ print
\"sum
= 1+2+3+...+500\"\ i=0
\ while(i<500)
{ \ sum=sum+i
\ i=i+1\
}\ print
\"sum=\",sum \ }";< /SPAN>
2. Строка записи программы вычисления корня квадратного
char prog1[]
= "{\ a=1
b=-7
c=10\
print
\”ax2
+ bx
+ c
= 0\”\ d=b*b-4*a*c\
if(d<0)
print
\" D<0
\”\ else
{\ x1=(-1*b+vd)/(2*a)
\ x2=(-1*b-vd)/(2*a)
\ print
\”x1
= \”, x1,
\”x2
= \”,
x < /SPAN> 2\ } }";
Программа для ввода команды или программы и вызова интерпретатора.
void
main()
{
TopVar=0; //инициализация стека и
таблицы переменных
TopStack=0;
while(1)
{
printf("end
- exitofprogramm\n\
tabl
- printtableofidentifair\n\
prog0
- runprogram
< SUM=1+2+3+...+500>\n\
prog1
- runprogram
< ax2
+ bc
+ c
= 0 >\n\
runinputstring\n");
printf("interpet>");
//вывод подсказки
gets(in_line);
//ввод строки символов
ch=&in_line[0];
//инициализация указателя разбора
if(match("end"))
//если это "end",
то завершение работы
break;
else
if(match("tabl"))
//если это "tabl",
то вывести таблицу символов
PrintTablVar();
else
if(match("prog0"))//выполнение первой программы
{
strcpy(in_line,prog0);
ch=&in_line[0];
Statement(1);
}
else
if(match("prog1"))//выполнение второй программы
{
strcpy(in_line,prog1);
ch=&in_line[0];
Statement(1);
}
else//иначе
вычислить значение выражения
Statement(1);
}
}