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

Построение формального языка 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], содержит следующие базисные элементы V_t , V_n , Z, P, где:

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

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

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