Создание парсера для простого языка псевдокодов?

Question

Я хотел сделать простой синтаксический анализатор для языка, подобного «псевдокоду» (оставаясь жестким), в Java. Пример псевдокода будет -

//This is a comment
$x1 = readint
$x2 = readint

$dx = $x2 - $x1
#f = $dx / 2

if ($dx > 0)
{
  loop while(#f > 1)
  {
     print(#f)
     #f = #f / 2
  }
}

Обратите внимание, что приведенный выше код является жестким в том смысле, что в строке не может быть более одного оператора, целые числа начинаются с $, числа с плавающей запятой начинаются с # и т. Д.

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

Этот подход хорош? Для операторов в цикле, как я могу хранить выражения, чтобы мне не приходилось токенизировать в каждой итерации?

Я мог бы подумать о преобразовании выражений (например, #f = #f / 2) в блочную нотацию, а затем о сохранении в стеке. И в каждой итерации, при выталкивании операндов я мог заменить значение для каждой переменной. Но достаточно ли это эффективно?

Заранее спасибо за любые предложения.

Answer 1

Хотя я думаю, что здорово, что вы хотите создать парсер для такого языка, сделать это гораздо сложнее, чем кажется. Синтаксический анализ - это очень хорошо изученная проблема, и есть много отличных алгоритмов, которые вы можете использовать, но их чрезвычайно сложно реализовать вручную. Хотя вы можете использовать приемы, такие как преобразование в RPN, для небольших примеров, таких как синтаксический анализ выражений, для создания полноценного языка программирования требуется гораздо более сложный набор приемов.

Чтобы разобрать язык такой сложности, вам, вероятно, лучше использовать генератор синтаксического анализа, а не пытаться писать свой собственный вручную. ANTLR и Java CUP - два хорошо известных инструмента для выполнения именно того, что вам интересно, и я настоятельно рекомендую использовать один из них.

Надеюсь, это поможет!

Answer 2

Для простых языков (это вызов для суждения, и, если вы неопытны, вы не сможете сделать этот вызов правильно), часто можно написать анализатор рекурсивного спуска вручную, что достаточно хорошо. Хорошей новостью является то, что кодирование синтаксического анализатора рекурсивного спуска довольно просто .

Если вы не уверены, используйте overkill в форме самого сильного генератора парсеров, который вы можете получить.

Answer 3

В простых случаях запись парсера вручную имеет смысл.

Однако использование StringTokenizer является показателем неправильной работы, поскольку StringTokenizer уже ПРОСТОЙ парсер.

парсер обычно читает символ и изменяет его состояние в зависимости от значения этого символа.

Просто простой синтаксический анализатор, a "b" делает следующий символ в верхнем регистре, e в нижний регистр. "" останавливается

 String input = "aDDbcDDeaaef.";

 int pos = 0;

 int state = 0;  
 while (pos < input.length()) {
    char z = input.charAt (pos);
    if (z == '.') break;
    switch (z) {
    case 'b': state = 1; break;
    case 'e': state = 0; break;
    default:
      if (state == 0) {
        System.out.print(Char.toLowerCase(z));
      } else {
        System.out.print(Char.toUpperCase(z));
      }
    }
    pos ++;
 }