Exercices

Exercice 1

Le rapport du langage Algol 60 contient la syntaxe suivante (traduite en EBNF) :

primary = unsignedNumber | variable | "(" arithmeticExpression ")" | ... .

factor = primary | factor "↑" primary.

term = factor | term ("×" | "/" | "÷") factor.

simpleArithmeticExpression = term | ("+" | "-") term |
    simpleArithmeticExpression ("+" | "-") term.

arithmeticExpression = simpleArithmeticExpression |
    "IF" BooleanExpression
    "THEN" simpleArithmeticExpression
    "ELSE" arithmeticExpression.

relationalOperator = "=" | "≠" | "≤" | "<" | "≥" | ">" .

relation = arithmeticExpression relationalOperator arithmeticExpression.

BooleanPrimary = logicalValue | variable | relation |
  "(" BooleanExpression ")" | ... .

BooleanSecondary = BooleanPrimary | "¬" BooleanPrimary.

BooleanFactor = BooleanSecondary | BooleanFactor "∧" BooleanSecondary.

BooleanTerm = BooleanFactor | BooleanTerm "∨" BooleanFactor.

implication = BooleanTerm | implication "⊃" BooleanTerm.

simpleBoolean = implication | simpleBoolean "≡" implication.

BooleanExpression = simpleBoolean |
    "IF" BooleanExpression "THEN" simpleBoolean "ELSE" BooleanExpression.

Dessinez les arbres syntaxiques des expressions suivantes (les lettres sont considérées comme des variables) :

Question 1

\(x + y + z\)

solution

Question 2

\(x \times y + z\)

solution

Question 3

\(x + y \times z\)

solution

Question 4

\((x - y) \times (x + y)\)

solution

Question 5

\(-x \div y\)

solution

Question 6

\(a + b < c + d\)

solution

Question 7

\(a + b < c \vee d \neq e \wedge \neg f \supset g > h \equiv i \times j = k \uparrow l \vee m - n + p \leq q\)

solution

Exercice 2

Question 1

La syntaxe présentée ci-dessus contient des ambiguïtés qui ont été éliminées dans le rapport révisé. Trouvez au moins deux structures différentes pour l’expression suivante

IF a THEN b ELSE c = d

solution

La première structure est la suivante :

La deuxième structure est la suivante :

Question 2

Proposez une syntaxe alternative qui ne soit pas ambiguë.

solution

Une solution consuste à remplacer la règle

relation = arithmeticExpression relationalOperator arithmeticExpression.

par

relation = simpleArithmeticExpression relationalOperator simpleArithmeticExpression.

Avec ce changement, la deuxième structure de la première partie de l’exercice n’est plus possible.