Анализ выражений стал проще – Journal.stuffwithstuff.com

19 марта 2011 г.
код Джава js язык сорока анализ

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

Когда вы пишете парсер, рекурсивный спуск это так же просто, как намазать арахисовое масло. Превосходно, когда вы можете понять, что анализировать, основываясь на следующем фрагменте кода, который вы просматриваете. Обычно это справедливо на уровнях объявлений и операторов грамматики языка, поскольку большая часть синтаксиса там начинается с ключевых слов.class, if, for, whileи т. д.

Анализ становится сложнее, когда дело доходит до выражений. Когда дело доходит до инфиксных операторов, таких как +постфиксные, такие как ++и даже выражения миксфиксов, такие как
?:, может быть трудно определить, какое выражение вы анализируете, пока не пройдете половину процесса. Ты может сделайте это с помощью рекурсивного спуска, но это муторная работа. Вам придется писать отдельные функции для каждого уровня приоритета (например, в JavaScript их 17), вручную обрабатывать ассоциативность и размазывать грамматику по куче кода синтаксического анализа, пока ее не станет трудно увидеть.

Арахисовое масло и желе — секретное оружие

Анализ Пратта решает эту проблему. Если рекурсивный спуск — это арахисовое масло, то синтаксический анализ Пратта — это желе. Когда вы объедините их вместе, вы получите простой, краткий и читаемый парсер, который может обрабатывать любую грамматику, которую вы ему добавляете.

Техника Пратта для обработки приоритета операторов и инфиксных выражений настолько проста и эффективна, что остается загадкой, почему о ней почти никто не знает. После семидесятых анализаторы приоритета операторов сверху вниз, кажется, отпали от земли. Дуглас Крокфорд JSLint использует один для анализировать JavaScriptно его лечение является одним из очень мало отдаленно современные статьи об этом.

Я думаю, что отчасти проблема в том, что терминология Пратта неясна, а статья Крокфорда сама по себе довольно туманна. Пратт использует такие термины, как «нулевой знаменатель», а Крокфорд добавляет к ним дополнительные вещи, такие как отслеживание лексической области действия, которые скрывают основную идею.

Вот тут-то я и вступаю. Я не буду делать ничего революционного. Я просто попытаюсь понять основные концепции анализаторов приоритета операторов сверху вниз и представить их настолько ясно, насколько смогу. Я заменю некоторые термины, чтобы (надеюсь) прояснить ситуацию. Надеюсь, я не оскорблю чьи-либо пуристские чувства. Я буду писать код на Java, вульгарном латинском языке программирования. Я полагаю, что если вы можете написать это на Java, вы можете написать это на чем угодно.

Что мы будем делать

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

Несмотря на простоту Bantam, он имеет полный набор операторов: префикс (+,
-, ~, !), постфикс (!), инфикс (+, -, *, /, ^) и даже условный оператор миксфикса (?:). Он имеет несколько уровней приоритета и правые и левые ассоциативные операторы. Он также имеет присваивание, вызовы функций и круглые скобки для группировки. Если мы сможем проанализировать это, мы сможем проанализировать что угодно.

С чего мы начнем

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

Токен — это наименьший фрагмент значимого кода. У него есть тип и связанная с ним строка. Данный from + offset(time)токены будут:

NAME "from"
PLUS "+"
NAME "offset"
LEFT_PAREN "("
NAME "time"
RIGHT_PAREN ")"

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

class ConditionalExpression implements Expression {
  public ConditionalExpression(
      Expression condition,
      Expression thenArm,
      Expression elseArm) {
    this.condition = condition;
    this.thenArm   = thenArm;
    this.elseArm   = elseArm;
  }

  public final Expression condition;
  public final Expression thenArm;
  public final Expression elseArm;
}

(Вам должен понравиться уровень бюрократии Java «пожалуйста, подпишите в четырех экземплярах». Как я уже сказал, если вы можете терпеть это в Java, это может работать в любой
язык.)

Мы начнем с простого Парсер сорт. Анализатор владеет потоком токенов, обрабатывает упреждающий просмотр и предоставляет базовые методы, необходимые для написания анализатора рекурсивного спуска сверху вниз с одним токеном упреждающего просмотра (это
ЛЛ(1)). Этого достаточно, чтобы мы пошли. Если нам понадобится больше позже, его легко расширить.

Хорошо, давайте создадим себе парсер!

Перво-наперво

Несмотря на то, что «полный» парсер Пратта довольно мал, мне показалось, что его сложно расшифровать. Что-то вроде быстрая сортировка, реализация представляет собой обманчиво простую горстку глубоко переплетенного кода. Чтобы распутать его, мы будем выстраивать его шаг за шагом.

Простейшими выражениями для анализа являются префиксные операторы и выражения с одним токеном. Для них текущий токен сообщает нам все, что нам нужно сделать. В Bantam есть одно выражение с одним токеном: именованные переменные. Он имеет четыре префиксных оператора: +, -, ~и !. Самый простой код для их анализа:

Expression parseExpression() {
  if (match(TokenType.NAME))       // Return NameExpression...
  else if (match(TokenType.PLUS))  // Return prefix + operator...
  else if (match(TokenType.MINUS)) // Return prefix - operator...
  else if (match(TokenType.TILDE)) // Return prefix ~ operator...
  else if (match(TokenType.BANG))  // Return prefix ! operator...
  else throw new ParseException();
}

Но это немного монолитно. Как видите, мы отключаем TokenType, чтобы перейти к другому поведению синтаксического анализа. Давайте закодируем это напрямую, создав карту TokenTypes с фрагментами кода синтаксического анализа. Мы назовем эти фрагменты «парселетами», и они реализуют это:

interface PrefixParselet {
  Expression parse(Parser parser, Token token);
}

Реализация парселета для анализа имен переменных проста:

class NameParselet implements PrefixParselet {
  public Expression parse(Parser parser, Token token) {
    return new NameExpression(token.getText());
  }
}

Мы можем использовать один класс для всех префиксных операторов, поскольку они отличаются только самим токеном оператора:

class PrefixOperatorParselet implements PrefixParselet {
  public Expression parse(Parser parser, Token token) {
    Expression operand = parser.parseExpression();
    return new PrefixExpression(token.getType(), operand);
  }
}

Вы заметите, что он вызывает обратно в parseExpression() для анализа операнда, который появляется после оператора (например, для анализа a в -a). Эта рекурсия заботится о вложенных операторах, таких как -+~!a.

Вернувшись в Парсер, скованный if операторы заменяются картой:

class Parser {
  public Expression parseExpression() {
    Token token = consume();
    PrefixParselet prefix = mPrefixParselets.get(token.getType());

    if (prefix == null) throw new ParseException(
        "Could not parse \"" + token.getText() + "\".");

    return prefix.parse(this, token);
  }

  // Other stuff...

  private final Map<TokenType, PrefixParselet> mPrefixParselets =
      new HashMap<TokenType, PrefixParselet>();
}

Чтобы определить имеющуюся у нас грамматику — переменные и четыре префиксных оператора — мы добавим следующие вспомогательные методы:

public void register(TokenType token, PrefixParselet parselet) {
  mPrefixParselets.put(token, parselet);
}

public void prefix(TokenType token) {
  register(token, new PrefixOperatorParselet());
}

И теперь мы можем определить грамматику следующим образом:

register(TokenType.NAME, new NameParselet());
prefix(TokenType.PLUS);
prefix(TokenType.MINUS);
prefix(TokenType.TILDE);
prefix(TokenType.BANG);

Это уже улучшение по сравнению с анализатором рекурсивного спуска, поскольку наша грамматика теперь более декларативна, а не распределена по нескольким императивным функциям, и мы можем видеть реальную грамматику в одном месте. Более того, мы можем расширить грамматику, просто зарегистрировав новые парселеты. Нам не нужно менять сам класс Parser.

Если мы только если бы были префиксные выражения, мы бы уже закончили. Увы, мы этого не делаем.

Застрял в середине

То, что мы имеем до сих пор, работает только в том случае, если первый токен сообщает нам, какое выражение мы анализируем, но это не всегда так. С таким выражением, как a + bмы не знаем, что у нас есть выражение добавления, пока не проанализируем
a и добраться до +. Нам нужно расширить синтаксический анализатор, чтобы поддержать это.

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

Он будет анализировать -a и оставь нас сидеть +. Это именно тот токен, который нам нужен, чтобы указать, какое инфиксное выражение нам нужно проанализировать. По сравнению с анализом префиксов единственное изменение в анализе инфиксов состоит в том, что существует другое выражение. до инфиксный оператор, который инфиксный анализатор получает в качестве аргумента. Давайте определим синтаксический анализатор, который поддерживает это:

interface InfixParselet {
  Expression parse(Parser parser, Expression left, Token token);
}

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

Наличие отдельных таблиц для префиксных и инфиксных выражений важно, поскольку иногда у нас есть как префиксный, так и инфиксный синтаксический анализатор для одного и того же TokenType. Например, префикс парселет для ( обрабатывает группировку в выражении типа a * (b + c). Между тем, инфикс посылка для ( обрабатывает вызовы функций, например
a(b).

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

class Parser {
  public void register(TokenType token, InfixParselet parselet) {
    mInfixParselets.put(token, parselet);
  }

  public Expression parseExpression() {
    Token token = consume();
    PrefixParselet prefix = mPrefixParselets.get(token.getType());

    if (prefix == null) throw new ParseException(
        "Could not parse \"" + token.getText() + "\".");

    Expression left = prefix.parse(this, token);

    token = lookAhead(0);
    InfixParselet infix = mInfixParselets.get(token.getType());

    // No infix expression at this point, so we're done.
    if (infix == null) return left;

    consume();
    return infix.parse(this, left, token);
  }

  // Other stuff...

  private final Map<TokenType, InfixParselet> mInfixParselets =
      new HashMap<TokenType, InfixParselet>();
}

Довольно просто. Мы можем реализовать инфиксный синтаксический анализатор для операторов двоичной арифметики, например + вот так:

class BinaryOperatorParselet implements InfixParselet {
  public Expression parse(Parser parser,
      Expression left, Token token) {
    Expression right = parser.parseExpression();
    return new OperatorExpression(left, token.getType(), right);
  }
}

Инфиксные синтаксические анализаторы также работают для постфиксных операторов. Я называю их «инфиксными», но на самом деле это «не что иное, как префикс». Если перед токеном стоит какое-то ведущее подвыражение, то токен будет обрабатываться инфиксным синтаксическим анализатором. Сюда входят постфиксные выражения и миксфиксные выражения, такие как ?:.

Постфиксные выражения так же просты, как синтаксический анализ префиксов с одним токеном: они просто принимают left операнд и оборачивает его в другое выражение:

class PostfixOperatorParselet implements InfixParselet {
  public Expression parse(Parser parser, Expression left,
      Token token) {
    return new PostfixExpression(left, token.getType());
  }
}

Микфикс тоже прост. Это похоже на рекурсивный спуск:

class ConditionalParselet implements InfixParselet {
  public Expression parse(Parser parser, Expression left,
      Token token) {
    Expression thenArm = parser.parseExpression();
    parser.consume(TokenType.COLON);
    Expression elseArm = parser.parseExpression();

    return new ConditionalExpression(left, thenArm, elseArm);
  }
}

Теперь мы можем анализировать префиксные, постфиксные, инфиксные и даже миксфиксные выражения. Используя довольно небольшой объем кода, мы можем анализировать сложные вложенные выражения, такие как a + (b ? c! : -d). Мы закончили, да? Ну, почти.

Простите, тетя Салли.

Наш парсер может анализировать все это, но он не анализирует его с правильным приоритетом или ассоциативностью. Если ты бросишь a - b - c в парсере он будет анализировать вложенные выражения, такие как a - (b - c), что неправильно. (ну на самом деле это так верно— то есть ассоциативно. Нам нужно, чтобы это было левый.)

И это последний Шаг, на котором мы это исправляем, — это то, где парсеры Пратта превращаются из довольно хороших в совершенно радикальные. Мы внесем два простых изменения. Мы расширяем
parseExpression() взять приоритет— число, указывающее, какие выражения могут быть проанализированы этим вызовом. Если parseExpression() встречает выражение, приоритет которого ниже разрешенного, он прекращает анализ и возвращает то, что имело на данный момент.

Чтобы выполнить эту проверку, нам нужно знать приоритет любого данного инфиксного выражения. Мы позволим парселету указать это:

public interface InfixParselet {
  Expression parse(Parser parser, Expression left, Token token);
  int getPrecedence();
}

Используя это, наш основной анализатор выражений выглядит следующим образом:

public Expression parseExpression(int precedence) {
  Token token = consume();
  PrefixParselet prefix = mPrefixParselets.get(token.getType());

  if (prefix == null) throw new ParseException(
      "Could not parse \"" + token.getText() + "\".");

  Expression left = prefix.parse(this, token);

  while (precedence < getPrecedence()) {
    token = consume();

    InfixParselet infix = mInfixParselets.get(token.getType());
    left = infix.parse(this, left, token);
  }

  return left;
}

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

private int getPrecedence() {
  InfixParselet parser = mInfixParselets.get(
      lookAhead(0).getType());
  if (parser != null) return parser.getPrecedence();

  return 0;
}

Вот и все. Чтобы внедрить приоритет в грамматику Бантама, мы создали небольшую таблицу приоритетов:

public class Precedence {
  public static final int ASSIGNMENT  = 1;
  public static final int CONDITIONAL = 2;
  public static final int SUM         = 3;
  public static final int PRODUCT     = 4;
  public static final int EXPONENT    = 5;
  public static final int PREFIX      = 6;
  public static final int POSTFIX     = 7;
  public static final int CALL        = 8;
}

Чтобы наши операторы анализировали свои операнды с правильным приоритетом, они передают соответствующее значение обратно в parseExpression() когда они вызывают его рекурсивно. Например, БинарныйОператорПарселет экземпляр, который обрабатывает + оператор передает Precedence.SUM когда он анализирует свой правый операнд.

Ассоциативность тоже проста. Если инфиксный парселет вызывает parseExpression() с такой же приоритет, который он возвращает для себя getPrecedence() позвони, получишь левую ассоциативность. Чтобы быть правоассоциативным, ему просто нужно передать одним меньще чем это вместо этого.

Иди и умножай

Я переписал парсер для сороки используя это, и это сработало как шарм. Я также работаю над парсером JavaScript, использующим эту технику, и опять же, она мне очень подошла.

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

Чтобы убедиться в этом, просто взгляните на полная программа.