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

Синтаксическая диаграмма — это направленный граф, с одним входным рядом и одним выходным и помеченными вершинами. Синтаксическая диаграмма задаёт язык. Цепочка пометок при вершинах на любом пути от входного ребра к выходному — это цепочка языка,

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

Расширенная (модифицированная) форма БН(МБНФ или РБНФ)

Это формальная система определения синтаксиса, в которой одни синтаксические категории определяются через другие. Так же как и БНФ используются для описания контекстно-свободных формальных грамматик. Отличается от БНФ более ёмкими конструкциями, позволяющими при той же выразительной способности упростить и сократить в объёме описание. Терминальные символы — это минимальные элементы грамматики не имеющие своей собственной грамматической структуры. Это могут быть предопределенные идентификаторы либо цепочки (последовательности символов в кавычках либо апострофах).

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

Каждый нетерминальный символ имеет своё имя, состоящее из строки символов.

Правила в РБНФ включают те же возможности что и БНФ но имеют более широкий набор возможных конструкций:

1. конкатенация: специального обозначения не имеет, определяется последовательной записью символов в выражении, правила вида А → BC означает что нетерминал А состоит из символов BC

2. выбор: обозначается «|» правило вида A → B|C|D элементы выбора называют ещё синтаксическими термами или просто термами

3. условное вхождение (факультативные цепочки): с помощью квадратных скобок выделяют необязательный элемент выражения, который может присутствовать или отсутствовать, например А → [B]C .

4. повторение: с помощью фигурных скобок можно обозначить конкатенацию любого количества(включая 0) записанных в них элементов. Правило вида:

A → {B} или A → ничего (λ) или A → B или A → BB или A → BB...BBB

если же требуется чтобы вывод был не пустым, то записываем так: A → B{B}.

Если для языка важно количество повторений некоторой цепочки, то вводят индексы, показывающие максимальное и минимальное количество повторений.

Задание. Привести БНФ и РБНФ для идентификатора, длина идентификаторов не больше 32 символов.

Для БНФ:

<идентификатор> → <буква>|<буква><остаток>

<остаток> → <буква/цифра/подчёркивание>|<буква/цифра/подчёркивание><остаток>

<буква/цифра/подчёркивание> → <буква>|<цифра>| _

<буква> → A|B|C|...|a|b|c...

<цифра> → 0|1|2|...

Для РБНФ:

<идентификатор> → <буква>|{<буква/цифра/подчёркивание>}³¹₀

<буква/цифра/подчёркивание> → <буква>|<цифра>| _

<буква> → A|B|C|...|a|b|c...

<цифра> → 0|1|2|...

Задание. Привести описание для арифметического выражения, содержащего плюс, минус, умножить, разделить и идентификатор.Приоритет выполненния операций стандартный общепринятый, нетерминальные символы записывать большими латинскими буквами, терминальные — малыми.

S → S+T|S-T|+T|-T

T → T*F|T/F|F

F → (S)|ug

S — арифметическая операция

T — слагаемое

F — множимое или делимое

Те операции которые имеют высший приоритет расположены ниже.