Программно-методический комплекс для обучения процессу создания компиляторов
Рефераты >> Программирование и компьютеры >> Программно-методический комплекс для обучения процессу создания компиляторов

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

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

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

В разделе «Шаги» перечисляются номера произведенных шагов. Раздел «Таблица кодов лексем» служит для отслеживания позиции в таблице кодов лексем и хранит значения таблицы и кода (или спецификатора) с которыми в дальнейшем происходит сравнение текущего элемента грамматики БНФ. Раздел «Элемент грамматики БНФ» содержит имя элемента, имя конструкции, в которую он входит, тип текущего элемента грамматики, номер таблицы, соответствующей ему, а также код (для терминальных символов), определенный по таблице кодов терминальных символов. В разделе «Формируемая таблица переходов» отслеживается текущая ячейка формируемой таблицы переходов, куда заносится формируемое значение, а также позиция следующей ячейки, с которой будет производиться работа на следующем шаге. В разделе «Выполненное действие» указывается выполненное действие.

Таблица построения предлагается как вспомогательное средство для заполнения формируемой таблицы переходов. Заполнять все шаги и ячейки в ней не обязательно, главное понять логику заполнения формируемой таблицы переходов. Приобретя опыт, в дальнейшем, можно обходиться без таблицы построений, заполняя формируемую таблицу переходов по БНФ грамматике, тексту программы, таблице кодов терминальных символов, таблице кодов лексем.

Из данных, полученных в разделе «Формируемая таблица переходов, текущая позиция» таблицы построения, заполняется формируемая таблица переходов. В результате должна получиться таблица 14.

Принятые сокращения в таблице построений.

НС – нетерминальный символ

ТС – терминальный символ

ИД – идентификатор

Лх – литерал, где х: Ц – целый тип, В – вещественный тип, С – строковый тип.

Л – литерал любого типа.

Наличие знака «–» впереди типа у элемента грамматики БНФ показывает, что данный элемент в разборе может не участвовать.

При заполнении таблицы построений особую сложность представляет работа с переходами. Ниже описывается работа с ними.

При обнаружении терминального символа в грамматике БНФ, необходимо осуществить переход на первый элемент конструкции с тем же именем. В таблице построений определяется номер последней не занятой строки в формируемой таблице переходов. Номером следующей позиции указывается номер этой строки, номер столбца – 1. Значение вносимого значения должно указывать на вторую ячейку последней пустой строки. Следующим шагом заполняется значение текущий позиции, адрес возврата и адрес следующей позиции. Например. После нахождения терминального символа <prog-name> начинает рассматриваться первый элемент конструкции <prog-name> – id. В формируемой таблице переходов последней свободной строкой является строка 2, на нее и осуществляется переход, следующая позиция указывает на строку 2, столбец 1 (шаг 2). На третьем шаге в ячейку возврата 2,1 (где 2 – номер строки, 1 – номер столбца) будет внесено значение, указывающее на ячейку 1,4, т.к. переход осуществлен из ячейки 1,3. Текущая позиция – 2,1, следующая позиция – 2,2.

При возврате возникают другие трудности. К примеру, при окончании конструкции происходит переход на пустую ячейку, затем осуществляется переход на ячейку возврата. Значение, заполненное в ячейке возврата ищется по таблице. По полученному значению осуществляется переход. Например, при окончании конструкции <id-list> (шаг 20), текущей ячейкой оказывается ячейка 5,7. Затем производится переход в ячейку 5,1 (шаг 21). По таблице определяем, что адрес возврата @4,3 (значение из шага 14), т.е. перейти на четвертую строку, третий столбец.

Далее отыскивается положение в грамматике БНФ по имени предыдущей позиции. Например, после перехода в ячейку 4,3 (шаг 22) отыскиваем в таблице имя элемента грамматики ячейки 4,2 (значение из шага 13), им оказывается нетерминальный символ <id-list> конструкции <dec>. По грамматике БНФ определяется, что следующий элемент конструкции <dec> является «:».

Таблица 13 – Таблица построений

Шаги

Таблица кодов лексем

Имя в программе

Элемент грамматики БНФ

Результат сравнения

Формируемая таблица переходов

Выполненное действие

текущая позиция

следующая позиция

позиция

табл

код, специф

тип

имя

текущая конструкция

тип

табл

код

(для ТС)

строка

столбец

вносимое значение

строка

столбец

1

1

1

1

ТС

PROGRAM

PROGRAM

<prog>

–ТС

1

1

+

1

2

$1,1

1

3

 

2

2

2

1

ИД

Prog1

<prog-name>

<prog>

НС

     

1

3

@2,2

2

1

 

3

2

2

1

ИД

Prog1

           

2

1

@1,4

2

2

 

4

2

2

1

ИД

Prog1

id

<prog-name>

ИД

2

 

+

2

2

$2,1

2

3

 

5

3

1

27

ТС

;

;

<prog-name>

–ТС

1

27

+

2

3

$1,27

2

4

 

6

4

1

2

ТС

VAR

 

<prog-name>

       

2

4

 

2

1

конец конструкции

7

4

1

2

ТС

VAR

           

2

1

 

1

4

переход

8

4

1

2

ТС

VAR

VAR

<prog>

–ТС

1

2

+

1

4

$1,2

1

5

 

9

5

2

2

ИД

a

<dec-list>

<prog>

НС

     

1

5

@3,2

3

1

 

10

5

2

2

ИД

a

           

3

1

@1,6

3

2

 

11

5

2

2

ИД

а

<dec>

<dec-list>

НС

     

3

2

@4,2

4

1

 

12

5

2

2

ИД

а

           

4

1

@3,3

4

2

 

13

5

2

2

ИД

а

<id-list>

<dec>

НС

     

4

2

@5,2

5

1

 

14

5

2

2

ИД

а

           

5

1

@4,3

5

2

 

15

5

2

2

ИД

а

id

<id-list>

ИД

2

 

+

5

2

$2,2

5

3

 

16

6

1

29

ТС

,

,

<id-list>

ТС

1

29

+

5

3

$1,29

5

4

 

17

7

2

3

ИД

b

id

<id-list>

ИД

2

 

+

5

4

$2,3

5

5

 

18

8

1

29

ТС

,

,

<id-list>

ТС

1

29

+

5

5

$1,29

5

6

 

19

9

2

4

ИД

c

id

<id-list>

ИД

2

 

+

5

6

$2,4

5

7

 

20

10

1

31

ТС

:

 

<id-list>

       

5

7

 

5

1

конец конструкции

21

10

1

31

ТС

:

           

5

1

 

4

3

переход

22

10

1

31

ТС

:

:

<dec>

ТС

1

31

+

4

3

:

4

4

 

23

11

1

5

ТС

INTEGER

<type>

<dec>

НС

     

4

4

@6,1

6

1

 

24

11

1

5

ТС

INTEGER

           

6

1

@4,5

6

2

 

25

11

1

5

ТС

INTEGER

INTEGER

<type>

ТС

1

5

+

6

2

$1,5

6

3

 

26

12

1

27

ТС

;

 

<type>

       

6

3

 

6

1

конец конструкции

27

12

1

27

ТС

;

           

6

1

 

4

5

переход

28

12

1

27

ТС

;

 

<dec>

       

4

5

 

4

1

конец конструкции

29

12

1

27

ТС

;

           

4

1

 

3

3

переход

30

12

1

27

ТС

;

;

<dec-list>

–ТС

1

27

+

3

3

$1,27

3

4

 

31

13

1

3

ТС

BEGIN

 

<dec-list>

       

3

4

 

3

1

конец конструкции

32

13

1

3

ТС

BEGIN

           

3

1

 

1

6

переход

33

13

1

3

ТС

BEGIN

BEGIN

<prog>

ТС

1

3

+

1

6

$1,3

1

7

 

34

14

2

2

ИД

а

<stmt-list>

<prog>

–НС

     

1

7

@7,2

7

1

 

35

14

2

2

ИД

а

           

7

1

@1,8

7

2

 

36

14

2

2

ИД

а

<stmt>

<stmt-list>

НС

     

7

2

@8,2

8

1

 

37

14

2

2

ИД

a

           

8

1

@7,3

8

2

 

38

14

2

2

ИД

a

<assign>

<stmt>

НС

     

8

2

@9,2

9

1

 

39

14

2

2

ИД

a

           

9

1

@8,3

9

2

 


Страница: