Introduction

La grammaire du langage misc telle que nous vous l'avons donnée n'est pas de type LL(1). Le but de cette série d'exercices est de découvrir pourquoi il en est ainsi, et de transformer la grammaire en une version LL(1).

Les résultats de cette série seront directement utiles pour le projet, car la technique de la descente récursive que nous vous demandons d'utiliser ne fonctionne que pour des grammaires LL(1). Vous devrez donc utiliser une version modifiée de la grammaire pour votre analyseur syntaxique.

Pour ne pas surcharger cette série, nous ne travaillerons que sur des sous-ensembles transformés de la grammaire du langage misc, mais les résultats obtenus ici s'étendent naturellement à la grammaire complète.

Exercice 1

Type = "Unit"
     | "Int"
     | "List" "[" Type "]"
     | "(" [ Type { "," Type } ] ")" Type.

Exercice 2

Calculez les ensembles first, follow et nullable pour tous les non-terminaux de la grammaire suivante (Expression, Term, Sign, Factor et Expressions). Dans cette grammaire, epsilon est la chaîne vide et number et ident sont des terminaux.

Expression  = Term
            | Expression "+" Term.

Term        = Sign Factor
            | Term "*" Sign Factor.

Sign        = epsilon
            | "-".

Factor      = ident
            | number
            | "(" ")"
            | "(" Expression ")"
            | Factor "(" ")"
            | Factor "(" Expressions ")".

Expressions = Expression
            | Expression "," Expressions.

Exercice 3

Transformez la grammaire suivante, qui n'est que la version EBNF de la grammaire de l'exercice précédent, afin de la rendre LL(1). Pour ce faire, utilisez les techniques d'élimination de la récursion à gauche et de factorisation à gauche.

Expression  = Term
            | Expression "+" Term.

Term        = [ "-" ] Factor
            | Term "*" [ "-" ] Factor.

Factor      = ident
            | number
            | "(" ")"
            | "(" Expression ")"
            | Factor "(" [ Expressions ] ")".

Expressions = Expression { "," Expression }.