II.7.2. Определение границ лексем

Язык констант и идентификаторов является регулярным, т.е. может быть описан с помощью регулярных грамматик. Распознавателем является КА (конечный автомат), поэтому основой для реализации являются КА. Существуют правила, при которых может быть построен КА, распознающий цепочки языка, заданного данной грамматикой. Он для каждой входной цепочки языка определяет, принадлежит ли она языку, заданному автоматом. Кроме того, он выполняет следующие действия:

1. определяет границы лексем, которые в тексте исходной программы не указаны;

2. выполняет действия для сохранения информации о обнаруженной лексеме и выдает сообщение об ошибке, если она не верна.

3.

II.7.3. Выполнение действий, связанных с лексемами

В большинстве компиляторов ЛА и СА – это взаимосвязанные части. Для организации взаимосвязи применяют два метода – это последовательный и параллельный. При 1ом ЛА просматривает весь текст исходной программы от начала до конца и преобразует его в ТЛ, которая заполняется сразу полностью. Компилятор использует ее для следующих фаз компиляции, не изменяя ее. Если в процессе разбора он не смог правильно определить тип лексемы, то считается, что исходная программа содержит ошибку. При параллельном варианте ЛА текста исходной программы выполняется поэтапно (по шагам). Он выделяет лексему в коде и передает ее в СА. СА, выполнив разбор конструкции языка может подтвердить правильность найденной лексемы и обратиться к ЛА за следующей лексемой либо отвергнуть найденную лексему. В этом случае он может проинформировать ЛА о том, что надо вернуться назад, к уже рассмотренному ранее элементу исходного кода и сообщить ему дополнительную информацию о том, какого типа лексему следует ожидать. В взаимодействии между собой, они могут перебрать несколько возможных вариантов лексем и если ни один из них не подойдет, будет считаться, что исходная программа содержит ошибку. Только после того, как СА успешно выполнит разбор очередной конструкции исходного языка, ЛА помещает лексему в ЛА и в ТИ и продолжается разбор в том же порядке.

 

 

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

 

II.7.4. Применение конечных автоматов (КА) для построения ЛА

Конечным автоматом называют

M(Q, V, δ, q_0,F), где

Q – конечное множество состояний автомата

V – конечное множество допустимых входных сигналов (алфавит автомата)

δ – функция перехода, отображающая V*Q(декартовое произведение множеств во множестве подмножеств)

Q: R(Q), т.е.

δ (a,q)=R, a ∈ V, q ∈ Q,

R ≤ Q

q₀ - начальное состояние автомата

q₀ ∈ Q

F – непустое множество конечных состояний автомата

F ≤Q, F 0

 

II.7.5. Алгоритм построения КА

Построение КА M(Q, V, δ, q_0,F) на основе автоматной леволинейной грамматики G(VT,VN,P,S) выполняется по следующему алгоритму:

1) строят множество состояний автомата Q таким образом, чтобы каждому нетерминальному символу из множества VN данной грамматики G соответствовало одно состояние из множества Q автомата M. В множество состояний автомата добавляется одно дополнительное состояние, обозначаемое H. Сохраняя обозначение нетерминальных символов гр. G для множества состояний M можно записать Q=VN ∪{H}

2) входным алфавитом автомата М является множество терминальных символов гр. G V=VT.

3) просмотрев всё множество правил исходной программы, если встречается правило вида

A → t ∈P, где A∈ VN, t ∈VT, то функция переходов δ (H,t) добавляют состояние A и

получают A ∈ δ(H,t). Если встречается правило вида A →B t ∈P, где A,B∈ VN, t ∈VT, то в функцию перехода δ (B,t) автомата М добавляется состояние A: A ∈ δ(B,t).

4) начальное состояние автомата М является состоянием Н

H: q₀ = H

5) множество конечных состояний автомата М состоит из 1 состояния, которое соответствует целевому символу гр. G

G:F={S}

На этом построение автомата заканчивается.

 

II.7.6. Пример применения КА для построения ЛА

Построение на основе леволинейной грамматики. Рассмотрим такую грамматику

G({“a”,”(“,”*”,”)”, ”,”{“,”}”},{S,C,K},P,S)

Все символы выделяются в кавычках, чтобы из фигурных скобок выдел.

P:

S→ (*)|K}

C→(*|Ca|C{|C}|C (|C*|C

K→{|Ka|KC|K*|K)|K{

Это леволинейная регулирующая грамматика. Для преобразования ее к автоматному виду используются специальные автоматы. Результатом 1го из алгоритмов является следующая леволинейная автоматная грамматика

G’({“a”,”(“,”*”,”)”,”{“,},{S,S1,C,C1,K},P’,S)

с правилами P’

S→S1)|K

S1→C*

C→C1*|Ca|C{|C}|C(|C*|C

C1→(

K→K(K*|K)|K{

Переобозначим нетерминальный символ в

C1 S1

D E

Получим грамматику

G’({“a”,”(“,”*”,”)”,”{“,”}”,},{S,E,C,D,K},P’,S)

P’

S→E)|K}

E→C*

C→D*|Ca|C{|C}|C(|C*|C)

D→(

K→{|Ka|KC|K*|K)|K{

Построим КА вида М(Q, V, δ, q_0,F) эквивалентную заданной гр.

Шаги:

1)строит множество состояний автомата, получает

Q=VN{H}={S,E,C,D,K,H}

2)в качестве алфавита входного самостоятельного автомата берут множество терминальных символов автомата, получаем

V={“a”,”(“,”*”,”)”,”{“,”}”}

3)рассмотрим множество правил грамматики

для правила S→ E)|K} имеем δ (E,”)”)={S}; δ (K,”}”={S}

для правила E→C* имеем δ (C,”*”)={E}

для правила C→D*|Ca|C{|C}|CC|C*|C) имеем

δ (D,”*”)={C}; δ (C,”a”)={C}; δ (C”{“)={C}; δ (C,”{“)={C}; δ (C,”(“)={C}

для правила D→C имеем δ (H,”(“)={D}

для правила K→{|Ka|K(|K*|K)|K{ имеем

δ (H,”{“)={K}; δ (K,”a”)={K}; δ (K,”(“)={K};

δ (K,”*”)={K}; δ (K,”)”)={K}; δ (K,”{“)={K}.

4)нормальным состоянием автомата является q₀ = 0

5) множеством конечных состояний автомата является множество F={S}

Выполнение алгоритма закончено. В итоге получили автомат

M({S,E,C,D,K,H},”a”,”(“,”*”,”)”,”{“,”}”} δ,H,{S})

с функциями переходов

δ (H,”{“)=K

δ (H,”(“)=D

δ (K,”a”)={K}

δ (K,”(“)={K}

δ (K,”*”)={K}

δ (K,”)”)={K}

δ (K,”{“)={K}

δ (K,”}”)={S}

δ (D,”*”)={C}

δ (C,”a”)={C}

δ (C,”{“)={C}

δ (C,”}”)={C}

δ (C,”(”)={C}

δ (C,”*”)={E,C}

δ (C,”)”)={C}

δ (E,”)”)={S}

Граф перехода этого автомата изображен на следующем рисунке

 

Это граф переходов недертем.

Строят эквивалентный ему детер. КА

M’({S,E,C,D,K,H},”a”,”(“,”*”,”)”,”{“,”}”} δ’,H,{S})

с функцией перехода

1…13 – те же, что и для недер. КА

δ’ (C,”)”)={C}

δ’ (C,”*”)={E}

δ’ (E,”a”)={C}

δ’ (E,”{“)={C}

δ’ (E,”}”)={C}

δ’ (E,”)”)={C}

δ’ (E,”*”)={E}

δ’ (E,”)”)={S}

 

Граф переходов этого автомата на следующем рисунке

 

Получают ЛА распознаватель для двух типов комментариев, если учесть, что а может обозначать любой символ алфавитно-цифровой символ, кроме а (,*,),{,}

 

II.8. Принципы построения синтаксических анализаторов (СА)

II.8.1. Значение СА

Это часть компилятора, которая отвечает за выявление и проверку синтаксических конструкций входного языка. В задачу СА входит:

1. поиск и выделение синтаксических конструкций в тексте исходной программы

2. установка типа и проверка правильности каждой синтаксической конструкции

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

Без синтаксического разбора работа компилятора бессмысленна, в то время, как ЛА в принципе не является обязательным, т.к. лексический разбор может быть решен на этапе синтаксического разбора. ЛА позволяет избавить сложный по структуре СА от решения сравнительно простых задач по выявлению и запоминанию лексем исходной программы. Выходом ЛА является ТЛ, которая используется на входе СА. Он исследует только один компонент каждой лексемы, т.е. ее тип. Остальная информация о лексеме используется на более поздних фазах компиляции. СА воспринимает выход СА и разбирает его в соответствии с грамматикой входного языка. В ней обычно не уточняется, какие конструкции следует считать лексемами. Обычно распознаются ключевые слова, константы и идентификаторы. Эти конструкции могут быть распознаны и СА. Какие конструкции должен распознать СА и ЛА определяет разработчик компилятора. В основе СА лежит распознаватель текста исходной программы, построенный на основе гр. входного языка. Чаще всего это КС грамматика(косвенно свободная). Поэтому в основе построения СА используется распознаватель для КС грамматик, а ими являются МП-автоматы, которые линейно ограничены.