{–}
{ Process Label Statement }
procedure Labels;
begin
Match('l');
end;
{–}
{ Process Const Statement }
procedure Constants;
begin
Match('c');
end;
{–}
{ Process Type Statement }
procedure Types;
begin
Match('t');
end;
{–}
{ Process Var Statement }
procedure Variables;
begin
Match('v');
end;
{–}
{ Process Procedure Definition }
procedure DoProcedure;
begin
Match('p');
end;
{–}
{ Process Function Definition }
procedure DoFunction;
begin
Match('f');
end;
{–}
Теперь испытайте компилятор используя несколько характерных входных последовательностей. Вы можете смешивать объявления любым образом, каким вам нравится пока последним символом в программе не будет ".", указывающий на конец программы. Конечно, ни одно из этих объявлений фактически ничего не объявляет, так что вам не нужны (и вы не можете использовать) любые символы, кроме тех, которые обозначают ключевые слова.
Мы можем расширить раздел операторов аналогичным способом. БНФ для него будет:
<statements> ::= <compound statement>
<compound statement> ::= BEGIN <statement>(';' <statement>) END
Заметьте, что утверждение может начинаться с любого идентификатора, исключая END. Так что первая пустой формой процедуры Statements будет:
{–}
{ Parse and Translate the Statement Part }
procedure Statements;
begin
Match('b');
while Look <> 'e' do
GetChar;
Match('e');
end;
{–}
Сейчас компилятор примет любое число объявлений, сопровождаемое блоком BEGIN основной программы. Сам этот блок может содержать любые символы (за исключением END), но они должны присутствовать.
Простейшая входная форма сейчас
'pxbe.'
Испытайте ее. Также попробуйте некоторые ее комбинации. Сделайте некоторые преднамеренные ошибки и посмотрите что произойдет.
К этому моменту вы должны начать видеть основную линию. Мы начинаем с пустого транслятора для обработки программы, затем в свою очередь мы расширяем каждую процедуру, основанную на ее БНФ определении. Подобно тому, как более низкоуровневые БНФ определения добавляют детали и развивают определения более высокого уровня, более низкоуровневые распознаватели будут анализировать более детально входную программу. Когда последняя заглушка будет расширена, компилятор будет закончен. Это нисходящая разработка/реализация в ее чистейшей форме.
Вы могли бы заметить, что даже хотя мы и добавляли процедуры, выходной результат программы не изменялся. Так и должно быть. На этих верхних уровнях не требуется никакой выдачи кода. Распознаватели функционируют просто как распознаватели. Они принимают входные последовательности, отлавливают плохие и направляют хорошие в нужные места, так что они делают свою работу. Если бы мы занимались этим немного дольше, код начал бы появляться.
Следующим шагом в нашем расширении должна возможно быть процедура 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;
{–}
Обратите внимание, что я должен был использовать ^Z чтобы указать на конец исходного кода. C не имеет ключевого слова типа END или "." для индикации конца программы.
С полным Си все не так просто. Проблема возникает потому, что в полном Си функции могут также иметь типы. Так что когда компилятор видит ключевое слово типа «int» он все еще не знает ожидать ли объявления данных или определение функции. Дела становятся более сложными так как следующим токеном может быть не имя... он может начинаться с "*" или "(" или комбинаций этих двух.
