Рекурсивный синтаксический анализ парсера

Ответ 1

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

Итак, в вашем случае, как вы упомянули выше, у вас будут процедуры: S(), L() и E(), я приведу пример того, как L() можно реализовать, а затем вы можете попробовать и сделать S() и E() самостоятельно.

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

/**
 * This procedure corresponds to the L non-terminal
 * L -> 'end'
 * L -> ';' S L
 */ 
public void L()
{
   if(currentToken == 'end')
   {
      //we found an 'end' token, get the next token in the input stream
      //Notice, there are no other non-terminals or terminals after 
      //'end' in this production so all we do now is return
      //Note: that here we return to the procedure that called L()
      getNextToken();
      return; 
   } 
   else if(currentToken == ';')
   {
      //we found an ';', get the next token in the input stream
      getNextToken();
      //Notice that there are two more non-terminal symbols after ';'
      //in this production, S and L; all we have to do is call those
      //procedures in the order they appear in the production, then return
      S();
      L();
      return;
   }
   else
   {
      //The currentToken is not either an 'end' token or a ';' token 
      //This is an error, raise some exception
      throw new IllegalTokenException(
          "Procedure L() expected an 'end' or ';' token "+
          "but received: " + currentToken);
   }
}

Теперь вы можете попробовать S() и E(), а затем вернуться назад.

Также как Кристофер указывает, что в вашей грамматике есть что-то, называемое болтающимся другим, что означает, что у вас есть постановка, которая начинается с одной и той же вещи, до точки:

S -> if E then S 
S -> if E then S else S

Итак, возникает вопрос, видит ли ваш синтаксис маркер "если", и какое производство следует выбрать для обработки ввода? Ответ заключается в том, что он не имеет понятия, какой из них выбрать, потому что в отличие от людей компилятор не может смотреть вперед во входной поток для поиска токена "еще". Это простая проблема для исправления, применяя правило, известное как Left-Factoring, очень похожее на то, как вы решаете проблему алгебры.

Все, что вам нужно сделать, это создать новый нетерминальный символ S '(S-prime), правая сторона которого будет содержать фрагменты нестандартных производств, поэтому ваши тэги S no:/p >

S  -> if E then S S'
S' -> else S 
S' -> e   
(e is used here to denote the empty string, which basically means there is no   
 input seen)

Ответ 2

Это не самая простая грамматика, потому что у вас есть неограниченное количество взглядов на ваше первое производственное правило:

S -> if E then S | if E then S else S |  begin S L | print E

рассмотрим

if 5 then begin begin begin begin ...

Когда мы определяем это глупое другое?

рассмотрим

if 5 then if 4 then if 3 then if 2 then print 2 else ...

Теперь, что else должен связываться с фрагментом if 5 then? Если нет, это действительно здорово, но явное.

Вы можете переписать свою грамматику (возможно, в зависимости от правила else) так же, как:

S -> if E then S (else S)? | begin S L | print E
L -> end | ; S L
E -> i

Что может быть или не быть тем, что вы хотите. Но псевдокод рода выскакивает из этого.

define S() {
  if (peek()=="if") {
    consume("if")
    E()
    consume("then")
    S()
    if (peek()=="else") {
      consume("else")
      S()
    }
  } else if (peek()=="begin") {
    consume("begin")
    S()
    L()
  } else if (peek()=="print") {
    consume("print")
    E()
  } else {
    throw error()
  }
}

define L() {
  if (peek()=="end") {
    consume("end")
  } else if (peek==";")
    consume(";")
    S()
    L()
  } else {
    throw error()
  }
}

define E() {
  consume_token_i()
}

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

Перевод с псевдокода на реальный код не слишком сложный, но он не является тривиальным. Возможно, на самом деле они не работают на струнах. Гораздо проще работать с токенами. И просто ходить предложение и потреблять это не совсем так же, как разбор его. Вы захотите что-то сделать, поскольку вы потребляете кусочки, возможно, создавая дерево синтаксического анализа (что означает, что эти функции, вероятно, возвращают что-то). И выброс ошибки может быть правильным на высоком уровне, но вы хотите поместить в сообщение какую-то значимую информацию. Кроме того, все становится более сложным, если вам требуется просмотр.

Я бы порекомендовал шаблоны языковой реализации Terence Parr (парень, который написал antlr, рекурсивный генератор парсетов спуска) при рассмотрении этих проблем. Книга Дракона (Aho, et al, рекомендованная в комментарии) тоже хороша (это, вероятно, доминирующий учебник в курсах компилятора).

Ответ 3

Я преподавал (действительно, помогал) раздел синтаксического анализа в классе PL в прошлом семестре. Я действительно рекомендую посмотреть слайды разбора на нашей странице: здесь. В принципе, для анализа рекурсивного спуска вы задаете себе следующий вопрос:

Я проанализировал немного нетерминала, теперь я нахожусь в точке, где я могу сделать выбор в отношении того, что я должен анализировать дальше. То, что я вижу дальше, будет принимать решения относительно того, к чему я не вернусь.

Ваша грамматика - кстати - демонстрирует очень распространенную двусмысленность, называемую "болтающимся другим", которая существует со времен Алгола. В смену парсеров (обычно создаваемых генераторами парсера) генерируется конфликт сдвига/уменьшения, в котором вы обычно выбираете произвольный сдвиг вместо сокращения, предоставляя вам общую "максимальную значимость". (Итак, если вы видите "if (b), то if (b2) S1 else S2" вы читаете его как "if (b) then {if (b2) {s1;} else {s2;}}" )

Бросьте это из своей грамматики и работайте с чуть более простой грамматикой:

T -> A + T
 |   A - T
 |   A
A -> NUM * A
   | NUM / A
   | NUM

мы также будем предполагать, что NUM - это то, что вы получаете от lexer (т.е. это просто токен). Эта грамматика LL (1), т.е. Вы можете анализировать ее с помощью рекурсивного парсера спуска, реализованного с использованием наивного алгоритма. Алгоритм работает следующим образом:

parse_T() {
  a = parse_A();
  if (next_token() == '+') {
    next_token();  // advance to the next token in the stream
    t = parse_T();
    return T_node_plus_constructor(a, t);
  }
  else if (next_token() == '-') {
    next_token();  // advance to the next token in the stream
    t = parse_T();
    return T_node_minus_constructor(a, t);
  } else {
    return T_node_a_constructor(a);
  }
}
parse_A() {
  num = token(); // gets the current token from the token stream
  next_token();  // advance to the next token in the stream
  assert(token_type(a) == NUM);
  if (next_token() == '*') {
    a = parse_A();
    return A_node_times_constructor(num, a);
  }
  else if (next_token() == '/') {
    a = parse_A();
    return A_node_div_constructor(num, a);
  } else {
    return A_node_num_constructor(num);
  }
}

Вы видите шаблон здесь:

для каждого нетерминала в вашей грамматике: проанализируйте первое, а затем посмотрите, что вы должны посмотреть, чтобы решить, что вы должны разборки. Продолжайте это, пока не закончите!

Кроме того, обратите внимание, что этот тип разбора обычно не создает то, что вы хотите для арифметики. Рекурсивные партизаны спуска (если вы не используете небольшой трюк с хвостовой рекурсией?) Не будут давать левые деривации. В частности, вы не можете писать левые рекурсивные правила, такие как "a → a - a", где самая левая ассоциативность действительно необходима! Вот почему люди обычно используют инструменты генератора парсеров. Но рекурсивный спуск-трюк все еще стоит знать и играть с ним.