Смекни!
smekni.com

Построение формального языка L (стр. 1 из 4)

Построение формального языка L

WHILE( <AB> ) [<FUNCTION([<PAR>, <PAR>, ...])>];

WHILE - входной терминальный символ

<AB > - условное выражение

<FUNCTION> - некоторая функция, которая может отсутствовать

<PAR> - параметры функции, которые тоже могут отсутствовать

Пример правильного синтаксиса:

WHILE(A>44<b=56+67) clrscr();

A>44<b=56+67 - условное выражение

clrscr() - функция, без параметров

Подбор грамматики G[Z] по языку L

Любая грамматика, к примеру G[Z], содержит следующие базисные элементы Vt, Vn, Z, P, где:

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

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

Z - начальный нетерминальный символ

P - множество правил вывода

G[<оператор>]:

1. <Оператор> - while(<AB> ) [<Функция>];

2. <AB>- T|<AB> < T|<AB> > T|<AB> <= T | <AB> >= T | <AB> != T

3. <T> - O | T*O | T**O | T+O | T-O | T/O

4. <O> - (<AB>) | <IDENT> | <ЦБЗ>

5. <IDENT> - Б{Б|Ц}

6. <ЦБЗ> - Ц{Ц}

7. <Функция> - <IDENT>([<PAR>{,<PAR>}])

8. <PAR> - <IDENT> | <ЦБЗ> | Ω

Классификация G[Z]

G[<оператор>]:

1. <Оператор> - while(<AB> ) [<Функция>];

2. <AB>- T|<AB> < T|<AB> > T|<AB> <= T | <AB> >= T | <AB> != T

3. <T> - O | T*O | T**O | T+O | T-O | T/O

4. <O> - (<AB>) | <IDENT> | <ЦБЗ>

5. <IDENT> - Б{Б|Ц}

6. <ЦБЗ> - Ц{Ц}

7. <Функция> - <IDENT>([<PAR>{,<PAR>}])

8. <PAR> - <IDENT> | <ЦБЗ> | Ω

Сделаем замену нетерминальных символов:

<Оператор> - Z

<AB> - A

<T> - B

<O> - C

<Функция > - D

<IDENT> - E

<ЦБЗ> - F

<PAR> - G

Сделаем замену терминальных символов:

WHILE - a

( - b

) - c

; - d

Ц - f

Б - g

, - h

G[Z]:

1. Z - abAc[D]d

2. A- B|A<B|A > B|A <= B |A >= B |A != B

3. B - C | B*C | B**C | B+C | B-C | B/C

4. C - bAc | E | F

5. E - g{g|f}

6. F - f{f}

7. D - Eb[G{hG}]c

8. G - E | F | Ω

Вывод : G[Z] - контекстно-свободная грамматика.

Выбор метода анализа

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

Диагностика и нейтрализация ошибок

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

Основная идея метода состоит в том, что по контексту без возврата отбрасываются те символы, которые привели в тупиковую ситуацию и разбор продолжается.

Приведем пример синтаксического разбора:

While (A > ) cls();

1. Z - abAc[D]d

2. A- B|A<B|A > B|A <= B |A >= B |A != B

3. B - C | B*C | B**C | B+C | B-C | B/C

4. C - bAc | E | F

5. E - g{g|f}

6. F - f{f}

7. D - Eb[G{hG}]c

8. G - E | F | Ω

Z

a b A c D

B A E

C B g{g} b G c

E C Ω

g E

g

While ( A > ) cls ( ) ;

тупиковая ситуация

Тестирование на цепочках

Протокол работы синтаксического распознавателя оператора цикла while языка С.

_____________________________________________________________________

Обрабатываем строчку - While(a>)cls();

Найден While проверка началась с символа - (

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - a

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - )

Проверка на ЦБЗ, текущий символ - )

Проверка на FUNC, текущий символ - c

Проверка на IDENT, текущий символ - c

Найденные ошибки в строке While(a>)cls();

Предупреждение: Отсутствует условие ()

Не найден идентификатор или ЦБЗ

_____________________________________________________________________

Обрабатываем строчку - while(1<(3*(43+5*(3-4-(4<454)))) ;

Найден While проверка началась с символа - (

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 1

Проверка на ЦБЗ, текущий символ - 1

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 3

Проверка на ЦБЗ, текущий символ - 3

Проверка на TERM

Проверка на O

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 4

Проверка на ЦБЗ, текущий символ - 4

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 5

Проверка на ЦБЗ, текущий символ - 5

Проверка на TERM

Проверка на O

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 3

Проверка на ЦБЗ, текущий символ - 3

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 4

Проверка на ЦБЗ, текущий символ - 4

Проверка на TERM

Проверка на O

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 4

Проверка на ЦБЗ, текущий символ - 4

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 4

Проверка на ЦБЗ, текущий символ - 4

Проверка на FUNC, текущий символ - ;

Проверка на IDENT, текущий символ - ;

Найденные ошибки в строке while(1<(3*(43+5*(3-4-(4<454)))) ;

Отсутствует )

Предупреждение: отсутствует имя функции

_____________________________________________________________________

Обрабатываем строчку - 435 4 whilei>>3t*(ewqw++()*we) rscr(456,345,rtgrt,345444rtr,,,)

Найден While проверка началась с символа - i

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - i

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 3

Проверка на ЦБЗ, текущий символ - 3

Проверка на TERM

Проверка на O

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - e

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - +

Проверка на ЦБЗ, текущий символ - +

Проверка на TERM

Проверка на O

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - w

Проверка на FUNC, текущий символ - r

Проверка на IDENT, текущий символ - r

Проверка на PAR, текущий символ - 4

Проверка на IDENT, текущий символ - 4

Проверка на ЦБЗ, текущий символ - 4

Проверка на PAR, текущий символ - 3

Проверка на IDENT, текущий символ - 3

Проверка на ЦБЗ, текущий символ - 3

Проверка на PAR, текущий символ - r

Проверка на IDENT, текущий символ - r

Проверка на PAR, текущий символ - 3

Проверка на IDENT, текущий символ - 3

Проверка на ЦБЗ, текущий символ - 3

Проверка на PAR, текущий символ - ,

Проверка на IDENT, текущий символ - ,

Проверка на ЦБЗ, текущий символ - ,

Найденные ошибки в строке 435 4 whilei>>3t*(ewqw++()*we) rscr(456,345,rtgrt,345444rtr,,,)

Отсутствует (

Отсутствует )

Предупреждение: Отсутствует условие ()

Отсутствует ; после функции

Параметр функции не может начинатся с цифры

Неизвестный идентификатор(ы) -

435, 4,

Не найден идентификатор или ЦБЗ

Идентификатор не может начинаться с цифры

Не найден или не верный параметр

Неизвестная знаковая конструкция

_____________________________________________________________________

Обрабатываем строчку - whiLE(43-(sss<233)fewfew) sd(we)

Найден While проверка началась с символа - (

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 4

Проверка на ЦБЗ, текущий символ - 4

Проверка на TERM

Проверка на O