Test task for jetbrains internship. Project title: Code Insight For R Language
Необходимо реализовать интерпретатор языка, описанного ниже. На стандартный вход подается программа на данном языке. Необходимо вывести значение последнего выражения в программе в десятичной системе счисления
Используйте один терминал для всех имен переменных и имен типов.
<character>
::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" | "_"
<digit>
::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<number>
::= <digit> | <digit> <number>
<identifier>
::= <character> | <identifier> <character>*
<operation>
::= "+" | "-" | "" | "/" | "%" | ">" | "<" | "="
<constant-expression>
::= "-" <number> | <number>
<binary-expression>
::= "(" <expression> <operation> <expression> ")"
<argument-list>
::= <expression> | <expression> "," <argument-list>
<call-expression>
::= <identifier> "(" <argument-list> ")"
<if-expression>
::= "[" <expression> "]?(" <expression> "):("<expression>")"
<expression>
::= <identifier> | <constant-expression> | <binary-expression> | <if-expression> | <call-expression>
<parameter-list>
::= <identifier> | <identifier> "," <parameter-list>
<function-definition>
::= <identifier>"(" <parameter_list> ")" "={" <expression> "}"
<function-definition-list>
: "" | <function-definition> <EOL> | <function-definition> <EOL> <function-definition-list>
<program>
::= <function-definition-list> <expression>
<EOL>
- символ перевода строки --- \n
, программа не содержит других пробельных символов(пробел, табуляция, и т.д.);
- Все переменные имеют тип 32-битный Integer;
- Гаранитруется, что вычисления не приводят к переполнению;
- Все арифметические операции аналогичны соответствующим операциям для 32-битного int в языка Java;
- Операции сравнения возвращают 1 если сравнение истинно и 0 если ложно;
- исполняет второе выражение, если первое выражение не равно 0; иначе исполняет третье;
- вызывает функцию с соответствующим именем;
- Выражение вычисляются слева направо;
- Калькулятор: На вход подается корректная программа без
<if-expression>
, у которой<function-definition-list>
пустой.
Пример: (2+2)
Ответ:4
Пример:(2+((3*4)/5))
Ответ:4 - Поддержка
<if-expression>
: в программе присутствуют<if-expression>
Пример:[((10+20)>(20+10))]?{1}:{0}
Ответ:0 - Поддержка функций:
<function-definition-list>
не пустой
Пример:
g(x)={(f(x)+f((x/2)))}
f(x)={[(x>1)]?{(f((x-1))+f((x-2)))}:{x}}
g(10)
Ответ:60 - Обработка ошибок:
-
Если программа не соответствует грамматике необходимо вывести:
SYNTAX ERROR
-
Если в программе используется неопределенная переменная необходимо вывести:
PARAMETER NOT FOUND <name>:<line>
здесь и далее<name>
и<line>
это ошибочное имя и номер строки на которой произошла ошибка -
Если программа вызывает функцию с неизвестным именем, то необходимо вывести:
FUNCTION NOT FOUND <name>:<line>
-
Если программа вызывает функцию с неверным числом аргументов, то необходимо вывести:
ARGUMENT NUMBER MISMATCH <name>:<line>
-
Если произошла ошибка выполнения необходимо, то вывести:
RUNTIME ERROR <expression>:<line>
<expression>
--- выражение в котором произошла ошибка.
Пример: 1 + 2 + 3 + 4 + 5
Ответ:SYNTAX ERROR
Пример:
f(x)={y}
f(10)
Ответ:
PARAMETER NOT FOUND y:1
Пример:
g(x)={f(x)}
g(10)
Ответ:
FUNCTION NOT FOUND f:1
Пример:
g(x)={(x+1)}
g(10,20)
Ответ:
ARGUMENT NUMBER MISMATCH g:2
Пример:
g(a,b)={(a/b)}
g(10,0)
Ответ:
RUNTIME ERROR (a/b):1
Представленная в задании грамматика имеет одно лишние правило. Так же грамматика содержит правое ветвление а значит по следствию из теоремы о связи LL(1)-грамматики с множествами FIRST и FOLLOW она не является LL(1)-грамматикой. Чтоб избавиться от правого ветвления воспользуем алгоритмом леой факторизации. Я не буду пошагово описывать процесс сведения, а лишь укажу результат сведения.
<character>
::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" | "_"
<digit>
::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<cont-number>
::= "" | <digit> <cont-number>
<number>
::= <digit> <cont-number>
<cont-identifier>
::= "" | <character> <cont-identifier>
<identifier>
::= <character> <cont-identifier>
<operation>
::= "+" | "-" | "*" | "/" | "%" | ">" | "<" | "="
<constant-expression>
::= "-" <number> | <number>
<binary-expression>
::= "(" <expression> <operation> <expression> ")"
<cont-argument-list>
::= "" | "," <expression> <cont-argument-list>
<argument-list>
::= <expression> <cont-argument-list>
<call-expression>
::= "" | "(" <argument-list> ")"
<if-expression>
::= "[" <expression> "]?(" <expression> "):("<expression>")"
<expression'>
::= <constant-expression> | <binary-expression> | <if-expression>
<expression>
::= <identifier> <call-expression> | <expression'>
<function-body>
::= "" | "={" <expression> "}" <EOL> <program>
<other-args'>
::= ")" | "," <args>
<other-args>
::= ")" <function-body> | "," <args-or-params>
<call-or-other'>
::= "<other-args'> | "(" <argument-list> ")" <other-args'>
<call-or-other>
::= "<other-args> | "(" <argument-list> ")" <other-args'>
<args>
::= <identifier> <call-or-other'> | <expression'> <other-args'>
<args-or-params>
::= <identifier> <call-or-other> | <expression'> <other-args'>
<cont-program>
::= "" | "("<args-or-params>
<program>
::= <identifier> <cont-program> | <expression'>
<EOL>
- символ перевода строки --- \n
, программа не содержит других пробельных символов(пробел, табуляция, и т.д.);
<identifier>
и <number>
будут считаться терминалами, с соответствующими регулярными выражениями
<identifier>
::= [a-zA-Z_]+
<number>
::= [0-9]+
Так же введем обозначение OP
, которому будет соответсвовать все возможные операции
Нетерминал | Описание | FIRST | FOLLOW |
---|---|---|---|
<program> |
Программа | <identifier> ,<number> , - , [ , ( |
$ |
<cont-program> |
Продолженеи программы | eps , ( |
$ |
<args-or-params> |
Аргумент или параметр функции(в зависимости от того вызов функции или объявление) | <identifier> ,<number> , - , [ , ( |
$ |
<args> |
Аргумент функции | <identifier> ,<number> , - , [ , ( |
$ |
<call-or-other> |
Описание аргументов функции текущего аргумента | ) , , , ( |
$ |
<call-or-other'> |
Описание аргументов функции текущего аргумента(случай когда уже не может быть описание функции) | ) , , , ( |
$ |
<other-args> |
Следующие арументы или параметры функции(в зависимости от того вызов функции или объявление) | ) , , |
$ |
<other-args'> |
Следующие аргументы функции | ) , , |
$ |
<function-body> |
Список параметров функции | eps , = |
$ |
<expression> |
Выражение | <identifier> ,<number> , - , [ , ( |
$ , } , ] , , , OP , ) |
<expression'> |
Выражение | <number> , - , [ , ( |
$ , } , ] , , , OP , ) |
<if-expression> |
Условный оператор | [ |
$ , } , ] , , , OP , ) |
<call-expression> |
Вызов функции | ( , eps |
$ , } , ] , , , OP , ) |
<argument-list> |
Список аргументов передаваемых в функцию | <identifier> ,<number> , - , [ , ( |
) |
<cont-argument-list> |
Продолжение списка аргументов передаваемых в функцию | , , eps |
) |
<binary-expression> |
Бинарная операция над двумя выражениями | ( |
$ , } , ] , , , OP , ) |
<constant-expression> |
Число | <number> , - |
$ , } , ] , , , OP , ) |
<operation> |
Бинарная операция | OP |
<identifier> ,<number> , - , [ , ( |