Синтаксическая диаграмма

Синтаксические диаграммы (или железнодорожные диаграммы ) — это способ представления контекстно-свободной грамматики . Они представляют собой графическую альтернативу форме Бэкуса-Наура , EBNF , расширенной форме Бэкуса-Наура и другим текстовым грамматикам как метаязыкам . Ранние книги, в которых используются синтаксические диаграммы, включают «Руководство пользователя Pascal», написанное Никлаусом Виртом. ^[1] (диаграммы начинаются на стр. 47) и руководство Burroughs CANDE . ^[2] В области компиляции обычно предпочтительны текстовые представления, такие как BNF или его варианты. BNF основан на тексте и используется авторами компиляторов и генераторами синтаксических анализаторов. Схемы железных дорог наглядны и могут быть более понятны непрофессионалам, иногда их включают в графический дизайн. Канонический источник, определяющий JSON формат обмена данными , представляет собой еще один пример популярного современного использования этих диаграмм.

Принцип синтаксических диаграмм

Представление грамматики представляет собой набор синтаксических диаграмм. Каждая диаграмма определяет «нетерминальную» стадию процесса. Существует основная диаграмма, которая определяет язык следующим образом: чтобы принадлежать языку, слово должно описывать путь на главной диаграмме.

Каждая диаграмма имеет точку входа и конечную точку. Диаграмма описывает возможные пути между этими двумя точками, проходя через другие нетерминалы и терминалы. Исторически терминалы представлялись круглыми коробками, а нетерминалы — прямоугольными, но официального стандарта не существовало.

Пример

В качестве примера мы используем арифметические выражения в различных грамматических форматах.

БНФ:

<expression> ::= <term> | <term> "+" <expression>
<term>       ::= <factor> | <factor> "*" <term>
<factor>     ::= <constant> | <variable> | "(" <expression> ")"
<variable>   ::= "x" | "y" | "z" 
<constant>   ::= <digit> | <digit> <constant>
<digit>      ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

ЕБНФ:

expression = term , [ "+" , expression ];
term       = factor , [ "*" , term ];
factor     = constant | variable | "(" , expression , ")";
variable   = "x" | "y" | "z"; 
constant   = digit , { digit };
digit      = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";

АБНФ:

expression = term ["+" expression]
term       = factor ["*" term]
factor     = constant / variable / "(" expression ")"
variable   = "x" / "y" / "z"
constant   = 1*digit
DIGIT      = "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9"

ABNF также поддерживает диапазоны, например DIGIT = %x30-39, но здесь он не используется для согласованности с другими примерами.

Красный (язык программирования) Диалект разбора:

Red [Title: "Parse Dialect"]
expression: [term opt ["+" expression]]
term:       [factor opt ["*" term]]
factor:     [constant | variable | "(" expression ")"]
variable:   ["x" | "y" | "z"]
constant:   [some digit]
digit:      ["0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"]

Этот формат также поддерживает диапазоны, например digit: charset [#"0" - #"9"], но здесь он не используется для согласованности с другими примерами.

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

См. также

Ссылки

Примечание: первая ссылка иногда блокируется сервером за пределами своего домена, но она доступна на archive.org . Файл также был отражен на сайте Standardpascal.org .

Внешние ссылки

[Wirth1974-1] Никлаус Вирт: Язык программирования Паскаль. (июль 1973 г.)

[burroughs71-2] Язык команды Burroughs B6700/B7700 И редактирования (CANDE): Информационное руководство

[1]

[2]