1. Синтаксис языков программирования. Описание синтаксиса. Нормальная форма Бэкуса-Наура (бнф).

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

Металингвистическая формула для языка модельного программирования ML.

<программа>::=<оператор>.|<оператор>;<программа>

(слева та конструкция, которую мы определяем, справа метапеременные, символы языка, после .|).

Металингвистическая формула содержит метапеременные, обозначающие соответственную конструкцию языка. Метапеременные заключаются <>, БНФ это название конструкции языка, например, <программа>,<оператор>.

Наша формула означает:

<программа>

1. <оператор>.

2. <оператор>;<оператор>.

3. ……………………….

-программа может состоять из 1-го оператора, из 2-х и нескольких операторов.

Определим, что такое <оператор>:

<оператор>::=<присваивание>|<условный>|<цикл>|<составной>

<присваивание>::=<идентификатор>:=<выражение>

<условный>::=if <логическое> then <оператор> else <оператор>

<цикл>::=while <логическое> do <оператор>

<составной>::=begin <программа> end (или «.»)

<идентификатор> - логическая единица.

<выражение>::=<терм>|<выражение>+<терм>|<выражение>-<терм>

<терм>::=<множитель>|<терм>*<множитель>|<терм>/<множитель>

<множитель>::=<идентификатор>|<const>|(<выражение>)

<логическое>::=<выражение><знак сравнения><выражение>

<знак сравнения>::=<|>|<=|>=|=|<>

<const> - логическая единица.

Грамматики Хомского.

G(V,T,P,б)

V-нетерминальный алфавит (метапеременная).

T-терминальный алфавит (символы языка).

P-правила вывода (формулы БНФ).

б-начальный символ грамматики (<программа>).

б€V

P (L→B); B€(VvT)*; L€(VvT)*·V·(VvT)*;

*-любая строчка, построенная над алфавитом;

А-алфавит (любое конечное множество А);

Все операции теории множеств можно производить над алфавитами, т.к. являются элементами множества.

A·B={ab,a€A,b€B}

A²=A·A

-множество всех строк длины «n» над алфавитом А.

-множество всех не пустых строк любой не пустой строки.

-множество всех строк над А, включая пустую строку.

Грамматики Хомского называется:

Уровни 1.

1. НС – непосредственно составляющих или КЗ – контекстно зависимых. Если для каждого правила грамматики соответствует условие:

-под знаком || понимаем длину строки.

Если одно название грамматики – неукорачивающаяся.

Уровни 2.

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

Если каждое правило обладает свойством:

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

Уровни 3.

3.Линейные –

Если каждое правило имеет следующий вид:

X→ay,X→a (праволинейная, нетерминал справа)

X→yа,X→a (леволинейная, нетерминал слева)

X,y€V

a€T*

x,y – нетерминальные символы;

а - строка терминальных символов.

Описание языка ml посредствам правил кс – грамматики.

1. P→S

2. P→S;P P-программа;

3. S→A А-оператор присваивания;

S→IF

4. S→WH WH-цикл;

S→BE BE-составной;

A→ID:=E E-арифметическое выражение

IF→IF L THEN S ELSE S S-оператор

(присутствуют терминалы и нетерминалы в правой части)

WH→WHILE L DO S

BE→BEGIN P END

E→E±T

T→M

T→T*/M

M→ID

M→C

M→(E)

L→EzE z-знак сравнения

z→<

z→<=

z→>

z→>=

z→=

z→<>

G({P,S,A,IF,WH,BE,E,L,T,M,z},T,P,p)

T-все символы/весь алфавит;

Р-множество правил.

Контекстно свободный язык-это язык, порождаемый контекстно-свободные грамматики.

Пример программы на языке ML:

A:=30;

B:=45;

If a<b then begin r1:=a;r2:=b end else

begin r1:=b;r2:=a end;

While r1<>r2 do begin r2:=r2-r1; begin

If r2<r1 then begin r3:=r1;

r1:=r2;

r2:=r3.

End.

End.

В ML построим вывод:

Все цепочки символов (терминалов или нетерминалов) выводятся

в грамматике называется сентенциальной формулой.

Вывод грамматики называется лево/правосторонним, если на каждом шаге правило грамматики применяется к самому левому/правому нетерминалу сентенциальной формуле.