Сети ЭВМ и телекоммуникации

Содержание

1. Постановка задачи 2
2. Теоретические основы разработки трансляторов 3
1. Построение лексического анализатора 3
2. Построение синтаксического анализатора 4
3. Описание синтаксических конструкций …………………………………………...6
4. Грамматика, описывающая язык…………………………………………………… 8
5. Управляющая таблица 8
6. Листинг  программы 9
7. Результаты работы программы 17
8. Список литературы  22

 

 

 

1.Постановка  задачи:

 

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

 

 

2.Теоретические основы разработки трансляторов

 

Процесс интерпретации исходной программы происходит в несколько этапов:

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

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

- выполнение программы

 

2.1 Построение лексического анализатора

 

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

- замена в программе идентификаторов  и констант лексемами делает  представление программы удобнее  для дальнейшей обработки;

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

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

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

При непрямом лексическом анализе требуется, прочитав цепочку символов, определить, образует ли эта цепочка лексему некоторого конкретного типа. В этом случае сканер работает вместе с синтаксическим анализатором,  как некоторая программная процедура SCAN

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

Непрямой сканер более экономичен ( в смысле экономии памяти), т.к. он не создает полной таблицы лексем для всего исходного текста программы.

Распознавание лексем выполняется  следующим образом:

- входная цепочка считывается  до тех пор, пока КА не  достигнет заключительного состояния;

- по достижению заключительного  состояния КА  сигнализирует о нахождению лексемы данного типа и сканер заносит информацию о ней в таблицу имен  (символов).

Таким образом, проблему построения непрямого  лексического анализатора для данного типа лексем можно представить как проблему построения и реализации КА, который по достижению заключительного состояния, выдает на выходе  лексему ( в этом смысле его можно рассматривать и как конечный преобразователь

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

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

1. вершина синтаксической диаграммы помечается начальным символом  грамматики S ;
2. между двумя подряд идущими терминальными символами вставляется нетерминальный символ AÎ N ;
3. перед альтернативой (разветвлением на несколько ветвей) ставиться только один нетерминальный символ  AÎN ;
4. перед выходящими ветвями итерации (цикла ) ставится один нетерминальный символ .

Далее следует записать правила  грамматики для каждого нетерминального символа. Все правила должны иметь вид : A® aB или A® a, где A , B Î N , a Î S È {e} (регулярная грамматика ) . При задании условий следует пользоваться следующими правилами :

1. Если два нетерминала А и В связаны одной ветвью  направленной от А к В и содержащей терминал а, то правило имеет вид     А ® аВ.

2. Если два нетерминала А и В связаны несколькими ветвями, направленными от А к В и содержащими терминалы a,b,..c, то правило имеет вид   А® аВ½bB½...½cB.

3. Если среди ветвей, связывающих нетерминалы А и В, содержится пустая (не содержащая терминалов) ветвь и имеется ветвь, связывающая В и С, содержащая терминал а , тогда правило имеет вид А® аС , то есть нетерминал В пропускается .

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

Таким образом, после распознавания  каждой лексемы, сканер должен занести в таблицу имен их характеристики (атрибуты). К этим атрибутам относятся: класс лексемы (обозначаемый обычно во внутреннем  представлении целым числом), фактическое значение лексемы (фактическое символическое имя), дополнительная информация.

 

2.2 Построение синтаксического анализатора

 

Синтаксический анализ подразумевает процесс анализа символьных цепочек с целью распознавания “правильных” или “неправильных” языковых конструкций. получение и представлении этой информации в виде дерева разбора или другой структуры. Эта структура называется промежуточной программой и используется для генерации кода.

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

Левым разбором цепочки a называется последовательность правил, примененных при левом выводе цепочки a из S.

Правым разбором цепочки a называется обращение последовательности правил, примененных при правом выводе цепочки a из S.

Эти разборы можно  представить в виде последовательности номеров из множества правил анализируемой грамматики.

Большинство методов  синтаксического анализа делят  на два класса разбора, – нисходящего и восходящего. Анализаторы, реализующие методы нисходящего разбора, выдают на выходе левые разборы и называются левыми анализаторами, а реализующие методы восходящего разбора, выдают правые разборы и называются правыми анализаторами. Эти анализаторы можно моделировать при помощи соответствующих МП - преобразователей.

Попытка реализации МП-преобразователей для широкого класса КС-грамматик приводит к так называемым алгоритмам с “возвратами”, которые требуют слишком больших затрат времени. На практике обычно ограничивают классы грамматик таким образом, чтобы сделать процесс разбора полностью детерминированным. Требованиям детерминированности левых анализаторов наилучшим образом удовлетворяют так называемые LL(k)-грамматики, для которых левый анализатор работает детерминировано, если позволить ему принимать во внимание k входных символов, расположенных справа от текущей входной позиции. Входная цепочка считывается таким анализатором один раз слева направо и в процессе анализа не происходит возвратов к уже прочитанной части цепочки. Такие анализаторы называются однопроходными. Иначе говоря, G будет LL(k)-грамматикой, если для данной цепочки w AaÎ(NUE)^* и первых k символов (если они есть), выводящихся из Aa, существует не более одного правила, которое можно применить к A, чтобы получить вывод какой-нибудь терминальной цепочки, начинающейся с w и продолжающейся упомянутыми k терминальными символами.

Разбор для LL(k)-грамматики удобно  осуществлять с помощью так называемого k-предсказывающего  алгоритма разбора, k-предсказывающий алгоритм А для КС-грамматики  G=(N,S,P,S)  использует входную ленту, магазин и выходную ленту и, по существу, моделирует работу МП-преобразователя, опустошающего магазин.

При чтении анализируемой цепочки, находящейся на  входной  ленте, входная головка может “заглядывать вперед” на k очередных символов.

На каждом такте сначала определяется  аванцепочка u и верхний символ магазина Х. Затем рассматривается элемент М(Х, u) управляющей таблицы и в соответствии с его содержанием выполняется одно из 4 действий:

1) если М(Х, u) = (b, i), то (x, Xa, p) (x, ba, p i), т.е. верхний символ магазина заменяется цепочкой b  и к выходу добавляется номер правила i, входная головка не сдвигается;

2) если М(а, u)= «выброс» и x=a , то (x, aa, p) ( , a, p), т.е. если верхний символ магазина совпадает с текущим входным символом, то он выбрасывается из магазина и входная головка сдвигается на один символ вправо;

3) если алгоритм достигает конфигурации (e, $, p), работа прекращается и выходная цепочка p называется разбором первоначальной входной цепочки. Будем считать, что M($, e) = «допуск» и (e, $, p) — допускающая конфигурация;

4) если M(Х, u)= «ошибка», то разбор прекращается и выдается сообщение об ошибке, а соответствующая конфигурация (x, Xa, p) называется ошибочной.

Для построения корректной управляющей таблицы М для заданной LL(1)-грамматики можно использовать следующий алгоритм:

Вход алгоритма: заданная LL(1)-грамматика G=(N, S, P, S).

Выход алгоритма: управляющая таблица М.

Описание алгоритма.

$ — маркер дна магазина. Таблица М определяется на множестве (N È S È {$})´(S È {e}) следующим образом:

1) если А®a — правило из P с номером i, то М(А, а) = (a, i) для всех (а¹е)ÎFIRST₁(a); если еÎFIRST₁(a), то М(А, b) = (a, i) для всех bÎFOLLOW₁(A);

2) М(а, а) = «выброс» для всех аÎS;

3) М($, е) = «допуск»;

4) в остальных случаях М(X, а)= «ошибка» для XÎ N È S È {$} и аÎS È {e}.

 

3. Описание синтаксических конструкций

 

Синтаксическая диаграмма  оператора присваивания:

Выражение оператора условия:

 

Синтаксическая диаграмма конструкции  If

 

 

 

 

 

 

Синтаксическая диаграмма описания переменных

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4 Грамматика, описывающая язык.

 

1)  S -> VAR PER; IF A THEN B ELSE B           12) I->+TI 

2) PER->K: INTEGER; M: DOUBLE;                 13) I->-TI

3) K -> F,F                                                         14) J->*FJ

4) F-> P                                                              15) J->/FJ

5) M-> F,F                                                          16) B->P:=E

6) A->E>E                                                           17) I->e          

7) A->E<E                                                          18) J->e               

8) E->TI                                                        

9) T->FJ                                                      

10) F->P                                                         

11) F->(E)       

 

5.Управляющая таблица такого анализатора построена по приведённому выше алгоритму и приведена ниже.

 
6.Листинг  программы:

unit Unit1;

 

interface

 

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, DB, ADODB, Grids, ComCtrls, StdCtrls, Buttons, XPMan, ExtCtrls;

 

type

  TForm1 = class(TForm)

    Memo1: TMemo;

    BitBtn1: TBitBtn;

    AT: TADOTable;

    ADOConnection1: TADOConnection;

    DataSource1: TDataSource;

    Button2: TButton;

    Kontr: TPageControl;

    TabSheet1: TTabSheet;

    StringGrid1: TStringGrid;

    TabSheet2: TTabSheet;

    StringGrid_UprTabl: TStringGrid;

    TabSheet4: TTabSheet;

    TV: TTreeView;

    OpenDialog1: TOpenDialog;

    TabSheet3: TTabSheet;

    TVV: TTreeView;

    TabSheet5: TTabSheet;

    Memo2: TMemo;

    TabSheet6: TTabSheet;

    Memo3: TMemo;

    GroupBox1: TGroupBox;

    GroupBox2: TGroupBox;

    Image1: TImage;

    Image2: TImage;

    procedure BitBtn1Click(Sender: TObject);

    procedure FormCreate(Sender: TObject);

   procedure Button2Click(Sender: TObject);

procedure SintaxTree(T:TTreenode; l,r: integer);

    procedure BuildSintaxTree;

    procedure Button3Click(Sender: TObject);

 

 

  private

    { Private declarations }

    StrCount :integer;

    Pri :array [1..255] of integer;

    Str :array [1..255] of string;

    procedure RecBuildTree(T: TTreeNode; i :integer);

 

  public

    { Public declarations }

  end;

 

var

  Form1: TForm1;

    globalX,GlobalY:integer;

 

 

implementation

 

var typ:array [3..10] of string=('Îïåðàòîð ïðèñâàèâàíèÿ','Çíàê ñðàâíåíèÿ','Çíàê îïåðàöèè','Ïåðåìåííàÿ','Öåëîå ÷èñëî','Ñêîáêà','Çàðåçåðâèðîâàíîå ñëîâî','Âåùåñòâåííîå ÷èñëî');

list:array [1..100] of string;

listZ:array [1..100] of integer;

list_cur:integer;

 

{$R *.dfm}

procedure LoadTiGrid();

var i,j,b,bj:integer;

begin

                form1.AT.First;

    for j:=0 to 28 do    begin

    for i:=0 to 17 do    begin

              form1.StringGrid_UprTabl.Cells[i,j+1]:=form1.AT.Fields.Fields[i].AsString;

                          end;

              form1.AT.Next;

                          end;

form1.StringGrid_UprTabl.Cells[1,0]:='VAR';

form1.StringGrid_UprTabl.Cells[2,0]:='IF';

form1.StringGrid_UprTabl.Cells[3,0]:='THEN';

form1.StringGrid_UprTabl.Cells[4,0]:='ELSE';

form1.StringGrid_UprTabl.Cells[5,0]:='ZN';