Классификация грамматик по Хомскому.

 

1) Грамматика типа 0 или общего вида

φ à ψ, φ ≠ e (e – символ конца)

φ может содержать не только терминальные символы

| ώ | - длина цепочки – число символов цепочки.

| φ | < | ψ |

Могут быть правила, которые укорачивают цепочки. Эта грамматика не имеет практического использования.

2) Грамматика типа 1 или непосредственных составляющих.

       Это контекстно-зависимая грамматика и неукорачивает длину цепочки.

       ξ₁ φ ξ₂ à ξ₁ ψ ξ₂

       ξ₁ ξ₂ φ ψ? V^*

       Грамматика контекстно-зависимая и неукорачивающая.

             G₈

       V_т = {a, b, с, d}

       I

       V_n = {I, A, B}

       R = {IàaAI, AIàAA, AAAàABA, aBA à bcdA, bI à ba}

3) Грамматика типа 2 или контекстно-свободная

A? V_n, ώ? V^*

             G₉

       V_т = {a, b}

       I

       V_n = {I }

       R = {IàcIa, IàbIb, Iàaa, I à bb}

             I à aIa à abIba à abaIaba à ababbaba

             L(G₉) = {xx¹; x? V_т^*}

4) Грамматика типа 3 или автоматная

a)левосторонняя

       A à a, A à Ba

b) правосторонняя

       A à a, A à aB

A, B? V_n, a? V_т

 В грамматике либо левосторонняя, либо правосторонняя.

A à aA; A à Aa – рекурсивное

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

G₁₀

V_т = {a, b}

I

V_n = {I  , A}

R = {IàaI, IàaA, AàbA, A à b}

L(G₁₀) = {aⁿb^m, a,b? V_т, n>0, m>0 }

L₀<=L_I<=L_II<=L_III

Язык L_III более узок, чем язык L_II и так далее.

 

Примеры построения грамматик.

 

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

V_т = {/,*}

V_n = {A,I} A будет обозначать любую непустую последовательность наклонных

R = {I à *B**, A à A/, Aà/}

B – произвольное количество черточек, разделенное *

B à A, B à B * A (!)

Чтобы получить произвольное количество цепочек из наклонных, введем нетерминальный символ B, который означает цепочку из наклонных, разделенная *, при этом надо добавить два правила (!) и изменить первоначальное правило:

I à *B** à *B*A** à *A*A** à*A/*A** à *//*A** à*//*/**

Примеры грамматик, используемых при определении языков программирования. Терминальные слова – множество основных символов языка, нетерминальные – синтаксические понятия языка. Для описание правил языка будем использовать язык Бекуса.

Пример: <целое без знака>

<>::= <> это есть

В левой части пишется определенное понятие, в правой цепочка символов и синтаксических понятий. В правой части могут быть символы.

Пример:

<целое без знака>::=<цифра>

<цифра>::=0| 1|2 … | 9.

V_т  = {0,1,2…9}

V_n = {I,A}

I

R = {IàIA, IàA, Aà0, Aà1…Aà9}

Пример грамматика для идентификатора:

<идентификатор>::=<буква>|<идентификатор><буква>|<идентификатор><цифра>

<цифра>::=0| 1| 2…|9

<буква>::=a|b|c…|z

V_т = {0,1,2…9,a,b,…,z}

V_n = {I,B,C}

R = {IàB, IàIB, IàIc, Bàa, Bà…z, Cà0…Cà9}

Контекстно-свободные грамматики типа 2

<идентификатор>::=<буква><конец идентификатора>

<буква>::=a|b…|z

<конец идентификатора>::=<буква><идентификатор>|<цифра><идентификатор>| BK

Предполагается что идентификатор заканчивается символом BK.

V_т = {0,1…9,a,b,c…,z,BK}

V_n ={I, B, C, E}

R = {IàBE, EàBE, EàCE, EàBK, Aàa..z, Cà0..9}

пример определения десятичное число с точкой и знаком.

<десятичное число с(.)>::=+<десятичное число с (.)>|<десятичное число с (.)>|-<десятичное число с (.)>

< десятичное число с (.)>::=<целое число>, <целое число> |. <целое число>.

<целое число>::= <цифра>|<целое число><цифра>

<цифра>::=0|1…|9

V_т ={0,1…9, +, -,.}

V_n = {P, Q, N, D}

R = {Pà+Q, PàQ, Pà-Q, QàN, QàN, NàD, NàND, Dà0, Dà1…Dà9}

 

Грамматика для выполнения арифметических операций.

 

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

V_т = {I, X, +, (,)}

V_n ={ E }

E

R = {Eài+E;EàI;Eài*E;Eà{E}}

E=>i+E=>i+E=>i+(E)=>i+(i*E)=>i+(i*i)

Набор данных правил не обеспечивает скобки для первых операндов.

V_т = {I, X, +, (,)}

V_n ={ E }

E

R = {EàE+E;EàE*E;Eà(E);Eài}

E=>E+E=>E+E*E=>i+i*I (1244)

E=>E*E=>E*i=>E+E*i=>i+i*i(24144)

 

Для одной и той же цепочки получили два синтаксического разбора, следовательно грамматика не однозначна.

Грамматика не обеспечивает приоритет операций сложение и умножение. Чтобы обеспечить приоритеты операций мы можем операции суммирования сделать в скобках, тогда:

R = (Eà9E+E);EàE*E,Eài)

E => (E+E) => (E+(E*E)) => (i+(i*i))

E => (E*E) => ((E+E)*E) => ((i+i)*i)

Грамматика получилась неоднозначной, однако каждая операция оказалась в своей скобке.

Приоритетность операции умножить по отношению к операции сложить обеспечивается благодаря скобкам.

V_т = {I, *, +, (,)}

V_n ={ E,T, P}

E – арифметическое выражение

Т – слагаемое (или терм)

Р – произведение или сам множитель

R={EàT,EàPPàP*P,Pà(T)*P,PàP*(T)*P,PàP*P,PàI,TàT+P,TàP+T,TàP+T,TàT+T,Tài}

Нужно получить: i + i * i

8,8 i+P*P

5     i+P

12   T+P

9     T

3     E

E=>T=>T + P => либоT+(T)*P=>T+(T)*I либо i+P=>i+(I)*P=>i+(T+T)*P либо i+(T+T)*i=>i+(i+i)*I либо T+(T+T)*i=>i+(i+i)*i

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

 

Соответствие конечных автоматов и автоматных грамматик.

 

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

Множество допустимых цепочек автомата называется языком, который допустим данным автоматом.

Утверждение:

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

 

⇐ Предыдущая3456789101112

Поделиться:

Воспользуйтесь поиском по сайту: