Распознаватели регулярных языков.
Распознавателями регулярных языков являются конечные автоматы, которые задаются как М(Q,V,δ,q0,F)
Q- множество состояний автомата;
V- множество допустимых символов автомата (алфавит автомата) ;
Δ - функции переходов;
q0 - начальное состояние автомата, q0ÎQ;
F - множество конечных состояний
Конечный автомат называется полностью определенным, если в каждом его состоянии существует функция переходов для всех возможных символов. Автомат работает по шагам или картам. Состояние автомата на каждом такте работы определяется его конфигурацией: (q,ω,n)
q - текущее состояние автомата, q ÎQ;
ω- цепочка входных символов;
n - положение указателя во входной цепочке символов.
Конфигурация на следующем такте работы определяется как (q’,ω,n+1).δ(*,состояние)=состяние.q’=δ(сим,q).
Начальная конфигурация автомата определяется следующей тройкой: ( q0,ω,0). Конечная конфигурация автомата: (f,ω,n). Говорят, что конечный автомат принимает цепочку символов, если получив ее на вход, он из начального состояния q0 может перейти в одно из конечных состояний из символа f.
Конечные автоматы: определение, конфигурация
Граф переходов конечного автомата
Это направленный помеченный граф с символами состояний конечных автоматов, в вершинах которых есть дуга (p,q), соединяющая два состояния автомата (p,q Î Q), помеченная символами (аÎV), если в конечном автомате определена функция перехода δ(а,p), причем q Î δ(a,p).
|
|
|
Начальное состояние – пунктирная окружность, конечное - две окружности.
Например: Конечный автомат М(Q,V,δ,q0,F): М({H,A,B,S},{a,b},δ,H,{S}); δ: δ(H,b)=B, δ(B,a)=A, δ(A,a)={B,S}. Рис 1
Рис1
Рис2
Для моделирования работы Конечного автомата его нужно привести к полностью определенному виду – исключить ситуации, из которых нет переходов по входным символам. Для этого в Конечный автомат добавляют еще одно состояние, которое называют ошибкой Е, и на это состояние замыкают все неопределенные переходы и переход из Е в самого себя. Рис 2
Если в каждом его состоянии для любого входного символа определена только одна функция перехода, то конечный автомат называется детерминированным.
Способы задания регулярных языков
1. с помощью регулярной грамматики
2. с помощью Конечного автомата
3. с помощью регулярного множества
Множество называется замкнутым относительно некоторй операции, если в результате выполнения этой операции над любым элементом множества получается новый элемент, принадлежащий тому же множеству.
Регулярные множества (и однозначно связанные с ними регулярные языки) замкнуты относительно следующих операций:
|
|
|
- пересечения;
- объединения;
- дополнения;
- итерации;
- конкатенации;
- гомоморфизма (изменения имён символов и подстановки цепочек вместо символов).
Проблемы разрешимые для регулярных языков:
- проблема эквивалентности;
- проблема принадлежности цепочки языку;
- проблема пустоты языка.
Назначение лексических анализаторов
Лексема - это структурная единица языка, которая состоит из элементарных символов языка.
- это часть компилятора, которая читает исходную программу и выделяет в ее тексте лексемы исходного языка.
Лексический анализатор не является обязательной частью, но включается в состав части компилятора, т.к. :
1. упрощает работу с текстами на этапе анализа и сокращает объем обработанной информации.
2. для выделения в тексте и разбора лексем применяется простая и эффективная техника анализа, в то время как на этапе синтаксического анализа используется достаточно сложные системы разбора.
3. лексический анализатор отделяет сложный по конструкции синтаксический анализатор от работы непосредственно с текстом исходной программы, структура которого может варьироваться от версии языка.
В большинстве компиляторов лексический и синтаксический анализаторы – это взаимосязанные части. Взаимодействие лексического синтаксического анализатора может осуществляться следующим образом:
|
|
|
Последовательно. Лексический анализатор рассматривает весь текст исходной программы от начала до конца и преобразует в структурный набор данных, таблицу лексем, в которой ключевые слова идентификатора заменяются на специально оговоренные коды, кроме того устанавливается связь с таблицей идентификатора.
Параллельно. Лексический анализатор исходного текста выполняется поэтапно так, что синтаксический анализатор, выполнив разбор очередной конструкции языка, обращался к лексическому анализатору за следующей лексемой, при этом указав, какую лексему следует ожидать. В этом случае при возникновении ошибки может произойти «отказ», и только в случае успешного выполнения разбора, лексема записывается в таблицу лексем.
Дата добавления: 2018-05-31; просмотров: 435; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!