Списковые структуры.

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

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

Например, для строки

†this is a list example†

список литералов

<†th†, †is †, †is †, †a †, †list example†>

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

WRITE(‘this is a list example’);

WRITE(‘th’, ‘is ‘, ‘is ‘, ‘a ‘, ‘list example’);

Спискам, как и строкам, могут быть присвоены имена, например:

L = <†th†, †is †, †is †, †a †, †list example†>

M = <†this is a list example†>

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

Если элемент x находится в списке K, мы обозначаем факт как принадлежности списку как

x Î K, если список K не имеет ни одного вхождения объекта x, мы говорим, x Ï K.

Например, †is † Î L, но †is † Ï M.

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

L₁ = †th†

L₂ = †is †

L₃ = †is †

L₄ = †a †

L₅ = †list example†

В то время M как содержит только одну строку

M₁ = †this is a list example†

Мы будем использовать индексы для именования элементов списков, используя 1 для обозначения первого элемента и т.д. L можно назвать 5-список, M - 1-список. Список без элементов, 0-список, называется пустым списком и обозначается <>. Необходимо отличать список, содержащий в себе одну строку, от этой строки. Например, M – 1-список с первым и единственным элементом M₁ и

M = <M₁>, но M ¹ M₁

Также необходимо иметь ввиду, что

<††> ¹ <>

потому что <††> это 1-спиоск, первый элемент которого пустая строка, а <> - 0-список и первый элемент там отсутствует.

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

C = <c, h, a, r, a, c, t, e, r>

Является списком символов и это не то же самое, что строка †character†

Следующий список является списком списков

<M, M> = <<†this is a list example†>, <†this is a list example†>>

где элементами 2-списка являются 1-списки М, рассмотренные выше.

Список может иметь элементы различных видов, например

Q = <A, <A>, †A†>

Содержит элементы, которые являются соответственно символом, списком и строкой.

Элемент данного списка Q₂ содержит единственный элемент – символ A.

(Q₂)₁ = A