Способы записи синтаксиса языка

Классы грамматик в соответствии с классификацией Хомского.

Грамматики с ограничениями на правила

V. Введение в теорию формальных языков

Питання

1. Які точки називаються стаціонарними для функції?

2. Як визначити точки, підозрілі на екстремум для функції? Необхідна умова локального екстремума функції.

3. Чи завжди для знаходження екстремума функції можна користуватися першою достатньою умовою?

4. Друга достатня умова локального екстремума.

5. Третя достатня умова локального екстремума.

6. Чи для будь-якої функції можна знайти її найменше і найбільше значення?

7. Визначення опуклої униз (вверх) функції.

8. Критерій опуклості функції.

9. Визначення точки перегину функції. Необхідна умова точки перегину функції.

10. Достатня умова точки перегину функції.

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

1. Праволинейной (выровненной вправо) грамматикой называется грамматика G, если каждое правило из Р имеет вид

A® xB или A® x

где A, B – нетерминалы, x – цепочка, состоящая из терминалов

Например, грамматика G2 = ({0,1}, {S}, S, P)

где P: S ® 0S;

S ® 1S;

S ® e,

определяет язык {0, 1}.

2. Контекстно-свободной (бесконтекстной) грамматикой (КС-грамматикой) называется грамматика G, если каждое правило из Р имеет вид:

A® a

где A Î N, a Î (T È N)*, то есть является цепочкой, состоящей из множества терминалов и нетерминалов и может быть пустой.

Например, грамматика G3 = ({E, T, F}, {a, +, *, (,)}, P, E)

где P: E ®T

E ® E + T

T ® F

T ® T * F

F ® (E)

F ® a.

порождает простейшие арифметические выражения.

Согласно определению, каждая праволинейная грамматика является контекстно- свободной.

Нетерминал А контекстно-свободной грамматикиG = (T, N, S, P) для некоторых a и b, если a=ε, называется леворекурсивным, а если b=ε, называется праворекурсивным.

Грамматика G называется леворекурсивной (соответственно праворекурсивной), если в G имеется хотя бы один леворекурсивный (соответственно праворекурсивный) нетерминал.

Грамматика, в которой рекурсивны все нетерминалы (возможно, кроме, начального символа) называется рекурсивной.

3. Контекстно-зависимой (неукорачивающей) грамматикой (КЗ-грамматикой) называется грамматика G, если каждое правило из P имеет вид:

a ® b

где | a | £ | b |, то есть вновь порождаемые цепочки не могут быть короче, чем исходные, а также пустыми (другие ограничения отсутствуют).

Например, грамматика G = ({a, b, c}, {B, C, S}, S, P)

где P: S ® aSBC;

S ® abc;

CB ® BC;

bB ® bb;

bC ® bc;

cC ® сc,

порождает язык { a ⁿ b ⁿ c ⁿ }, n ≥ 1 (n >0).

По определению КЗ-грамматика не допускает правил А ® e, где e – пустая цепочка, т. е. КС-грамматика с пустыми цепочками в правой части правил не является контекстно-зависимой.

Запрещение в контекстно-зависимой грамматике использования правил вида A→ε сделано для того, чтобы алгоритм, определяющий принадлежность цепочки языку, не зацикливается.

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

4. Грамматикой свободного (общего) вида(без ограничений) называется грамматика G, если в ней отсутствуют выше упомянутые ограничения.

Если язык L порождается грамматикой типа G, то L называется языком типа G.

Например, L(G) – КС-язык типа G.

Наиболее широкое применение при разработке трансляторов нашли КС-грамматики и порождаемые ими КС-языки.

Эта классификация называется включающей, т. е. все контекстно-свободные грамматики являются контекстно-зависимыми, а все контекстно-зависимые грамматики являются грамматиками общего вида и т. д.

Существуют языки, принадлежащие к типу i, но не к типу i+1: например, язык грамматики G_i является контекстно-зависимым, но не контекстно-свободным, т. е. не существует контекстно-свободной грамматики, порождающий этот язык.

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

Метаязыки используются для задания грамматики языков программирования со времен Алгола 60. Еще раньше они начали использоваться при описании небольших языков в статьях, посвященных формальным грамматикам.

Дата добавления: 2014-01-11