Разница между анализом сверху вниз и снизу вверх
Share
ключевое отличие между разбором сверху вниз и снизу вверх является то, что низходящий Синтаксический анализ выполняет синтаксический анализ от начального символа до входной строки, тогда как нижний синтаксический анализ выполняет синтаксический анализ от входной строки до начального символа.. Кроме того, еще одно важное различие между синтаксическим анализом «сверху вниз» и «снизу вверх» заключается в том, что синтаксический анализ «сверху вниз» использует большую часть левой деривации, а синтаксический анализ «снизу вниз» использует большую часть правой производной.
Языки высокого уровня помогают писать компьютерные программы. Их легче понять программисту, но не компьютеру. Поэтому высокоуровневая программа преобразует в машинный код. Задача компилятора - преобразовать читаемый человеком исходный код в машиночитаемый машинный код. Программа проходит несколько шагов для преобразования в машинный код. Весь этот процесс называется языковой системой обработки. Одним из них является сборник. Синтаксический анализатор или анализатор находится в компиляторе, и он выполняет задачу синтаксического анализа.
СОДЕРЖАНИЕ
1. Обзор и основные отличия
2. Что такое разбор сверху вниз
3. Что такое анализ снизу вверх
4. Сравнение бок о бок - анализ сверху вниз и снизу вверх в табличной форме
5. Резюме
Что такое разбор сверху вниз?
Каждый язык программирования имеет набор правил для представления языка. Синтаксический анализатор или анализ разбирает входную строку и проверяет, соответствует ли она грамматическим произведениям. Другими словами, грамматика должна создавать эту строку, используя дерево разбора.
При синтаксическом анализе сверху вниз синтаксический анализ происходит от начального символа и достигнет заданной входной строки. Рассмотрим следующие правила производства грамматики. Строка ввода (w) - cad.
S -> cAd
A -> ab / a
Дерево разбора после выполнения анализа сверху вниз выглядит следующим образом.
Рисунок 01: Разобрать дерево 1 с разбором сверху вниз
S производит c A d, а A производит b. Строка кабд. Это не обязательная строка. Таким образом, необходимо сделать возврат, то есть использовать другие альтернативы.
Точно так же S производят c A d. Применение другой опции для A даст. Теперь он дает необходимую строку. Поэтому синтаксический анализатор принимает эту входную строку. Дерево разбора после выполнения анализа сверху вниз выглядит следующим образом.
Рисунок 02: Разобрать дерево 2 с разбором сверху вниз
Когда входной строкой (w) является abbcde
Рассмотрим следующие правила производства грамматики.
S -> AABE
A -> Abc / b
B -> D
В разборе сверху вниз,
S -> aABe (Подставляя A -> Abc)
S -> aAbcBe (Подставляя A -> b)
S -> abbcBe (Подставляя B -> d)
S -> abbcde
Замена начинается сначала с самой левой переменной, а затем со следующей правой позиции и так далее. Следовательно, он следует наиболее левому методу деривации. Кроме того, важно решить, какое производственное правило выбрать при наличии переменной.
Что такое анализ снизу вверх?
При анализе снизу вверх происходит другой способ. Разбор происходит от входной строки до начального символа. Рассмотрим следующие правила создания грамматики и пусть входная строка будет w ad cad
S -> cAd
A -> ab / a
Дерево разбора после выполнения анализа снизу вверх выглядит следующим образом.
Рисунок 03: Разобрать дерево с анализом снизу вверх
Данная строка является CAD. A генерируется A. c, A и d объединяются, чтобы получить начальный символ S.
Когда входной строкой (w) является abbcde
Рассмотрим следующие правила производства грамматики.
S -> AABE
A -> Abc / b
B -> D
В восходящем разборе,
S -> aABe (Подставляя B -> d)
S -> aAde (Подставляя A -> Abc)
S -> aAbcde (Подставляя A -> b)
S -> abbcde
Замена начинается сначала с самой правой переменной, а затем перемещается в следующую левую позицию и так далее. Следовательно, он следует методу левого мотива.
Какая разница между синтаксическим анализом сверху вниз и снизу вверх?
Нисходящий синтаксический анализ - это стратегия синтаксического анализа, которая сначала просматривает самый высокий уровень дерева разбора и обрабатывает дерево разбора, используя правила формальной грамматики. Синтаксический анализ «снизу вверх» - это стратегия синтаксического анализа, которая сначала просматривает самый нижний уровень дерева разбора и обрабатывает дерево разбора, используя правила формальной грамматики. Разбор происходит от начального символа до входной строки, сверху вниз. С другой стороны, синтаксический анализ происходит от входной строки до начального символа, при анализе снизу вверх.
Кроме того, основное решение при синтаксическом анализе сверху вниз состоит в том, чтобы выбрать, какое производственное правило использовать для построения строки, в то время как основное решение при синтаксическом анализе снизу вверх состоит в том, чтобы выбрать, когда использовать производственное правило для уменьшения строки, чтобы получить начальный символ. Кроме того, синтаксический анализ сверху вниз использует самый левый вывод, а синтаксический анализ снизу вниз использует самый правый вывод.
Резюме - Разбор сверху вниз и разбор снизу вверх
Разница между синтаксическим анализом сверху вниз и снизу вверх состоит в том, что синтаксический анализ сверху вниз выполняет синтаксический анализ от начального символа до входной строки, а синтаксический анализ снизу вниз выполняет синтаксический анализ от входной строки до начального символа..
Ссылка:
1. «Лекция 5 по проектированию компиляторов - Введение в парсеры и анализ LL (1)». Проект лекций по компилятору 5 - Введение в парсеры и парсинг LL (1), Выездные лекции Равиндрабабу Равула, 22 мая 2014 года. Доступно здесь
