Алфавит, цепочка, грамматика

Формальная грамматика(грамматика) – способ описания формального языка, т.е. выделения некоторого подмножества из множества всех слов некоторого конечного алфавита.

Конечное множество символов А называется алфавитом.

Цепочкой называется любая конечная последовательность символов данного алфавита. (α).

Множество всех цепочек включает пустую цепочку .

- все цепочки из алфавита А.

- усеченная итерация мн.А (не содержит )

- полная итерация мн-ва А

Длина цепочки – количество символов в ней.

если α и β - цепочки, то цепочка αβ называется конкатенацией

(или сцеплением) цепочек α и β.

- n-я степень цепочки α. Это конкатенация n цепочек α.

Грамматика бознач. G(Z) и предст. собой непустое мн-во продукционных правил, где Z – нач. символ грамматики.

U ::= и – продукционное правило. В общем случае и левая и правая часть могут быть цепочками символов.

У грамматики есть словарь V символов, который образует цепочки. Словарь делится на 2 непересек. подмн-ва:

- нетерминальные символы (могут встреч. и в левой и в прав. Части продукц. правила )

- терминальные(конечные, неделимые) симв. (только справа)

Как пр. нетермин. симв. предст. в виде аббревиатур в < >.

<число>::=2

Правила с одинак. левой частью объед. в одно правило.

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

Вывод из грамматики

порождающая грамматика G - это четверка (VT, VN, P, S),

VT - алфавит терминал. символов,

VN - алфавит нетерминал. симв., не пересекающийся с VT

P - конечное подмножество множества

Эл-т (α, β) множества P наз. правилом вывода и записывается в виде α → β,

S - начальный символ (цель) грамматики, S Є VN.

цепочка β Є (1) непосредственно выводима из

цепочки α Є (2) в грамматике G = (VT, VN, P, S) (обозначим α → β), если α = ξ1 γ ξ 2 , β = ξ 1 δ ξ 2 , где

ξ1, ξ2, δ Є (1), а γ Є (2). и правило вывода γ → δ содерж. в P.

цепочка β Є (1) выводима из цепочки

α Є (2) в грамматике G = (VT, VN, P, S) (обозначим α Þ β) если существуют цепочки γ 0 , γ1, ... , γn

(n>=0), такие, что α = γ0→ γ1→ ... → γn = β

Посл - ть γ0, γ1, ... , γn называется выводом длины n.

X=>+Y – из цепоч.X выводима цепоч.Y

X=>*Y – выводима любая цеп. Y, включая начальную цеп.X

Любая цепочка, порожденная из нач. символа грамматики G, называется сентенциальной формой.

Языком, порождаемым грамматикой, называется множество всех цепочек Є VT, выводимых из S с помощью P или другими словами это множество терминальных сентенциальных форм.

С.Ф., состоящая только из терминал. симв. – это предложение.

Разбор (синт деревья)

В теории синтаксического анализа решается задача установления принадлежности некот. цепочки языку грамматики. Это установление принадлежности в теории компиляторов называется разбором.

Все виды разбора делятся на 2 класса:

1. Разбор снизу вверх (основан на редукции исходной цепочки к начальному символу грамматики)

2. Разбор сверху вниз (основан на построении вывода из начального символа грамматики искомой цепочки)

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

Метод восходящего разбора заключается в том, что исходную цепочку пытаются “свернуть” к начальному символу S; на каждом шаге ищут подцепочку, которая совпадает с правой частью какого-либо правила вывода; если такая подцепочка находится, то она заменяется нетерминалом из левой части этого правила.

В теории синтаксич. анализа используется аппарат теории графов – деревья. Синтаксическим деревом называют конструкцию, включающую ряд понятий:

узлы дерева соот-ют терм. и нетерм. символам; узел дерева, соот-щий нач. симв. – Корень; узел, соот-щий терм. симв. наз. Листом и не имеет исходящих ветвей; Куст узла – множество др. узлов, подчин-х данному узлу. Концевые узлы (листья) кустов не имеют.

<число>

<чс> <цифра>

<цифра> 1

2

Одно и то же дерево может соответствовать разным выводам.

Каждому дереву может соответствовать неск. выводов.

Вывод 1:

<число> => <чс><цифра> => <цифра><цифра> => <цифра>1 =>21

Вывод 2:

<чс>1 => <цифра>1 => 21

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