Пред.Страница След.Страница Раздел Содержание

6.4. Распознавание лексем

Выявление лексем во входном тексте может быть выполнено с помощью распознавателя. Обычно лексемы определяются с помощью автоматных грамматик, поэтому распознаватель лексем должен представлять собой конечный автомат. Для построения распознавателя необходимо иметь грамматику, порождающую последовательность лексем заданного входного языка, наборы символов, определяющие начало и конец каждой лексемы. Эти данные могут быть получены из заданной схемы грамматики. Так схема грамматики для последовательности лексем может быть построена на основе определений лексем. Наборы символов для начала и конца лексемы, обозначенной соответственно нетерминальными символами L и K, определяются функциями ПЕРВ(L) и СЛЕД(K).

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

1. В заданной грамматике входного языка выделить правила, определяющие лексемы L₁, L₂, … , L_r.
2. Каждое правило, определяющее лексему L_j, вида L_j ®x A_j заменить правилом I®x A_j, где I – начальный символ искомой грамматики.
3. Для каждой лексемы имеющей заключительное правило L_j ®x заменить это правило правилом вида L_j ®xZ, где Z – конечный символ искомой грамматики.
4. Для каждой лексемы имеющей заключительное правило K_j ®$, построить множество СЛЕД(K_j) = { x_j1, x_j2, …, x_jq } и множество правил вида:
   K_j ® x_j1Z | x_j2 Z |…| x_jqZ.
5. Для каждой лексемы L_j, состоящей из нескольких символов с₁, с₂,…, с_m построить цепочку правил вида:
   L_j ® с₁B₁ | с₂ B₂ |…| с_m Z.
6. Если в грамматика имеется две многосимвольные лексемы L_j и L_k, такие что символы L_k представляют собой начальный отрезок лексемы L_j, например, L_k®с₁, то нужно построить множество СЛЕД(с₁) = { z_j1, z_j2, …, z_jt }, исключить из этого множества символ с₂ и построить множество правил вида:
   B₁® z_j1Z | z_j2 Z |…| z_jtZ.
7. Объединить начальное состояние I и заключительное состояние Z, чтобы построить распознаватель многократного действия.

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

В качестве примера рассмотрим построение грамматики последовательности лексем для входного языка, приведенного в предыдущем разделе.

Лексемами этого языка являются, во-первых, идентификаторы и числа, которые описываются следующими правилами:

<Идентификатор> ::= <буква><Про_идентификатор>

<Про_идентификатор>::= <буква><Про_идентификатор> |
<цифра><Про_идентификатор>

<Про_идентификатор>::= $

<Число> ::= <цифра><Про_число>

<Про_число>::= <цифра><Про_число>

<Про_число>::= $

<буква>::=a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z

<цифра> ::= 0|1|2|3|4|5|6|7|8|9

Множества символов, которые могут следовать за этими лексемами, определяются следующими функциями:

СЛЕД(<Про_идентификатор>) = {:,;, =, &, |, !, ), ,},

СЛЕД(<Про_число>) = {;,&, |, )}.

Добавим к описанию лексем правила, завершающие лексемы, начальный и конечный символы грамматики, а также обозначим нетерминальные символы буквами A и B.

В результате поучаем правила искомой грамматики в виде:

<I> ::= <буква><A>

<A>::= <буква><A> | <цифра><A>

<A>::= :Z | ;Z | =Z | &Z | ‘|’Z | !Z | )Z | ,Z

<I> ::= <цифра><B>

<B>::= <цифра><B>

<B>::= ;Z | &Z | ‘|’Z | )Z

<буква>::=a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z

<цифра>::= 0|1|2|3|4|5|6|7|8|9

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

Порождающие правила для этих лексем запишем так:

<Отношение> ::= !<Про_неравенство>

<Про_неравенство>::= =<Про_отношение>

<Совпадающие_знаки> ::= =<Про_совпадающие_знаки>

<Про_совпадающие_знаки>::= $

<Про_совпадающие_знаки>::= = <Про_отношение>

<Про_отношение>::= $

Заменяя нетерминальные символы буквами C, D, E и учитывая символы, завершающие лексемы,

СЛЕД(=) = { (, ~, <буква>},

СЛЕД(==) = { <буква>, <цифра> },

получаем правила искомой грамматики в виде:

<I> ::= !<C>

<C> ::= =<E>

<I> ::= =<D>

<D>::= (Z | ~Z | <буква>Z

<D>::= = <E>

<E>::= <буква>Z| <цифра>Z .

В-третьих, лексемами являются односимвольные терминалы, являющиеся разделителями и знаками операций. Для таких лексем построим правила вида:

<I>::= (Z | )Z | ;Z | &Z | VZ | ~Z |<Z |>Z |,Z| :Z.

Множество построенных порождающих правил является схемой грамматики, порождающей последовательность лексем заданного входного языка. Этим правилам соответствует представленная на рисунке 6.4 диаграмма переходов автомата, являющегося распознавателем лексем.

Рис. 6.4. Диаграмма переходов распознавателя лексем

Пред.Страница След.Страница Раздел Содержание