Парсер для программы чата с использованием генератора синтаксического анализа ANTLR

Что такое синтаксический анализ (парсинг)?

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

Разница между методами анализа сверху вниз и снизу вверх

Анализ сверху вниз

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

Анализ снизу вверх

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

Различия между анализом сверху вниз и снизу вверх кратко описаны ниже.

  • Стратегия

Подход сверху вниз начинается с оценки дерева синтаксического анализа сверху и с движения вниз для анализа других узлов.

Подход снизу вверх начинается с оценки дерева синтаксического анализа с самого нижнего уровня дерева и продвижения вверх для анализа узла.

  • Попытка

Анализ сверху вниз пытается найти самое левое производное для данной строки.

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

  • Тип деривации

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

При восходящем синтаксическом анализе используется самая правая деривация.

  • Цель

Анализ сверху вниз ищет производственное правило, которое будет использоваться для построения строки.

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

Подробный пример метода восходящего анализа

Здесь мы рассматриваем только технику синтаксического анализа сдвиг-сокращение.

Shift-Уменьшить синтаксический анализ

Это тип восходящего синтаксического анализа с двумя основными действиями: сдвигом и сокращением.

  • Другие очевидные действия принимаются и ошибка

Входная строка (т.е. анализируемая) состоит из двух частей

  • Левая часть представляет собой строку терминалов и нетерминалов и хранится в стеке.
  • Правая часть - это строка терминалов, считываемых из входного буфера.
  • Нижняя часть стека и конец ввода представлены символом $

Действия Shift-Уменьшение

  • Shift: переместить следующий входной символ из правой строки в верхнюю часть стека
  • Уменьшить: определите строку на вершине стопки, которая является телом производства, и замените тело на голову.

Shift-Уменьшить синтаксический анализ

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

Пример синтаксического анализа "Shift-Уменьшение" e

Мы начинаем с заданной грамматики, как показано ниже.

Рассмотрим заданную строку ввода id1 * id2 во входном буфере.

Как вы решаете, когда переходить, а когда сокращать?

Шаги в парсерах Shift-Reduce

Общая техника сдвига-уменьшения

• Если в стеке нет дескриптора, сдвинуть

• Если в стеке есть дескриптор, уменьшите

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

Рассмотрим пример выше.

  • Мы начинаем с перемещения следующего входного символа из правой строки на вершину стека, поскольку в стеке нет дескриптора. (Сдвиг)
  • Так как на вершине стека есть обработчик id1, и мы определяем, что это тело продукционного правила грамматики F - ›id, мы заменяем тело заголовком F (сокращаем на F -› id)
  • Поскольку обработчик теперь F на вершине стека, и мы идентифицируем, что это тело продукционного правила грамматики F - ›F, мы заменяем тело заголовком T (уменьшаем на T -› F)
  • Поскольку входной буфер не пуст, мы берем следующий входной символ * из правой строки на вершину стека (Shift)
  • Мы перемещаем следующий входной символ id2 из правой строки в верхнюю часть стека, поскольку в стеке нет дескриптора. (Сдвиг)
  • Так как обработчик id2 находится на вершине стека, и мы определяем, что это тело продукционного правила грамматики F - ›id, мы заменяем тело заголовком F (сокращаем на F -› id)
  • Так как на вершине стека находится строка T * F, и мы определяем, что это тело продукционного правила грамматики T - ›T * F, мы заменяем тело заголовком T (уменьшаем на T - ›Т * Ж)
  • Так как обработчик T находится наверху стека, и мы определяем, что это тело продукционного правила грамматики E - ›T, мы заменяем тело заголовком E (сокращаем на E -› T)
  • Поскольку начальный символ грамматики находится наверху стека, а входной буфер пуст, мы достигли конечной цели, и строка принимается с грамматикой. Разбор прошел успешно. (Принимать)

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

Использование генератора синтаксического анализа ANTLR для создания синтаксического анализатора программы чата

Парсер для программы чата

Сначала настройте ANTLR4 на вашем компьютере, следуя официальным инструкциям (https://www.antlr.org/). На самом деле ANTLR - это две вещи: инструмент, который переводит вашу грамматику в синтаксический анализатор / лексер на Java (или другом целевом языке), и время выполнения, необходимое для сгенерированных синтаксических анализаторов / лексеров.

Грамматика программы чата

Мы начинаем с определения грамматики для простой чат-программы.

  • Есть абзацы, и мы используем новые строки в качестве разделителей между сообщениями.
  • Мы разрешаем смайлы, упоминания и ссылки. Мы не будем поддерживать HTML-теги.
  • Мы предоставляем пользователям простой способ КРИЧАТЬ и форматировать цвет текста.

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

Затем выполните следующие команды: (Протестировано на платформе Windows с Java 8 JDK и antlr-4.7.2)

// Переходим в папку с образцами проекта

cd ChatProgramParser

// Запускаем файлы грамматики ANTLR (Chat.g4), выполнив следующий код в терминале

antlr4 Chat.g4

// Компилируем сгенерированные java файлы (сгенерированный файл парсера)

скомпилировать Chat * .java

// Тестируем Grammer с файлами в папке примеров

// Для графического интерфейса дерева синтаксического анализа используйте параметр -gui

grun Chat chat -gui examples \ inputValid1.txt

// Для просмотра дерева синтаксического анализа в терминале используйте параметр -tree

grun Chat chat -tree examples \ inputValid1.txt

Вы можете скачать исходный код следующего проекта с https://github.com/RolandHewage/ANTLRChatProgramParser

Оставайтесь на связи, чтобы увидеть больше интересных статей.