В следующем разделе мы рассмотрим грамматики экспрессии парсинга (PEG)., вариант расширенной формы Backus-Naur (EBNF)с другим толкованием. Проще понять PEG, используя синтаксические диаграммы. Синтаксические диаграммы представляют собой графическую грамматику. Он широко использовался Никлаусом Виртомв «Руководстве пользователя Паскаля». Синтаксические диаграммы легко понятны программистам из-за их сходства с потоковыми диаграммами. Изоморфизм диаграмм и функций делает их идеальными для представления рекурсивных парсеров спуска, которые по существу являются взаимно рекурсивными функциями.
Исторически сложилось так, что грамматики для парсеров использовались только для описания грамматики (отсюда и название). ВДухемы используем очень похожее обозначение для генерации продукции. Почти все описанные здесь понятия одинаково применимы и к.Дух.Qiпарсеры иДух. Кармагенераторы.
Все диаграммы имеют одну точку входа и один выход. Стрелы соединяют все возможные пути через грамматику от точки входа до точки выхода.
Терминалы представлены круглыми ящиками. Терминалы являются атомарными и обычно представляют собой простые символы, струны или жетоны.
Нетерминалы представлены коробками. Диаграммы модулируются с использованием названных нетерминалов. Сложная диаграмма может быть разбита на набор нетерминалов. Нетерминалы также позволяют рекурсию (то есть нетерминал может называть себя).
Самой основной композицией является последовательность. B следует за A:
Отныне мы будем называть упорядоченный выборальтернативами. В PEG упорядоченный выбор и альтернативы не совсем одинаковы. PEG позволяет сделать выбор в пользу одной или нескольких ветвей. В PEG в случае двусмысленности всегда выигрывает первый.
Необязательно (ноль или один):
А теперь петли. У нас есть ноль-или-больше и один-или-больше:
Обратите внимание, что, как и в PEG, эти петли ведут себя жадно. Если перед конечной точкой находится еще одно «А», оно всегда выйдет из строя, потому что предыдущий цикл уже исчерпал все «А», и больше ничего не осталось. Это ключевое различие между PEG и общими бесконтекстными граммарами (CFG). Это поведение довольно очевидно с синтаксическими диаграммами, поскольку они напоминают блок-схемы.
Ниже приведены синтаксические версии предикатов PEG. Традиционно они не встречаются в синтаксических диаграммах. Это специальные расширения, которые мы изобрели, чтобы внимательно следить за ПЭГ.
Во-первых, мы вводим новый элемент, Предикат:
Это похоже на условия в блок-схемах, где ветвь «Нет» отсутствует и всегда сигнализирует о неудачном анализе.
У нас есть две версии предиката.ПредсказаниеиНе предсказывать:
.Предсказаниепробует предикат, P, и преуспевает, если P преуспевает, или иначе терпит неудачу. Противоположностью этому является.Не предсказывать. Он пробует предикат, P, и терпит неудачу, если P преуспевает или иным образом преуспевает. Обе версии выглядят заранее, но не потребляют никаких вводных данных, независимо от того, увенчается ли успехом P или нет.
