4. Синтаксический анализ регулярных языков

Задачей синтаксического анализа считается проверка, принадлежит ли произвольная заданная цепочка   T ^* языку L(G) для заданной грамматики G. На основе методов синтаксического анализа решаются задачи синтаксически управляемой обработки данных (например, текстов). Такой задачей является и задача трансляции. Регулярные языки и порождающие их А-грамматики используются, в основном, для лексического анализа  распознавания в тексте его лексических единиц, лексем, т.е. слов, из которых по более сложным правилам строится текст. 

Если язык задан регулярным выражением, то для синтаксического анализа этого языка можно построить его А-грамматику с помощью алгоритма из теоремы 3.8. Для анализа регулярного языка используют устройство, называемое конечным автоматом, которое можно построить по А-грамматике языка. 

 

4.1. Конечные автоматы

4.1.1. Основные определения

Конечный автомат состоит из ленты конечной длины, на которой записан текст, и читающей головки, движущейся вдоль ленты слева направо. Автомат в каждый момент находится в каком-то состоянии, которых у него конечное число. На каждом шаге автомат сдвигается на один символ вправо (читает символ) и переходит в новое состояние (которое может совпадать со старым). Новое состояние определяется старым состоянием и прочитанным символом. Если прочитан последний символ, автомат останавливается. Новое состояние может определяться неоднозначно  тогда автомат называется недетерминированным. Для анализа же используются детерминированные автоматы. Автомат сообщает, допустима ли прочитанная цепочка.

Формально, конечным автоматом называется набор A = (Q,T,t,q₀,F), где T  текстовый алфавит; Q  конечное множество состояний, T  Q =  ; q₀  Q  начальное состояние; F  Q  множество заключительных состояний; t  множество правил перехода, t  QTQ.

Правило перехода (q,a,q')  t записывается в виде (q,a)  q' и означает, что из q автомат может перейти в q', прочитав символ a. 

Конфигурацией автомата называется любая цепочка вида q, где q  Q и   T ^*, в начальной конфигурации q = q₀. Отношение перехода _A на множестве конфигураций определяется следующим образом:

qа _A q'  (q,a)  q'  t

Если для каждой пары (q,a) имеется не более одного правила перехода, то автомат называется детерминированным. Тогда t называется функцией перехода и t(q,a) = q', если есть правило (q,a)  q'.

Определим отношение qq', означающее, что состояние q' достижимо из q на цепочке   T ^*, как наименьшее отношение, удовлетворяющее следующим условиям:

1. qq;

2. qaq', если в t есть правило (q,a)  q" и q"q'.

Говорят, что цепочка   T ^* допускается автоматом A, если на  из начального состояния достижимо какое-нибудь заключительное, т.е. если q₀q и q  F. Множество всех допускаемых автоматом A цепочек называется языком, допускаемым автоматом A и обозначается L(A). 

Пример 4.1. Множество идентификаторов допускается автоматом с Q ={q₀,q₁}, F ={q₁}, T ={a,...,z,0,...,9} и правилами

(q₀,a)  q₁, ..., (q₀,z)  q₁, (q₁,a)  q₁, ..., (q₁,z)  q₁, (q₁,0)  q₁, ..., (q₁,9)  q₁. 

Автомат можно наглядно представлять его диаграммой  помеченным ориентированным графом, вершинами которого являются состояния, помеченные именем или номером состояния, а помеченная дуга qaq' соответствует правилу (q,a)  q'. Заключительные состояния будем обозначать двойным кружком. Так, предыдущий автомат представляется диаграммой

Из определений непосредственно вытекает

Л е м м а  4.1. qq'     в диаграмме есть путь из q в q', метки дуг которого образуют цепочку  (учитываются и пути нулевой длины, соответствующие  = ). 