Грамматики и синтаксические деревья
Это введение в синтаксический анализ охватывает контекстно-свободные грамматики и синтаксические деревья на базовом уровне. Достаточно просто понять комбинаторы парсеров, которые будут представлены в следующем сообщении блога.
Парсеры
Парсер принимает входные данные и преобразует их в результат, как функция. Входные данные парсера - это текст на языке, который он понимает. Результатом может быть синтаксическое дерево, результат вычисления выражения, всего один бит, означающий "правильно" / "ошибка", или любая другая информация, которую мы хотим получить из текста. Иногда выводом является сообщение об ошибке, указывающее на синтаксическую ошибку.
Тексты могут быть написаны как на естественном, так и на искусственном языках. Поскольку естественные языки обычно очень сложны, мы сосредотачиваемся на искусственных языках, например. г. языки программирования, такие как 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.