Строки и языки

E = M * C + 2

Атрибуты токенов

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

Например, нам могут понадобиться лексемы идентификаторов, номера строк, где эти идентификаторы встретились впервые и т.п. Вся эта (и другая) информация хранится в хаписях таблицы символов (таблице имен).

Пример. Токены и связанные с ними значения атрибутов для инструкции

Это можно рассматривать как пары < токен, значение атрибута >. В некоторых парах нет надобности в значениях атрибута. Тогда <токен, - >

Для определения токенов (для задания шаблонов) используются регулярные выражения.

Алфавит – конечное непустое множество символов.

Обычно алфавит обозначается символом .

Пример.

1. бинарный или двоичный алфавит.
2. множество строчных букв английского алфавита.
3. 

Строка над алфавитом конечная последовательность символов из алфавита .

Пример.

01101 – строка над алфавитом .

Синонимы термина «строка» - слово, предложение, цепочка.

Пустая строка – это строка, не содержащая ни одного символа. Пустая строка обозначается - .

Длина строки – количество символов в строке, с учетом их повторения.

Пример.

обозначение для множества всех строк длины , состоящих из символов алфавита .

Пример.

.

1. независимо от алфавита .
2. 
3. 
4. 
5. …

Между и есть небольшое отличие. алфавит, множество всех строк единичной длины, построенных из символов алфавита .

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

Пример. . .

обозначение множества всех строк над алфавитом , кроме пустой строки, т.е.

Имеют место следующие равенства:

Пусть и строки.

Конкатенация строк и является строкой, сформированной путем дописывания строки

обозначение конкатенации строк и .

Пример.

.

.

Пустая строка – нейтральный элемент по отношению к операции конкатенация, т.е. для любой строки справедливо соотношение .

Язык – подмножество строк из .

Иначе: если алфавит и , то это язык над или в .

Примеры языков.

1. . язык, состоящий из всех строк, в которых единиц следуют за нулями для некоторого :
   .
2. . множество строк, содержащих поровну нулей и единиц:
   .
3. язык, для любого алфавита .
4. пустой язык в любом алфавите.
5. язык, содержащий лишь пустую строку.