Синтаксический анализатор

 

       Цель  работы:

       Изучение  основных понятий теории грамматик  простого и операторного предшествования, ознакомление с алгоритмами синтаксического  анализа (разбора) для некоторых  классов КС-грамматик, получение  практических навыков создания простейшего  синтаксического анализатора для  заданной грамматики операторного предшествования. 

       Задание:

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

       Текст на входном языке задается в виде символьного (текстового) файла. Допускается  исходить из условия, что текст содержит не более одного предложения входного языка. Программа должна выдавать сообщения  о наличие во входном тексте ошибок. 

       Исходная  грамматика входного языка форме  Бэкуса-Наура: 

G({if, then,else <, >, =, a, :=, (, ), ;}, {S, F, T, E}, P, S) с правилами P:

S ® F;

F ® if E then T else F | if E then F | a := a   

T ® if E then T else T | a := a  

E ® a<a | a>a | a=a   
 

Множества крайних левых и крайних правых символов L(U), R(U) относительно всех символов грамматики представлены в таблице ^{1. В таблице 3 описаны итоговые множества крайних левых и крайних правых} символов  

Таблица 1

 
 

Таблица 2

 

Таблица 3

 
 
 

       Множества крайних левых и крайних правых терминальных символов L_t(U), R_t(U) относительно всех нетерминальных символов грамматики и итоговые множества крайних левых и крайних правых терминальных символов L_t(U), R_t(U) относительно всех нетерминальных символов грамматики представлены соответственно в таблицах 4 и 5. 

Таблица 4

 

Таблица 5

 
 

Матрица операторного предшествования показана в таблице 5

Таблица 5 – Матрица операторного предшествования.

 
 
 
 
 
 

Входная цепочка: if a1 > a2 then a3 := a5  else a3 := a2; 
 

   

 
 
 

Рис1.Загрузка исходного файла. 

Рис 2.Таблица  лексем. 
 
 

 

Рис 3.Дерево вывода. 
 
 
 
 
 
 
 
 

 Текст программы. 
 

unit FormLab3; 

interface 

uses

  Windows, Messages, SysUtils, Classes, Graphics, Controls,

  Forms, Dialogs, StdCtrls, ComCtrls, Grids,

  LexElem, SyntSymb; 

type

  TLab3Form = class(TForm)

    PageControl1: TPageControl;

    SheetFile: TTabSheet;

    SheetLexems: TTabSheet;

    BtnExit: TButton;

    GroupText: TGroupBox;

    ListIdents: TMemo;

    EditFile: TEdit;

    BtnFile: TButton;

    BtnLoad: TButton;

    FileOpenDlg: TOpenDialog;

    GridLex: TStringGrid;

    SheetSynt: TTabSheet;

    TreeSynt: TTreeView;

    procedure BtnLoadClick(Sender: TObject);

    procedure BtnFileClick(Sender: TObject);

    procedure EditFileChange(Sender: TObject);

    procedure BtnExitClick(Sender: TObject);

    procedure FormCreate(Sender: TObject);

    procedure FormClose(Sender: TObject;

                var Action: TCloseAction);

   private

    { Список лексем }

    listLex: TLexList;

    { Синтаксический стек }

    symbStack: TSymbStack;

    { Процедура инициализации таблицы

      для отображения списка лексем }

    procedure InitLexGrid;

    { Процедура  отображения синтаксического дерева }

    procedure MakeTree(nodeTree: TTreeNode;

                       symbSynt: TSymbol);

   public

    { Public declarations }

  end; 

var

  Lab3Form: TLab3Form; 

implementation 

{$R *.DFM} 

uses FncTree, LexType, LexAuto; 

procedure TLab3Form.InitLexGrid;

{ Процедура инициализации  таблицы

  для отображения  списка лексем }

begin

  with GridLex do

  begin

    RowCount := 2;

    Cells[0,0] := '№ п\п';

    Cells[1,0] := 'Лексема';

    Cells[2,0] := 'Значение';

    Cells[0,1] := '';

    Cells[1,1] := '';

    Cells[2,1] := '';

  end;

end; 

procedure TLab3Form.FormCreate(Sender: TObject);

{ В начале  выполнения инициализируем список  лесем,

  таблицу  идентификаторов и синтаксический  стек }

begin

  InitTreeVar;

  listLex := TLexList.Create;

  symbStack := TSymbStack.Create;

end; 

procedure TLab3Form.FormClose(Sender: TObject;

                      var Action: TCloseAction);

{ В конце выполнения  очищаем список лесем,

  таблицу  идентификаторов и синтаксический  стек }

begin

  symbStack.Free;

  listLex.Free;

  ClearTreeVar;

end; 

procedure TLab3Form.EditFileChange(Sender: TObject);

begin

  { Можно читать  файл, только когда его имя  не пустое }

  BtnLoad.Enabled := (EditFile.Text <> '');

end; 

procedure TLab3Form.BtnFileClick(Sender: TObject);

begin

  if FileOpenDlg.Execute then

  { Выбор имени файла с помощью стандартного диалога }

  begin

    EditFile.Text := FileOpenDlg.FileName;

    BtnLoad.Enabled := (EditFile.Text <> '');

  end;

end; 

procedure TLab3Form.BtnLoadClick(Sender: TObject);

{ Процедура чтения  и анализа файла }

var

  i,iCnt,iErr: integer;

  symbRes: TSymbol;

  nodeTree: TTreeNode;

begin

  { Очищаем список лексем }

  listLex.Clear;

  { Очищаем синтаксический стек }

  symbStack.Clear;

  { Очищаем таблицу отображения списка лексем

    и  синтаксическое дерево }

  InitLexGrid;

  TreeSynt.Items.Clear;

  try

    { Чтение  файла в список строк }

    ListIdents.Lines.LoadFromFile(EditFile.Text);

    except

      MessageDlg('Ошибка чтения файла!',mtError,[mbOk],0);

      Exit;

  end;

  { Анализ  списка строк и заполнение  списка лексем }

  iErr := MakeLexList(ListIdents.Lines,listLex);

  if iErr <> 0 then

  { Если анализ  не успешный, выводим сообщение  об ошибке }

  begin

    MessageDlg(Format('Неверная лексема "%s" в строке %d!',

               [listLex[0].LexInfoStr,iErr]),

               mtWarning,[mbOk],0);

    { Берем позицию ошибочной лексемы из фиктивной лексемы

      в начале списка и позиционируем  на нее список строк }

    ListIdents.SelStart := listLex[0].PosAll;

    ListIdents.SelLength := listLex[0].PosNum;

    { Отображаем позицию ошибки в списке строк }

    ListIdents.SetFocus;

  end

  else

  { Если анализ успешный, отображаем список лексем