🗊 Теория языков программирования и методы трансляции Тема №5 Восходящий синтаксический анализ (down-top)

Теория языков программирования и методы трансляции Тема №5 Восходящий синтаксический анализ (down-top)

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

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

Восходящий синтаксический анализ. Основные понятия. Рассмотрим язык {xnym|n,m>0}, генерируемый следующими продукциями: предложение языка xxxyy можно сгенерировать при помощи правого порождения порождения

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

Восходящий синтаксический анализ. Основные понятия. Пусть предложение хххуу читается слева направо, тогда совсем не очевидно, почему первый х не заменяется X на первом этапе синтаксического анализа, используя соответствующую продукцию грамматики, или почему первый у подобным образом на четвертом этапе не заменяется Y. Очевидно, что для выполнения синтаксического анализа требуется некоторая дополнительная информация, отличная от предоставляемой продукциями грамматики.

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

Восходящий синтаксический анализ. Критерии принятия решений. Этапы процесса синтаксического анализа могут рассматриваться как состоящие из двух типов действий. 1. Перемещение последнего считанного символа в стек – действие переноса (shift action). 2. Замена строки наверху стека посредством применения продукции грамматики – действие свертки (reduce action).

Восходящий синтаксический анализ. Критерии принятия решений.

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

Восходящий синтаксический анализ. Основные понятия. В строке символов на вершине стека возможно будут определены правые части более одной продукции, так что на определенном этапе синтаксического анализа могут существовать две или более возможных свертки. Если, в определенный момент кажутся возможными действия свертки и переноса, говорят, что имеет место конфликт перенос/свертка (shift-reduce conflict). Если возможными кажутся несколько операций свертки, говорят, что имеет место конфликт свертка/свертка (reduce-reduce conflict). С целью выработки детерминирован­ного метода синтаксического анализа могут применяться различные стратегии разрешения названных конфликтов. На практике данные конфликты разрешаются с использованием следующей информации Предшествующая история синтаксического анализа. Информация, полученная путем предпросмотра.

Восходящий синтаксический анализ. Основные понятия. Как и при нисходящем синтаксическом анализе, для разрешения конфликтов обычно используется один символ предпросмотра. Кроме того, для разрешения конфликтов может использоваться информация, касающаяся истории синтаксического анализа. В приведенном выше примере символом предпросмотра, определяющим применение продукции Xx был у; подобным образом, символ предпросмотра ┴ (маркер конца) определяет применение такой продукции: Yy

Восходящий синтаксический анализ. LR(k)-грамматика. Грамматика, все конфликты которой, возникающие при восходящем синтаксическом анализе слева направо, могут быть разрешены с использованием фиксированного объема информации, касающейся уже проведенного анализа, и конечного числа символов предпросмотра, называется LR(k)-грамматикой. Здесь L означает чтение слева (Left) направо, R – правые порождения (Rightmost), a k обозначает количество символов предпросмотра. Языком LR(k) называется язык, который можно сгенерировать посредством LR(k) -грамматики, Если требуется только один символ предпросмотра, грамматика и язык относятся к классу LR(1).

Восходящий синтаксический анализ. Критерии принятия решений. Рассмотрим пример. Пусть имеется грамматика со следующими продукциями. 1. EE+T 2. ET 3. TT*F 4. TF 5. F(E) 6. Fx Здесь E – символ предложения. Грамматика может использоваться в качестве основы для восходящего синтаксического анализа

Восходящий синтаксический анализ. Критерии принятия решений.

Восходящий синтаксический анализ. Критерии принятия решений. Первый х, помещаемый в стек, сворачивается в F, затем в T, затем в Е, тогда как второй и третий х сворачиваются в F, потом в T, а четвертый x – только в F, Первый и второй символы х имеют одинаковые символы предпросмотра, и различная их трактовка основана на предшествующей истории синтаксического анализа. Для третьего и четвертого символов х символы предпросмотра отличаются (* и ┴ , соответственно), и снова имеем различную трактовку — и снова, основанную на истории синтаксического анализа. Критерий принятия решения относительно предпринимаемого действия – переноса или свертки (или выбора из нескольких возможных сверток) – может содержаться в таблице, называемой таблицей синтаксического анализа. Поскольку таблица синтаксического анализа создается инструментальным средством, наподобие YACC, программисту нет нужды понимать принципы ее формирования. Впрочем, некоторые вопросы ее использования все же стоит рассмотреть.

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

Восходящий синтаксический анализ. Таблица синтаксического анализа. В начале процесса синтаксического анализа анализатор находится в состоянии 1, а входным символом является первый введенный символ. Каждый шаг анализа определяется позицией таблицы, соответствующей текущему состоянию, и входным символом. Позиция таблицы может принадлежать к одному из двух типов. 1. Позиция переноса вида Sm, вынуждающая анализатор выполнить действие переноса и изменить текущее состояние на состояние т. 2. Позиция свертки вида Rn, вынуждающая анализатор выполнить действие свертки, используя продукцию п.

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

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

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

Восходящий синтаксический анализ. Таблица синтаксического анализа. Если позиция таблицы определяет действие свертки, имеют место следующие операции. Из стека символов удаляются п символов и из стека состояний удаляются п состояний, где п – число символов в правой части продукции, фигурирующей в свертке. Анализатор переходит в состояние на вершине стека состояний. Входной символ становится символом в левой части продукции, определенной в позиции свертки.

Восходящий синтаксический анализ. Таблица синтаксического анализа.

Восходящий синтаксический анализ. Таблица синтаксического анализа. Проследим анализ следующего предложения. х + х + х*х

Восходящий синтаксический анализ. Таблица синтаксического анализа. Рассмотрев, как синтаксический анализатор использует одноименную таблицу, пришло время определить принципы ее формирования из контекстно-свободной грамматики. Вначале проиллюстрируем роль состояний, рассмотрев создание таблицы синтаксического анализа для простой грамматики, генерирующей конечный язык. Рассмотрим грамматику со следующими продукциями (Р – символ предложения). 1. PbD;Se 2. D d;d 3. S s;s bd;d;s;se

Восходящий синтаксический анализ. Таблица синтаксического анализа. Как обычно, предполагается, что синтаксический анализатор изначально находится в состоянии 1. Для отображения этого факта следует несколько изменить форму записи грамматики 1. P1bD;Se 2. D d;d 3. S s;s После считывания символа b грамматика будет находиться в состоянии 2. 1. P1b2D;Se 2. D d;d 3. S s;s

Восходящий синтаксический анализ. Таблица синтаксического анализа. Анализатор находится в состоянии 2 до распознавания символа D, так что соответствующее обозначение помещаем и в начало продукции для нетерминала D 1. P1b2D;Se 2. D 2d;d 3. S s;s Состояния 3 и 4 также соответствуют считыванию символов продукции 1. Поскольку анализатор находится в состоянии 4 до распознавания символа S, оно также соответствует началу продукции для S. 1. P1b2D3;4Se 2. D 2d;d 3. S 4s;s

Восходящий синтаксический анализ. Таблица синтаксического анализа. Подобным образом вводим еще восемь состояний, в которых может находиться синтаксический анализатор. 1. P1b2D3;4S5e6 2. D 2d7;8d9 3. S 4s10;11s12 Вся информация, необходимая для направления процесса анализа, содержится в представленной выше аннотированной грамматике, но удобнее ее представить в табличной форме.

Восходящий синтаксический анализ. Таблица синтаксического анализа. Позиции переноса заносятся в таблицу легко. Например, из начала правой части продукции 1, состояние 1, при входном символе b очевидным является перенос в состояние 2, другие позиции переноса также очевидны. Рассмотрим теперь позиции свертки. Состояние в конце продукции – это состояние, в котором должна происходить свертка, так что из аннотированной версии продукции 1 видим, что в состоянии 6 должна иметь место свертка согласно продукции 1. Действия свертки вносятся в каждый столбец состояния свертки, если в рассматриваемой строке нет действий переноса; по этой причине действия переноса всегда заносятся в таблицу до действий свертки. Позднее будет рассмотрен вопрос о том, что происходит при возникновении конфликта между действиями переноса и свертки (конфликт перенос/свертка) или между двумя действиями свертки (конфликт свертка/свертка).

Восходящий синтаксический анализ. Таблица синтаксического анализа.

Восходящий синтаксический анализ. Таблица синтаксического анализа. Другим способом представления таблицы синтаксического анализа является ориентированный граф. Это представление называется характеристическим конечным автоматом (characteristic finite state machine) далее ХКА. Если передать управление синтаксическим анализом данному конечному автомату и соотнести с каждым состоянием номер его вершины, то при действии переноса это номер будет заносится в стек состояний. При действии свертки поведение анализатора будет несколько иным. В этом случае из стека будет извлечено требуемое число состояний и проходится такое число обратно по конечному автомату. Как и ранее следующий входной символ – это символ в правой части продукции, только что использованной при свертке. ХКА формируется аналогично тому, как в грамматику добавлялись аннотации.

Восходящий синтаксический анализ. Таблица синтаксического анализа.

Восходящий синтаксический анализ. Таблица синтаксического анализа. В большинстве случаев действия свертки поместить в таблицу не так просто, как может показаться из приведенного примера для иллюстрации вернемся к рассмотренной выше грамматике. 1. EE+T 2. ET 3. TT*F 4. TF 5. F(E) 6. Fx Аннотирование грамматики происходит следующим образом. В первую очередь устанавливается состояние 1.

Восходящий синтаксический анализ. Таблица синтаксического анализа. 1. E1E+T 2. E1T 3. T1T*F 4. T1F 5. F1(E) 6. F1x Каждая позиция, в которую было помещено состояние 1 – это пример конфигурации грамматики. По определению, конфигурация – это позиция в правой части продукции перед первым символом, после последнего символа или между двумя любыми символами. Конфигурации, соответствующие одному состоянию, неразличимы с точки зрения синтаксического анализатора. Далее вводим в грамматику состояние 2, которое соответствует единственной конфигурации.

Восходящий синтаксический анализ. Таблица синтаксического анализа. 1. E1E2+T 2. E1T 3. T1T*F 4. T1F 5. F1(E) 6. F1x Состояние 3, поскольку оно появляется перед нетерминалом, соответствует нескольким конфигурациям. 1. E1E2+3T 2. E1T 3. T1,3T*F 4. T1,3F 5. F1,3(E) 6. F1,3x

Восходящий синтаксический анализ. Таблица синтаксического анализа. На первый взгляд может показаться странным наличие двух состояний, соответствующих одной конфигурации грамматики (например, оба состояния 1 и 3 появляются в начале правой части продукции 3). В то же время, если учитывать историю синтаксического анализа, два состояние различимы, поскольку состояние 3 всегда появляется после символа +, а состояние 1 – нет. Вводим далее состояние 4. 1. E1E2+3T4 2. E1T 3. T1,3T4*F 4. T1,3F 5. F1,3(E) 6. F1,3x

Восходящий синтаксический анализ. Таблица синтаксического анализа. Состояние 4 появляется в двух местах: в конце продукции 1, где оно соответствует действию свертки, и поскольку оно определено как состояние, в которое переходит состояние 3 при считывании символа, после Т в продукции 3. Уже видно, что состояние 4 приведет к некоторому конфликту перенос/свертка. По подобной причине состояние 5 так же появляется в двух местах в конце продукции 2 (действие свертки) и в продукции 3 (перенос). Отметим что в продукции 3 состояния, идущие перед T в правой части, появляются в порядке, соответствующем состояниям, идущим после T, т.е. после состояния 1 идет состояние 5, а после 3 – состояние 4.

Восходящий синтаксический анализ. Таблица синтаксического анализа. 1. E1E2+3T4 2. E1T5 3. T1,3T5,4*F 4. T1,3F 5. F1,3(E) 6. F1,3x Состояние 6 появляется в нескольким местах, поскольку оно предшествует нетерминалу и далее просто вводятся состояния 7 и 8. 1. E1E2+3T4 2. E1T5 3. T1,3T5,4*6F7 4. T1,3F8 5. F1,3,6(E) 6. F1,3,6x

Восходящий синтаксический анализ. Таблица синтаксического анализа. Состояние 9 несколько сложнее, так как оно появляется перед нетерминалом, поэтому должно находиться в начале правил для этого нетерминала и т.д. рекурсивно. 1. E1,9E2+3T4 2. E1,9T5 3. T1,3,9T5,4*6F7 4. T1,3,9F8 5. F1,3,6,9(9E) 6. F1,3,6,9x

Восходящий синтаксический анализ. Таблица синтаксического анализа. Состояние 10 следует вводить аккуратно. Состояние 10 следует после Е в состоянии 9, таким образом, появляется после Е в продукциях 1 и 5. В то же время, в продукциях 2 и 3 уже не нужно вводить новые состояния, которые бы "помнили", появилось это состояние из продукции в состоянии 1 или в состоянии 9. По этой кажущейся несколько условной причине любое новое состояние, введенное после Т в данных продукциях, будет соответствовать набору конфигураций, идентичному существующему в уже введенном состоянии. 1. E1,9E2,10+3T4 2. E1,9T5 3. T1,3,9T5,4*6F7 4. T1,3,9F8 5. F1,3,6,9(9E10) 6. F1,3,6,9x

Восходящий синтаксический анализ. Таблица синтаксического анализа. В продукциях 4-6 уже не требуются новые состояния, следующие за 8 (по причинам, сходным с приведенными выше для продукций 2 и 3). Оставшиеся состояния грамматики вводятся без каких-либо проблем. 1. E1,9E2,10+3T4 2. E1,9T5 3. T1,3,9T5,4*6F7 4. T1,3,9F8 5. F1,3,6,9(9E10)11 6. F1,3,6,9x12

Восходящий синтаксический анализ. Таблица синтаксического анализа.

Восходящий синтаксический анализ. Таблица синтаксического анализа.

Восходящий синтаксический анализ. Таблица синтаксического анализа.

Восходящий синтаксический анализ. Таблица синтаксического анализа.

Восходящий синтаксический анализ. Таблица синтаксического анализа.

Восходящий синтаксический анализ. Таблица синтаксического анализа.

Восходящий синтаксический анализ. Таблица синтаксического анализа.

Восходящий синтаксический анализ. Таблица синтаксического анализа.

Восходящий синтаксический анализ. SLR(1)-грамматика.

Восходящий синтаксический анализ. LALR(1)-грамматика.

Восходящий синтаксический анализ. LALR(1)-грамматика.

Восходящий синтаксический анализ.

Восходящий синтаксический анализ.

Восходящий синтаксический анализ. Особенности LR-анализа.

Восходящий синтаксический анализ. Особенности LR-анализа.

Восходящий синтаксический анализ. Введение в YACC.

Восходящий синтаксический анализ. Введение в YACC.

Восходящий синтаксический анализ. Введение в YACC.

Восходящий синтаксический анализ. Введение в YACC.

Восходящий синтаксический анализ. Введение в YACC.

Восходящий синтаксический анализ. Введение в YACC.

Восходящий синтаксический анализ. Введение в YACC.

Восходящий синтаксический анализ. Введение в YACC.

Восходящий синтаксический анализ. Использование YACC.

Восходящий синтаксический анализ. Использование YACC.

Восходящий синтаксический анализ. Использование YACC.