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

vvedenie v razbor kontekstno svobodnyh grammatik?v=1656575415

Кристофер Диггинс

0*yyZM9V_77Q-uAj0F
Фото Йоханнеса Пленио на Unsplash

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

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

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

  • Теги открытия/закрытия HTML/XML
  • открывают/закрывают скобки {/} на языках программирования
  • открывать/закрывать скобки в арифметических выражениях

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

Разбор математических выражений

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

Например, рассмотрим выражение: (2 + (3 * (7–4)))

Обратите внимание, что структура арифметического выражения фактически является деревом:

  + / \ 2   *   / \  3   -     / \     7 4

Деревовидная структура, созданная в результате запуска анализатора CFG, называется a дерево разбора.

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

Существует два популярных способа выражения грамматик CFG:

  1. Расширенная форма Бахуса-Наура (EBNF) – описывает CFG в терминах правила производства. Это правила, которые при использовании могут генерировать все возможные юридические фразы в языке.
  2. Разбор грамматики экспрессии (PEG) — описывает CFG в терминах правила распознавания. Это правила, которые можно использовать для соответствия действительным фразам в языке.

Формализм PEG имеет преимущество над EBNF, поскольку отражение на синтаксическом анализаторе однозначно и может быть легко автоматизированным.

Ниже приведен простой PEG, снятый со страницы Википедии, описывающий математические формулы, применяющие основные четыре операции к неотъемлемым
целые числа.

Expr ← SumSum ← Product ((‘+’ / ‘-’) Product)*Product ← Value ((‘*’ / ‘/’) Value)*Value ← [0–9]+ / ‘(‘ Expr ‘)’

Просто на английском мы можем прочитать это так:

  • Expr это Sum
  • Sum это Product за которым следует нуль или больше подшаблонов, состоящих из «+» или «-», за которыми следует Product
  • Product это Value за которым следует ноль или более подшаблонов, состоящих из «*» или «/», за которыми следует a Value
  • Value является либо одним или несколькими членами набора символов {0,..9}, либо это открытая скобка “(“, за которой следует Expr и закрывающая скобка «)».

Генераторы синтаксических анализаторов против синтаксических библиотек

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

1. Используйте генератор синтаксических анализаторов — инструмент, генерирующий исходный код для парсера по абстрактному определению парсера. Некоторые популярные примеры JavaScript включают Jison, PEG.js, nearley и ANTLR.

2. Используйте библиотеку анализа — библиотека, позволяющая излагать правила разбора как API. Некоторые примеры JavaScript включают Myna, Parsimmon и Chevrotain.

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

Написание синтаксических анализаторов в TypeScript/JavaScript с помощью библиотеки разбора Myna

1*YvovmmxWoIEpHKQ1Fu6cxw
Common Myna от Махеша Айера из Wikimedia Commons

Недавно для проекта, над которым я работал (язык Heron), требовалась библиотека анализа, которая могла бы запускаться в браузере. Я считаю, что сложность и накладные расходы существующих библиотек слишком велики. Учитывая, что у меня был предварительный опыт написания библиотек синтаксического анализа на C++ и C#, я решил написать библиотеку анализатора под названием Мина с помощью TypeScript.

Myna использует свободный синтаксис (цепочка методов), чтобы облегчить определение синтаксического анализатора как набора правил (суб-парсер), напоминающих грамматику PEG.

Следующий пример из репозитории Myna GitHub:

От конкретного синтаксического дерева (CST) до абстрактного синтаксического дерева (AST)

Когда синтаксический анализатор обрабатывает входные данные, каждое успешно подобранное правило (он же производство грамматики) может быть отображено на узел в анализируемом дереве. Это буквальное отображение правил производства на узлы дерева a конкретное синтаксическое дерево (CST).

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

Проще всего создать узлы в дереве вывода только для определенных правил и пропустить другие правила. Эта упрощенная версия дерева анализа называется an абстрактное синтаксическое дерево (AST). На AST может выполняться несколько проходов, чтобы превратить его в альтернативные представления AST, чтобы упростить дальнейшие шаги обработки.

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

Использование сгенерированного абстрактного синтаксиса Myna

Вот пример использования определенного Myna анализатора в Node.JS для оценки арифметического выражения:

Заключительные слова

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

Myna была написана на TypeScript (имеющий знакомый для большинства программистов синтаксис), содержится в одном файле без зависимостей и содержит менее 1200 строк, включая подробную документацию.

Если вы заинтересованы в применении Myna к более сложному сценарию, посмотрите на язык программирования Chickadee. Это полностью реализовано в TypeScript и зависит только от библиотеки разбора Myna. Chickadee – это крошечный язык программирования, разработанный специально для того, чтобы помочь людям узнать о методах внедрения языков программирования.

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *