Расширенные формы Бэкуса-Наура (РБНФ)

 

Для повышения удобства и компактности описаний, в РБНФ вводятся следующие дополнительные конструкции (метасимволы):

квадратные скобки «[» и «]» означают, что заключенная в них синтаксическая конструкция может отсутствовать;

фигурные скобки «{» и «}» означают повторение заключенной в них синтаксической конструкции ноль или более раз;

сочетание фигурных скобок и косой черты «{/» и «/}» используется для обозначения повторения один и более раз;

круглые скобки «(» и «)» используются для ограничения альтернативных конструкций.

Пример 2.3. В соответствии с данными правилами синтаксис модельного языка М будет выглядеть следующим образом:

 

<буква> ::= 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

<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

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

<число> ::= {/< цифра> /}

<ключевое_слово> ::= program | var | begin | end | int | bool | read | write | if |

                                       then | else | while | do | true | false

<разделитель> ::= ( | ) | , | ; | : | := | . | { | } |+ | - | * | / | Ú | Ù | Ø | = | < | >

<программа> ::= program <описание> ; <тело>.

<описание> ::= var <идентификатор> {, <идентификатор>}: (int | bool)

<тело> ::= begin {<оператор>; } end

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

                                 <ввода> | <вывода>

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

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

<цикла> ::= while <выражение> do <оператор>

<составной>:: = begin {<оператор> ;} end

<ввода>:: = read(<идентификатор>)

<вывода>:: = write(<выражение>)

<выражение>:: = <сумма> | <сумма> ( = | < | >) <сумма>

<сумма> ::= <произведение> { (+ | - | Ú) <произведение>}

<произведение>:: = <множитель> { (* | / | Ù) <множитель>}

<множитель>:: = <идентификатор> | <число> | <логическая_константа> |

   Ø <множитель> | (<выражение>)

<логическая_константа>:: = true | false

 

Диаграммы Вирта

 

В метаязыке диаграмм Вирта используются графические примитивы, представленные на рисунке 2.1.

При построении диаграмм учитывают следующие правила:

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

каждому правилу соответствует своя графическая диаграмма, на которой терминалы и нетерминалы соединяются посредством дуг;

альтернативы в правилах задаются ветвлением дуг, а итерации - их слиянием;

должна быть одна входная дуга (располагается обычно слева или сверху), задающая начало правила и помеченная именем определяемого нетерминала, и одна выходная, задающая его конец (обычно располагается справа и снизу);

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

 

 

 

Пример 1.4. Описание синтаксиса модельного языка М с помощью диаграмм

 

 

 

Описание синтаксиса модельного языка М с помощью диаграмм Вирта представлено на рисунке 2.2.

цифра         

                                                                                                                                                                                                                                                                                                                                                                                                                

 

 

Рисунок 2.2 – Синтаксические правила модельного языка М

 

Буква

 

 

Идентификатор

 

число

 

 

ключевое_слово

 

 

Рисунок 2.2 – Синтаксические правила модельного языка М, лист 2

Разделитель

 

программа

 

описание

 

тело

 

 

Рисунок 2.2 – Синтаксические правила модельного языка М, лист 3

Оператор

 

выражение

идентификатор

присваивания

 

 

условный

 

цикла

 

составной

 

 

ввода

 

вывода

 

Рисунок 2.2 – Синтаксические правила модельного языка М, лист 4

выражение

 

 

сумма

 

 

            

 

 

 

 

 

произведение

 

 

            

 

 

 

Операнд

 

логическая_константа

 

Рисунок 2.2 – Синтаксические правила модельного языка М, лист 5

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

program

var k, n, sum: int;

begin

read(n);

sum:= 0;

i:=1;

while i<=n do

  begin

       read(k);

       sum:=sum+k;

       k:=k+1

  end;

write(sum/n)

end.

2.2 Общая структура компилятора

 

Определение 2.2. Компилятор – это программа, которая осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд или языке ассемблере.

Основные функции компилятора:

1) проверка исходной цепочки символов на принадлежность к входному языку;

2) генерация выходной цепочки символов на языке машинных команд или ассемблере.

Процесс компиляции состоит из двух основных этапов: синтеза и анализа. На этапе анализа выполняется распознавание текста исходной программы и заполнение таблиц идентификаторов. Результатом этапа служит некоторое внутреннее представление программы, понятное компилятору.

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

Данные этапы состоят из более мелких этапов, называемых фазами. Состав фаз и их взаимодействие зависит от конкретной реализации компилятора. Но в том или ином виде в каждом компиляторе выделяются следующие фазы:

лексический анализ;

синтаксический анализ;

семантический анализ;

подготовка к генерации кода;

генерация кода.

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

По количеству проходов выделяют одно-, двух-, трех- и многопроходные компиляторы. В данном пособии предлагается схема разработки трехпроходного компилятора, в котором первый проход – лексический анализ, второй - синтаксический, семантический анализ и генерация внутреннего представления программы, третий – интерпретация программы.

Общая схема работы компилятора представлена на рисунке 2.3.

 

 

 

Рисунок 2.3 – Общая схема работы компилятора

⇐ Предыдущая12345678Следующая ⇒

Поделиться: