Automates déroulants et analyse

L'analyse est utilisée pour dériver une chaîne en utilisant les règles de production d'une grammaire. Il est utilisé pour vérifier l'acceptabilité d'une chaîne. Le compilateur est utilisé pour vérifier si une chaîne est syntaxiquement correcte ou non. Un analyseur prend les entrées et construit un arbre d'analyse.

Un analyseur peut être de deux types -

  • Top-Down Parser - L'analyse descendante commence par le haut avec le symbole de début et dérive une chaîne à l'aide d'un arbre d'analyse.

  • Bottom-Up Parser - L'analyse ascendante commence par le bas avec la chaîne et arrive au symbole de début en utilisant un arbre d'analyse.

Conception de l'analyseur de haut en bas

Pour l'analyse descendante, un PDA possède les quatre types de transitions suivants:

  • Pop le non-terminal sur le côté gauche de la production en haut de la pile et pousser sa chaîne de droite.

  • Si le symbole du haut de la pile correspond au symbole d'entrée en cours de lecture, faites-le apparaître.

  • Poussez le symbole de départ «S» dans la pile.

  • Si la chaîne d'entrée est entièrement lue et que la pile est vide, passez à l'état final «F».

Exemple

Concevez un analyseur de haut en bas pour l'expression "x + y * z" pour la grammaire G avec les règles de production suivantes -

P: S → S + X | X, X → X * Y | Y, Y → (S) | id

Solution

Si le PDA est (Q, ∑, S, δ, q 0 , I, F), alors l'analyse descendante est -

(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)

Conception d'un analyseur ascendant

Pour l'analyse ascendante, un PDA a les quatre types de transitions suivants -

  • Poussez le symbole d'entrée actuel dans la pile.

  • Remplacez le côté droit d'une production en haut de la pile par son côté gauche.

  • Si le haut de l'élément de pile correspond au symbole d'entrée actuel, faites-le apparaître.

  • Si la chaîne d'entrée est entièrement lue et seulement si le symbole de début «S» reste dans la pile, faites-le apparaître et passez à l'état final «F».

Exemple

Concevez un analyseur de haut en bas pour l'expression "x + y * z" pour la grammaire G avec les règles de production suivantes -

P: S → S + X | X, X → X * Y | Y, Y → (S) | id

Solution

Si le PDA est (Q, ∑, S, δ, q 0 , I, F), alors l'analyse ascendante est -

(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)