Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






LR(1)- разбор с использованием автоматов с магазинной памятью





 

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

Выполняя команды управляющей таблицы, автомат осуществляет переходы между внутренними состояниями. Новое внутреннее состояние для очередного перехода может быть указано в выбранной из таблицы команде так же, как в таблице переходов конечного автомата. Команды такого типа называются «сдвиг». Переход в новое состояние в этом случае сопровождается записью этого состояния в стек состояний и перемещением к следующему символу входной строки с записью прочитанного символа в стек символов. Таким образом в стеках происходит накопление истории поведения автомата. Возможность воспользоваться этой историей у автомата появляется после выполнения команды другого типа, которая называется «приведение». По команде «приведение» из стека символов удаляются символы, образующие правую часть правила, номер которого указан в команде. Синхронное изменение содержаний стеков обеспечивает удаление такого же количества записей из стека состояний, в результате чего автомат переходит в то внутреннее состояние, в котором он уже был несколько шагов назад, и которое осталось теперь в вершине стека состояний после удалений. Удаленная правая часть правила в сентенциальной форме должна быть заменена на левую часть этого правила. Эта замена проявляется в работе автомата в виде имитации чтения такого нетерминала из входной строки после изменения содержаний стеков вышеупомянутыми удалениями.

Процесс распознавания считается успешно завершенным, т.е. входная строка считается принадлежащей языку, принимаемому автоматом, если эта входная строка полностью прочитана, автомат находится в начальном внутреннем состоянии и из входной строки имитируется чтение аксиомы. Вывод о некорректности распознаваемой строки делается автоматом при обнаружении команды «ошибка» в ситуациях, аналогичных тем, что были упомянуты при описании LL(1)- разбора.

Пример 4.

Рассмотрим процесс распознавания, например, строки i*i языка, заданного грамматикой

1) < S >::= < E >

2) < E >::= < T > + < E >

3) < E >::= < T >

4) < T >::= < F > * < T >

5) < T >::= < F >

6) < F >::= i

Аксиомой является символ < S >.

Управляющая таблица для автомата с магазинной памятью, выполняющего LR(1)- разбор для заданного языка, изображена на рис. 11.

 

  < S > < E > < T > < F > i + * $
  допуск         ошибка ошибка ошибка
  ошибка ошибка ошибка ошибка ошибка ошибка ошибка приведение,1
  ошибка ошибка ошибка ошибка ошибка   ошибка  
  ошибка         ошибка ошибка ошибка
  ошибка ошибка ошибка ошибка ошибка ошибка ошибка приведение,2
  ошибка ошибка ошибка ошибка ошибка приведение,5   приведение,5
  ошибка ошибка       ошибка ошибка ошибка
  ошибка ошибка ошибка ошибка ошибка приведение,4 ошибка приведение,4
  ошибка ошибка ошибка ошибка ошибка приведение,6 приведение,6 приведение,6

Рис.11. Управляющая таблица автомата, выполняющего LR(1)-разбор

 

Внутренние состояния автомата обозначены целыми числами от1 до 9. Начальное состояние обозначено числом 1. В командах типа «сдвиг» указаны внутренние состояния, в которые осуществляется переход при выполнении этих команд. Команды «приведение» снабжены целыми числами – номерами правил, по которым выполняется процедура приведения – замена правой части правила на левую.

Процесс распознавания автоматом типа LR(1) строки i*i проиллюстрирован таблицей:

Содержание стека символов Содержание стека состояний Входная строка Команда управляющей таблицы
    i * i $  
i   i * i $ приведение,6
    i < F > * i $  
< F >   i * i $  
* < F >   i * i $  
i * < F >   i * i $ приведение,6
* < F >   i * i < F > $  
< F > * < F >   i * i $ приведение,5
* < F >   i * i < T > $  
< T > * < F >   i * i $ приведение,4
    i * i < T > $  
< T >   i * i $ приведение,3
    i * i < E > $  
< E >   i * i $ приведение,1
    i * i < S > $ допуск

 

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

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

Правила разметки правых частей правил для построения LR(1)-таблицы разбора приведены в [4]:

1. Начальные позиции правых частей правил для аксиомы отмечаются индексом начального состояния автомата.

2. Индекс состояния, непосредственно справа от которого находится нетерминал, следует распространять на позиции перед первыми символами всех правых частей правил для данного нетерминала (и т.д. рекурсивно).

3. Если непосредственно слева от одного и того же символа в каких-либо правилах установлены одинаковые метки, то и непосредственно справа от этого символа в этих правилах следует поставить одну и ту же метку.

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

1) < S >::= 1 < E >2

2) < E >::= 1,4 < T >3+ 4< E >5

3) < E >::= 1,4 < T >3

4) < T >::= 1,4,7 < F > 6 * 7< T >8

5) < T >::= 1,4,7 < F >6

6) < F >::= 1,4,7 i 9

Так же, как и в размеченном регулярном выражении, в размеченном правиле LR(1)-грамматики символ, слева и справа от которого находятся индексы внутренних состояний, считается входным воздействием для перехода автомата из одного внутреннего состояния в другое. При этом индекс, находящийся слева от символа, - это индекс исходного состояния, а индекс, находящийся справа от символа, - это индекс состояния перехода. Правила занесения такого перехода в LR(1)-таблицу совпадает с правилом занесения аналогичного перехода в таблицу переходов конечного автомата: исходное внутреннее состояние определяет координату строки ячейки таблицы, символ входного воздействия определяет координату столбца ячейки таблицы а содержание ячейки таблицы – это индекс состояния перехода. Так, например, из того, что в размеченном правиле слева от символа + находится индекс 3, а справа - индекс 4, следует, что в ячейку таблицы с координатами (3, +) должна быть помещена команда 4.

Ячейки командам типа «приведение» назначаются из следующих соображений. Замена правой части правила на левую, выполняемая по команде «приведение», может осуществляться автоматом, когда эта правая часть полностью прочитана в стек символов, а автомат, следовательно, находится в состоянии, индекс которого занимает позицию справа от последнего символа правой части правила. Так, например, команда приведения по правилу номер 4 (приведение,4) помещена в строке 8 таблицы потому, что индекс 8 внутреннего состояния автомата занимает крайнюю справа позицию в размеченном правиле номер 4. Что же касается столбца таблицы, в который следует поместить команду типа «приведение», он определяется тем терминальным символом, который может наблюдаться во входной строке после того, как правая часть правила прочитана в стек символов. Иными словами, этот терминальный символ может следовать после прочитанной в стек правой части правила. А поскольку приведение заключается в замене правой части правила на левую, об этом же терминальном символе можно сказать, что он является символом-следователем для нетерминала левой части правила, участвующего в приведении. Термин «символ-следователь» имеет здесь тот же смысл, что и в рассуждениях о Λ -правила в LL(1)-грамматиках. Продолжая рассматривать в качестве примера правило с номером 4, можно сказать, что столбцы ячеек таблицы, в которые следует поместить команду приведения по этому правилу, определяются символами-следователями для нетерминала < T >, стоящего в левой части этого правила (но не того < T >, справа от которого стоит индекс 8!). В правиле номер 2 после символа < T > находится +. Следовательно, + - символ-следователь для < T >. Кроме того < T > занимает последнюю позицию в определении < E > (правило номер 3), который, в свою очередь, занимает последнюю позицию в определении < S > (правило номер1) а следователем для аксиомы < S > является маркер $. Поэтому еще одним символом-следователем для < T > оказывается $. Поводя итог рассмотрению правила номер 4, определяем, что команда приведения по этому правилу должна быть размещена в ячейках таблицы с координатами (8, +) и (8, $).

Приведенные выше LR(1)-таблица и размеченная грамматика соответствуют друг другу в том смысле, что таблица построена по этой разметке грамматики. Применение правил разметки в несколько иной последовательности могло бы изменить нумерацию внутренних состояний, а значит, и несколько видоизменить LR(1)-таблицу, но никак не отразилось бы на функционировании автомата по LR(1)-разбору задаваемых ему строк.

Свойство LR(1), как и свойство LL(1), является частным свойством КС-грамматик и КС-языков. Впрочем, следует заметить, что LL(1)-грамматика всегда является и LR(1)-грамматикой.

В заключение обсуждения LR(1)-анализаторов остановимся на использовании одного из программных средств автоматизации их конструирования. Аналогично тому, как утилита Flex по регулярным выражениям генерирует программную реализацию распознавателя регулярного языка, утилита Bison по LR(1)-грамматике генерирует программную реализацию распознавателя LR(1)-языка. Программная реализация распознавателя LR(1)-языка оформлена в виде C-функции int yyparse().

Следует заметить, что Flex и Bison обычно используются в паре. Функция, сгенерированная Flex (int yylex()), выполняя лексический анализ текста, т.е. выявляя в нем простейшие синтаксические конструкции-лексемы, становится поставщиком терминальных символов для сгенерированного Bison LR(1)-анализатора, который выявляет в исходном тексте более сложные конструкции, составленные из лексем. Входной язык Bison в некоторых деталях отличается от формы Бэкуса-Наура, используемой нами для записи правил грамматики. Наиболее существенными представляются следующие. Вместо символа::= используется:; угловые скобки для обозначения нетерминальных символов не используются, а именуются нетерминальные символы произвольными идентификаторами; после перечисления через символ | всех правых частей правил с одним нетерминалом в левой части следует поставить символ;.

Грамматика, на примере которой обсуждалось построение LR(1)-анализатора, для обработки ее утилитой Bison может быть описана так:

S: E

;

E: T’+’E

|

T

;

T: F’*’T

|

F

;

F: ‘i’

;

Терминальные символы грамматики, каковыми в этом примере являются +, *, и i, могут быть представлены просто символьными константами. Но поскольку, как уже было сказано, задача ввода анализируемого текста и формирование из его литер терминальных, с точки зрения LR(1)-грамматики, символов возложена на отдельную функцию лексического анализа, даже если терминальный символ изображается одной литерой, необходимо позаботиться о том, чтобы эта функция поставляла LR(1)-анализатору прочитанные коды символов +, *, и i. Впрочем, выполнение лексического анализа специальной функцией позволяет терминальным символам LR(1)-грамматики иметь и более сложную структуру, а именно: они могут быть предложениями регулярного языка. Функция же лексического анализа, распознавая эти предложения, формирует и возвращает LR(1)-анализатору их коды, так называемые токены. В правилах грамматики терминальные символы-токены следует обозначить идентификаторами, а при оформлении входного потока для Bison перечислить их в специальной директиве %token. Этими же идентификаторами для обозначения токенов должна пользоваться функция лексического анализа. Более детально правила оформления входного файла для Bison изложены в [3]. Приведем содержание файла, оформленного по этим правилам для рассматриваемого примера, скорректировав, впрочем, описание языка таким образом, чтобы операнды для операций + и * могли быть произвольными идентификаторами.

%{

#include <iostream>

#include <string>

using namespace std;

void yyerror(char const* msg);

int yylex();

int yyparse();

#include <iostream>

%}

%token ident

%%

S: E

;

E: T'+'E

|

T

;

T: F'*'T

|

F

;

F: ident

;

%%

extern FILE *yyin;

void yyerror(char const* msg)

{

cerr << msg << endl;

}

void main()

{

yyin = fopen("test.txt","r");

if (yyparse()!= 0)

{

cout << "Syntax error, document rejected"

<< endl;

} else

cout << "Success" << endl;

}

 

Если функцию yylex() для такого анализатора предполагается построить с помощью Flex, то входной файл для этой утилиты может быть таким:

%option noyywrap

%option yylineno

%option never-interactive

%{

#include <string>

#include <iostream>

#include "tokens.h"

using namespace std;

%}

Identifier [a-z]([a-z]|[0-9])*

%%

\+ {return '+';}

\* {return '*';}

{Identifier} {return ident;}

%%

Содержание файла tokens.h может быть сгенерировано утилитой Bison, если выполнить ее с опцией –d. Данные, по которым генерируется этот файл – список имен в директиве %token. Каждому имени из списка директивы ставится в соответствие целое число (токен) с помощью конструкции #define. По директиве, включенной в вышеприведенное описание, в заголовочный файл будет записана строка: #define ident 257.

Анализатор, построенный на основе этих описаний, способен распознавать арифметические выражения, в которых разрешены операции + и *, а операндами являются идентификаторы. Например, строка a+b1*c23 должна быть определена им как принадлежащая языку, принимаемому LR(1)-автоматом. Сообщение об успешном завершении анализа входной строки предусмотрено в функции main. В приведенном тексте программы – это слово «Success». Для синтаксически некорректных строк в этой же функции предусмотрен вывод сообщения «Syntax error, document rejected». Оно может быть получено, например, в ответ на входную строку d+*e4.

 

 

Date: 2015-10-19; view: 1918; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.007 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию