К этому моменту вы должны начать видеть основную линию. Мы начинаем с пустого транслятора для обработки программы, затем в свою очередь мы расширяем каждую процедуру, основанную на ее БНФ определении. Подобно тому, как более низкоуровневые БНФ определения добавляют детали и развивают определения более высокого уровня, более низкоуровневые распознаватели будут анализировать более детально входную программу. Когда последняя заглушка будет расширена, компилятор будет закончен. Это нисходящая разработка/реализация в ее чистейшей форме.

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

Следующим шагом в нашем расширении должна возможно быть процедура Statements. Определение Pascal:

<statement> ::= <simple statement> <structured statement> <simple statement> ::= <assignment> <procedure call> null <structured statement> ::= <compound statement>

<if statement>

<case statement>

<while statement> <repeat statement> <for statement>

<with statement> Это начинает выглядеть знакомыми. Фактически вы уже прошли через процесс синтаксического анализа и генерации кода и для операций присваивания и для управляющих структур. Это место, где верхний уровень встречается с нашим восходящим методом из предыдущих уроков. Конструкции будут немного отличаться от тех, которые мы использовали для KISS, но в этих различиях нет ничего, чего бы вы не смогли сделать.

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

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

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

Если бы я собирался обратиться к вопросам которые мы еще не охватили, я предпочел бы сделать это в контексте KISS. Мы не пытаемся построить полный копилятор Pascal, поэтому я собираюсь остановить на этом расширение Pascal. Давайте взглянем на очень отличающийся язык.

СТРУКТУРА СИ

Язык C совсем другой вопрос, как вы увидите. Книги по C редко включают БНФ определения языка. Возможно дело в том, что этот язык очень сложен для описания в

БНФ.

Одна из причин что я показываю вам сейчас эти структуры в том что я могу впечатлить вас двумя фактами:

1 . Определение языка управляет структурой компилятора. Что работает для одного языка может быть бедствием для другого. Это очень плохая идея попытаться принудительно встроить данную структуру в компилятор. Скорее вы должны позволить БНФ управлять структурой, как мы делали здесь.

2. Язык, для которого сложно написать БНФ также будет возможно сложен для написания компилятора. Си - популярный язык и он имеет репутацию как позволяющий сделать практически все, что возможно. Несмотря на успех Small С, С является непростым для анализа языком.

Программа на C имеет меньше структур, чем ее аналог на Pascal. На верхнем уровне все в C является статическим объявлением или данных или функций. Мы можем зафиксировать эту мысль так:

<program> ::= ( <global declaration> )*

<global declaration> ::= <data declaration> <function>

В Small C функции могут иметь только тип по умолчанию int, который не объявлен. Это делает входную программу легкой для синтаксического анализа: первым токеном является или "int", "char" или имя функции. В Small C команды препроцессора также обрабатываются компилятором соответствующе, так что синтаксис становится: <global declaration> ::= # <preprocessor command> int <data list> char <data list> <ident> <function body> Хотя мы в действительности больше заинтересованы здесь в полном C , я покажу вам код, соответствующий структуре верхнего уровня Small C.

{ Parse and Translate A Program }

procedure Prog;

begin

while Look <> *Z do begin case Look of #: PreProc; i: IntDecl; c: CharDecl; else DoFunction(Int); end; end; end;

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

С полным Си все не так просто. Проблема возникает потому, что в полном Си функции могут также иметь типы. Так что когда компилятор видит ключевое слово типа "int" он все еще не знает ожидать ли объявления данных или определение функции. Дела становятся более сложными так как следующим токеном может быть не имя... он может начинаться с

"*" или "(" или комбинаций этих двух.

Точнее говоря, БНФ для полного Си начинается с: <program> ::= ( <top-level decl> )* <top-level decl> ::= <function def> <data decl> <data decl> ::= [<class>] <type> <decl-list> <function def> ::= [<class>] [<type>] <function decl> Теперь вы можете увидеть проблему: первые две части обьявлений для данных и функций могут быть одинаковыми. Из-за неоднозначности в этой грамматике выше, она является неподходящей для рекурсивного синтаксического анализатора. Можем ли мы преобразовать ее в одну из подходящих? Да, с небольшой работой. Предположим мы запишем ее таким образом:

<top-level decl> [<class>] <decl> <decl> ::= <type> <typed decl> <function decl> <typed decl> ::= <data list> <function decl>

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

Для начала, наберите следующую версию основной программы:

{ Main Program } begin

Init;

while Look <> *Z do begin GetClass; GetType; TopDecl; end; end.

На первый раз просто сделайте три процедуры-заглушки которые ничего не делают, а только вызывают GetChar.

Работает ли эта программа? Хорошо, было бы трудно не сделать это, так как мы в действительности не требовали от нее какой-либо работы. Уже говорилось, что компилятор Си примет практически все без отказа. Несомненно это правда для этого компилятора, потому что в действительности все, что он делает, это съедает входные символы до тех пор, пока не найдет Z.

Затем давайте заставим GetClass делать что-нибудь стоящее. Объявите глобальную переменную

var Class: char; и измените GetClass

{ Get a Storage Class Specifier } Procedure GetClass; begin

if Look in [a, x, s] then begin Class := Look; GetChar; end

else Class := a; end;

Здесь я использовал три одиночных символа для представления трех классов памяти "auto", "extern" и "static". Это не единственные три возможных класса... есть также