Вид сверху

Вид сверху - СТРУКТУРА СИ

Содержание материала

Страница 6 из 6

СТРУКТУРА   СИ

Язык 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.

Code:

{ 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" он все еще не знает ожидать ли объявления данных или определение функции. Дела становятся более сложными так как следующим токеном может быть не имя... он может начинаться с "*" или "(" или комбинаций этих двух.

Точнее говоря, БНФ для полного Си начинается с:

     <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>

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

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

Code:

{ Main Program }

begin

   Init;

   while Look <> ^Z do begin

      GetClass;

      GetType;

      TopDecl;

   end;

end.

 
 

 

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

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

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

     var Class: char;

и измените GetClass

Code:

{  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". Это не единственные три возможных класса... есть также "register" и "typedef", но это должно дать вам представление. Заметьте, что класс по умолчанию "auto".

Мы можем сделать подобную вещь для типов. Введите следующую процедуру:

Code:

{  Get a Type Specifier }

procedure GetType;

begin

   Typ := ' ';

   if Look = 'u' then begin

      Sign := 'u';

      Typ := 'i';

      GetChar;

      end

   else Sign := 's';

   if Look in ['i', 'l', 'c'] then begin

      Typ := Look;

      GetChar;

   end;

end;

 
 

 

Обратите внимание, что вы должны добавить еще две глобальные переменные Sign и Typ.

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

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

Вставьте следующую версию TopDecl:

Code:

{ Process a Top-Level Declaration }

procedure TopDecl;

var Name: char;

begin

   Name := Getname;

   if Look = '(' then

      DoFunc(Name)

   else

      DoData(Name);

end;

 
 

 

(Заметьте, что так как мы уже прочитали имя, мы должны передать его соответствующей подпрограмме.)

Наконец, добавьте две процедуры DoFunc и DoData:

Code:

{ Process a Function Definition }

procedure DoFunc(n: char);

begin

   Match('(');

   Match(')');

   Match('{');

   Match('}');

   if Typ = ' ' then Typ := 'i';

   Writeln(Class, Sign, Typ, ' function ', n);

end;

 

{ Process a Data Declaration }

procedure DoData(n: char);

begin

   if Typ = ' ' then Expected('Type declaration');

   Writeln(Class, Sign, Typ, ' data ', n);

   while Look = ',' do begin

      Match(',');

      n := GetName;

      WriteLn(Class, Sign, Typ, ' data ', n);

   end;

   Match(';');

end;

 
 

 

Так как мы еще далеки от получения выполнимого кода, я решил чтобы эти две подпрограммы только сообщали нам, что они нашли.

Протестируйте эту программу. Для объявления данных дайте список, разделенный запятыми. Мы не можем пока еще обрабатывать инициализаторы. Мы также не можем обрабатывать списки параметров функций но символы "(){}" должны быть.

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

Можем ли мы продолжать пока не получим что-то, что действует более похоже на компилятор. Конечно мы можем. Должны ли мы? Это другой вопрос. Я не знаю как вы, но у меня начинает кружиться голова, а мы все еще далеки от того, чтобы даже получить что-то кроме объявления данных.

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

Мы могли бы развивать обе эти структуры намного дальше, но помните, что наша цель здесь не в том, чтобы построить компилятор C или Pascal, а скорее изучать компиляторы вообще. Для тех из вас, кто хотят иметь дело с Pascal или C, я надеюсь, что дал вам достаточно начал чтобы вы могли взять их отсюда (хотя вам скоро понадобятся некоторые вещи, которые мы еще не охватили здесь, такие как типы и вызовы процедур). Остальные будьте со мной в следующей главе. Там я проведу вас через разработку законченного компилятора для TINY, подмножества KISS.

 

Новые статьи

Ранние статьи

Случайные статьи

Популярные статьи

Подробности
Категория: Лекции по построению компилятора на Pascal

Добавить комментарий

Не использовать не нормативную лексику.

Просьба писать ваши замечания, наблюдения и все остальное,
что поможет улучшить предоставляемую информацию на этом сайте.

ВСЕ КОММЕНТАРИИ МОДЕРИРУЮТСЯ ВРУЧНУЮ, ТАК ЧТО СПАМИТЬ БЕСПОЛЕЗНО!

Защитный код
Обновить