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

Автор работы: Пользователь скрыл имя, 17 Января 2014 в 16:57, курсовая работа

Описание работы

Язык должен допускать использование логических выражений, в состав которых могут входить отношения, круглые скобки и знаки логических операций: И, ИЛИ, НЕ и, в случае наличия в языке логического типа, константы и переменные этого типа. Приоритет операций обычный.
Операции над переменными структурированного типа определяются вариантом задания.
Состав операторов языка:
оператор присваивания;
оператор ввода;
оператор вывода;
составной оператор;

Скачать архив (226.39 Кб) Сколько стоит заказать работу?
Файлы: 1 файл

Теория языков прогрммирования.doc

— 561.00 Кб (Скачать файл)

Вход: лексема типа «однолитерный  разделитель» или «двулитерный разделитель»;.

 

  1. Процедура AddLexem(Type, Lexem) – добавляет запись(pos) о лексеме в таблицу лексем заданного класса и вызывает процедуру WriteToken(Type,pos);

Вход: лексема и ее тип.

 

  1. Процедура WriteToken(Type, Position) – формирует токен и записывает его в выходной поток токенов.

Вход: номер лексемы в соответствующей таблице лексем.

 

3.4. Таблицы лексем.

  1. Таблица ключевых слов.

Таблица ключевых слов

имя ключевого слова


  1. Таблица идентификаторов.

Таблица идентификаторов

имя

Тип

значение 


  1. Таблица целых констант.

Таблица целых констант

значение 


  1. Таблица разделителей.

Таблица разделителей

Разделитель


  1. Таблица строковых констант.

Таблица строковых констант

значение


  1. Таблица пользовательских типов. (Заполняется на этапе синтаксического анализа)

Таблица пользовательских типов

Имя

Начало

Конец


  1. Таблица меток (Заполняется на этапе синтаксического анализа)

Таблица меток

Имя

Номер тетрады


  1. Таблица строковых переменных. (Заполняется на этапе синтаксического анализа)

Таблица строковых переменных

Имя

Длина

Значение


  1. Таблица промежуточных значений. (Заполняется на этапе синтаксического анализа)

Таблица промежуточных значений

Тип

Значение


 

 

3.5. Тестирование лексического  анализатора

 

Тестовая программа

Выходной поток токенов

program Test;

const

  C=10;

type

    TCounter=0..C;

var

  i:TCounter;

  CurEl:integer;

  summa:integer;

begin

  writeln(‘Hello World!!!’);

  i:=0;

  summa:=0;

  repeat

        read(CurEl);

        summa:=summa+CurEl;

        i:=i+1;

  until i=C;

  write(summa);

end.

program 1 1 id 2 1 ; 4 1

const 1 2

  id 2 2 = 4 2 nat 3 1 ; 4 1

type 1 15

  id 2 3 = 4 2 nat 3 2 .. 4 19 id 2 2 ; 4 1

var 1 3

  id 2 4 : 4 4 id 2 3 ; 4 1

  id 2 5 : 4 4 integer 1 4 ; 4 1

  id 2 6 : 4 4 integer 1 4 ; 4 1

begin 1 7

  writeln 1 17 ( 4 9 scon 5 1 ) 4 10 ; 4 1

  id 2 4 := 4 7 nat 3 2 ; 4 1

  id 2 6 := 4 7 nat 3 2 ; 4 1

  repeat 1 8

    read 1 10 ( 4 9 id 2 5 ) 4 10 ; 4 1

    id 2 6 := 4 7 id 2 6 + 4 12 id 2 5 ; 4 1

    id 2 4 := 4 7 id 2 4 + 4 12 nat 3 3 ; 4 1

  until 1 9 id 2 4 = 4 2 id 2 2 ; 4 1

  write 1 11 ( 4 9 id 2 6 ) 4 10 ; 4 1

end 1 12 . 4 13


 

 

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

Статические таблицы лексем:

 

1. Таблица ключевых  слов

  

4. Таблица разделителей

1

program

  

1

;

2

const

  

2

=

3

var

  

3

,

4

integer

  

4

:

5

char

  

5

[

6

string

  

6

]

7

begin

  

7

:=

8

repeat

  

8

<=

9

until

  

9

(

10

read

  

10

)

11

write

  

11

*

12

end

  

12

+

13

and

  

13

.

14

label

  

14

<

15

type

  

15

>

16

readln

  

16

>=

17

writeln

  

17

<>

18

goto

  

18

/

19

if

  

19

..

20

then

      

21

else

      

22

length

      

23

concat

      

24

replace

      

25

pos

      

26

StrChar

      

27

copy

      

28

Same

      

29

or

      

30

not

      

 

Сформированные таблицы лексем:


 

 

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

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

Опишем порядок действий, выполняемых при разработке синтаксического анализатора.

4.1. Построение КС-грамматики входного языка

Для построения КС-грамматики входного языка необходимо:

  1. Заменить металингвистические переменные БНФ обозначениями нетерминальных символов, используя короткие имена;
  2. В качестве терминальных символов использовать токены;
  3. Металингвистический символ «::=» заменить символом «à»;
  4. Заменить одну металингвистическую формулу с n альтернативами на n правил грамматики с одинаковым символом в левой части правила вывода;
  5. Исключить металингвистические символы [ ] и { }, включив в правила грамматики e-правила и рекурсивные правила.

 

Получившаяся грамматика должна быть грамматикой простого предшествования.

 

Грамматика  простого предшествования

 

Синтаксический анализ, основанный на простом предшествовании, использует для выделения основы правовыводимой цепочки αβw три отношения предшествования (<), (=) и (>) следующим образом:

 

    • если β — основа, то между всеми смежными символами цепочки α выполняется либо отношение (<), либо (=);
    • между последним символом цепочки α и первым символом цепочки β выполняется отношение (<);
    • между смежными символами основы выполняется отношение (=);
    • между последним символом цепочки β и первым символом цепочки w выполняется отношение (>).

Очевидно, что правый конец основы правовыводимой цепочки грамматики простого предшествования можно выделить, просматривая эту цепочку слева направо до тех пор, пока впервые не встретится отношение (>). Для нахождения левого конца основы надо просмотреть ее назад, пока не встретится отношение (<). Цепочка, заключенная между отношениями (<) и (>), будет основой. Если грамматика является обратимой, т. е. не содержит правил с одинаковой правой частью, то основу можно однозначно свернуть. Этот процесс продолжается до тех пор, пока входная цепочка не свернется к начальному символу (либо пока дальнейшие свертки окажутся невозможными).

 

Отношения предшествования для  КС-грамматики G = (N, Σ, Р, S) определяются на множестве (N U Σ U {┴}) × (N U Σ U {ε}) следующим образом:

    • X < У, если в множестве правил грамматики Р есть правило А -> αXBβ и существует вывод В =>+ Yγ;
    • X = Y, если в Р содержится правило вида А -> αXYβ;
    • X > а, если в Р есть правило вида А -> αBYβ и существуют выводы В =>+ γX и Y => аδ (если У=>° аδ, то Y= а);
    • ┴ < X для всех X, для которых S =>+ Хα;
    • Y > ε для всех Y, для которых S =>* αY.

 

КС-грамматика G = (N, Σ, P, S) называется грамматикой предшествования, если она приведенная, не содержит ε -правил и для любой пары символов из множества N U Σ выполняется не более одного отношения предшествования.

 

Обратимая грамматика предшествования  называется грамматикой простого предшествования.

 

Построение  грамматики по БНФ

 

 

    S    ->  pro id  ;   Def BOp . 

    S    ->  pro id  ;   BOp . 

    S    ->  Def BOp . 

    S    ->  BOp . 

 

    Def  ->  DfL Def

    Def  ->  DfL

    Def  ->  DfC Def

    Def  ->  DfC

    Def  ->  DfT Def

    Def  ->  DfT

    Def  ->  DfV Def

    Def  ->  DfV

 

    DfL  ->  lab LLb

    LLb  ->  M   ; 

   LLb  ->  M   ,   LLb

 

    DfC  ->  con LCn

    LCn  ->  Cn1 ;   LCn

   LCn  ->  Cn1 ; 

    Cn1  ->  id  =   Pex

 

   DfT  ->  typ LTp

    LTp  ->  Tp1 ;   LTp

    LTp  ->  Tp1 ; 

    Tp1  ->  id  =   Typ

    Tp1  ->  id  =   id

   Typ  ->  Cid ..  Cid

    Typ  ->  int

   Typ  ->  chr

    Typ  ->  str

 

    DfV  ->  var LVr

    LVr  ->  DV1 ; 

    LVr  ->  DV1 ;   LVr

    Vr1  ->  id

    Vr1  ->  Vr1 ,   id

    Vrs  ->  Vr1

    DV1  ->  Vrs :   id

    DV1  ->  Vrs :   int

    DV1  ->  Vrs :   chr

    DV1  ->  Vrs :   str

 

    M    ->  id

    M    ->  nat

 

    Opl  ->  M   :   Op

   Opl  ->  Op

    Op   ->  BOp

    Op   ->  O:=

    Op   ->  OIO

    Op   ->  OMn

 

    BOp  ->  beg OPs end

    OPs  ->  Op1

    Op1  ->  Opl

    Op1  ->  Opl ;   Op1

 

    O:=  ->  id  :=  Pex

 

    OIO  ->  OIn

    OIO  ->  OOu

    OIn  ->  rd  (   Vrs ) 

    OOu  ->  wr  (   LWr ) 

    W1   ->  Pex

    W1   ->  Pex ,   W1

    LWr  ->  W1

 

    OMn  ->  ORu

    OMn  ->  OGo

    OMn  ->  OIf

    ORu  ->  rpt Ops unt Lex

    OGo  ->  got M 

    OIf  ->  if  Lex thn Opl

    OIf  ->  if  Lex thn Opl els Opl

 

    Lex  ->  Z1  F1

    Lex  ->  Z1

   Z1   ->  Z2  F2

    Z1   ->  Z2

    Z2   ->  Z3

    Z3   ->  not Z3

    Z3   ->  Z4

    Z4   ->  sme (   str ,   str ) 

    Z4   ->  Pex Sgn Pex

    Z4   ->  (   Lex ) 

    F1   ->  or  Z1  F1

    F1   ->  or  Z1

    F2   ->  and Z2  F2

    F2   ->  and Z2

    Sgn  ->  < 

    Sgn  ->  > 

    Sgn  ->  = 

    Sgn  ->  <=

    Sgn  ->  >=

    Sgn  ->  <>

 

    Pex  ->  T1  E1

    Pex  ->  T1

    E1   ->  +   T1  E1

    E1   ->  +   T1

    E1   ->  -   T1  E1

    E1   ->  -   T1

    E2   ->  *   T2  E2

    E2   ->  *   T2

    E2   ->  /   T2  E2

    E2   ->  /   T2

    T1   ->  T2  E2

    T1   ->  T2

    T2   ->  id

    T2   ->  Cid

    T2   ->  Scn

    T2   ->  Fun

  T2   ->  (   Pex ) 

 

    Fun  ->  int (   Pex ) 

    Fun  ->  str (   Pex ) 

    Fun  ->  lng (   Pex ) 

    Fun  ->  cnc (   Pex ,   Pex ) 

    Fun  ->  pos (   Pex ,   Pex ) 

    Fun  ->  sym (   Pex ,  Pex ) 

 

    Cid  ->  -   nat

    Cid  ->  nat

 

    Scn  ->  '   Sms ' 

    Scn  ->  '   ' 

    Sms  ->  Sym

    Sym  ->  Any

    Sym  ->  Any Sym

 

4.2. Разбиение грамматики на подграмматики

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

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

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

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

  1. Совокупности выделенных из грамматики взаимосвязанных правил должна представлять собой КС-грамматику.
  2. Основной символ подграмматики становится (специальным) терминальным символом исходной грамматики.
  3. Если множества нетерминальных символов подграмматики и модифицированной   исходной   грамматики  не  пересекаются,  то  синтаксический анализ для каждой из них может быть реализован при помощи отдельного процессора с магазинной памятью.

 

1. Базовая грамматика программы GR1 (Начальный символ S)

Терминалы :

  pro = program      ;  id  = идент      ;  ;   =   ;        ;

  Def = *БлокОпис    ;  BOp = *БлокОпер  ;  .   =   .        ;

Нетерминалы :

  S   = НачСимвол                 4 ;

Правила :

   1)  S    ->  pro id  ;   Def BOp . 

   2)  S    ->  pro id  ;   BOp . 

   3)  S    ->  Def BOp . 

   4)  S    ->  BOp . 

 

2. Грамматика раздела описаний GR2 (Начальный символ Def)

Терминалы :

  DfL = ОписМеток    ; DfC = ОписКонст ;  DfT = ОписТипов    ;

  DfV = ОписПерем ;

Информация о работе Разработка языка программирования, являющегося подмножеством заданного языка