Грамматики и синтаксические деревья

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

Парсеры

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

Тексты могут быть написаны как на естественном, так и на искусственном языках. Поскольку естественные языки обычно очень сложны, мы сосредотачиваемся на искусственных языках, например. г. языки программирования, такие как Java, языки разметки, такие как XML, и так далее. Мы определяем такие языки с помощью грамматик. Среди различных типов грамматик мы сосредотачиваемся на простых, но мощных контекстно-свободных грамматиках. Их достаточно для определения большинства языков программирования.

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

Грамматика, не зависящая от контекста, состоит только из слов и фраз. Ученые-информатики говорят о терминалах (вместо слов) и нетерминалах (вместо фраз). В этом сообщении блога мы будем придерживаться слов и фраз. Давайте посмотрим на пример грамматики: арифметические выражения из начальной школы, например. г. «(1 + 2) * 3 + 4». Мы используем слова «(«, «)», «+», «*» и цифры «0», .., «9». В нашем примере грамматики используются следующие фразы: Цифра, Число, Множаемое, Сложение, Выражение. В рамках этого введения мы будем писать названия фраз жирным шрифтом и начинать с заглавной буквы. Чтобы определить язык выражения, мы просто записываем, каким должно быть отношение между фразами и словами. Для каждой фразы мы записываем одно или несколько правил, которые говорят нам, как должен выглядеть текст этой фразы. Начнем с цифры.

Digit := "0"
Digit := "1"
...
Digit := "9"

Мы читаем символ «..: = ..» как «.. может быть ..». Если мы прочитаем это так, мы получим «Цифра может быть« 0 »». и так далее. Это определение повторяет «Цифра: =» много раз. Введем аббревиатуру «.. | .. », который мы читаем как« .. или .. ». Мы используем это сокращение только с правой стороны символа определения «..: = ..». Определение цифры теперь помещается в одну строку и по-прежнему имеет то же значение, что и выше.

Digit := "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Кроме того, мы должны указать, что одно слово или фраза должны следовать за другим. Мы используем обозначение «.. ^ ..» и читаем его как «.., за которым следует ...». Этого уже достаточно, чтобы определить Число и другие оставшиеся фразы.

Number := Digit | Digit ^ Number

Вспомнив правила чтения этого материала, мы обнаруживаем, что он выглядит так: «Число может быть цифрой или цифрой, за которой следует Число ». Это рекурсивное определение, а Цифра - это базовый случай. Символ «^» имеет более высокий приоритет, чем «|», поэтому это цифра или (цифра, за которой следует число), а не (цифра или цифра), за которой следует число. . Последнее в любом случае не имело бы особого смысла. Продолжаем определять оставшиеся части грамматики выражений.

Multiplicand := Number | "(" ^ Expression ^ ")"

Множаемое - это левая и правая части произведений. Мы не делаем различий между множителями и множителями. Мы можем умножать числа и выражения, заключенные в круглые скобки. Мы не хотим, чтобы слово «+» было вне скобок, потому что оно должно иметь более низкий приоритет, чем «*». Член (1+2) может быть множимым, но 1+2 - нет.

Addend := Multiplicand | Multiplicand ^ "*" ^ Addend

Сложение - это левая или правая часть сумм. Это может быть одиночное Множаемое или Множаемое, за которым следует «*», за которым следует еще одно Сложение. Это просто рекурсивный способ сказать, что сложение может быть целым продуктом Multiplicand s.

Expression := Addend | Addend ^ "+" ^ Expression

Выражения - это суммы из слагаемых.

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

Одно число является выражением, и вот почему: согласно грамматике выражение может быть добавлением, может Множимое может быть числом. Как насчет «(1 + 2) * 3», теперь это Выражение? Записывать почему это немного громоздко. Мы все равно это делаем - все просто. Не стесняйтесь переходить к синтаксическим деревьям, чтобы описать это более красиво. Согласно грамматике, выражение может быть слагаемым, может быть множимым, за которым следует «*», за которым следует слагаемое . Как мы видели, добавление может быть числом вроде цифры 3 в конце. Множаемое может быть «(», за которым следует Выражение, за которым следует «)». Наконец, нам нужно проверить, что «1 + 2» - это выражение. Снова используя определение, мы видим, что Выражение может быть Дополнением, за которым следует «+», за которым следует Выражение - оба из которых могут быть числа.

Синтаксические деревья

Для лучшего обзора мы можем использовать дерево синтаксиса. Синтаксическое дерево показывает все отношения «.. может быть ..», которые мы используем в нашем выводе выше. Каждое такое отношение между словами и фразами «(1 + 2) * 3» становится одной или несколькими ветвями дерева. Каждое слово или фраза становится листом или узлом дерева. Таким образом, математический текст превращается в произведение искусства.

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

С помощью комбинаторов парсеров мы можем создавать такие абстрактные синтаксические деревья в Go.

Вывод

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