SEG-2506 - Construction de logiciel - Hiver 2016

Devoir 2 - Analyse lexicale

Donné: 22 février - Remise: vendredi, le 11 mars pendant la session de lab - Vous pouvez travailler en groups de deux.

À remettre: Le rapport SUR PAPIER. Fichiers Lex dans un fichier zip dans un courriel au TA.

1. Trouver des expressions régulières pour des langages (15 points)

Trouvez des expressions régulières qui définissent les langages suivants:

  1. Les tags XML. Les tags débutants peuvent contenir des attributs. La forme des tags est montrée par les exemples suivants:
  2. Toutes les chaînes sur l'alphabet  {a,b} qui ne contiennent pas la sous-chaîne aba.
  3. Toutes les chaînes sur l'alphabet  {a,b} dont le nombre des "a" est un multiple de trois (zéro inclu).

Clarifications:

2. Trouvez des automates accepteurs (15 points)

Pour chaque langage défini sous point (1), trouvez un automate accepteur déterministe qui accepte exactement ce langage.

3. Comparaison d'expression régulières (20 points)

Nous considérons les pairs d'expressions régulières suivants. Pour chaque pair, indiquez si les deux expressions désignent le même langage ou non. Si elle désignent le même langage, donnez une preuve de l'égalité des langages en utilisant les propriétés algébriques des opérateurs des expressions régulières. Si elle désignent des langages différents, donnez un exemple de chaîne qui fait partie de l'un des langages mais pas de l'autre.

  1. (a|b|c)*                  a*|b*|c*
  2. a(b|c)|(aa|bb)c       (ac|bbc|ab|aac)
  3. a(bca)*bc              ab(cab)*c
  4. a (b*a|cba)*           (ab*|acb)*a

4. Construire un analyseur lexical en utilisant Lex (50 points)

Votre tâche: Construire un analyseur lexical pour une version simpifiée du langage Pascal. L'analyseur devrait compter le nombre d'occurences (dans un programme) des identificateurs (incluant les mots clés et mots réservés), des nombres, de lignes de programme, et des commentaires. Note: pour cette exerice, vous devriez compter les mots clés et mots réservés comme des identificateurs.

Méthode: Vous devriez utiliser Lex (ou Flex) comme vous avez fait dans le Lab-5.

Information: Vous trouvez ci-dessous une définition de la syntaxe de Pascal, quelques notes sur l'analyse lexicale, et un exemple d'un programme simple en Pascal. La syntaxe est définie dans une notation BNF - il n'est pas nécessaire de comprendre cette notation en détail. Voici quelques explications concernant la notation utilisée dans la définition de la grammaire`

Définition de la syntaxe:

1

2

3

4

Un exemple de programme en Pascal

p