Файл: Отчеты оформляются в виде файлов формата Microsoft Word (файлы других форматов не принимаются), размер шрифта 1214.docx
Добавлен: 12.01.2024
Просмотров: 628
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
Основные требования к отчетам по лабораторным работам
Лабораторная/практическая работа № 1
Лабораторная/практическая работа № 2
Лабораторная/практическая работа № 3
Лабораторная/практическая работа № 4
Лабораторная/практическая работа № 5
Лабораторная/практическая работа № 6
Лабораторная/практическая работа № 7
алгоритм нисходящего синтаксического акцепта, способы процедурной реализации синтаксического акцептора и соответственно преобразования порождающей грамматики в текст программы так называемого «рекурсивного спуска». Затем будут рассмотрены две разные автоматные реализации нисходящего синтаксического акцептора и соответствующие методы преобразования порождающей грамматики в управляющие таблицы таких автоматов.
Эта идея очень проста (при условии, что грамматика относится к так называемому классу LL(1)) и состоит в следующем.
– во-первых, существенно усложняется процесс формирования дерева и необходимые для этого структуры данных из-за необходимости обеспечивать возвраты для перебора пригодных правил;
– во-вторых, даже если усложнить алгоритм и реализовать возвраты, то резко, до неприемлемых на практике значений порядка N в кубе, возрастает количество циклов алгоритма для восстановления дерева (N - количество слов в анализируемой программе).
А3.1 Этот терминал не совпадает с текущим терминалом из предложения. В этом случае входная цепочка символов в целом не может быть выведена из начального нетерминала грамматики, т.е. не является правильным предложением языка, порождаемого грамматикой. Процесс синтаксического анализа нужно остановить по обнаружению ошибки.
А3.2 Этот терминал совпадает с текущим терминалом из предложения и не является терминалом ► (конец файла). Нужно перейти к следующему узлу в нижнем уровне дерева (сделать следующий текущим), прочитать следующий терминал из предложения путем вызова лексического анализатора и установить полученное от него слово в качестве нового текущего терминала. Затем должен быть выполнен возврат к шагу А2 для продолжения восстановления дерева.
А3.3 Этот терминал совпадает с текущим терминалом из предложения и является терминалом ► (конец файла). Восстановление дерева завершено, анализируемое предложение является правильным.
Таким образом, из описания существа процесса нисходящего синтаксического анализа следует, что грамматика должна быть предварительно проанализирована на принадлежность к так называемому классу LL(1) для исключения возможности возникновения ситуаций вида 2.3. Одновременно будет определен способ проверки того, может ли из правой части правила быть выведена цепочка терминалов, начинающаяся с имеющегося на шаге 2 текущего терминала.
Свяжем с каждым правилом грамматики множество терминалов, называемое множеством выбора и вычисляемое следующим образом.
Пусть есть правило N : j.
В зависимости от того, какова цепочка символов j, составляющая его правую часть правила, множество его выбора вычисляется так:
Здесь M пр (j) – множество предшественников цепочки j;
Mпосл (N) – множество последователей нетерминала N.
LL(1)-грамматикой называется такая контекстно-свободная грамматика, у которой множества выбора правил с одинаковым нетерминалом в левой части попарно не пересекаются.
Любая такая грамматика может быть использована для организации нисходящего детерминированного восстановления дерева грамматического разбора предложений порождаемого ею языка. Другими словами, на основе любой LL(1)-грамматики может быть построен детерминированный нисходящий синтаксический акцептор, проверяющий правильность предложений языка.
Вычислим множества выбора для правил известных нам грамматик Ga1 и Ga2 , используя свойства символов и множества предшественников и последователей, изучавшиеся в предыдущей работе и проверим, относятся ли эти грамматики к классу LL(1).
Вначале рассмотрим свойства грамматики Ga2 (табл. 4.1, правая часть). Заметим, что в ее системе порождающих правил для каждого нетерминала либо есть единственное правило, либо множества выбора нескольких правил, содержащих один и тот же нетерминал в левой части (правила 2 и 3 для R, правила 5 и 6 для W, правила 7, 8 и 9 для V), не пересекаются. Поэтому при восстановлении дерева разбора в любом цикле на шаге 2 по любому текущему входному символу можно выбрать ровно одно правило для замены нетерминала – то, чье множество выбора содержит текущий входной терминал.
Таблица 4.1
Например, если текущий узел нижнего уровня восстанавливаемого дерева содержит нетерминал W, а текущим терминалом из входной цепочки является знак операции сложения + (или круглая закрывающая скобка ) или конец файла ►), то заменять узел W следует на правую часть правила 6, т. е. на пустую цепочку. Если же текущий терминал из входной цепочки есть знак операции умножения *, то вместо узла с W необходимо подставить цепочку из двух узлов * и U, т. е. правую часть правила 5. Если же ткущий терминал - это идентификатор ident, константа const или открывающая скобка (, то никакое правило не может быть использовано для замены нетерминала W. Это свидетельствует о том, что входная цепочка не может быть выведена из начального нетерминала этой грамматики и, следовательно, не является правильным предложением. Например, при попытке восстановления дерева разбора цепочки ( x+ y ) z► возникнет именно эта ситуация. Очередной уровень дерева разбора, выведенный из нетерминала S, будет выглядеть так:
S ( x+ y ) WR
Текущий узел выделен рамкой. Текущим терминалом является идентификатор z. Поскольку идентификатор не входит ни в одно множество выбора правил, имеющих нетерминал W в левой части, то не существует способа вывода остатка входной цепочки, имеющего вид z►, из цепочки узлов W R, а следовательно, и дерева грамматического разбора всей входной цепочки ( x + y ) z► из начального нетерминала S.
Грамматика Ga2 принадлежит к классу LL(1)-грамматик.
Обратимся теперь к грамматике Ga1(табл. 4.1, левая часть). Множества выбора правил 1 и 2 для нетерминала S одинаковы (а следовательно, пересекаются). Одинаковы также множества выбора правил 3 и 4 для нетерминала T. Поэтому попытка восстановления дерева разбора правильной цепочки (например:
( x + y ) * z►) может завести нас в тупик вследствие неверного принятия решения уже на первом шаге, если вместо подстановки по правилу 2
S T
будет выбрана подстановка по правилу 1
S S + T.
И та и другая подстановка в данный момент формально применимы, поскольку множества выбора и правила 1, и правила 2 содержат терминал (.Если будет выбрано правило 1, то впоследствии никаким способом уже нельзя будет вывести цепочку
( x + y ) * z► из цепочки S + T.
Возможность принятия неверного решения при использовании грамматики Ga1 возникает каждый раз, когда на текущем уровне восстанавливаемого дерева самым левым оказывается либо нетерминал S, либо нетерминал T.
Грамматика Ga1 не относится к классу LL(1)-грамматик. Это является следствием леворекурсивности нетерминалов S и T. Любая левая рекурсия
(в том числе косвенная) влечет за собой пересечение множеств выбора правил, имеющих в левой части леворекурсивный нетерминал. Поясним это на простом примере прямой левой рекурсии. Пусть в системе порождающих правил грамматики есть такие правила для нетерминала N:
N : N β
N : γ .
Заметим, что первое правило – причина левой рекурсии, а из правой части второго правила должна быть выводима цепочка терминалов (если это не так или второго правила просто нет, то нетерминал N бесплоден и должен быть удален из грамматики со всеми своими правилами).
Каково бы ни было множество выбора второго правила, оно целиком содержится и в множестве выбора первого правила, поскольку
Mвыб (N β) = Mпр (N β),
а множество предшественников цепочки N β по определению включает в себя множество предшественников нетерминала N, которое содержит, в свою очередь, множество предшественников цепочки γ. Следовательно, множества выбора этих правил пересекаются и содержат оба множество предшественников цепочки символов γ.
Итак, любая леворекурсивная грамматика не принадлежит классу
-
Основная идея группы нисходящих методов восстановления дерева грамматического разбора.
Эта идея очень проста (при условии, что грамматика относится к так называемому классу LL(1)) и состоит в следующем.
-
Создается корень дерева (он же – самый верхний его уровень), в виде узла, содержащего начальный нетерминал грамматики; из анализируемого предложения считывается первое слово – это текущий терминал (считывание слова – это вызов лексического анализатора). Далее нисходящий синтаксический анализатор постоянно циклически работает ровно с двумя символами: один берется из текущего узла нижнего уровня восстанавливаемого дерева, другим является текущий терминал. В каждом повторении цикла реализуется либо шаг А2, либо шаг А3. -
Если текущий узел нижнего уровня дерева содержит нетерминал, то просматриваются те и только те правила грамматики, которые содержат этот нетерминал в левой части. Возможны по меньшей мере три разных результата этого просмотра:
-
Нет ни одного правила, из правой части которого можно вывести остаток предложения, начинающийся с текущего терминала. Это означает, что входная цепочка символов в целом не может быть выведена из начального нетерминала грамматики, т.е. не является правильным предложением языка, порождаемого грамматикой. Процесс синтаксического анализа нужно остановить по обнаружению ошибки. -
Если из правой части просматриваемого правила можно вывести цепочку символов, начинающуюся с текущего терминала из предложения, то это правило можно применить для замены узла последовательностью узлов, формируемых из цепочки символов правой части. Если такое правило в точности одно, то текущий уровень дерева разбора преобразуется в следующий путем замены текущего узла на цепочку узлов, формируемых из символов правой части этого правила. Текущим узлом становится первый узел этой цепочки или, если правая часть правила пуста, то узел, следующий за обработанным текущим узлом. Текущий терминал не изменяется, выполняется возврат к шагу А2. -
Если правил, из правой части каждого из которых можно вывести цепочку символов, начинающуюся с текущего терминала из предложения, найдено несколько, то обнаружена невозможность обеспечить безоткатное однонаправленное движение сверху вниз для восстановления дерева. Процесс синтаксического анализа нужно остановить. Эта грамматика не годится для нисходящего синтаксического анализа, потому что:
– во-первых, существенно усложняется процесс формирования дерева и необходимые для этого структуры данных из-за необходимости обеспечивать возвраты для перебора пригодных правил;
– во-вторых, даже если усложнить алгоритм и реализовать возвраты, то резко, до неприемлемых на практике значений порядка N в кубе, возрастает количество циклов алгоритма для восстановления дерева (N - количество слов в анализируемой программе).
-
Если текущий узел нижнего уровня дерева содержит терминал, то возможны ровно три случая:
А3.1 Этот терминал не совпадает с текущим терминалом из предложения. В этом случае входная цепочка символов в целом не может быть выведена из начального нетерминала грамматики, т.е. не является правильным предложением языка, порождаемого грамматикой. Процесс синтаксического анализа нужно остановить по обнаружению ошибки.
А3.2 Этот терминал совпадает с текущим терминалом из предложения и не является терминалом ► (конец файла). Нужно перейти к следующему узлу в нижнем уровне дерева (сделать следующий текущим), прочитать следующий терминал из предложения путем вызова лексического анализатора и установить полученное от него слово в качестве нового текущего терминала. Затем должен быть выполнен возврат к шагу А2 для продолжения восстановления дерева.
А3.3 Этот терминал совпадает с текущим терминалом из предложения и является терминалом ► (конец файла). Восстановление дерева завершено, анализируемое предложение является правильным.
-
Пригодность грамматики для реализации нисходящего разбора. LL(1)-грамматики
Таким образом, из описания существа процесса нисходящего синтаксического анализа следует, что грамматика должна быть предварительно проанализирована на принадлежность к так называемому классу LL(1) для исключения возможности возникновения ситуаций вида 2.3. Одновременно будет определен способ проверки того, может ли из правой части правила быть выведена цепочка терминалов, начинающаяся с имеющегося на шаге 2 текущего терминала.
Свяжем с каждым правилом грамматики множество терминалов, называемое множеством выбора и вычисляемое следующим образом.
Пусть есть правило N : j.
В зависимости от того, какова цепочка символов j, составляющая его правую часть правила, множество его выбора вычисляется так:
-
Mвыб (N : j) = Mпр (j), если j содержит хотя бы один терминал или неаннулируемый нетерминал; -
Mвыб (N : j) = Mпосл (N), если j есть пустая цепочка; -
Mвыб (N : j) = M пр (j) Mпосл (N), если j не пуста, но состоит только из аннулируемых нетерминалов.
Здесь M пр (j) – множество предшественников цепочки j;
Mпосл (N) – множество последователей нетерминала N.
LL(1)-грамматикой называется такая контекстно-свободная грамматика, у которой множества выбора правил с одинаковым нетерминалом в левой части попарно не пересекаются.
Любая такая грамматика может быть использована для организации нисходящего детерминированного восстановления дерева грамматического разбора предложений порождаемого ею языка. Другими словами, на основе любой LL(1)-грамматики может быть построен детерминированный нисходящий синтаксический акцептор, проверяющий правильность предложений языка.
Вычислим множества выбора для правил известных нам грамматик Ga1 и Ga2 , используя свойства символов и множества предшественников и последователей, изучавшиеся в предыдущей работе и проверим, относятся ли эти грамматики к классу LL(1).
Вначале рассмотрим свойства грамматики Ga2 (табл. 4.1, правая часть). Заметим, что в ее системе порождающих правил для каждого нетерминала либо есть единственное правило, либо множества выбора нескольких правил, содержащих один и тот же нетерминал в левой части (правила 2 и 3 для R, правила 5 и 6 для W, правила 7, 8 и 9 для V), не пересекаются. Поэтому при восстановлении дерева разбора в любом цикле на шаге 2 по любому текущему входному символу можно выбрать ровно одно правило для замены нетерминала – то, чье множество выбора содержит текущий входной терминал.
Таблица 4.1
| Грамматика G a1 | Грамматика G a2 | ||||||
| | Правило | Способ | Множество | | Правило | Способ | Множество |
| 0 | Z : S ► | M пр(S ► ) | (, ident, const | 0 | Z : S ► | M пр(S ►) | (, ident, const |
| 1 | S : S + T | M пр(S + T) | (, ident, const | 1 | S : U R | M пр(U R) | (, ident, const |
| 2 | S : T | M пр(T) | (, ident, const | 2 | R : + S | M пр(+ S) | + |
| 3 | T : T * V | M пр(T * V) | (, ident, const | 3 | R : | M посл (R) | (, ► |
| 4 | T : V | M пр(V) | (, ident, const | 4 | U : V W | M пр(VW) | (, ident, const |
| 5 | V : ( S ) | M пр(( S )) | ( | 5 | W : * U | M пр(+ S) | * |
| 6 | V : ident | M пр(i) | ident | 6 | W : | M посл (W) | +, (, ► |
| 7 | V : const | M пр(c) | const | 7 | V : ( S ) | M пр( (S) ) | ( |
| | | | | 8 | V : ident | M пр(ident) | ident |
| | | | | 9 | V : const | M пр(const) | const |
Например, если текущий узел нижнего уровня восстанавливаемого дерева содержит нетерминал W, а текущим терминалом из входной цепочки является знак операции сложения + (или круглая закрывающая скобка ) или конец файла ►), то заменять узел W следует на правую часть правила 6, т. е. на пустую цепочку. Если же текущий терминал из входной цепочки есть знак операции умножения *, то вместо узла с W необходимо подставить цепочку из двух узлов * и U, т. е. правую часть правила 5. Если же ткущий терминал - это идентификатор ident, константа const или открывающая скобка (, то никакое правило не может быть использовано для замены нетерминала W. Это свидетельствует о том, что входная цепочка не может быть выведена из начального нетерминала этой грамматики и, следовательно, не является правильным предложением. Например, при попытке восстановления дерева разбора цепочки ( x+ y ) z► возникнет именно эта ситуация. Очередной уровень дерева разбора, выведенный из нетерминала S, будет выглядеть так:
S ( x+ y ) WRТекущий узел выделен рамкой. Текущим терминалом является идентификатор z. Поскольку идентификатор не входит ни в одно множество выбора правил, имеющих нетерминал W в левой части, то не существует способа вывода остатка входной цепочки, имеющего вид z►, из цепочки узлов W R, а следовательно, и дерева грамматического разбора всей входной цепочки ( x + y ) z► из начального нетерминала S.
Грамматика Ga2 принадлежит к классу LL(1)-грамматик.
Обратимся теперь к грамматике Ga1(табл. 4.1, левая часть). Множества выбора правил 1 и 2 для нетерминала S одинаковы (а следовательно, пересекаются). Одинаковы также множества выбора правил 3 и 4 для нетерминала T. Поэтому попытка восстановления дерева разбора правильной цепочки (например:
( x + y ) * z►) может завести нас в тупик вследствие неверного принятия решения уже на первом шаге, если вместо подстановки по правилу 2
S T
будет выбрана подстановка по правилу 1
S S + T.
И та и другая подстановка в данный момент формально применимы, поскольку множества выбора и правила 1, и правила 2 содержат терминал (.Если будет выбрано правило 1, то впоследствии никаким способом уже нельзя будет вывести цепочку
( x + y ) * z► из цепочки S + T.
Возможность принятия неверного решения при использовании грамматики Ga1 возникает каждый раз, когда на текущем уровне восстанавливаемого дерева самым левым оказывается либо нетерминал S, либо нетерминал T.
Грамматика Ga1 не относится к классу LL(1)-грамматик. Это является следствием леворекурсивности нетерминалов S и T. Любая левая рекурсия
(в том числе косвенная) влечет за собой пересечение множеств выбора правил, имеющих в левой части леворекурсивный нетерминал. Поясним это на простом примере прямой левой рекурсии. Пусть в системе порождающих правил грамматики есть такие правила для нетерминала N:
N : N β
N : γ .
Заметим, что первое правило – причина левой рекурсии, а из правой части второго правила должна быть выводима цепочка терминалов (если это не так или второго правила просто нет, то нетерминал N бесплоден и должен быть удален из грамматики со всеми своими правилами).
Каково бы ни было множество выбора второго правила, оно целиком содержится и в множестве выбора первого правила, поскольку
Mвыб (N β) = Mпр (N β),
а множество предшественников цепочки N β по определению включает в себя множество предшественников нетерминала N, которое содержит, в свою очередь, множество предшественников цепочки γ. Следовательно, множества выбора этих правил пересекаются и содержат оба множество предшественников цепочки символов γ.
Итак, любая леворекурсивная грамматика не принадлежит классу