10

2. Проектирование Синтаксического анализатора

2.1. Описание языка

2.1.1. Бэкусовы нормальные формы

ПРОГРАММА

<ПРОГРАММА>::=

program <ИДЕНТИФИКАТОР>;<ОПИСАНИЯ>;<СОСТ_ОПЕРАТОР>.|

program <ИДЕНТИФИКАТОР> ; <СОСТ_ОПЕРАТОР>.|

<ОПИСАНИЯ> ; <СОСТ_ОПЕРАТОР>.|

<СОСТ_ОПЕРАТОР>.

РАЗДЕЛ ОПИСАНИЙ

<ОПИСАНИЯ>::=

<РАЗДЕЛ ОПИСАНИЯ>|

<ОПИСАНИЯ> ; < РАЗДЕЛ ОПИСАНИЯ>

1. <РАЗДЕЛ ОПИСАНИЯ>::=

label <ОПИСАНИЕ_МЕТОК> |

var <ОПИСАНИЕ_ПЕРЕМЕННЫХ>|

const <ОПИСАНИЕ_КОНСТАНТ>

1.1. <ОПИСАНИЕ_МЕТОК>::=

<МЕТКА> |

<ОПИСАНИЕ_МЕТКИ> , <МЕТКА>

1.2. <ОПИСАНИЕ_ПЕРЕМЕННЫХ>::=

<ОП1>|

<ОПИСАНИЕ_ПЕРЕМЕННЫХ> ; <ОП1>

<ОП1>::=<СПИСОК_ПЕРЕМЕННЫХ> : <ТИП>

1.2.1. <СПИСОК_ПЕРЕМЕННЫХ>::=

<ИДЕНТИФИКАТОР>|

<СПИСОК_ПЕРЕМЕННЫХ>,<ИДЕНТИФИКАТОР>

1.2.2. <ТИП>::= integer | boolean | array[<Список промежутков>] of boolean

<Список промежутков>::=

<Промежуток>|

<Промежуток>,<Список промежутков>

<Промежуток> ::= <ЦЕЛОЕ БЕЗ ЗНАКА> . . <ЦЕЛОЕ БЕЗ ЗНАКА>

1.3. <ОПИСАНИЕ_КОНСТАНТ>::=

<ОПИСАНИЕ_КОНСТ>|

<ОПИСАНИЕ_КОНСТАНТ> ; <ОПИСАНИЕ_КОНСТ>

<ОПИСАНИЕ_КОНСТ>::=<ИДЕНТИФИКАТОР> = <ЦЕЛОЕ_bool>;

<ЦЕЛОЕ_bool> = <ЦЕЛОЕ>| true | false

Раздел операторов

<СОСТ_ОПЕРАТОР>::=

begin <СПИСОК ОПЕРАТОРОВ> end |

begin end

<СПИСОК ОПЕРАТОРОВ>::=

<ОПЕРАТОР >|

<СПИСОК ОПЕРАТОРОВ>;< ОПЕРАТОР >

2. <ОПЕРАТОР> ::= <ОП1> | <СПИСОК_МЕТОК> :

<ОП1>::= <СПИСОК_МЕТОК> : <ОП2>|

<ОП2>

<ОП2>::= <ОП3> | <СОСТ_ОПЕРАТОР>

2.1. <СПИСОК_МЕТОК>::=

<МЕТКА> |

<СПИСОК_МЕТОК> : <МЕТКА>

2.2. <ОП3>::= <ОПЕРАТОР_ПРИСВАИВАНИЯ>|

<ОПЕРАТОР_ВВОДА> |

<ОПЕРАТОР_ВЫВОДА> |

<ОПЕРАТОР_ПЕРЕХОДА> |

<УСЛОВНЫЙ_ОПЕРАТОР>|

<ОПЕРАТОР_ЦИКЛА>|

2.2.1. <ОПЕРАТОР_ПРИСВАИВАНИЯ> ::= <ПЕРЕМ>:=<ВЫРАЖЕНИЕ>

2.2.2. <ОПЕРАТОР_ВВОДА> ::=

readln(<СПИСОК_ПАРАМЕТРОВ>) | read(<СПИСОК_ПАРАМЕТРОВ>)

2.2.3. <ОПЕРАТОР_ВЫВОДА> ::=

writeln(<СПИСОК_ПАРАМЕТРОВ>) |

write(<СПИСОК_ПАРАМЕТРОВ>)

<СПИСОК_ПАРАМЕТРОВ> ::=

<ПАРАМЕТР> |

<СПИСОК_ПАРАМЕТРОВ>,<ПАРАМЕТР>

<ПАРАМЕТР> ::= <ПЕРЕМ> | <ЦЕЛОЕ> | '<СТРОКА>'

2.2.4. <ОПЕРАТОР_ПЕРЕХОДА> ::= goto <МЕТКА>

2.2.5. <УСЛОВНЫЙ_ОПЕРАТОР> ::=

if <ВЫРАЖЕНИЕ> then <СОСТ_ОПЕРАТОР> |

if <ВЫРАЖЕНИЕ> then <СОСТ_ОПЕРАТОР> else <СОСТ_ОПЕРАТОР>

2.2.6. <ОПЕРАТОР_ЦИКЛА> ::= while <ВЫРАЖЕНИЕ> do <ОП2>

Выражения

<ВЫРАЖЕНИЕ> ::= <ВЫРАЖЕНИЕ> < <В1> | <В1>

<В1>::= <В1> > <В2> | <В2>

<В2>::= <В2> <= <В3> | <В3>

<В3>::= <В3> >= <В4> | <В4>

<В4>::= <В4> <> <В5> | <В5>

<В5>::= <В5> = <В6> | <В6>

<В6>::= <В6> or <В7> | <В7>

<В7>::= <В7> – <В7> | <В8>

<В8>::= <В7> + <В9> | <В9>

<В9>::= <В8> / <В10> | <В10>

<В10>::= <В10> and <В11> | <В11>

<В11>::= <В11> * <В12> | <В12>

<В12>::= <В12> not <В13> | <В13>

<В13>::=(<ВЫРАЖЕНИЕ>) | <ЦЕЛОЕ> | <ПЕРЕМ>

***<СТРОКА> ::= <СИМВОЛ> | <СТРОКА><СИМВОЛ>

<МЕТКА>::= <ИДЕНТИФИКАТОР> | <ЦЕЛОЕ БЕЗ ЗНАКА>

<ЦЕЛОЕ>::= – – <ЦЕЛОЕ БЕЗ ЗНАКА>|

<ЦЕЛОЕ БЕЗ ЗНАКА>

Здесь знак – – означает унарный минус

<ПЕРЕМ>::= <ИДЕНТИФИКАТОР>|

<ИДЕНТИФИКАТОР> [<ИНДЕКСЫ>]

<ИНДЕКСЫ>::= <ВЫРАЖЕНИЕ>, <ИНДЕКСЫ>|

<ВЫРАЖЕНИЕ>

***<ЦЕЛОЕ БЕЗ ЗНАКА>::= <ЦИФРА> | <ЦЕЛОЕ БЕЗ ЗНАКА> <ЦИФРА>

***<ИДЕНТИФИКАТОР>::= <БУКВА> | <БУКВА> <ПОЛЕД_СИМ>

***<ПОСЛЕД_СИМ>::= <СИМВОЛ> | <ПОСЛЕД_СИМ><СИМВОЛ>

***<СИМВОЛ>::=<БУКВА>|<ЦИФРА>

***<ЦИФРА>::=1|2|3|4|5|6|7|8|9|0

***<БУКВА>::=

_|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z

Здесь звездочками отмечены те описания, которые на этапе лексического анализа становятся лексемами, т.е. при описании синтаксиса языка эти элементы можно рассматривать как терминалы.

2. Синтаксис языка

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

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