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

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

Считыватель символов / считыватель ввода

Основная цель абстракции средства чтения символов - иметь поставщик символов, который не зависит от типа ввода. Таким образом, лексер может просто полагаться на методы peek () / consumer () для предоставления символов, необходимых для создания токенов.

Однако, наряду с методом peek(), возникает еще одно требование в отношении реализации этих методов. То есть, чтобы облегчить _2 _ / _ 3_, считыватель символов должен иметь возможность отслеживать символы, которые были просмотрены вперед, не отбрасывая их, и должен иметь возможность предоставить их снова при вызове другого метода peek() или consume(). Другими словами, программа чтения символов должна сохранять в памяти просмотренные символы. Этого можно добиться двумя способами:

  • Читатель в памяти
  • Читатель потока

Читатель в памяти

Прочтите весь ввод сразу и сохраните его как большой массив символов / буфер. Поддерживайте индекс, чтобы указать позицию последнего использованного символа (скажем, i). Когда,

  • peek(k), верните (i + k) -й символ из буфера.
  • consume(k), верните (i + k) -й символ из буфера. И сделайте i = i + k.

Это довольно просто реализовать. Но он потребляет много памяти, так как весь исходный код загружается в память сразу.

Читатель потока

Использует кольцевой буфер (емкостью N) для хранения только выбранных символов. Не считывает весь исходный код в память. Сохраняет размер буфера (скажем, n) и начальную позицию буфера (скажем, i),

Когда вызывается peek(k),

  • Если k ‹n, это означает, что k-й символ находится в буфере. Затем верните k-й символ из буфера.
  • Если k≥n, это означает, что k-й символ отсутствует в буфере. Считайте до k-го символа и добавьте его в буфер. Поскольку в буфере уже находится n символов, будет прочитано общее k-n символов. Затем верните k-й символ из буфера.

Когда вызывается consume(k), просто верните k- -й элемент из i- -го места буфера, и обновить i до индекса возвращаемого элемента.

Этот подход очень эффективен с точки зрения памяти, поскольку он сохраняет в памяти не более k (≤n) символов на заданное время. Однако емкость буфера N необходимо отрегулировать и зафиксировать в зависимости от того, сколько символов потребуется лексеру для просмотра. например: если лексер просматривает не более 5 символов, то для N можно установить значение 5 (или больше). Если вы не уверены, сколько символов будет просматривать лексер, можно на всякий случай установить какое-нибудь большое значение, например 20, 100 или даже 500, в зависимости от реализации лексера.

Лексер

Лексер обычно представляет собой конечный автомат. Он начинается с начального состояния. Затем, в зависимости от первого встречного символа, лексический анализатор изменяет состояние и продолжает работать с / lex в этом состоянии, пока не достигнет конца состояния. Способы производства токенов различаются от штата к штату.

Например, рассмотрим набор символов «Hello, world!». Lexer запускается в режиме «по умолчанию», где запятая ( ,) - это одиночный токен, пробел - это конец токена, а восклицательный знак - это токен оператора. Когда лексер достигает первых двойных кавычек, он переходит в состояние «строковый литерал», где запятые, пробелы и все другие символы (кроме двойных кавычек) также считаются частью токена. . Однако режим строкового литерала заканчивается, когда он достигает второй двойной кавычки и завершает обработку этого строкового литерала. Затем лексический анализатор выдает этот строковый литерал как токен и затем возвращается в режим по умолчанию.

Соответствующий код для приведенного выше лексера будет выглядеть так:

Выпуск токена

Лексер играет две подроли во время лексирования / токенизации. Один из них - Сканирование, а второй - Оценка. Сканирование - это часть, которую мы обсуждали в предыдущем разделе, где лексер проверяет / просматривает входные символы и определяет соответствие грамматического правила. Затем, в зависимости от содержимого отсканированных символов, он выдает соответствующий токен. Токен не только состоит из содержимого символа, но и имеет связанный с ним тип / вид. Как правило, токены, выдаваемые лексером, делятся на четыре основные категории:

  • Ключевые слова - предопределенный набор имен (идентификаторов), известных лексеру и синтаксическому анализатору.
  • Идентификаторы - имена, значения которых являются динамическими.
  • Литералы - строковые литералы, числовые литералы и т. д. Значения являются динамическими.
  • Токены синтаксиса - предопределенный набор токенов, таких как разделители, арифметические операторы и т. д., например: {,}, [, +, -, (,)

Смотреть вперед

Бывают ситуации, когда лексер не может определить, какое правило лексера обрабатывать, просто глядя только на следующий символ. Одним из примеров в java является оператор «больше чем» (›), оператор сдвига вправо со знаком (››) и оператор сдвига вправо без знака (›››). Когда лексер достигает первого символа «› », он не может просто определить, какой из трех токенов он будет обрабатывать. Чтобы определить это, лексер должен проверить второй символ. Если вторым символом не является «› », то он может завершиться, предполагая, что это оператор« больше ». Если вторым символом также является «› », то он также должен проверить третий символ.

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

Обработка пробелов

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

  • Присоединить пробел к ближайшему следующему токену - каждый токен будет иметь ведущие пробелы. Любые пробелы в конце файла будут прикреплены к токену EOF.
  • Прикрепить пробелы к последнему обработанному токену - у каждого токена будут только конечные пробелы. Требуется специальный токен начала файла (SOF) для захвата пробелов в начале файла.
  • Разделите пробелы и прикрепите их как к последнему обработанному токену, так и к следующему непосредственному токену - токен может иметь как начальные, так и конечные пробелы. Как правило, первая новая строка после токена завершает конечный пробел (конечные пробелы не могут содержать символы новой строки). Однако ведущие пробелы могут содержать символы новой строки.

Парсер

Есть два основных подхода к синтаксическому анализу:

  • Нисходящий синтаксический анализ - анализирует ввод путем поиска правил формальной грамматики сверху вниз. Другими словами, сначала определяется высокоуровневая структура ввода, прежде чем анализировать ее дочерние элементы. Например, при синтаксическом анализе элемента верхнего уровня файла синтаксический анализатор сначала решает, какой элемент он будет анализировать (например, является ли это определением функции или определением переменной). Только тогда он начинает синтаксический анализ дочерних элементов этого элемента верхнего уровня. При нисходящем синтаксическом анализе сначала сопоставляется крайний левый вывод грамматической продукции. Таким образом, токены потребляются и сопоставляются слева направо. Анализаторы LL (L слева направо, L крайнее производное) являются примерами синтаксических анализаторов сверху вниз.
  • Анализ снизу вверх - анализатор сначала пытается проанализировать листовые узлы, а затем, в зависимости от этих проанализированных узлов, выбирает родительский и анализирует его. При восходящем синтаксическом анализе сначала сопоставляется самый правый вывод грамматической продукции. Анализаторы LR (L слева направо, R крайнее правое происхождение) являются примерами синтаксических анализаторов снизу вверх.

Построение дерева синтаксического анализа может осуществляться как сверху вниз, так и снизу вверх в обоих этих подходах.

Оба парсера LL и LR обычно обозначаются связанным с ним числом, например LL (1), LR (1), LL (k) и т. Д. Это число (обычно 'k') означает количество просмотров вперед, используемых анализатором (аналогично лексеру). То есть, взяв, например, синтаксический анализ сверху вниз, синтаксическому анализатору необходимо предварительно просмотреть некоторые токены, чтобы определить, какой узел верхнего уровня он должен анализировать. В этой статье я сосредоточусь на синтаксическом анализе LL, поскольку они, как правило, намного проще по сравнению с синтаксическими анализаторами снизу вверх.

LL (k) Парсеры с рекурсивным спуском

Анализаторам LL необходимо проверить некоторые токены в будущем, чтобы решить, какое правило грамматики будет обрабатывать, когда есть альтернативные правила. Иногда это количество токенов для опережающего просмотра является постоянным. В таких случаях число записывается как числовое значение. Однако для большинства парсеров это значение зависит от правила грамматики и текущего ввода (т.е. зависит от контекста) и не может быть определено заранее. Такие парсеры используют произвольный k, который обозначается как LL (k) или LR (k).

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

например: метод AparseExpression() может вызывать метод parserBinaryExpression(), если текущее обрабатываемое выражение является двоичным выражением (например: a+b). Но поскольку и RHS, и LHS двоичного выражения снова являются своего рода выражением, parserBinaryExpression() будет вызовите parseExpression() внутри, создав рекурсию. См. Ниже образец кода:

Expression parseExpression() {
   ...
   if (binaryExpr) {
      parseBinaryExpression();
   }
   ...
}
Expression parseBinaryExpression() {
   lhsExpr = parseExpression();
   binaryOp = parseBinaryOp();
   rhsExpr = parseExpression();
   ...
}

Прогнозирование и отслеживание с возвратом

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

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

Грамматические требования

При реализации логики синтаксического анализа для правила грамматики в анализаторе с предсказанием рекурсивного спуска LL (k) грамматика должна удовлетворять следующим условиям:

  1. Не должно быть леворекурсивным

Если правило грамматики леворекурсивное, его необходимо переписать таким образом, чтобы исключить леворекурсию. например:

binary-expr := expression binary-operator expression
expression := binary-expr | basic-literal | . . .

Здесь правило двоичного выражения остается рекурсивным, поскольку левая часть продукции (левая часть двоичного оператора) снова может быть другим двоичным выражением. Поэтому, если мы попытаемся реализовать это, наши функции синтаксического анализа в конечном итоге застрянут в бесконечной рекурсии. Чтобы избежать этого, необходимо исключить левую рекурсию правила грамматики. Это можно сделать, переписав приведенное выше правило как:

binary-expr := terminal-expression binary-operator expression
terminal-expression := basic-literal | var-ref | func-call | . . .
expression := binary-expr | terminal-expression | . . .

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

2. Должен быть линейным

Обратите внимание на приведенное ниже правило грамматики.

function := func-def | func-decl
func-def := functionSig ‘{‘ statements ‘}’
func-decl:= functionSig ‘;’

Здесь оба func-def и func-decl имеют общий компонент functionSig . Проблема с такими правилами заключается в том, что во время синтаксического анализа синтаксический анализатор сначала пытается сопоставить источник с func-def, а если это не удается, он пытается сопоставить его в func-decl. Однако во время этого процесса functionSig будет пройден дважды. Этого можно избежать, переписав правило грамматики таким образом, чтобы общие произведения были исключены из альтернативных правил. например:

function := functionSig (func-body | ‘;’)
func-body := ‘{‘ statements ‘}’

Таблица парсера

Теоретически вы бы слышали, что предиктивные синтаксические анализаторы LL (k) основаны на таблице синтаксического анализа, и нам нужно будет построить таблицу синтаксического анализа. Таблица синтаксического анализа просто определяет, какой символ ожидать и какое следующее правило следует соблюдать, в зависимости от грамматики. Анализатор следует / просматривает эту таблицу, чтобы определить, какой токен анализировать.

Однако на практике таблица парсера нам вообще не нужна! Это может показаться немного спорным, но на то есть несколько причин:

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

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

Expression parseBinaryExpression() {
   lhsExpr = parseExpression();
   binaryOp = parseBinaryOp();
   rhsExpr = parseExpression();
   ...
}

Здесь ожидаемые токены и их порядок встроены в логику самого метода parseBinaryExpression(). Ему больше не нужна помощь таблицы синтаксического анализа.

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