Синтаксический анализ используется для получения строки с использованием правил производства грамматики. Он используется для проверки приемлемости строки. Компилятор используется для проверки правильности синтаксической строки. Парсер принимает входные данные и строит дерево разбора.
Парсер может быть двух типов:
-
Анализатор сверху вниз — синтаксический анализ сверху вниз начинается с символа начала и выводит строку с использованием дерева синтаксического анализа.
-
Анализатор снизу вверх — анализ снизу вверх начинается снизу строкой и доходит до начального символа с использованием дерева разбора.
Анализатор сверху вниз — синтаксический анализ сверху вниз начинается с символа начала и выводит строку с использованием дерева синтаксического анализа.
Анализатор снизу вверх — анализ снизу вверх начинается снизу строкой и доходит до начального символа с использованием дерева разбора.
Дизайн нисходящего парсера
Для анализа сверху вниз в КПК есть следующие четыре типа переходов:
-
Наденьте нетерминал с левой стороны производства на вершину стека и нажмите на правую струну.
-
Если верхний символ стека совпадает с читаемым символом ввода, вставьте его.
-
Вставьте стартовый символ «S» в стек.
-
Если входная строка полностью прочитана, а стек пуст, перейдите в конечное состояние «F».
Наденьте нетерминал с левой стороны производства на вершину стека и нажмите на правую струну.
Если верхний символ стека совпадает с читаемым символом ввода, вставьте его.
Вставьте стартовый символ «S» в стек.
Если входная строка полностью прочитана, а стек пуст, перейдите в конечное состояние «F».
пример
Разработайте анализатор сверху вниз для выражения «x + y * z» для грамматики G со следующими правилами производства:
P: S → S + X | X, X → X * Y | Y, Y → (S) | Я бы
Решение
Если КПК (Q, ∑, S, δ, q 0 , I, F), то разбор сверху вниз —
(x + y * z, I) ⊢ (x + y * z, SI) ⊢ (x + y * z, S + XI) ⊢ (x + y * z, X + XI)
⊢ (x + y * z, Y + XI) ⊢ (x + y * z, x + XI) ⊢ (+ y * z, + XI) ⊢ (y * z, XI)
⊢ (y * z, X * YI) ⊢ (y * z, y * YI) ⊢ (* z, * YI) ⊢ (z, YI) ⊢ (z, zI) ⊢ (ε, I)
Дизайн снизу вверх парсера
Для анализа снизу вверх КПК имеет следующие четыре типа переходов:
-
Вставьте текущий входной символ в стек.
-
Замените правую часть производства в верхней части стека левой стороной.
-
Если вершина стекового элемента совпадает с текущим входным символом, вставьте его.
-
Если входная строка полностью прочитана и только если начальный символ «S» остается в стеке, вытолкните ее и перейдите в конечное состояние «F».
Вставьте текущий входной символ в стек.
Замените правую часть производства в верхней части стека левой стороной.
Если вершина стекового элемента совпадает с текущим входным символом, вставьте его.
Если входная строка полностью прочитана и только если начальный символ «S» остается в стеке, вытолкните ее и перейдите в конечное состояние «F».
пример
Разработайте анализатор сверху вниз для выражения «x + y * z» для грамматики G со следующими правилами производства:
P: S → S + X | X, X → X * Y | Y, Y → (S) | Я бы
Решение
Если КПК (Q, ∑, S, δ, q 0 , I, F), то анализ снизу вверх —
(x + y * z, I) ⊢ (+ y * z, xI) ⊢ (+ y * z, YI) ⊢ (+ y * z, XI) ⊢ (+ y * z, SI)
⊢ (y * z, + SI) ⊢ (* z, y + SI) ⊢ (* z, Y + SI) ⊢ (* z, X + SI) ⊢ (z, * X + SI)
⊢ (ε, z * X + SI) ⊢ (ε, Y * X + SI) ⊢ (ε, X + SI) ⊢ (ε, SI)