Ключевое различие между синтаксическим анализом сверху вниз и снизу вверх заключается в том, что синтаксический анализ сверху вниз выполняет синтаксический анализ от начального символа до входной строки, а синтаксический анализ снизу выполняет синтаксический анализ от входной строки до начального символа. Кроме того, еще одно важное различие между синтаксическим анализом сверху вниз и снизу вверх заключается в том, что при синтаксическом анализе сверху вниз используется наиболее левое происхождение, а при синтаксическом анализе снизу вниз используется наиболее правое происхождение.
Языки высокого уровня помогают писать компьютерные программы. Их легче понять программисту, но не компьютеру. Поэтому программа высокого уровня преобразуется в машинный код. Задача компилятора состоит в том, чтобы преобразовать удобочитаемый исходный код в машиночитаемый машинный код. Программа проходит несколько шагов для преобразования в машинный код. Весь этот процесс называется системой обработки языка. Одним из них является компиляция. Анализатор синтаксиса или синтаксический анализатор находится в компиляторе и выполняет задачу синтаксического анализа.
Что такое разбор сверху вниз?
Каждый язык программирования имеет набор правил для представления языка. Анализатор синтаксиса или синтаксический анализ берет входную строку и проверяет, соответствует ли она грамматике. Другими словами, грамматика должна создавать эту строку с помощью дерева синтаксического анализа.
При синтаксическом анализе сверху вниз синтаксический анализ происходит от начального символа и достигает заданной входной строки. Рассмотрим следующие правила производства грамматики. Входная строка (w) имеет вид cad.
S -> cAd
A -> аб /а
Дерево синтаксического анализа после выполнения синтаксического анализа сверху вниз выглядит следующим образом.
Рисунок 01: Дерево синтаксического анализа 1 с разбором сверху вниз
S производит c A d, а A производит b. Строка кабд. Это не обязательная строка. Итак, необходимо сделать возврат, то есть использовать другие альтернативы.
Аналогично, S производят c A d. Применение другого варианта для A даст a. Теперь он дает требуемую строку. Поэтому синтаксический анализатор принимает эту входную строку. Дерево синтаксического анализа после выполнения синтаксического анализа сверху вниз выглядит следующим образом.
Рисунок 02: Дерево синтаксического анализа 2 с разбором сверху вниз
Когда входная строка (w) имеет вид abcde
Рассмотрите следующие правила вывода грамматики.
S -> aABe
A -> Abc/b
B -> d
При разборе сверху вниз
S -> aABe (заменяет A -> Abc)
S -> aAbcBe (Подстановка A -> b)
S -> abbcBe (заменяет B ->d)
S -> abcde
Подстановка начинается с самой левой переменной, затем переходит к следующей правой позиции и так далее. Следовательно, он следует наиболее левому методу вывода. Кроме того, важно решить, какое продукционное правило выбрать, когда есть переменная.
Что такое анализ снизу вверх?
В восходящем парсинге происходит по-другому. Разбор происходит от входной строки до начального символа. Рассмотрим следующие правила производства грамматики и пусть входная строка будет w ɛ cad
S -> cAd
A -> аб /а
Дерево синтаксического анализа после выполнения синтаксического анализа снизу вверх выглядит следующим образом.
Рисунок 03: Дерево синтаксического анализа с разбором снизу вверх
Данная строка является cad. A генерируется A. C, A и d объединяются, чтобы получить начальный символ S.
Когда входная строка (w) имеет вид abcde
Рассмотрите следующие правила вывода грамматики.
S -> aABe
A -> Abc/b
B -> d
В разборе снизу вверх
S -> aABe (заменяет B ->d)
S -> aAde (Замена A -> Abc)
S -> aAbcde (Замена A -> b)
S -> abcde
Подстановка начинается с самой правой переменной, а затем переходит к следующей левой позиции и так далее. Следовательно, он следует методу вывода левых слов.
В чем разница между анализом сверху вниз и снизу вверх?
Синтаксический анализ сверху вниз - это стратегия синтаксического анализа, которая сначала просматривает самый высокий уровень дерева синтаксического анализа и работает вниз по дереву синтаксического анализа, используя правила формальной грамматики. Синтаксический анализ снизу вверх - это стратегия синтаксического анализа, которая сначала просматривает самый нижний уровень дерева синтаксического анализа и обрабатывает дерево синтаксического анализа, используя правила формальной грамматики. Анализ происходит от начального символа до входной строки при анализе сверху вниз. С другой стороны, синтаксический анализ происходит от входной строки до начального символа при разборе снизу вверх.
Кроме того, основное решение при синтаксическом анализе сверху вниз состоит в том, чтобы выбрать, какое продукционное правило использовать для построения строки, в то время как основное решение при синтаксическом анализе снизу вверх состоит в том, чтобы выбрать, когда использовать продукционное правило для сокращения строки до получить начальный символ. Кроме того, при синтаксическом анализе сверху вниз используется максимальное левое происхождение, а при разборе снизу вниз используется наиболее правое.
Резюме – парсинг сверху вниз и снизу вверх
Разница между синтаксическим анализом сверху вниз и снизу вверх заключается в том, что синтаксический анализ сверху вниз выполняет синтаксический анализ от начального символа до входной строки, а синтаксический анализ снизу выполняет синтаксический анализ от входной строки до начального символа.
