Парсеры для чайников

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

Что такое лексинг?

Это процесс разделения строки на слова (лексемы).

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

Что такое синтаксический разбор?

Это процесс обработки текста. В нашем случае это программа, которая каким-то образом понимает грамматику фактической строки.

Группы парсеров

Для начала давайте разделим парсеры на две большие группы

Рукописные парсеры — парсеры, которые вы пишете вручную.

Примеры:

• рекурсивные парсеры

Автоматически генерируемые — существуют генераторы парсеров, эти инструменты могут взять грамматику вашего языка и выдать результат.

Примеры:

• LR(K): SLR(1) LALR(1)
• GLR
• PEG

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

Типичным примером контекстно-зависимых элементов являются так называемые мягкие ключевые слова, то есть строки, которые в определенных местах могут считаться ключевыми словами, но в остальных случаях могут использоваться как идентификаторы.

Язык и грамматика

Давайте создадим наш новый язык:

Алфавит: Σ = {x,y} (набор символов).
Язык: L(Σ) = {x, y, xx, xy ... }.

Таким образом, язык — это также набор некоторых случайных комбинаций двух символов из алфавита.

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

Формальная грамматика

G = (N, T, P, S)

Давайте рассмотрим пример и попробуем применить наши новые знания о грамматике.

⭢ другими словами, означает «можно определить как».

S ⭢ xZ
Z ⭢ y

Итак, давайте начнем читать это как предложение:

• Начальный символ (S) is может быть определен как xZ
• где x — терминал, а Z — нетерминал.
• После этого рассмотрим вторую постановку (Z ⭢ y).
• Сделаем подстановку или применим деривацию

S ⭢ xZ ⭢ xy

Деривация — последовательность правил производства, чтобы получить входную строку.

Контекстно-свободные грамматики

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

• Только нетерминалы на LHS (левой стороне)
• Отсутствие контекста на LHS
• RHS: смесь нетерминалов и терминалов.

БНФ-нотация

Такие обозначения рассматриваются как БНФ-нотации

S : xZ
Z : y

или они могут выглядеть примерно так:

<postal-address> ::= <name-part> <street-address> <zip-part>

      <name-part> ::= <personal-part> <last-name> <opt-suffix-part> <EOL> | <personal-part> <name-part>

  <personal-part> ::= <initial> "." | <first-name>

 <street-address> ::= <house-num> <street-name> <opt-apt-num> <EOL>

       <zip-part> ::= <town-name> "," <state-code> <ZIP-code> <EOL>

<opt-suffix-part> ::= "Sr." | "Jr." | <roman-numeral> | ""
    <opt-apt-num> ::= <apt-num> | ""

Процесс производных

Последовательность подстановки для получения фактической строки. Давайте рассмотрим этот вид грамматики.

E : E + E
  | E * E
  | number

| — означает или

Начнем процесс деривации:

E ⇒ E + E
  ⇒ number + E
  ⇒ number + E * E
  ⇒ number + number * E
  ⇒ number + number * number
  ⇒ 2 + 5 * 3

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

E ⇒ E + E
  ⇒ E + E * E
  ⇒ E + E * number
  ⇒ E + number * number
  ⇒ number + number * number
  ⇒ 2 + 5 * 3

Самая левая деривация используется при разборе LL и рекурсивном приличном разборе.

С другой стороны, правая деривация может быть более мощной и охватывать более сложные языки (LR-разбор).

Деревья разбора

Дерево разбора — это представление кода, приближенное к конкретному синтаксису. Оно показывает многие детали реализации синтаксического анализатора. Например, каждому правилу обычно соответствует определенный тип узла.

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

А в случае самой правой деривации мы получим следующий результат:

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

Неоднозначные грамматики

Почему неоднозначные грамматики представляют собой проблему? Потому что вы можете получить разные результаты от выполнения выражения.

Вот причины, по которым грамматика может быть неоднозначной:

• Старшинство операторов

Возьмем пример из предыдущего параграфа:

Результатом этого дерева разбора будет 17.

А если мы посмотрим на дерево справа.

Результатом будет 21. Это неправильно, потому что оператор умножения (*) имеет больший приоритет, чем оператор плюс (+).

• Ассоциативность

Давайте рассмотрим этот вид грамматики и построим несколько деревьев разбора:

E : E - E
  | number

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

Левые рекурсивные правила на помощь

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

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

E : E - number
  | number

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

Обеспечение правильного предшествования

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

Давайте рассмотрим некоторые грамматики:

E : E + E
  | E * E
  | number

Введем новые нетерминалы:

E : E + T
  | T;

T : T * F
  | F;

F : number;

Давайте посмотрим на дерево результатов:

Абстрактные синтаксические деревья

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

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

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

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

Не стесняйтесь задавать вопросы, высказывать любые мнения или опасения, а также обсуждать свою точку зрения. Делитесь, подписывайтесь и делайте код, а не войну. ❤️

Если вы найдете ошибку, я буду рад исправить ее или поучиться у вас — просто дайте мне знать.

Вы можете написать мне в Twitter или связаться со мной в LinkedIn. Я всегда открыт для новых связей, людей и возможностей.